diff options
Diffstat (limited to 'src/engine')
| -rw-r--r-- | src/engine/ttable.c | 165 |
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 |