diff options
| -rwxr-xr-x | .gitignore | 2 | ||||
| -rw-r--r-- | amr_array.h | 110 | ||||
| -rw-r--r-- | amr_memory.h | 164 | ||||
| -rw-r--r-- | il_redblack.cpp | 821 |
4 files changed, 1097 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100755 index 0000000..09ff560 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +tags +*.out diff --git a/amr_array.h b/amr_array.h new file mode 100644 index 0000000..d9546d2 --- /dev/null +++ b/amr_array.h @@ -0,0 +1,110 @@ +// AMR ARRAY +// GENERAL ARRAYS FOR C +// > Mainly for prototyping and small internal programs +// +// Documentation: +// +// AMR_MALLOC: +// malloc function, can be replace with a custom allocator (todo) +// AMR_FREE: +// free function, can be replace with a custom allocator (todo) +// amr_arr_len: +// get array length +// amr_arr_cap: +// get array capacity +// amr_arr_init: +// initialize array, see usage for how to use. +// amr_arr_tinit: +// initialize array with type. gets around void cast issue, annoying on +// c++ +// amr_arr_push(arr, value): +// push an element on to the end of an array. +// will not care about holes in array. +// amr_arr_pushcarr(arr, carr): +// push a c-style constant size array +// amr_arr_join(arr_a, arr_b): +// join/push all items from array b into array a +// amr_arr_clear(arr): +// clears array. (actually just resets the len variable of array, +// since operations first work on array len, this is all +// we need to "clear" it) +// +// Usage: +// +// typdef T arr_t; // optional, but recommended to signify a type is an array. +// // Highlights intent, prevents confusion +// +// int main() { +// arr_t *myarr; +// amr_arr_init(myarr, capacity); +// +// amr_arr_push(myarr, 2); +// ... +// } + +#ifndef __AMR_INCLUDE_AMR_ARRAY_H +#define __AMR_INCLUDE_AMR_ARRAY_H + +#include "stdlib.h" +#include "assert.h" +#include "string.h" + +struct ArrayHeader { + int len; + int cap; +}; +typedef struct ArrayHeader ArrayHeader; + +#define __CARR_LEN(CARR) (sizeof((CARR))/sizeof((CARR)[0])) +#define AMR_MALLOC(x) malloc((x)) +#define AMR_FREE(p) free((p)) +#define amr_arr_len(A) ((((ArrayHeader*)(A)) - 1)->len) +#define amr_arr_cap(A) ((((ArrayHeader*)(A)) -1)->cap) + +#define amr_arr_init(ARR, CAP) { \ + ArrayHeader *H = (ArrayHeader*)AMR_MALLOC((CAP)*sizeof((ARR)[0]) + sizeof(ArrayHeader)); \ + H->len = 0; \ + H->cap = (CAP); \ + ARR = (void*)(H+1); \ +} + +#define amr_arr_tinit(T, ARR, CAP) { \ + ArrayHeader *H = (ArrayHeader*)AMR_MALLOC((CAP)*sizeof((ARR)[0]) + sizeof(ArrayHeader)); \ + H->len = 0; \ + H->cap = (CAP); \ + ARR = (T*)(H+1); \ +} + +#define amr_arr_push(ARR, VAL) { \ + ArrayHeader *H = ((ArrayHeader*)(ARR)-1); \ + assert(H->len+1 <= H->cap); \ + (ARR)[H->len++] = (VAL); \ +} + +#define amr_arr_pushcarr(ARR, ELE) { \ + ArrayHeader *H = ((ArrayHeader*)(ARR)-1); \ + assert(H->len+(__CARR_LEN((ELE))) <= H->cap); \ + memcpy((ARR)+H->len, (ELE), sizeof((ELE))); \ + H->len += (__CARR_LEN((ELE))); \ +} + +#define amr_arr_join(A, B) { \ + ArrayHeader *HA = (ArrayHeader*)(A)-1; \ + ArrayHeader *HB = (ArrayHeader*)(B)-1; \ + assert(HA->len + HB->len <= HA->cap); \ + memcpy((A) + HA->len, (B), sizeof((B)[0])*HB->len); \ + HA->len += HB->len; \ +} + +#define amr_arr_clear(ARR) { \ + ArrayHeader *H = (ArrayHeader*)(ARR)-1; \ + H->len = 0; \ +} + +#define amr_arr_free(ARR) { \ + AMR_FREE((ArrayHeader*)(ARR)-1); \ +} + +#endif // __AMR_INCLUDE_AMR_ARRAY_H + + diff --git a/amr_memory.h b/amr_memory.h new file mode 100644 index 0000000..f1d3b23 --- /dev/null +++ b/amr_memory.h @@ -0,0 +1,164 @@ +#ifndef __AMR_INCLUDE_AMR_MEMORY_H +#define __AMR_INCLUDE_AMR_MEMORY_H + +#define AMRM_KB(x) ((x)*1024) +#define AMRM_MB(x) ((AMR_KB(x))*1024) +#define AMRM_GB(x) ((AMR_MB(x))*1024) + +#ifndef AMRM_DEFAULT_ALIGNMENT +#define AMRM_DEFAULT_ALIGNMENT (2*sizeof(void *)) +#endif + +//////////////////////////////////////////////////// +// +// Arena +// + + +// This struct is defined publicly but it really is supposed to be opaque +// and is used by all the functions here +struct amrm_Arena { + unsigned char *arena; + size_t prev_offset; + size_t curr_offset; + size_t capacity; +}; + +typedef struct amrm_Arena amrm_Arena; + +int8_t amrm__is_power_of_two(uintptr_t x); +// Uses some bit manipulation to check if x is a power of two. +// This is needed for alignment + +uintptr_t amrm__fast_modulo(uintptr_t p, uintpt_t a) { +// Uses a bitwise operator to calculate modulus + +uintptr_t amrm__align_forward(uintptr_t ptr, size_t alignment); +// Ensures a ptr is aligned by 'alignment' +// It does this by fast_modulus(ptr, alignment) and moves ptr ahead +// by the necessary amount to have it be word aligned + +void amrm_arena_init(amrm_Arena *a, unsigned char *raw_buffer, size_t capacity); +// Initialise memory arena struct +// Pass in raw buffer, acquired through malloc +// (but in future, test for os syscalls to acquire virtual pages) +// and the capacity of buffer in bytes + +void* amrm_arena_alloc(amrm_Arena *a, size_t size); +// Allocate memory in arena, which roughly translates to +// perform bound checks, request memory from the arena and update offsets + +void* amrm_arena_alloc_aligned(amrm_Arena *a, size_t size, size_t alignment); +// This is the function called by amrm_arena_alloc. The main item is that it +// expects an alignment + +void* amrm_arena_resize(amrm_Arena *a, void *old, + size_t old_size, size_t new_size); +// Resize memory in arena +// Pass the current pointer to old, along with its size and the new requested size + +void* amrm_arena_resize_aligned(amrm_Arena *a, void *old, + size_t old_size, size_t new_size, size_t alignment); +// Same as amrm_arena_resize, this is what it calls. It just expects an alignment + +void amrm_arena_clear(amrm_Arena *a); +// "clears" an arena, though what this actually does it clears the offsets +// so the arena considers itself empty. + +//////////////////////////////////////////////////// +// +// IMPLEMENTATION +// + +#ifdef AMR_ARRAY_IMPLEMENTATION + +int8_t amrm__is_power_of_two(uintptr_t x) { + return (x & (x-1)) == 0; +} + +uintptr_t amrm__fast_modulo(uintptr_t p, uintpt_t a) { + return (p & (a-1)); +} + +uintptr_t amrm__align_forward(uintptr_t ptr, size_t alignment) { + uintptr_t p, a, mod; + p = ptr; + a = (uintptr_t)alignment; + mod = amrm__fast_modulo(p, a); + if (mod != 0) { + p += (a-mod); + } + + return p; +} + +void amrm_arena_init(amrm_Arena *a, unsigned char *raw_buffer, size_t capacity) { + a->arena = raw_buffer; + a->prev_offset = 0; + a->curr_offset = 0; + a->capacity = capacity; +} + +void* amrm_arena_alloc(amrm_Arena *a, size_t size) { + return amrm_arena_alloc_aligned(a, size, AMRM_DEFAULT_ALIGNMENT); +} + +void* amrm_arena_alloc_aligned(amrm_Arena *a, size_t size, size_t alignment) { + void *ptr = NULL; + + assert(is_power_of_two(alignment)); + + uintptr_t curr_ptr = (uintptr_t)a->buffer + a->curr_offset; + uintptr_t curr_ptr_aligned = amrm__align_forward(curr_ptr, alignment); + // if I really want to do a bounds check here, I think that is on the + // compiler to catch, mainly because if someone is typing that they need + // an insane amount of memory, then catch that + if (curr_ptr_aligned + size <= a->buffer + a->capacity) { + ptr = curr_ptr_aligned; + a->prev_offset = a->curr_offset; + a->curr_offset = (ptr - (uintptr_t)a->buffer) + size; + memset(ptr, 0, size); + } + + return ptr; +} + +void* amrm_arena_resize(amrm_Arena *a, void *old, size_t old_size, size_t new_size) { + return amrm_arena_resize_aligned(a, old, old_size, new_size, AMRM_DEFAULT_ALIGNMENT); +} + +void* amrm_arena_resize_aligned(amrm_Arena *a, void *old, + size_t old_size, size_t new_size, size_t alignment) { + unsigned char *mem_old = (unsigned char*)old; + void *ptr = NULL; + + assert(amrm__is_power_of_two(alignment)); + assert(old >= a->buffer && old + old_size < a->buffer + a->capacity); + + ptr = old; + if (a->buffer + a->curr_offset == old) { + // if last element, just extend and update state + size_t curr_offset_new = a->prev_offset + new_size; + if (curr_offset_new <= a->capacity) { + a->curr_offset = curr_offset_new; + } + } else { + uintptr_t curr_ptr = a->buffer + a->curr_offset; + uintptr_t curr_ptr_aligned = amrm__align_forward(curr_ptr, alignment); + if (curr_ptr_aligned + new_size <= (uintptr_t)a->buffer + a->capacity) { + ptr = curr_ptr_aligned; + memset(ptr, 0, new_size); + memmove(ptr, old, new_size); + } + } + return ptr; +} + +void amrm_arena_clear(amrm_Arena *a) { + a->prev_offset = 0; + a->curr_offset = 0; +} + +#endif // AMR_ARRAY_IMPLEMENTATION + +#endif // __AMR_INCLUDE_AMR_MEMORY_H diff --git a/il_redblack.cpp b/il_redblack.cpp new file mode 100644 index 0000000..93fdf72 --- /dev/null +++ b/il_redblack.cpp @@ -0,0 +1,821 @@ +#include "stdio.h" +#include "stdint.h" +#include "assert.h" + +#ifndef AMRT_MEMORY +#include "stdlib.h" +#include "string.h" +#define AMRT_MALLOC(X) malloc((X)) +#define AMRT_FREE(X) free((X)) +#define AMRT_MEMZERO(S, N) memset((S), 0, (N)) +#endif + +enum AMRT_COLOR { + AMRT_COLOR_BLACK = 0, + AMRT_COLOR_RED, +}; + +enum AMRT_DIR { + AMRT_DIR_LEFT = 0, + AMRT_DIR_RIGHT +}; + +typedef int amrt_status; +typedef int amrt_idx; + +#define AMRT_NIL 0; + +struct amrt_rb_node { + AMRT_COLOR color; + AMRT_DIR dir; + int value; + size_t __size; + size_t __level; + amrt_idx parent; + union { + amrt_idx child[2]; + struct { + amrt_idx left; + amrt_idx right; + }; + struct { + amrt_idx prev; + amrt_idx next; + }; + }; +}; + +struct amrt_rb_tree { + amrt_idx head; + amrt_idx freelist; + size_t node_max; + size_t node_count; + amrt_rb_node *nodes; +}; + +// Core Functions +amrt_rb_tree amrt_RBInit(size_t max_ele); +amrt_status amrt_RbInsert(amrt_rb_tree *tree, int value); +size_t amrt_RBSearch(amrt_rb_tree *tree, int value); +amrt_status amrt_RBIndexedDelete(amrt_rb_tree *tree, amrt_idx node_idx); +amrt_status amrt_RBDelete(amrt_rb_tree *tree, int value); +void amrt_RBClear(amrt_rb_tree *tree); +void amrt_RBTerminate(amrt_rb_tree *tree); +void amrt_RBPrint(amrt_rb_tree *tree); + +// Helper Functions +amrt_status amrt__RBFreelistPop(amrt_rb_tree *tree); +amrt_status amrt__RBFreelistReclaim(amrt_rb_tree *tree, amrt_idx node_idx); +void amrt__RBRotateUp(amrt_rb_tree *tree, amrt_idx node_idx); +amrt_idx amrt__RBSubtreeFindSmallestNode(amrt_rb_tree *tree, amrt_idx node_idx); +amrt_status amrt__RBIgnoreNode(amrt_rb_tree *tree, amrt_idx node_idx); +void amrt__RBUpdateLevels(amrt_rb_tree *tree, amrt_idx node_idx, int level); + +// Testing Functions +int amrt__RBValidateColors(amrt_rb_tree, amrt_idx node_idx); +int amrt__RBCountNodes(amrt_rb_tree tree, amrt_idx node_idx); +bool amrt__RBSetupValid(amrt_rb_tree tree, amrt_idx node_idx); +amrt_status amrt__RBValidate(amrt_rb_tree tree); + + +amrt_rb_tree amrt_RBInit(size_t max_ele) { + amrt_rb_tree tree = {0}; + if (!max_ele) return tree; + + size_t cap = 1 + max_ele; // 1 (index 0) is reserved for nil node + tree.node_max = cap; + tree.nodes = (amrt_rb_node*)AMRT_MALLOC(sizeof(amrt_rb_node)*tree.node_max); + tree.freelist = tree.head + 1; + + amrt_rb_node free = tree.nodes[tree.freelist]; + free.__size = max_ele - tree.freelist; + tree.nodes[tree.freelist] = free; + + return tree; +} + +amrt_status amrt_RBInsert(amrt_rb_tree *tree, int value) { + amrt_idx search_idx = tree->head; + amrt_rb_node search_node = tree->nodes[search_idx]; + amrt_idx parent_idx = search_node.parent; + AMRT_DIR search_dir = search_node.dir; + + // @step: find index for node insertion + while(search_idx) { + parent_idx = search_idx; + if (value < search_node.value) { + search_idx = search_node.left; + search_dir = AMRT_DIR_LEFT; + } else { + search_idx = search_node.right; + search_dir = AMRT_DIR_RIGHT; + } + search_node = tree->nodes[search_idx]; + } + + // @step: + // pop slot from free list + amrt_idx node_idx = amrt__RBFreelistPop(tree); + amrt_rb_node node = {}; + node.value = value; + node.dir = search_dir; + node.color = AMRT_COLOR_BLACK; + node.parent = parent_idx; + node.left = AMRT_NIL; + node.right = AMRT_NIL; + tree->nodes[node_idx] = node; + + // update parent + amrt_rb_node parent = tree->nodes[parent_idx]; + if (parent_idx) { + parent.child[node.dir] = node_idx; + tree->nodes[parent_idx] = parent; + } + + tree->node_count++; + + + // @step: color node + int colored = 0; + while (!colored) { + if (!parent_idx) { + tree->head = node_idx; + colored = 1; + } else if (parent.color == AMRT_COLOR_BLACK) { + node.color = AMRT_COLOR_RED; + tree->nodes[node_idx] = node; + colored = 1; + } else if (parent.color == AMRT_COLOR_RED) { + amrt_idx grandparent_idx = parent.parent; + amrt_rb_node grandparent = tree->nodes[grandparent_idx]; + AMRT_DIR unc_dir = (AMRT_DIR)!parent.dir; + amrt_idx unc_idx = grandparent.child[unc_dir]; + amrt_rb_node uncle = tree->nodes[unc_idx]; + if (unc_idx && uncle.color == AMRT_COLOR_RED) { + node.color = AMRT_COLOR_RED; + parent.color = AMRT_COLOR_BLACK; + uncle.color = AMRT_COLOR_BLACK; + + tree->nodes[node_idx] = node; + tree->nodes[parent_idx] = parent; + tree->nodes[unc_idx] = uncle; + + // update variables for node n-2 + node_idx = grandparent_idx; + node = grandparent; + parent_idx = grandparent.parent; + parent = tree->nodes[parent_idx]; + + // not needed but signifies that we will loop again + colored = 0; + + } else { + if (node.dir != parent.dir) { + // node near uncle + amrt__RBRotateUp(tree, node_idx); + // get updated node + node = tree->nodes[node_idx]; + parent_idx = node.parent; + amrt__RBRotateUp(tree, node_idx); + // get update node + node = tree->nodes[node_idx]; + amrt_idx old_parent_idx = parent_idx; + amrt_rb_node old_parent = tree->nodes[old_parent_idx]; + + // update colors + node.color = AMRT_COLOR_BLACK; + old_parent.color = AMRT_COLOR_RED; + tree->nodes[node_idx] = node; + tree->nodes[old_parent_idx] = old_parent; + + colored = 1; + + } else { + // node away from uncle + amrt__RBRotateUp(tree, parent_idx); + // get update nodes + grandparent = tree->nodes[grandparent_idx]; + parent = tree->nodes[parent_idx]; + node = tree->nodes[node_idx]; + + // update colors + parent.color = AMRT_COLOR_BLACK; + grandparent.color = AMRT_COLOR_RED; + node.color = AMRT_COLOR_RED; + + tree->nodes[node_idx] = node; + tree->nodes[parent_idx] = parent; + tree->nodes[grandparent_idx] = grandparent; + + colored = 1; + + } + } + } + } + + // @step: update head + amrt_idx head_idx = tree->head; + amrt_rb_node head = tree->nodes[head_idx]; + while(head.parent) { + head_idx = head.parent; + head = tree->nodes[head_idx]; + } + tree->head = head_idx; + + return 0; +} + +amrt_idx amrt_RBSearch(amrt_rb_tree tree, int to_find) { + amrt_idx node_idx = tree.head; + amrt_idx to_find_idx = AMRT_NIL; + + while (node_idx && !to_find_idx) { + amrt_rb_node node = tree.nodes[node_idx]; + if (to_find == node.value) { + to_find_idx = node_idx; + } else if (to_find < node.value) { + node_idx = node.left; + } else { + node_idx = node.right; + } + } + + return to_find_idx; +} + +amrt_status amrt_RBDelete(amrt_rb_tree *tree, int to_delete) { + amrt_idx idx = amrt_RBSearch(*tree, to_delete); + amrt_status status = amrt_RBIndexedDelete(tree, idx); + return status; +} + +amrt_status amrt_RBIndexedDelete(amrt_rb_tree *tree, amrt_idx node_idx) { + if (!node_idx) return 0; + + amrt_rb_node node = tree->nodes[node_idx]; + + if (node.left && node.right) { + // @step: both child present, narrow down to case of 1 or no child + amrt_idx right_smallest_idx = amrt__RBSubtreeFindSmallestNode(tree, node.right); + + if (right_smallest_idx) { + // replace node with smallest node + amrt_rb_node right_smallest = tree->nodes[right_smallest_idx]; + node.value = right_smallest.value; + tree->nodes[node_idx] = node; + + node_idx = right_smallest_idx; + node = right_smallest; + } + } + + bool colored = false; + while (!colored) { + AMRT_DIR child_dir = node.left ? AMRT_DIR_LEFT : AMRT_DIR_RIGHT; + amrt_idx parent_idx = node.parent; + amrt_idx child_idx = node.child[child_dir]; + amrt_rb_node parent = tree->nodes[parent_idx]; + amrt_rb_node child = tree->nodes[child_idx]; + + bool no_parent = !parent_idx; + bool node_black = node.color == AMRT_COLOR_BLACK; + bool node_red = node.color == AMRT_COLOR_RED; + bool child_black = child.color == AMRT_COLOR_BLACK; + bool child_red = child.color == AMRT_COLOR_RED; + bool node_black_child_red = node_black && child_red; + + if (no_parent || node_red || node_black_child_red) { + // color child + if (child_idx) { + child.color = AMRT_COLOR_BLACK; + tree->nodes[child_idx] = child; + } + + colored = 1; + // ??remove parent?? + } else { + // node black child black + amrt_idx sibling_idx = parent.child[!node.dir]; + amrt_rb_node sibling = tree->nodes[sibling_idx]; + amrt_idx close_nephew_idx = sibling.child[!sibling.dir]; + amrt_idx far_nephew_idx = sibling.child[sibling.dir]; + amrt_rb_node close_nephew = tree->nodes[close_nephew_idx]; + amrt_rb_node far_nephew = tree->nodes[far_nephew_idx]; + if (parent.color == AMRT_COLOR_RED) { + if (!close_nephew_idx || + close_nephew.color == AMRT_COLOR_BLACK) { + amrt__RBRotateUp(tree, sibling_idx); + colored = 1; + // ??remove parent?? + } else { + amrt__RBRotateUp(tree, close_nephew_idx); + // update vars and colors + parent = tree->nodes[parent_idx]; + parent.color = AMRT_COLOR_BLACK; + tree->nodes[parent_idx] = parent; + amrt__RBRotateUp(tree, close_nephew_idx); + colored = 1; + // ??remove parent?? + } + } else { + // CASE: Parent Black + if (sibling_idx && sibling.color == AMRT_COLOR_RED) { + // SUBCASE: Sibling Red + // make parent red + // make sibling black + parent.color = AMRT_COLOR_RED; + sibling.color = AMRT_COLOR_BLACK; + tree->nodes[parent_idx] = parent; + tree->nodes[sibling_idx] = sibling; + // rotate sibling up + amrt__RBRotateUp(tree, sibling_idx); + + colored = 0; + } else { + // SUBCASE: Sibling Black + if (far_nephew_idx && far_nephew.color == AMRT_COLOR_RED) { + // SUBCASE: Far Nephew Red + // color far nephew black + far_nephew.color = AMRT_COLOR_BLACK; + tree->nodes[far_nephew_idx] = far_nephew; + // rotate sibling up + amrt__RBRotateUp(tree, sibling_idx); + + colored = 1; + } else { + // SUBCASE: Far Nephew Black + if (close_nephew_idx && close_nephew.color == AMRT_COLOR_RED) { + // SUBCASE: Close Nephew Red + // color close nephew black + close_nephew.color = AMRT_COLOR_BLACK; + tree->nodes[close_nephew_idx] = close_nephew; + // rotate close nephew up + amrt__RBRotateUp(tree, close_nephew_idx); + // rotate close nephew up + amrt__RBRotateUp(tree, close_nephew_idx); + + colored = 1; + } else { + // SUBCASE: Close Nephew Black + + // Color Sibling Red + sibling.color = AMRT_COLOR_RED; + tree->nodes[sibling_idx] = sibling; + + // Move X Up and try to resolve again + // @todo: possibly, remove this function + // and do everything here, might be cleaner + amrt__RBIgnoreNode(tree, node_idx); + + // update parent + parent = tree->nodes[parent_idx]; + amrt_idx grandparent_idx = parent.parent; + if (parent_idx) { + parent.parent = node_idx; + node.child[child_dir] = AMRT_NIL; + node.child[!node.dir] = parent_idx; + AMRT_DIR parent_dir = parent.dir; + parent.dir = (AMRT_DIR)!node.dir; + node.dir = parent_dir; + + tree->nodes[parent_idx] = parent; + } + node.parent = grandparent_idx; + if (grandparent_idx) { + amrt_rb_node grandparent = tree->nodes[grandparent_idx]; + grandparent.child[node.dir] = node_idx; + tree->nodes[grandparent_idx] = grandparent; + } + tree->nodes[node_idx] = node; + + colored = 0; + } + } + } + } + } + } + amrt__RBIgnoreNode(tree, node_idx); + amrt__RBFreelistReclaim(tree, node_idx); + tree->node_count--; + + return 0; +} + +void amrt_RBClear(amrt_rb_tree *tree) { + AMRT_MEMZERO(tree->nodes, tree->node_max); + tree->head = AMRT_NIL; + tree->node_count = 0; + tree->freelist = tree->head + 1; + amrt_rb_node free = tree->nodes[tree->freelist]; + free.__size = tree->node_max - tree->freelist; + tree->nodes[tree->freelist] = free; +} + +void amrt_RBTerminate(amrt_rb_tree *tree) { + AMRT_FREE(tree->nodes); + *tree = {}; +}; + +void amrt_RBPrint(amrt_rb_tree *tree) { + amrt_idx *item_queue = (amrt_idx*)AMRT_MALLOC(sizeof(amrt_idx)*tree->node_max); + + amrt__RBUpdateLevels(tree, tree->head, 0); + + item_queue[0] = tree->head; + int i = 0; + int qidx = 1; + do { + amrt_idx iter_idx = item_queue[i]; + if (!iter_idx) continue; + amrt_rb_node iter = tree->nodes[iter_idx]; + if (iter.left) item_queue[qidx++] = iter.left; + if (iter.right) item_queue[qidx++] = iter.right; + } while (i++ < tree->node_count); + + int level = 0; + printf("\n============= BEGIN OF TREE ==========\n"); + for (i=0; i<qidx; i++) { + amrt_idx item_idx = item_queue[i]; + if (!item_idx) continue; + amrt_rb_node item = tree->nodes[item_idx]; + if (item.__level > level) { + printf("> Level %d: \n", level); + level++; + } + printf("Idx: %d, Color: %d, Item: %d, Dir: %d, Parent: %d, Left: %d, Right: %d\n", + item_idx, item.color, item.value, item.dir, item.parent, item.left, item.right); + } + printf("\n============= END OF TREE ==========\n"); + AMRT_FREE(item_queue); +} + +// Helper Functions + +amrt_idx amrt__RBFreelistPop(amrt_rb_tree *tree) { + amrt_idx head_idx = tree->freelist; + amrt_idx curr_free_idx = head_idx; + amrt_idx next_free_idx = curr_free_idx; + amrt_rb_node curr_free_node = tree->nodes[curr_free_idx]; + amrt_rb_node next_free_node = curr_free_node; + + // check if there is a free node available + // assumption is that head is valid + if (!curr_free_idx || !curr_free_node.__size) return curr_free_idx; + + if (curr_free_node.__size - 1) { + // free node has space + // move head 1 index ahead + next_free_idx = curr_free_idx + 1; + next_free_node = tree->nodes[next_free_idx]; + // decrease size + next_free_node.__size = curr_free_node.__size-1; + } else if (curr_free_node.next) { + // Other free nodes present + // move head to next free node + next_free_idx = curr_free_node.next; + } else { + // This is the last available free node + // Do nothing + // Keep it marked as head + // But keep providing this + // Alternatives: + // - assert and crash + // - allocate more + } + + tree->nodes[next_free_idx] = next_free_node; + tree->freelist = next_free_idx; + + return curr_free_idx; +} + +amrt_status amrt__RBFreelistReclaim(amrt_rb_tree *tree, amrt_idx node_idx) { + // @todo: + // implement freelist reclaim + // cases as far as i understand + // + // node before freelist head + // - check if node is right before old freelist head + // - mark node as freelist head and update size accordingly + // + // node after freelist head + // - get free idx just before node idx + // - join node with previous free and update size if continguous OR + // - update next and prev + // + // also dont forget to update nodes with proper elements + + if (!node_idx || tree->freelist == node_idx) return 0; + + amrt_idx freelist_idx = tree->freelist; + amrt_rb_node freelist = tree->nodes[freelist_idx]; + if (node_idx < freelist_idx) { + // node before freelist + amrt_rb_node node = {}; + node.__size = 1; + node.next = freelist_idx; + if (node_idx + 1 == freelist_idx) { + node.__size += freelist.__size; + node.next = freelist.next; + } + tree->nodes[node_idx] = node; + tree->freelist = node_idx; + } else { + amrt_idx iter_idx = freelist_idx; + amrt_rb_node iter = tree->nodes[iter_idx]; + while (iter.next < node_idx) { + iter_idx = iter.next; + iter = tree->nodes[iter_idx]; + } + // we have iter --- fit node here ------>iter.next + amrt_rb_node node = {}; + node.__size = 1; + node.next = iter.next; + iter.next = node_idx; + if (iter.__size + iter_idx == node_idx) { + // node right next to iter + // extend iter + iter.next = node.next; + iter.__size++; + } + tree->nodes[iter_idx] = iter; + tree->nodes[node_idx] = node; + } + + return 0; +} + +void amrt__RBRotateUp(amrt_rb_tree *tree, amrt_idx node_idx) { + if (node_idx) { + amrt_rb_node node = tree->nodes[node_idx]; + amrt_idx parent_idx = node.parent; + if (parent_idx) { + amrt_rb_node parent = tree->nodes[parent_idx]; + amrt_idx grandparent_idx = parent.parent; + amrt_rb_node grandparent = tree->nodes[grandparent_idx]; + + amrt_idx near_child_idx = node.child[!node.dir]; + amrt_rb_node near_child = tree->nodes[near_child_idx]; + + node.parent = grandparent_idx; + parent.parent = node_idx; + node.child[!node.dir] = parent_idx; + parent.child[node.dir] = near_child_idx; + + if (near_child_idx) { + near_child.parent = parent_idx; + near_child.dir = node.dir; + } + + AMRT_DIR parent_dir = parent.dir; + parent.dir = (AMRT_DIR)!node.dir; + + if (grandparent_idx) { + grandparent.child[parent_dir] = node_idx; + node.dir = parent_dir; + } + + // update + tree->nodes[grandparent_idx] = grandparent; + tree->nodes[parent_idx] = parent; + tree->nodes[near_child_idx] = near_child; + tree->nodes[node_idx] = node; + } + } + + return; +} + +amrt_idx amrt__RBSubtreeFindSmallestNode(amrt_rb_tree *tree, amrt_idx node_idx) { + + amrt_idx smallest_node_idx = node_idx; + amrt_rb_node node = tree->nodes[smallest_node_idx]; + while(node.left) { + smallest_node_idx = node.left; + node = tree->nodes[smallest_node_idx]; + } + return smallest_node_idx; +} + +amrt_status amrt__RBIgnoreNode(amrt_rb_tree *tree, amrt_idx node_idx) { + amrt_rb_node node = tree->nodes[node_idx]; + amrt_idx parent_idx = node.parent; + amrt_idx left_idx = node.left; + amrt_idx right_idx = node.right; + + if (left_idx && right_idx) return 1; + + amrt_idx child_idx = left_idx ? left_idx : right_idx; + amrt_rb_node parent = tree->nodes[parent_idx]; + amrt_rb_node child = tree->nodes[child_idx]; + + if (child_idx) { + child.parent = parent_idx; + child.dir = node.dir; + tree->nodes[child_idx] = child; + } + if (parent_idx) { + parent.child[node.dir] = child_idx; + tree->nodes[parent_idx] = parent; + } else { + // grandparent was nil + // parent would have been root + // child is new root + tree->head = child_idx; + } + + return 0; +} + +void amrt__RBUpdateLevels(amrt_rb_tree *tree, amrt_idx node_idx, int level) { + tree->nodes[node_idx].__level = level++; + amrt_rb_node node = tree->nodes[node_idx]; + if (node.left) { + amrt__RBUpdateLevels(tree, node.left, level); + } + if (node.right) { + amrt__RBUpdateLevels(tree, node.right, level); + } +} + +int amrt__RBValidateColors(amrt_rb_tree tree, amrt_idx node_idx) { + if (!node_idx) return 0; + amrt_rb_node node = tree.nodes[node_idx]; + + // validate red equality + bool red_equality_met = true; + if (node.color == AMRT_COLOR_RED) { + amrt_idx child_idx = node.left; + amrt_rb_node child = tree.nodes[child_idx]; + red_equality_met = ( + red_equality_met && + !child_idx || child.color == AMRT_COLOR_BLACK + ); + child_idx = node.right; + child = tree.nodes[child_idx]; + red_equality_met = ( + red_equality_met && + !child_idx || child.color == AMRT_COLOR_BLACK + ); + } + int black_count = node.color == AMRT_COLOR_BLACK; + int ltree_count = amrt__RBValidateColors(tree, node.left); + int rtree_count = amrt__RBValidateColors(tree, node.right); + black_count += rtree_count; + + bool black_equality_met = ltree_count >= 0 && ltree_count == rtree_count; + if (black_equality_met && red_equality_met) { + return black_count; + } else { + return -1; + } +} + +int amrt__RBCountNodes(amrt_rb_tree tree, amrt_idx node_idx) { + if (!node_idx) return 0; + + int node_count = 1; + amrt_rb_node node = tree.nodes[node_idx]; + node_count += amrt__RBCountNodes(tree, node.left); + node_count += amrt__RBCountNodes(tree, node.right); + + return node_count; +} + +bool amrt__RBSetupValid(amrt_rb_tree tree, amrt_idx node_idx) { + amrt_rb_node node = tree.nodes[node_idx]; + amrt_idx left_idx = node.left; + amrt_idx right_idx = node.right; + bool is_valid = true; + if (left_idx) { + amrt_rb_node left = tree.nodes[left_idx]; + bool subtree_valid = amrt__RBSetupValid(tree, left_idx); + is_valid = ( + is_valid && left.value <= node.value && + subtree_valid + ); + } + if (right_idx) { + amrt_rb_node right = tree.nodes[right_idx]; + bool subtree_valid = amrt__RBSetupValid(tree, right_idx); + is_valid = ( + is_valid && node.value <= right.value && + subtree_valid + ); + } + return is_valid; +} + +amrt_status amrt__RBValidate(amrt_rb_tree tree) { + // 1. root is black + amrt_idx head_idx = tree.head; + bool is_root_black = tree.nodes[head_idx].color == AMRT_COLOR_BLACK; + // 2. equal number of black nodes on each path + // 3. no consecutive red node + bool is_coloring_valid = amrt__RBValidateColors(tree, head_idx) >= 0; + // 4. inserted nodes match nodes in tree + bool is_node_count_valid = amrt__RBCountNodes(tree, head_idx) == tree.node_count; + // 5. validate node values are btree correct + bool is_btree_setup_valid = amrt__RBSetupValid(tree, head_idx); + + bool is_tree_valid = ( + is_root_black && is_coloring_valid && is_node_count_valid && + is_btree_setup_valid + ); + if (is_tree_valid) { + printf("RB Tree Validation: Success! all rules are mantained\n"); + } else { + printf("RB Tree Validation: Failure! \n"); + if (!is_root_black) { + printf("root is not black\n"); + } + if (!is_coloring_valid) { + printf("coloring is not correct. (Not sure which coloring)\n"); + } + if (!is_node_count_valid) { + printf("node count is not matching number of accessible nodes in the tree\n"); + } + if (!is_btree_setup_valid) { + printf("btree setup is not valid\n"); + } + } + return is_tree_valid; +} + +int main(void) { + amrt_rb_tree test_tree = amrt_RBInit(100); + amrt_RBInsert(&test_tree, 10); + amrt_RBInsert(&test_tree, 11); + amrt_RBInsert(&test_tree, 12); + amrt_RBInsert(&test_tree, 13); + amrt_RBInsert(&test_tree, 14); + amrt_RBInsert(&test_tree, 15); + amrt_RBInsert(&test_tree, 20); + amrt_RBInsert(&test_tree, 21); + amrt_RBInsert(&test_tree, 22); + amrt_RBInsert(&test_tree, 23); + amrt_RBInsert(&test_tree, 24); + amrt_RBInsert(&test_tree, 25); + amrt_RBInsert(&test_tree, 30); + amrt_RBInsert(&test_tree, 31); + amrt_RBInsert(&test_tree, 32); + amrt_RBInsert(&test_tree, 33); + amrt_RBInsert(&test_tree, 34); + amrt_RBInsert(&test_tree, 35); + amrt_RBInsert(&test_tree, 40); + amrt_RBInsert(&test_tree, 41); + amrt_RBInsert(&test_tree, 42); + amrt_RBInsert(&test_tree, 43); + amrt_RBInsert(&test_tree, 44); + amrt_RBInsert(&test_tree, 45); + amrt_RBInsert(&test_tree, 50); + amrt_RBInsert(&test_tree, 51); + amrt_RBInsert(&test_tree, 52); + amrt_RBInsert(&test_tree, 53); + amrt_RBInsert(&test_tree, 54); + amrt_RBInsert(&test_tree, 55); + + assert(amrt__RBValidate(test_tree)); + + assert(amrt_RBSearch(test_tree, 33)); + assert(!amrt_RBSearch(test_tree, 1998)); + + amrt_RBPrint(&test_tree); + amrt_RBDelete(&test_tree, 54); + amrt_RBDelete(&test_tree, 50); + amrt_RBDelete(&test_tree, 52); + amrt_RBDelete(&test_tree, 53); + + assert(amrt__RBValidate(test_tree)); + + // Testing Operations on duplicates + printf("\nTesting operations on duplicates\n"); + amrt_RBClear(&test_tree); + amrt_RBInsert(&test_tree, 32); + amrt_RBInsert(&test_tree, 32); + amrt_RBInsert(&test_tree, 32); + amrt_RBInsert(&test_tree, 32); + amrt_RBInsert(&test_tree, 32); + amrt_RBInsert(&test_tree, 54); + amrt_RBInsert(&test_tree, 54); + amrt_RBInsert(&test_tree, 54); + amrt_RBInsert(&test_tree, 54); + amrt_RBInsert(&test_tree, 54); + amrt_RBInsert(&test_tree, 85); + amrt_RBInsert(&test_tree, 85); + amrt_RBInsert(&test_tree, 85); + + amrt_RBDelete(&test_tree, 54); + amrt_RBDelete(&test_tree, 54); + amrt_RBDelete(&test_tree, 32); + amrt_RBDelete(&test_tree, 54); + amrt_RBDelete(&test_tree, 32); + amrt_RBDelete(&test_tree, 32); + assert(amrt__RBValidate(test_tree)); + + amrt_RBTerminate(&test_tree); + + return 0; +} |