added the remaining ttable tests & fixed bugs

1 files changed, 79 insertions, 86 deletions

diff --git a/src/engine/ttable.c b/src/engine/ttable.c
index 851e389..fc1b6f0 100644
--- a/src/engine/ttable.c
+++ b/src/engine/ttable.c
@@ -47,21 +47,28 @@ u64 zobrist_hash(position_t position) {
   return output;
 }
 
-void ttable_init(ttable_t *table) {
-  ttable_t output = calloc(TABLE_SIZE, sizeof(tbucket_t));
-  memcpy(table, &output, sizeof(output));
+void ttable_init(ttable_t *table, size_t size_in_binary_log) {
+  assert(size_in_binary_log < 64);
+  int size = 1ULL << size_in_binary_log;
+  table->buckets = calloc(size, sizeof(tbucket_t));
+  table->mask = size - 1;
 }
 
 void ttable_deinit(ttable_t table) {
-  free(table);
+  free(table.buckets);
 }
 
 void __ttable_insert(ttable_t table, struct ttable_insert_args args) {
-  tbucket_t *bucket = table + (args.key & TT_MASK);
+  tbucket_t *bucket = table.buckets + (args.key & table.mask);
   tentry_t *best = bucket->entries;
 
-  int count = bucket->items_filled;
-  for (int i = 1; i < count; i++) {
+  int ci = 0;
+
+  for (int i = 0; i < TT_BUCKET_SIZE; i++) {
+    if (atomic_load(&bucket->entries[i].key) == args.key) {
+      best = bucket->entries + i;
+      break;
+    }
     if (bucket->entries[i].depth >= best->depth) continue;
     best = bucket->entries + i;
   }
@@ -79,7 +86,7 @@ void __ttable_insert(ttable_t table, struct ttable_insert_args args) {
 }
 
 tentry_t *ttable_find(ttable_t table, u64 key) {
-  tbucket_t *bucket = table + (key & TT_MASK);
+  tbucket_t *bucket = table.buckets + (key & table.mask);
 
   for (int i = 0; i < TT_BUCKET_SIZE; i++) {
     if (atomic_load(&(bucket->entries + i)->key) != key) continue;
@@ -91,20 +98,19 @@ tentry_t *ttable_find(ttable_t table, u64 key) {
 
 #ifdef TEST_MOD
 
-bool test_empty_ttable() {
+bool test_ttable_empty() {
   ttable_t table;
-  ttable_init(&table);
+  ttable_init(&table, 4);
 
   if (ttable_find(table, 123456789ULL) != NULL) return false;
 
   ttable_deinit(table);
-
   return true;
 }
 
 bool test_ttable_insert_and_find() {
   ttable_t table;
-  ttable_init(&table);
+  ttable_init(&table, 4);
 
   u64 key = 0x123456789ABCDEF0ULL;
   ttable_insert(table, .key = key, .depth = 8, .flag = TT_EXACT);
@@ -123,7 +129,7 @@ bool test_ttable_insert_and_find() {
 
 bool test_ttable_wrong_key() {
   ttable_t table;
-  ttable_init(&table);
+  ttable_init(&table, 4);
 
   u64 key = 0x123456789ABCDEF0ULL;
   ttable_insert(table, .key = key, .depth = 8, .flag = TT_EXACT);
@@ -135,7 +141,7 @@ bool test_ttable_wrong_key() {
 
 bool test_ttable_update_existing() {
   ttable_t table;
-  ttable_init(&table);
+  ttable_init(&table, 4);
 
   u64 key = 987654321ULL;
   ttable_insert(table, .key = key, .depth = 10, .flag = TT_LOWERBOUND);
@@ -151,77 +157,64 @@ bool test_ttable_update_existing() {
   return true;
 }
 
-// bool FAH_test_bucket_collision() {
-//   ttable_t table;
-//   ttable_init(&table);
-//
-//
-//
-//     TranspositionTable tt;
-//     tt_init(&tt, 1); // one bucket
-//
-//     tt_store(&tt, 1, 10, 10, 5, TT_EXACT);
-//     tt_store(&tt, 2, 20, 20, 5, TT_EXACT);
-//     tt_store(&tt, 3, 30, 30, 5, TT_EXACT);
-//     tt_store(&tt, 4, 40, 40, 5, TT_EXACT);
-//
-//     assert(tt_probe(&tt, 1) != NULL);
-//     assert(tt_probe(&tt, 2) != NULL);
-//     assert(tt_probe(&tt, 3) != NULL);
-//     assert(tt_probe(&tt, 4) != NULL);
-//
-//     tt_destroy(&tt);
-// }
-
-// void test_replace_shallowest(void) {
-//     TranspositionTable tt;
-//     tt_init(&tt, 1);
-//
-//     tt_store(&tt, 1, 0, 0, 10, TT_EXACT);
-//     tt_store(&tt, 2, 0, 0, 20, TT_EXACT);
-//     tt_store(&tt, 3, 0, 0, 30, TT_EXACT);
-//     tt_store(&tt, 4, 0, 0, 40, TT_EXACT);
-//
-//     // Bucket is full.
-//
-//     tt_store(&tt, 5, 0, 0, 25, TT_EXACT);
-//
-//     assert(tt_probe(&tt, 1) == NULL);
-//
-//     assert(tt_probe(&tt, 2) != NULL);
-//     assert(tt_probe(&tt, 3) != NULL);
-//     assert(tt_probe(&tt, 4) != NULL);
-//     assert(tt_probe(&tt, 5) != NULL);
-//
-//     tt_destroy(&tt);
-// }
-
-// void test_many_entries(void)
-// {
-//     TranspositionTable tt;
-//     tt_init(&tt, 1 << 16);
-//
-//     for (uint64_t i = 0; i < 50000; i++)
-//     {
-//         tt_store(&tt,
-//                  i * 7919,
-//                  i,
-//                  i,
-//                  i % 64,
-//                  TT_EXACT);
-//     }
-//
-//     for (uint64_t i = 0; i < 50000; i++)
-//     {
-//         TTEntry *e = tt_probe(&tt, i * 7919);
-//
-//         if (e)
-//         {
-//             assert(e->key == i * 7919);
-//         }
-//     }
-//
-//     tt_destroy(&tt);
-// }
+bool test_bucket_collision() {
+  ttable_t table;
+  ttable_init(&table, 2);
+
+  ttable_insert(table, .key = 1, .depth = 10, .flag = TT_EXACT);
+  ttable_insert(table, .key = 2, .depth = 20, .flag = TT_EXACT);
+  ttable_insert(table, .key = 3, .depth = 30, .flag = TT_EXACT);
+  ttable_insert(table, .key = 4, .depth = 40, .flag = TT_EXACT);
+
+  if (ttable_find(table, 1) == NULL) return false;
+  if (ttable_find(table, 2) == NULL) return false;
+  if (ttable_find(table, 3) == NULL) return false;
+  if (ttable_find(table, 4) == NULL) return false;
+
+  ttable_deinit(table);
+  return true;
+}
+
+bool test_ttable_replace_shallowest() {
+  ttable_t table;
+  ttable_init(&table, 0);
+
+  ttable_insert(table, .key = 1, .depth = 10, .flag = TT_EXACT);
+  ttable_insert(table, .key = 2, .depth = 20, .flag = TT_EXACT);
+  ttable_insert(table, .key = 3, .depth = 30, .flag = TT_EXACT);
+  ttable_insert(table, .key = 4, .depth = 40, .flag = TT_EXACT);
+
+  // Bucket is full.
+  ttable_insert(table, .key = 5, .depth = 25, .flag = TT_EXACT);
+
+  if (ttable_find(table, 1) != NULL) return false;
+
+  if (ttable_find(table, 2) == NULL) return false;
+  if (ttable_find(table, 3) == NULL) return false;
+  if (ttable_find(table, 4) == NULL) return false;
+  if (ttable_find(table, 5) == NULL) return false;
+
+  ttable_deinit(table);
+  return true;
+}
+
+bool test_ttable_many_entries() {
+  ttable_t table;
+  ttable_init(&table, 16);
+
+  for (u64 i = 0; i < 50000; i++) {
+    ttable_insert(table, .key = i * 7919, .depth = i % 64, .flag = TT_EXACT);
+  }
+
+  for (u64 i = 0; i < 50000; i++) {
+    tentry_t *e = ttable_find(table, i * 7919);
+
+    if (e == NULL) continue;
+    if (e->key != i * 7919) return false;
+  }
+
+  ttable_deinit(table);
+  return true;
+}
 
 #endif