From 6bcbbd2bd3710e13cad79b6822ef93e796d5e105 Mon Sep 17 00:00:00 2001 From: ken Date: Fri, 10 Mar 2017 17:50:51 -0800 Subject: [PATCH] dht reimplemented, 66% net execution time overall --- src/testston.c | 324 +++++++++++++--------------------------- ston/ston_ht.h | 392 ++++++++++++------------------------------------- 2 files changed, 191 insertions(+), 525 deletions(-) diff --git a/src/testston.c b/src/testston.c index 0f0f1f9..0c0fc19 100644 --- a/src/testston.c +++ b/src/testston.c @@ -1,7 +1,10 @@ #include //malloc #include //print #include //memcpy +#include //clock #include "../ston/ston.h" +#define XXH_PRIVATE_API +#include "../xxHash/xxhash.h" /* ansi terminal colors */ #define RED "\x1b[31m" @@ -13,238 +16,107 @@ #define CLRC "\x1b[0m" //clear current color #define CLRCN CLRC"\n" -#define print_val(val) do { \ - for (i = 0; i < (size_t)columns; i++) \ - printf("["YELLOW"%x"CLRC"]",val[i]); \ - printf("\n"); \ - } while(0) - -#define check_ht(_HT) \ - if ((_HT) == NULL) \ - { fprintf(stderr,RED"Could not allocate ht32"CLRCN); \ - return -1; \ - } \ - else \ - printf("ht_size: [units:%i][bytes:%li]\n",ston_ht_size(ht),ston_ht32_size(ht)); \ - -#define check_dht(_HT) \ - if ((_HT) == NULL) \ - { fprintf(stderr,RED"Could not allocate dht32"CLRCN); \ - return -1; \ - } \ - else \ - printf("ht_size: [units:%i][bytes:%i]\n",ston_dht_units(_HT,_HT->header.start_depth),ston_dht_bytes(_HT,_HT->header.start_depth)); \ +#define startclock(_STR) do { \ + start = clock(); \ + printf(_STR": "); \ + } while (0) +#define startclockf(_STR,...) do { \ + start = clock(); \ + printf(_STR": ",__VA_ARGS__); \ + } while (0) + +#define endclock() do { \ + end = clock(); \ + printf("%5f",(end - start)/(double)CLOCKS_PER_SEC); \ + } while (0) + +#define endclockn() do { \ + end = clock(); \ + printf("%5f\n",(end - start)/(double)CLOCKS_PER_SEC); \ + } while (0) + +#define $($)#$ +#define do_test(_COL,_COUNT,_HT,_FREE,_HTNEW,_HTINSERT,_HTROW,_SEED) do { \ + printf("[ " $(_HT) " ] "); \ + columns = _COL; \ + count = _COUNT; \ + _HT = _HTNEW; \ + startclockf("Filling " $(_HT) " with %i entries",count); \ + while (count--) \ + { key = XXH32(&count,4,_SEED); \ + val[0] = key; \ + for (i = 0; i < columns; i++) \ + val[i] = key - i; \ + _HTINSERT(_HT,key,val,0,columns); \ + } \ + endclockn(); \ + count = _COUNT; \ + fail = 0; \ + startclock("Reading entries"); \ + while (count--) \ + { key = XXH32(&count,4,_SEED); \ + htval = _HTROW(_HT,key); \ + if (htval == NULL) \ + { fail++; \ + printf("Row returned null\n"); \ + break; \ + } \ + if (*htval != key) \ + fail++; \ + for (i = 1; i < columns; i++) \ + if (htval[i] != key - i) \ + fail++; \ + } \ + endclock(); \ + if (fail) \ + printf(RED"\nFAIL"CLRC"(%i)\n", fail); \ + else \ + printf(GREEN"\nPASS"CLRCN); \ + _FREE(_HT); \ + } while (0) int main(int argc, char* argv[]) { static ston_ht ht; - uint32_t* htval, previous_val; + static ston_dht dht; uint32_t val[255], key; - size_t idx; + uint32_t* htval; size_t i; - size_t elements; uint16_t columns; int fail; - - printf("up2pow [5] = [%i]\n",ston_up2pow(5)); - for (i = 0; i < 77; i += 7) - printf("trailing0 [%X] = [%x]\n",(uint32_t)i,ston_trailing0(i)); - - columns = 2; - elements = 1; - ht = ston_ht32_new(columns,elements,0,malloc); - check_ht(ht); - key = 0xFF; - val[0] = key; - val[1] = 0x5; - printf("ht32_insertx: [%x] = ", key); - print_val(val); - ston_ht32_insertx(ht,key,val,0,columns); - idx = 1; - htval = ston_ht32_row(ht,key); - printf("Read value [%x] matches: %s"CLRCN, htval[idx], - (htval[idx] == val[idx]) ? GREEN"PASS" : RED"FAIL"); - - val[1] = 0x2; - previous_val = ston_ht32_insert(ht,key,1,val[1]); - printf("ht32_insert: [%x] = ", key); - print_val(val); - printf("Previous value [%x] matches [5]: %s"CLRCN, previous_val, - (previous_val == 0x5) ? GREEN"PASS" : RED"FAIL"); - - free(ht); - - columns = 4; - elements = 20; - ht = ston_ht32_new(columns,elements,0,malloc); - check_ht(ht); - printf("Filling hashtable with %i entries\n", (int)elements); - for(key = 0xCEED; elements--; key *= 7) - { val[0] = key; - for(i = 1; i < columns; i++) - val[i] = i * key; - ston_ht32_insertx(ht,key,val,0,columns); - } - elements = 20; - printf("Reading entries: "); - fail = 0; - for(key = 0xCEED; elements--; key *= 7) - { htval = ston_ht32_row(ht,key); - if (*htval != key) - fail++; - for(i = 1; i < columns; i++) - if (htval[i] != (uint32_t)(i * key)) - fail++; - } - if (fail) - printf(RED"FAIL"CLRC"(%i)\n", fail); - else - printf(GREEN"PASS"CLRCN); - int max_capacity = ston_up2pow(20 << 1) - 20; - int cap = max_capacity; - printf("Overfilling hashtable with %i entries\n", max_capacity); - for(key = 0xCEED2; cap--; key *= 13) - { val[0] = key; - for(i = 1; i < columns; i++) - val[i] = key * -i; - ston_ht32_insertx(ht,key,val,0,columns); - } - printf("Reading entries: "); - cap = max_capacity; - fail = 0; - for(key = 0xCEED2; cap--; key *= 13) - { htval = ston_ht32_row(ht,key); - if (*htval != key) - fail++; - for(i = 1; i < columns; i++) - if (htval[i] != (uint32_t)(key * -i)) - fail++; - } - if (fail) - printf(RED"FAIL"CLRC"(%i)\n", fail); - else - printf(GREEN"PASS"CLRCN); - - cap = 20; - printf("Post-capacity insertion of %i\n",cap); - for (key = 0xCEED3; cap--; key *= 23) - { val[0] = key; - for(i = 1; i < columns; i++) - val[i] = key * -i; - size_t count = ston_ht32_insertx(ht,key,val,0,columns); - printf("Insertion %2i wrote %i bytes: %s"CLRCN, (int)cap, (int) count, - (count == 0) ? GREEN"PASS" : RED"FAIL"); - } - - - printf("Refilling hashtable with %i entries\n", max_capacity); - cap = max_capacity; - for(key = 0xCEED2; cap--; key *= 13) - { val[0] = key; - for(i = 1; i < columns; i++) - val[i] = key * i; - ston_ht32_insertx(ht,key,val,0,columns); - } - printf("Reading entries: "); - cap = max_capacity; - fail = 0; - for(key = 0xCEED2; cap--; key *= 13) - { htval = ston_ht32_row(ht,key); - if (*htval != key) - fail ++; - for (i = 1; i < columns; i++) - if (htval[i] != (uint32_t)(key * i)) - fail++; - } - if (fail) - printf(RED"FAIL"CLRC"(%i)\n", fail); - else - printf(GREEN"PASS"CLRCN); - - free(ht); - - - printf("\n--------- DHT ----------\n\n"); - - ston_dht dht; - elements = 500; - columns = 6; - dht = ston_dht32_new(columns, malloc, free); - check_dht(dht); - elements = 50000; - printf("Filling Dynamic hashtable with %i entries\n", (int)elements); - for(key = 0xCEED; elements--; key *= 7) - { val[0] = key; - for(i = 1; i < columns; i++) - val[i] = i * key; - ston_dht32_insertx(dht,key,val,0,columns); - } - elements = 50000; - printf("Reading entries: "); - fail = 0; - for(key = 0xCEED; elements--; key *= 7) - { htval = ston_dht32_row(dht,key); - if (*htval != key) - fail++; - for(i = 1; i < columns; i++) - if (htval[i] != (uint32_t)(i * key)) - fail++; - } - if (fail) - printf(RED"FAIL"CLRC"(%i)\n", fail); - else - printf(GREEN"PASS"CLRCN); - max_capacity = 100000; - cap = max_capacity; - printf("Overfilling hashtable with %i entries\n", max_capacity); - for(key = 0xCEED2; cap--; key *= 13) - { val[0] = key; - for(i = 1; i < columns; i++) - val[i] = key * -i; - ston_dht32_insertx(dht,key,val,0,columns); - } - printf("Reading entries: "); - cap = max_capacity; - fail = 0; - for(key = 0xCEED2; cap--; key *= 13) - { htval = ston_dht32_row(dht,key); - if (*htval != key) - fail++; - for(i = 1; i < columns; i++) - if (htval[i] != (uint32_t)(key * -i)) - fail++; - } - if (fail) - printf(RED"FAIL"CLRC"(%i)\n", fail); - else - printf(GREEN"PASS"CLRCN); - - max_capacity = 5000000; - printf("Refilling hashtable with %i entries\n", max_capacity); - cap = max_capacity; - for(key = 0xCEED2; cap--; key *= 13) - { val[0] = key; - for(i = 1; i < columns; i++) - val[i] = key * i; - ston_dht32_insertx(dht,key,val,0,columns); - } - printf("Reading entries: "); - cap = max_capacity; - fail = 0; - for(key = 0xCEED2; cap--; key *= 13) - { htval = ston_dht32_row(dht,key); - if (*htval != key) - fail ++; - for (i = 1; i < columns; i++) - if (htval[i] != (uint32_t)(key * i)) - fail++; - } - if (fail) - printf(RED"FAIL"CLRC"(%i)\n", fail); - else - printf(GREEN"PASS"CLRCN); - - ston_dht_free(dht); - - return 0; + clock_t start, end; + int count; + printf("\nLow usage:\n"); + do_test(2,200,ht,free,ston_ht32_new(2,200,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); + do_test(5,200,ht,free,ston_ht32_new(5,200,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); + do_test(2,200,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); + do_test(5,200,dht,ston_dht_free,ston_dht32_new(5,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); + + printf("\nLow-mid usage:\n"); + do_test(2,10000,ht,free,ston_ht32_new(2,10000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); + do_test(5,10000,ht,free,ston_ht32_new(5,10000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); + do_test(2,10000,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); + do_test(5,10000,dht,ston_dht_free,ston_dht32_new(5,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); + + printf("\nMid usage:\n"); + do_test(2,500000,ht,free,ston_ht32_new(2,500000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); + do_test(5,500000,ht,free,ston_ht32_new(5,500000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); + do_test(2,500000,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); + do_test(5,500000,dht,ston_dht_free,ston_dht32_new(5,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); + + printf("\nMid-high usage:\n"); + do_test(2,9000000,ht,free,ston_ht32_new(2,9000000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); + do_test(5,9000000,ht,free,ston_ht32_new(5,9000000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); + do_test(2,9000000,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); + do_test(2,9000000,dht,ston_dht_free,ston_dht32_new(5,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); + + /* printf("\nHigh usage:\n"); */ + /* do_test(2,90000000,ht,free,ston_ht32_new(2,90000000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); */ + /* do_test(2,90000000,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); */ + + /* printf("\nHuge usage:\n"); */ + /* do_test(2,100000000,ht,free,ston_ht32_new(2,100000000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); */ + /* do_test(2,100000000,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); */ + + printf("\nDONE\n"); } diff --git a/ston/ston_ht.h b/ston/ston_ht.h index 4cddc78..2d9cb79 100644 --- a/ston/ston_ht.h +++ b/ston/ston_ht.h @@ -52,6 +52,8 @@ STON_FUNC_STATIC STON_FUNC_NOINLINE ston_ht ston_ht32_fread(FILE*,long,void*(*)(size_t)); +STON_FUNC_STATIC +STON_FUNC_NOINLINE size_t ston_ht32_fwrite(ston_ht,FILE*,long); #else #include @@ -151,6 +153,8 @@ ston_ht ston_ht32_create entire structure is verified, and all file operations are finished. Returns NULL with properly set errno on failure. */ +STON_FUNC_STATIC +STON_FUNC_NOINLINE ston_ht ston_ht32_fread ( FILE* file, long fpos, @@ -187,6 +191,8 @@ ston_ht ston_ht32_fread /* Writes a 32-bit hash table from memory into a file at fpos. Returns the number of bytes written to the file, errno is set on error. */ +STON_FUNC_STATIC +STON_FUNC_NOINLINE size_t ston_ht32_fwrite ( struct ston_ht_header_t* ht, FILE* file, @@ -279,238 +285,68 @@ ston_ht32_insertx } -#ifndef STON_DHT_SIZE -#define STON_DHT_SIZE 4096 -#endif - /* STON Dynamic Hashtable Structure A dynamic form of the generic hashtable implementation above which uses external allocation. */ typedef struct ston_dht_header_t -{ uint16_t columns; - uint8_t unit_bytes; - uint8_t start_depth; -}ston_dht_h; - -typedef struct ston_dht_t -{ ston_dht_h header; - void* pages[sizeof(void*) * 8]; - void* (*ht_alloc)(size_t); - void (*ht_free)(void*); -}* ston_dht; - -STON_FUNC -ston_dht ston_dht_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t),void(*)(void*)); -STON_FUNC -uint32_t* ston_dht32_row(ston_dht,uint32_t); -STON_FUNC -uint32_t ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t); -STON_FUNC -size_t ston_dht32_insertx(ston_dht,uint32_t,uint32_t*,uint16_t,size_t); -STON_FUNC -ston_dht ston_dht_free(ston_dht); - -#define ston_dht_units(_HT,_DEPTH) ((_HT)->header.columns << _DEPTH) -#define ston_dht_bytes(_HT,_DEPTH) (ston_dht_units(_HT,_DEPTH) * (_HT)->header.unit_bytes) -#define ston_dht_new(_COL,_ALOC,_FRE) (ston_dht_create(_COL,3,sizeof(int),_ALOC,_FRE)) -#define ston_dht_sized(_COL,_N,_ALOC,_FRE) (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N),sizeof(int),_ALOC,_FRE))) -#define ston_dht32_entry(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL) -#define ston_dht32_new(_COL,_ALOC,_FRE) (ston_dht_create(_COL,0,sizeof(uint32_t),_ALOC,_FRE)) -#define ston_dht32_sized(_COL,_N,_ALOC,_FRE) (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N)),sizeof(uint32_t),_ALOC,_FRE)) - - -/* Creates a new bucketted hash table, provided a memory allocation function - that takes a single size_t bytes, a memory free function, a column count, and - a row count which determines the size of the buckets. -*/ -STON_FUNC -ston_dht ston_dht_create -( uint16_t columns, - uint8_t start_depth, - uint8_t unit_bytes, - void* (*ht_alloc)(size_t), - void (*ht_free)(void*) -) -{ ston_dht ht = (ston_dht) ht_alloc(sizeof(struct ston_dht_t)); - if (ht != NULL) - { ht->header.columns = columns; - ht->header.start_depth = start_depth; - ht->header.unit_bytes = unit_bytes; - memset(ht->pages, 0, sizeof(void*) * sizeof(void*) * 8); - ht->pages[start_depth] = ht_alloc(ston_dht_bytes(ht, start_depth)); - ht->ht_alloc = ht_alloc; - ht->ht_free = ht_free; - if (ht->pages[start_depth] == NULL && ht_free != NULL) - ht_free(ht); - else - memset(ht->pages[start_depth], 0, ston_dht_bytes(ht, start_depth)); - } - return ht; -} - -/* Returns a pointer to the row of data in the hashtable containing the provided - key, inserts if not found. Returns NULL on overflow. -*/ -STON_FUNC -uint32_t* ston_dht32_row -( struct ston_dht_t* ht, - uint32_t key -) -{ uint16_t columns = ht->header.columns; - uint8_t depth = ht->header.start_depth; - uint32_t mask = ((0x1 << depth) - 1) >> 1; - void* page; - uint32_t* row; - uint32_t row_key; - next_page: - if (ht->pages[depth] == NULL) - { ht->pages[depth] = ht->ht_alloc(ston_dht_bytes(ht, depth)); - if (ht->pages[depth] == NULL) - return NULL; - memset(ht->pages[depth], 0, ston_dht_bytes(ht, depth)); - } - page = ht->pages[depth]; - row = (uint32_t*)page + ((key & mask) * columns); - row_key = *row; - if (row_key == key || row_key == 0) - { row[0] = key; - return row; - } - depth++; - mask = (mask << 1) | 0x1; - goto next_page; -} - -/* Inserts a value into a hashtable at the specified column, returning the - previous value */ -STON_FUNC -uint32_t ston_dht32_insert -( struct ston_dht_t* ht, - uint32_t key, - uint16_t column, - uint32_t value -) -{ uint32_t* value_location, old_value; - value_location = ston_dht32_entry(ht,key,column); - old_value = *value_location; - *value_location = value; - return old_value; -} - -/* Insert multiple values, returning the number of bytes written */ -STON_FUNC -size_t -ston_dht32_insertx -( struct ston_dht_t* ht, - uint32_t key, - uint32_t* data_src, - uint16_t start_column, - size_t units -) -{ uint32_t* data_row = ston_dht32_row(ht,key); - uint32_t* data_limit = data_row + ht->header.columns; - uint32_t* data_trg = data_row + start_column; - if (data_row == NULL) - return 0; - while (units-- && data_trg < data_limit) - *data_trg++ = *data_src++; - return (size_t)(data_trg - data_row); -} - -/* Free the dynamic hash table */ -STON_FUNC -struct ston_dht_t* ston_dht_free -( struct ston_dht_t* ht ) -{ void (*ht_free)(void*) = ht->ht_free; - uint8_t depth = ht->header.start_depth; - void** pages = ht->pages; - if (ht_free != NULL) - { while (pages[depth] != NULL) - ht_free(pages[depth++]); - ht_free(ht); - return NULL; - } - return ht; -} - -/******************************************************************************** -********************************************************************************* -********************************************************************************* -********************************************************************************/ -typedef struct ston_dht2_header_t { uint16_t val_bytes; uint8_t key_bytes; uint8_t flags; -}ston_dht2_h; - -typedef struct ston_dht2_bucket_t -{ uint8_t depth; - void* page; - uint32_t count; -}ston_dht2_bucket_h,* ston_dht2_bucket; +}ston_dht_h; -#define STON_DHT_BUCKETS_SIZE (sizeof(void*) * 8) -typedef struct ston_dht2_t -{ ston_dht2_h header; - ston_dht2_bucket_h buckets[1 + STON_DHT_BUCKETS_SIZE]; - ston_dht2_bucket bsp; - uint32_t row_bytes; - uint8_t buckets_len; +typedef struct ston_dht_t +{ ston_dht_h header; void* (*ht_alloc)(size_t); void (*ht_free)(void*); -}* ston_dht2; + void* bucket_root; + size_t rowsize, bucketsize; +}* ston_dht; STON_FUNC -ston_dht2 ston_dht2_create(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*)); +ston_dht ston_dht_new(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*)); STON_FUNC -uint32_t* ston_dht232_row(ston_dht2,uint32_t); -STON_FUNC -uint32_t ston_dht232_insert(ston_dht2,uint32_t,uint16_t,uint32_t); -STON_FUNC -size_t ston_dht232_insertx(ston_dht2,uint32_t,uint32_t*,uint16_t,size_t); +ston_dht ston_dht_free(ston_dht); STON_FUNC -ston_dht2 ston_dht2_free(ston_dht2); - -#define ston_dht2_bytes(_HT,_DEPTH) ((_HT)->row_bytes << (_DEPTH)) -#define ston_dht2_new(_COL,_ALOC,_FRE) (ston_dht2_create(_COL,sizeof(int),_ALOC,_FRE)) -#define ston_dht232_new(_COL,_ALOC,_FRE) (ston_dht2_create(_COL,sizeof(uint32_t),_ALOC,_FRE)) -#define ston_dht232_entry(_HT,_KEY,_COL) (ston_dht232_row(_HT,_KEY) + _COL) - +void* ston_dht_data(ston_dht,void*); +STON_FUNC_STATIC +STON_FUNC_NOINLINE +void ston_dht_free_bucket(ston_dht,void*); +/* STON_FUNC */ +/* ston_dht ston_dht_iterate_start(ston_dht); */ +/* STON_FUNC */ +/* ston_dht ston_dht_iterate_next(ston_dht); */ + +// Compatibility macros +#define ston_dht32_new(_COL,_ALOC,_FRE) (ston_dht_new(4 * _COL, 4, _ALOC, _FRE)) +#define ston_dht32_row(_HT,_K) ((uint32_t*)((uint8_t*)ston_dht_data(_HT,&(_K)) - 4)) +#define ston_dht32_insertx(_HT,_K,_VP,_OFFS,_N) \ + memcpy((uint32_t*)((uint8_t*)ston_dht_data(_HT,&(_K)) + ((_OFFS - 1) * 4)),_VP,_N * 4) /* Creates a new bucketted hash table, provided a memory allocation function that takes a single size_t bytes, a memory free function, a column count, and a row count which determines the size of the buckets. */ -static ston_dht2_bucket_h dummy_bucket = { (uint8_t)-1, NULL, (uint32_t)-1 }; - STON_FUNC -ston_dht2 ston_dht2_create +ston_dht ston_dht_new ( uint16_t val_bytes, uint8_t key_bytes, void* (*ht_alloc)(size_t), void (*ht_free)(void*) ) -{ ston_dht2 ht = (ston_dht2) ht_alloc(sizeof(struct ston_dht2_t)); +{ ston_dht ht = (ston_dht) ht_alloc(sizeof(struct ston_dht_t)); if (ht != NULL) { ht->header.val_bytes = val_bytes; ht->header.key_bytes = key_bytes; - ht->row_bytes = val_bytes + key_bytes; + ht->rowsize = sizeof(void*) + key_bytes + val_bytes; + ht->bucketsize = ht->rowsize * 0x100; ht->ht_alloc = ht_alloc; ht->ht_free = ht_free; - size_t i; - for (i = 0; i <= STON_DHT_BUCKETS_SIZE; i++) - ht->buckets[i] = dummy_bucket; - ht->bsp = ht->buckets + STON_DHT_BUCKETS_SIZE - 1; - ht->bsp->page = ht_alloc(ston_dht2_bytes(ht, 4)); - if (ht->bsp->page == NULL && ht_free != NULL) + ht->bucket_root = ht_alloc(ht->bucketsize); + if (ht->bucket_root == NULL && ht_free != NULL) ht_free(ht); else - { memset((ht->bsp->page), 0, ston_dht2_bytes(ht,4)); - ht->bsp->depth = 4; - ht->bsp->count = 0; - ht->buckets_len = 1; - } + memset((ht->bucket_root), 0, ht->bucketsize); } return ht; } @@ -519,116 +355,74 @@ ston_dht2 ston_dht2_create /* Returns a pointer to the row of data in the hashtable containing the provided key, inserting if not found, or NULL if a memory error occurs */ STON_FUNC -uint32_t* ston_dht232_row -( struct ston_dht2_t* ht, - uint32_t key +void* ston_dht_data +( struct ston_dht_t* ht, + void* key ) -{ int8_t bucket_no = (int8_t)ht->buckets_len - 1; - uint32_t* row, row_key, mask; - size_t bytes; - int8_t zero_bucket = (int8_t)-1; - ston_dht2_bucket bsp = ht->bsp; - ston_dht2_bucket_h bucket; +{ size_t key_bytes = ht->header.key_bytes; + uint8_t* key_byte = (uint8_t*)key; + uint8_t* bucket = (uint8_t*)ht->bucket_root; + uint8_t** bucketp; + uint8_t* row,* a,* b; + uint8_t a_not_empty; + size_t i; + next_row: + row = bucket + (ht->rowsize * (*key_byte)); + a = row + sizeof(void*); + b = (uint8_t*)key; + a_not_empty = 0; + for (i = 0; i < key_bytes; i++) + { a_not_empty |= a[i]; + if (a_not_empty && a[i] != b[i]) + goto next_bucket; + } + if (!a_not_empty) + memcpy(row + sizeof(void*),key,key_bytes); + goto done; next_bucket: - bucket = bsp[bucket_no]; - /* Find until out of allocated pages, then insert at last empty bucket position */ - if (bucket.page == NULL) - { if (zero_bucket != (int8_t)-1) - { bucket = bsp[zero_bucket]; - mask = (0x1 << bucket.depth) - 1; - row = (uint32_t*)bucket.page + (key & mask); - *row = key; - bucket.count++; - /* Swap the buckets up a level if the count has exceeded its parent's count */ - if (bucket.count > bsp[zero_bucket + 1].count) - { bsp[zero_bucket] = bsp[zero_bucket + 1]; - bsp[zero_bucket + 1] = bucket; - } - else - bsp[zero_bucket].count = bucket.count; - return row; - } - /* No buckets with a slot, shift the key right by depth, try again add a new bucket */ - bsp--; - bucket.depth = 4 + (ht->buckets_len >> 1); - bucket.count = 1; - bytes = ston_dht2_bytes(ht,bucket.depth); - if ((bucket.page = ht->ht_alloc(bytes)) == NULL) - { printf("Failed to allocate %lu bytes, bucket %i at with len %i\n", - bytes, bucket_no, ht->buckets_len); - return NULL; - } - memset(bucket.page,0,bytes); - *bsp = bucket; - ht->bsp = bsp; - ht->buckets_len++; - mask = (0x1 << bucket.depth) - 1; - row = (uint32_t*)bucket.page + (key & mask); - *row = key; - return row; + key_byte++; + bucketp = (uint8_t**)row; + if (*bucketp == NULL) + { if ((*bucketp = ht->ht_alloc(ht->bucketsize)) == NULL) + return NULL; + else + memset(*bucketp,0,ht->bucketsize); } - /* Compute mask, and use it to find the row in the page */ - mask = (0x1 << bucket.depth) - 1; - row = (uint32_t*)bucket.page + (key & mask); - /* Look at the key at row[0], branch */ - row_key = *row; - if (row_key == key) - return row; - if (row_key == 0) - zero_bucket = bucket_no; - bucket_no--; - goto next_bucket; + bucket = *bucketp; + goto next_row; + done: + return (void*) row + sizeof(void*) + key_bytes; } -/* Inserts a value into a hashtable at the specified column, returning the - previous value */ +/* Free the dynamic hash table */ STON_FUNC -uint32_t ston_dht232_insert -( struct ston_dht2_t* ht, - uint32_t key, - uint16_t column, - uint32_t value -) -{ uint32_t* value_location, old_value; - value_location = ston_dht232_entry(ht,key,column); - old_value = *value_location; - *value_location = value; - return old_value; +struct ston_dht_t* ston_dht_free +( struct ston_dht_t* ht ) +{ void (*ht_free)(void*) = ht->ht_free; + if (ht_free == NULL) + return NULL; + ston_dht_free_bucket(ht, ht->bucket_root); + ht_free(ht); + return ht; } -/* Insert multiple values, returning the number of bytes written */ -STON_FUNC -size_t -ston_dht232_insertx -( struct ston_dht2_t* ht, - uint32_t key, - uint32_t* data_src, - uint16_t start_column, - size_t units +/* Recursively free pages by lookup */ +STON_FUNC_STATIC +STON_FUNC_NOINLINE +void ston_dht_free_bucket +( struct ston_dht_t* ht, + void* bucket ) -{ uint32_t* data_row = ston_dht232_row(ht,key); - uint32_t* data_limit = data_row + ht->row_bytes; - uint32_t* data_trg = data_row + start_column; - if (data_row == NULL) - return 0; - while (units-- && data_trg < data_limit) - *data_trg++ = *data_src++; - return (size_t)(data_trg - data_row); -} - -/* Free the dynamic hash table */ -STON_FUNC -struct ston_dht2_t* ston_dht2_free -( struct ston_dht2_t* ht ) -{ void (*ht_free)(void*) = ht->ht_free; - uint8_t bucket = ht->buckets_len; - if (ht_free != NULL) - { while (bucket--) - ht_free(ht->buckets[bucket].page); - ht_free(ht); - return NULL; +{ size_t key_bytes = ht->header.key_bytes; + size_t val_bytes = ht->header.val_bytes; + void** bucket_cur = (void**)((uint8_t*)bucket); + void** bucket_max = (void**)((uint8_t*)bucket_cur + ((sizeof(void*) + key_bytes + val_bytes) * 0x100)); + while (bucket_cur < bucket_max) + { if (*bucket_cur != NULL) + ston_dht_free_bucket(ht, *bucket_cur); + bucket_cur = (void**)((uint8_t*)bucket_cur + sizeof(void*) + key_bytes + val_bytes); } - return ht; + ht->ht_free(bucket); } -- 2.18.0