Attempting Zobrist hashing

1 files changed, 24 insertions, 57 deletions

diff --git a/include/cnn1986_treap_cache.c b/include/cnn1986_treap_cache.c
index 06553c1..94eda58 100644
--- a/include/cnn1986_treap_cache.c
+++ b/include/cnn1986_treap_cache.c
@@ -5,36 +5,31 @@
 // ===================================================================
 
 typedef struct treap_node_s {
+	uint64_t key;
 	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;
+	/*
+	 * 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)
+void recurse_tree(const TreapNode n);
+TreapNode new_treap_node(const float in_result, const uint64_t key);
+void bubble_up(const TreapNode n);
 
 // ===================================================================
 // Exported functions
@@ -51,13 +46,12 @@ void cnn1986_cache_free(void) {
 	return;
 }
 
-int cnn1986_cache_seek(float *out_result) {
+int cnn1986_cache_seek(const uint64_t key, 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;
+
+	while (n != NULL && n->key != key) {
+		if (n->key > key) n = n->right;
 		else n = n->left;
 	}
 	if (n == NULL) return EXIT_FAILURE;
@@ -65,24 +59,22 @@ int cnn1986_cache_seek(float *out_result) {
 	return EXIT_SUCCESS;
 }
 
-int cnn1986_cache_insert(float in_result) {
+int cnn1986_cache_insert(const uint64_t key, const float in_result) {
 	if (root == NULL) {
-		root = new_treap_node(in_result);
+		root = new_treap_node(in_result, key);
 		cnn1986_num_cached = 1;
 		return EXIT_SUCCESS;
 	}
-	TreapNode s = root, n = root, m = new_treap_node(in_result);
+	TreapNode s = root, n = root,
+		m = new_treap_node(in_result, key);
 	// 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;
+		if (n->key >= key) n = n->right;
+		else n = n->left;
 	}
 	// Make it a leaf
-	e = compare_data(s);
-	if (e == GT) s->right = m;
+	if (s->key > key) s->right = m;
 	else s->left = m;
 	m->parent = s;
 	// Now bubble upward to satisfy the heap property
@@ -95,26 +87,6 @@ int cnn1986_cache_insert(float in_result) {
 // 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);
@@ -122,20 +94,15 @@ void recurse_tree(TreapNode n) {
 	free(n);
 }
 
-TreapNode new_treap_node(float in_result) {
+TreapNode new_treap_node(const float in_result, const uint64_t key) {
 	TreapNode n = malloc(sizeof(struct treap_node_s));
 	// TODO: trap
+	n->key = key;
 	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;
+	n->weight = RANDOM32;
+	XORSHIFT;
 	// Set value
 	n->result = in_result;
 	return n;