aboutsummaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/negamax.h5
-rw-r--r--include/tt_llcht.c85
-rw-r--r--include/tt_llcht.h (renamed from include/tt_treap.h)14
-rw-r--r--include/tt_treap.c158
4 files changed, 95 insertions, 167 deletions
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 <math.h>
#include <tak.h>
+
#include <actions.h>
-#include <xorshift64.h>
#include <cnn1986.h>
-#include <tt_treap.h>
+#include <tt_llcht.h>
+#include <xorshift64.h>
#include <zobrist.h>
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_treap.h b/include/tt_llcht.h
index 3991e79..f9a7a78 100644
--- a/include/tt_treap.h
+++ b/include/tt_llcht.h
@@ -1,11 +1,10 @@
-#ifndef TT_TREAP_H
-#define TT_TREAP_H
+#ifndef TT_LLCHT_H
+#define TT_LLCHT_H
#include <stdlib.h>
#include <stdint.h>
#include <actions.h>
-#include <xorshift64.h>
// ===================================================================
// Types
@@ -13,10 +12,9 @@
enum TT_FLAG { TT_EXACT, TT_LOWERBOUND, TT_UPPERBOUND };
-typedef struct treap_node_s {
+typedef struct tt_node_s {
uint64_t key;
- uint32_t weight;
- struct treap_node_s *left, *right, *parent;
+ struct tt_node_s *next;
enum TT_FLAG flag;
uint8_t depth;
float value;
@@ -27,6 +25,8 @@ typedef struct treap_node_s {
// Globals
// ===================================================================
+#define TT_LLCHT_SIZE ((uint32_t)((1<<19) - 1))
+
extern uint32_t tt_num_cached;
// ===================================================================
@@ -36,7 +36,7 @@ extern uint32_t tt_num_cached;
int tt_init(void);
void tt_free(void);
-tt_entry_t *tt_seek(uint64_t key);
+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,
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;
-}
generated by cgit v1.3.1 (git 2.54.0) at 2026-08-30 17:13:43 +0000