Last active
February 19, 2023 20:42
-
-
Save ATMI/99e20a3d3581190124b11a825ca2218f to your computer and use it in GitHub Desktop.
SegmentedQueue test
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment