Removed treap in favour of linked-list chained hash table

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;
-}