Hash collisions

1 files changed, 15 insertions, 36 deletions

diff --git a/include/cnn1986_cache.c b/include/cnn1986_cache.c
index d9545ac..692920a 100644
--- a/include/cnn1986_cache.c
+++ b/include/cnn1986_cache.c
@@ -4,9 +4,11 @@
 #define DATA_COUNT_SHIFT (DATA_STONE_SHIFT+2)
 #define COLOUR_MASK      0x3F // 0b00111111
 
-uint32_t cnn1986_num_cached, cnn1986_max_num_cached;
+uint32_t cnn1986_num_cached, cnn1986_max_num_cached = 1000000;
 node_t *head = NULL, *tail = NULL;
 
+int cnn1986_cache_init(void) { return EXIT_SUCCESS; }
+
 void cnn1986_cache_free(void) {
 	node_t *c = head, *n;
 	while (c) {
@@ -18,37 +20,22 @@ void cnn1986_cache_free(void) {
 	tail = NULL;
 }
 
-int cnn1986_cache_seek(float *out_result) {
+int cnn1986_cache_seek(const uint64_t key[4],
+											 float *out_result) {
 	node_t *c = head;
-
-	if (c == NULL) return EXIT_FAILURE;
-
-	uint8_t comp_data[25], fail;
-	for (int k=0; k<25; k++) {
-		comp_data[k] = (colours[k] & COLOUR_MASK)
-			| (STONE_AT(k) << DATA_STONE_SHIFT)
-			| (COUNT_AT(k) << DATA_COUNT_SHIFT);
-	}
-
-	// We've checked c = head already, so uncoditionally test it
-	do {
-		// Compare
-		fail = 0;
-		if (c->black_count == black_count && c->white_count == white_count) {
-			for (int k=0; k<25; k++) {
-				if (comp_data[k] != c->data[k]) {
-					fail = 1;
-					break;
-				}
+	while (c != NULL) {
+		// Either seek next or move to front and return
+		uint8_t fail = 0;
+		for (int k=0; k<4; k++) {
+			if (c->key[k] != key[k]) {
+				fail = 1; break;
 			}
-		} else { fail = 1; }
+		}
 
-		// Either seek next or move to front and return
 		if (fail) {
 			c = c->next;
 		} else {
 			*out_result = c->result;
-
 			// Move to front
 			if (c != head) {
 				if (tail == c) tail=c->prev;
@@ -59,16 +46,14 @@ int cnn1986_cache_seek(float *out_result) {
 				head->prev = c;
 				head = c;
 			}
-
 			return EXIT_SUCCESS;
 		}
-	} while (c);
-
+	}
 	// Failed to find it
 	return EXIT_FAILURE;
 }
 
-int cnn1986_cache_insert(float in_result) {
+int cnn1986_cache_insert(const uint64_t key[4], float in_result) {
 	node_t *new = malloc(sizeof(node_t));
 	if (new == NULL) return EXIT_FAILURE;
 	// TODO: check errno
@@ -76,14 +61,8 @@ int cnn1986_cache_insert(float in_result) {
 	new->next = head;
 	if (head) head->prev = new;
 	head = new;
+	for (int k=0; k<4; k++) new->key[k] = key[k];
 	new->result = in_result;
-	new->white_count = white_count;
-	new->black_count = black_count;
-	for (int k=0; k<25; k++) {
-		new->data[k] = (colours[k] & COLOUR_MASK)
-			| (STONE_AT(k) << DATA_STONE_SHIFT)
-			| (COUNT_AT(k) << DATA_COUNT_SHIFT);
-	}
 	if (cnn1986_num_cached == 0) tail = new;
 	cnn1986_num_cached++;