From 8f15c1131342376ab3de2c6ce50d1ca5f20ec32a Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Tue, 26 Jan 2021 23:54:46 -0500 Subject: I don't have the presence of mind to debug this right now --- include/negamax.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'include/negamax.h') diff --git a/include/negamax.h b/include/negamax.h index 43995d1..bba5af9 100644 --- a/include/negamax.h +++ b/include/negamax.h @@ -6,6 +6,7 @@ #include #include #include +#include extern const float infty; extern char negamax_ptn[9]; @@ -25,3 +26,4 @@ negamax_free(void); // negamax_display_progress function is called on every new square at // the top level. float negamax_generate(void); +extern uint8_t yes; -- cgit v1.3.1 From 1be9fac33c8227564079356c63840d227c88725f Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Thu, 28 Jan 2021 13:53:19 -0500 Subject: Removed treap in favour of linked-list chained hash table --- include/negamax.h | 5 +- include/tt_llcht.c | 85 ++++++++++++++++++++++++++++ include/tt_llcht.h | 45 +++++++++++++++ include/tt_treap.c | 158 ----------------------------------------------------- include/tt_treap.h | 45 --------------- 5 files changed, 133 insertions(+), 205 deletions(-) create mode 100644 include/tt_llcht.c create mode 100644 include/tt_llcht.h delete mode 100644 include/tt_treap.c delete mode 100644 include/tt_treap.h (limited to 'include/negamax.h') diff --git a/include/negamax.h b/include/negamax.h index bba5af9..b41871e 100644 --- a/include/negamax.h +++ b/include/negamax.h @@ -2,10 +2,11 @@ #include #include + #include -#include #include -#include +#include +#include #include extern const float infty; diff --git a/include/tt_llcht.c b/include/tt_llcht.c new file mode 100644 index 0000000..03fa6cb --- /dev/null +++ b/include/tt_llcht.c @@ -0,0 +1,85 @@ +#include "tt_llcht.h" + +// =================================================================== +// Variables +// =================================================================== + +uint32_t tt_num_cached; +static tt_entry_t *table[TT_LLCHT_SIZE+1]; + +// =================================================================== +// Helper declarations +// =================================================================== + +tt_entry_t * +new_ll_node(const uint64_t key, const enum TT_FLAG flag, + const uint8_t depth, const float value, + const action_t action); + + +// =================================================================== +// Exported functions +// =================================================================== + +int tt_init(void) { + for (uint k=0; k<=TT_LLCHT_SIZE; k++) + table[k] = NULL; + return EXIT_SUCCESS; +} + +void tt_free(void) { + tt_entry_t *n, *nn; + for (uint k=0; k<=TT_LLCHT_SIZE; k++) { + n = table[k]; + while (n) { + nn = n->next; + free(n); + n = nn; + } + } +} + +tt_entry_t *tt_seek(const uint64_t key) { + tt_entry_t *lookup = table[key & TT_LLCHT_SIZE]; + while (lookup && lookup->key != key) + lookup = lookup->next; + return lookup; +} + +int tt_insert(const uint64_t key, const enum TT_FLAG flag, + const uint8_t depth, const float value, + const action_t action) { + tt_entry_t *new = new_ll_node(key, flag, depth, value, action), *n; + // TODO: trap + + const uint32_t idx = key & TT_LLCHT_SIZE; + if ((n = table[idx]) != NULL) { + for (; n->next != NULL; n = n->next); + n->next = new; + } else { + table[idx] = new; + } + + tt_num_cached++; + + return EXIT_SUCCESS; +} + +// =================================================================== +// Helper function implementations +// =================================================================== + +tt_entry_t * +new_ll_node(const uint64_t key, const enum TT_FLAG flag, + const uint8_t depth, const float value, + const action_t action) { + tt_entry_t *new = malloc(sizeof(struct tt_node_s)); + // TODO: trap errno + new->key = key; + new->next = NULL; + new->flag = flag; + new->depth = depth; + new->value = value; + new->action = action; + return new; +} diff --git a/include/tt_llcht.h b/include/tt_llcht.h new file mode 100644 index 0000000..f9a7a78 --- /dev/null +++ b/include/tt_llcht.h @@ -0,0 +1,45 @@ +#ifndef TT_LLCHT_H +#define TT_LLCHT_H + +#include +#include + +#include + +// =================================================================== +// Types +// =================================================================== + +enum TT_FLAG { TT_EXACT, TT_LOWERBOUND, TT_UPPERBOUND }; + +typedef struct tt_node_s { + uint64_t key; + struct tt_node_s *next; + enum TT_FLAG flag; + uint8_t depth; + float value; + action_t action; +} tt_entry_t; + +// =================================================================== +// Globals +// =================================================================== + +#define TT_LLCHT_SIZE ((uint32_t)((1<<19) - 1)) + +extern uint32_t tt_num_cached; + +// =================================================================== +// Methods +// =================================================================== + +int tt_init(void); +void tt_free(void); + +tt_entry_t *tt_seek(const uint64_t key); + +int tt_insert(const uint64_t key, const enum TT_FLAG flag, + const uint8_t depth, const float value, + const action_t action); + +#endif diff --git a/include/tt_treap.c b/include/tt_treap.c deleted file mode 100644 index 369d767..0000000 --- a/include/tt_treap.c +++ /dev/null @@ -1,158 +0,0 @@ -#include "tt_treap.h" - -// =================================================================== -// Variables -// =================================================================== - -uint32_t tt_num_cached; -static tt_entry_t * root; - -// =================================================================== -// Helper declarations -// =================================================================== - -void recurse_tree(tt_entry_t *n); -void bubble_up(tt_entry_t *n); - -tt_entry_t * -new_treap_node(const uint64_t key, const enum TT_FLAG flag, - const uint8_t depth, const float value, - const action_t action); - - -// =================================================================== -// Exported functions -// =================================================================== - -int tt_init(void) { - root = NULL; - tt_num_cached = 0; - return EXIT_SUCCESS; -} - -void tt_free(void) { - recurse_tree(root); - return; -} - -tt_entry_t *tt_seek(const uint64_t key) { - if (root == NULL) return NULL; - tt_entry_t * n = root; - - while (n != NULL && n->key != key) { - if (n->key > key) n = n->right; - else n = n->left; - } - return n; -} - -int tt_insert(const uint64_t key, const enum TT_FLAG flag, - const uint8_t depth, const float value, - const action_t action) { - tt_entry_t *m = new_treap_node(key, flag, depth, value, action); - if (root == NULL) { - root = m; - tt_num_cached = 1; - return EXIT_SUCCESS; - } - tt_entry_t *s = root, *n = root; - // Find the correct position by doing a BST traversal - while (n!=NULL) { - s = n; - if (n->key >= key) n = n->right; - else n = n->left; - } - // Make it a leaf - if (s->key > key) s->right = m; - else s->left = m; - m->parent = s; - // Now bubble upward to satisfy the heap property - bubble_up(m); - tt_num_cached++; - return EXIT_SUCCESS; -} - -// =================================================================== -// Helper implementations -// =================================================================== - -void recurse_tree(tt_entry_t *n) { - if (n==NULL) return; - if (n->left != NULL) recurse_tree(n->left); - if (n->right != NULL) recurse_tree(n->right); - free(n); -} - -tt_entry_t * -new_treap_node(const uint64_t key, const enum TT_FLAG flag, - const uint8_t depth, const float value, - const action_t action) { - tt_entry_t *n = malloc(sizeof(struct treap_node_s)); - // TODO: trap - n->key = key; - n->flag = flag; - n->depth = depth; - n->value = value; - n->left = NULL; - n->right = NULL; - n->parent = NULL; - n->action = action; - XORSHIFT64; n->weight = RANDOM32; - return n; -} - -void rotate_left(tt_entry_t *n) { - tt_entry_t *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(tt_entry_t *n) { - tt_entry_t *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(tt_entry_t *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; -} diff --git a/include/tt_treap.h b/include/tt_treap.h deleted file mode 100644 index 3991e79..0000000 --- a/include/tt_treap.h +++ /dev/null @@ -1,45 +0,0 @@ -#ifndef TT_TREAP_H -#define TT_TREAP_H - -#include -#include - -#include -#include - -// =================================================================== -// Types -// =================================================================== - -enum TT_FLAG { TT_EXACT, TT_LOWERBOUND, TT_UPPERBOUND }; - -typedef struct treap_node_s { - uint64_t key; - uint32_t weight; - struct treap_node_s *left, *right, *parent; - enum TT_FLAG flag; - uint8_t depth; - float value; - action_t action; -} tt_entry_t; - -// =================================================================== -// Globals -// =================================================================== - -extern uint32_t tt_num_cached; - -// =================================================================== -// Methods -// =================================================================== - -int tt_init(void); -void tt_free(void); - -tt_entry_t *tt_seek(uint64_t key); - -int tt_insert(const uint64_t key, const enum TT_FLAG flag, - const uint8_t depth, const float value, - const action_t action); - -#endif -- cgit v1.3.1