diff options
Diffstat (limited to 'include/cnn1986_treap_cache.c')
| -rw-r--r-- | include/cnn1986_treap_cache.c | 198 |
1 files changed, 198 insertions, 0 deletions
diff --git a/include/cnn1986_treap_cache.c b/include/cnn1986_treap_cache.c new file mode 100644 index 0000000..06553c1 --- /dev/null +++ b/include/cnn1986_treap_cache.c @@ -0,0 +1,198 @@ +#include "cnn1986_treap_cache.h" + +// =================================================================== +// Types +// =================================================================== + +typedef struct treap_node_s { + uint32_t weight; + struct treap_node_s *left, *right, *parent; + colour_stack_t colours[25]; + data_t celldat[25]; + uint8_t white_count, black_count; + float result; +} * TreapNode; + +enum E_CMP { EQ, GT, LT }; + +// =================================================================== +// Variables +// =================================================================== + +uint32_t cnn1986_num_cached; +uint32_t cnn1986_max_num_cached; // TODO +static TreapNode root; +static uint64_t xors = (uint64_t)123134124234879; + +// =================================================================== +// Helper declarations +// =================================================================== + +enum E_CMP compare_data(TreapNode n); +void recurse_tree(TreapNode n); +TreapNode new_treap_node(float in_result); +void bubble_up(TreapNode n); + +#define XORSHIFT { xors ^= xors >> 12; xors ^= xors << 25; xors ^= xors >> 27; } +#define RANDOM (xors *= 0x2545F4914F6CDD1D) + +// =================================================================== +// Exported functions +// =================================================================== + +int cnn1986_cache_init(void) { + root = NULL; + cnn1986_num_cached = 0; + return EXIT_SUCCESS; +} + +void cnn1986_cache_free(void) { + recurse_tree(root); + return; +} + +int cnn1986_cache_seek(float *out_result) { + if (root == NULL) return EXIT_FAILURE; + TreapNode n = root; + enum E_CMP e; + e = compare_data(n); + while (n != NULL && e != EQ) { + if (e == GT) n = n->right; + else n = n->left; + } + if (n == NULL) return EXIT_FAILURE; + *out_result = n->result; + return EXIT_SUCCESS; +} + +int cnn1986_cache_insert(float in_result) { + if (root == NULL) { + root = new_treap_node(in_result); + cnn1986_num_cached = 1; + return EXIT_SUCCESS; + } + TreapNode s = root, n = root, m = new_treap_node(in_result); + // Find the correct position by doing a BST traversal + enum E_CMP e; + while (n!=NULL) { + s = n; + e = compare_data(n); + if (e == LT) n = n->left; + else n = n->right; + } + // Make it a leaf + e = compare_data(s); + if (e == GT) s->right = m; + else s->left = m; + m->parent = s; + // Now bubble upward to satisfy the heap property + bubble_up(m); + cnn1986_num_cached++; + return EXIT_SUCCESS; +} + +// =================================================================== +// Helper implementations +// =================================================================== + +enum E_CMP compare_data(TreapNode n) { + if (n->white_count < white_count) return LT; + else if (n->white_count > white_count) return GT; + + if (n->black_count < black_count) return LT; + else if (n->black_count > black_count) return GT; + + for (int k = 0; k<25; k++) { + if (n->colours[k] < colours[k]) return LT; + if (n->colours[k] > colours[k]) return GT; + } + + for (int k = 0; k<25; k++) { + if (n->celldat[k] < celldat[k]) return LT; + if (n->celldat[k] > celldat[k]) return GT; + } + + return EQ; +} + +void recurse_tree(TreapNode n) { + if (n==NULL) return; + if (n->left != NULL) recurse_tree(n->left); + if (n->right != NULL) recurse_tree(n->right); + free(n); +} + +TreapNode new_treap_node(float in_result) { + TreapNode n = malloc(sizeof(struct treap_node_s)); + // TODO: trap + n->left = NULL; + n->right = NULL; + n->parent = NULL; + XORSHIFT; n->weight = RANDOM; + // Set key + for (int k = 0; k<25; k++) { + n->celldat[k] = celldat[k]; + n->colours[k] = colours[k]; + } + n->black_count = black_count; + n->white_count = white_count; + // Set value + n->result = in_result; + return n; +} + +void rotate_left(TreapNode n) { + TreapNode a = n->parent, b = a->left, c = n->left; + /* + We are the right child, so do this + a n + / \ / \ + b n --> a d + / \ / \ + c d b c + */ + n->parent = a->parent; + // We may have to repair one level up as well + if (a->parent!=NULL) { + if (a->parent->left == a) a->parent->left = n; + else a->parent->right = n; + } + a->parent = n; + n->left = a; a->parent = n; + a->left = b; if (b!=NULL) b->parent = a; + a->right = c; if (c!=NULL) c->parent = a; +} + +void rotate_right(TreapNode n) { + TreapNode a = n->parent, b = a->right, d = n->right; + /* + We are the left child, so do this + a n + / \ / \ + n b --> c a + / \ / \ + c d d b + */ + n->parent = a->parent; + // We may have to repair one level up as well + if (a->parent!=NULL) { + if (a->parent->left == a) a->parent->left = n; + else a->parent->right = n; + } + a->parent = n; + n->right = a; a->parent = n; + a->left = d; if (d!=NULL) d->parent = a; + a->right = b; if (b!=NULL) b->parent = a; +} + +//This preserves the BST quality of the treap +void bubble_up(TreapNode n) { + // Nothing to be done in this case + if (n==NULL || n->parent == NULL) return; + // Bubble until the treap invariants are satisfied + while (n->parent != NULL && n->weight < n->parent->weight) { + if (n->parent->left == n) rotate_right(n); + else rotate_left(n); + } + if (n->parent == NULL) root = n; +} |