SegmentedQueue test

main.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdint.h>

#define N 1000

static size_t K_SIZE = 4;
static int64_t COMPLEXITY = 0;

static inline size_t min(size_t a, size_t b) {
	if (a < b) return a; else return b;
}

typedef int element_t;

#define INVALID_ELEMENT (-1)

typedef struct node {
	struct node *previous;
	struct node *next;
	size_t read_index;
	size_t write_index;
	element_t *elements;
} node_t;

typedef struct dll {
	node_t *first;
	node_t *last;
} dll_t;

static inline node_t *node_new(void) {
	node_t *node = (node_t *)calloc(1, sizeof(node_t));
	node->elements = (element_t *)calloc(K_SIZE, sizeof(element_t));
	return node;
}

static inline size_t node_get_elements_count(const node_t *node) {
	return node->write_index - node->read_index;
}

void node_elements_move(node_t *dst, size_t dst_index, node_t *src, size_t count) {
	size_t src_index = src->read_index;
	// sanity for debug
	assert(dst_index + count <= (K_SIZE) && src_index + count <= src->write_index);
	// NOTE: consider using memmove()
	dst->write_index = dst_index + count;
	src->read_index = src_index + count;
	COMPLEXITY += count;
	if (dst != src || dst_index < src_index) {
		while (count--) {
			dst->elements[dst_index++] = src->elements[src_index++];
		}
	}
	else {
		dst_index += count;
		src_index += count;
		while (count--) {
			dst->elements[--dst_index] = src->elements[--src_index];
		}
	}
}

size_t node_elements_rebase(node_t *node, size_t base) {
	const size_t count = node_get_elements_count(node);
	assert(base + count <= (K_SIZE));
	if (count) {
		if (node->read_index != base) {
			node_elements_move(node, base, node, count);
		}
	}
	// anyway rebase indices
	node->read_index = base;
	node->write_index = base + count;
	return count;
}

static inline dll_t *dll_new(void) {
	return calloc(1, sizeof(dll_t));
}

void dll_node_remove(dll_t *dll, node_t *node) {
	assert(node->write_index == node->read_index);
	node_t *previous = node->previous;
	node_t *next = node->next;
	// relink list
	if (next) next->previous = previous;
	if (previous) previous->next = next;
	// update root
	if (dll->first == node) dll->first = next;
	if (dll->last == node) dll->last = previous;
	// free the node
	free(node);
}

void offer(dll_t *dll, element_t value) {
	node_t *last = dll->last;
	if (!last) {
		dll->first = dll->last = last = node_new();
	}
	// check last is full
	if (last->write_index >= (K_SIZE)) {
		node_t *newbie = node_new();
		last->next = newbie;
		newbie->previous = last;
		dll->last = last = newbie;
	}
	last->elements[last->write_index++] = value;
	COMPLEXITY++;
}

element_t poll(dll_t *dll) {
	node_t *first = dll->first;
	assert(first);
	if (!first) {
		return INVALID_ELEMENT;
	}
	element_t value = first->elements[first->read_index++];
	COMPLEXITY++;
	size_t first_count = node_get_elements_count(first);
	// sanity checks for debug, also treats read overrun as size_t is unsigned
	assert(first_count <= (K_SIZE));
	// check if the last node is empty and should be removed
	if (!first_count) {
		// sanity checks for debug
		assert(first == dll->last && !first->previous && !first->next);
		dll_node_remove(dll, first);
	}
		// check if the first node is half-empty and needs re-balancing
	else if (first_count < ((K_SIZE) >> 1)) {
		// check next two segments for re-balancing
		node_t *second = first->next;
		if (second) {
			node_t *third = second->next;
			size_t second_count = node_get_elements_count(second);
			// anyway move first's elements to the beginning
			node_elements_rebase(first, 0);
			// if it is the first segment, and there exist two segments after,
			// then proceed similarly to previous two cases;
			if (third) {
				// the sum m = size(si−1) + size(si) + size(si+1)
				size_t third_count = node_get_elements_count(third);
				size_t m = first_count + second_count + third_count;
				// if the sum m < 2k, then replace these three segments with two segments of size m/2
				if (m < ((K_SIZE) << 1)) {
					m >>= 1;
					// append elements from the second segment into the first
					size_t move = min(m - first_count, second_count);
					node_elements_move(first, first_count, second, move);
					// move second's elements to the beginning is any exists
					node_elements_rebase(second, 0);
					// move all the third's segment elements into the second one
					node_elements_move(second, second->write_index, third, third_count);
					// remove third
					dll_node_remove(dll, third);
				}
					// if the sum m >= 2k, then replace these three segments with tree segments of size m/3
				else {
					m /= 3;
					size_t move = m - first_count;
					if (move >= second_count) {
						// move all the elements from the second to the first segment
						node_elements_move(first, first_count, second, second_count);
						// move rest elements from the third segment
						node_elements_move(first, first_count + second_count, third, move - second_count);
						// move elements from the third to the empty second
						node_elements_move(second, 0, third, m);
						// move third's elements to the beginning is any exists
						node_elements_rebase(third, 0);
					}
					else {
						// move elements from the second to the first segment
						node_elements_move(first, first_count, second, move);
						// move second's elements to the beginning
						second_count = node_elements_rebase(second, 0);
						if (second_count != m) {
							if (second_count < m) {
								// move elements from the third to the second
								node_elements_move(second, second_count, third, m - second_count);
								// move third's elements to the beginning
								node_elements_rebase(third, 0);
							}
							else {
								move = second_count - m;
								// reserve space in the third segment
								node_elements_rebase(third, move);
								// move last elements from the second to the third
								while (move--) {
									third->elements[move] = second->elements[--second->write_index];
								}
								third->read_index = 0;
							}
						}
					}
				}
			}
				// if it is the first segment and only one segment after it exists,
				// move as many elements from the last segment to the first one as possible;
			else {
				size_t move = (K_SIZE) - first_count;
				if (move < second_count) {
					node_elements_move(first, first_count, second, move);
					node_elements_rebase(second, 0);
				}
				else {
					node_elements_move(first, first_count, second, second_count);
					// if the last segment becomes empty, remove it
					dll_node_remove(dll, second);
				};
			}
		}
	}
	return value;
}

void test_burst(void) {
	COMPLEXITY = 0;
	dll_t *list = dll_new();

	for (int i = 0; i < N; ++i) {
		offer(list, i);
	}

	for (int i = 0; i < N; ++i) {
		element_t value = poll(list);
		// printf("%d ", value);
		assert(value == i);
	}

	// printf("%zu\t%lu\n", K_SIZE, COMPLEXITY);
	free(list);
}

void test_random(uint seed) {
	COMPLEXITY = 0;
	dll_t *list = dll_new();

	element_t values_offered = 0;
	element_t values_polled = 0;

	for (int i = 0; i < N; ++i) {
		if ((values_polled == values_offered) || (rand_r(&seed) & 1)) {
			offer(list, values_offered++);
		}
		else {
			element_t value = poll(list);
			assert(value == values_polled);
			values_polled++;
		}
	}

	printf("%zu\t%lu\n", K_SIZE, COMPLEXITY);
	free(list);
}


int main() {
	for (K_SIZE = 4; K_SIZE <= 1000; ++K_SIZE) {
		test_burst();
		// test_random(0x7357533D);
		printf("%zu\t%ld\n", K_SIZE, COMPLEXITY);
	}

	return 0;
}