From 16091722cd675ef3e48a56c22fc827eb5cde352e Mon Sep 17 00:00:00 2001 From: ken Date: Wed, 1 Mar 2017 16:00:46 -0800 Subject: [PATCH] dht implementation first round tests pass --- src/testston.c | 166 +++++++++++++++++++++++++++++++++++++++++++++---- ston/ston_ht.h | 66 +++++++++++++------- 2 files changed, 199 insertions(+), 33 deletions(-) diff --git a/src/testston.c b/src/testston.c index 32910b0..014a58c 100644 --- a/src/testston.c +++ b/src/testston.c @@ -36,9 +36,10 @@ int main(int argc, char* argv[]) size_t i; size_t elements; uint16_t columns; + int fail; printf("up2pow [5] = [%i]\n",ston_up2pow(5)); - for (i = 0; i < 255; i += 7) + for (i = 0; i < 77; i += 7) printf("trailing0 [%X] = [%x]\n",(uint32_t)i,ston_trailing0(i)); columns = 2; @@ -69,41 +70,184 @@ int main(int argc, char* argv[]) elements = 20; ht = ston_ht32_new(columns,elements,0,malloc); check_ht(ht); - printf("Filling hashtable with entries\n"); + 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); } - printf("Reading entries\n"); elements = 20; + printf("Reading entries: "); + fail = 0; for(key = 0xCEED; elements--; key *= 7) { htval = ston_ht32_row(ht,key); - printf("[%s%x"CLRC"]",(*htval == key) ? GREEN : RED,*htval); + if (*htval != key) + fail++; for(i = 1; i < columns; i++) - printf("[%s%x"CLRC"]",(htval[i] == (uint32_t)(i * key)) ? GREEN : RED,htval[i]); - putchar('\n'); + 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; - printf("Overfilling hashtable with %i entries\n", max_capacity); 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\n"); + printf("Reading entries: "); cap = max_capacity; + fail = 0; for(key = 0xCEED2; cap--; key *= 13) { htval = ston_ht32_row(ht,key); - printf("[%s%x"CLRC"]",(*htval == key) ? GREEN : RED,*htval); + 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++) - printf("[%s%x"CLRC"]",(htval[i] == (uint32_t)(key * -i)) ? GREEN : RED,htval[i]); - printf("\n"); + 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 = 50; + columns = 6; + dht = ston_dht32_new(columns, elements, 0, malloc, free); + check_ht(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 = (ston_up2pow(50 << 1) * (ston_dht_pagemax(dht) - ston_dht_pagestart(dht))) - 50000; + 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); + + 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_dht32_insertx(dht,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_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_dht32_free(dht); + return 0; } diff --git a/ston/ston_ht.h b/ston/ston_ht.h index b17e18e..fb5d566 100644 --- a/ston/ston_ht.h +++ b/ston/ston_ht.h @@ -63,7 +63,7 @@ ston_ht ston_ht32_fread(FILE*,long,void*(*)(size_t)); typedef struct ston_ht_header_t { uint16_t ht_columns; uint8_t ht_2pow, ht_flags; -}* ston_ht; +}ston_ht_h,* ston_ht; #define STON_HT_HEADERSIZE (sizeof(struct ston_ht_header_t)) STON_FUNC @@ -79,7 +79,7 @@ uint32_t ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t); STON_FUNC size_t ston_ht32_insertx(ston_ht,uint32_t,uint32_t*,size_t,size_t); -#define ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create((struct ston_ht_header_t){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_FN)) +#define ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create((ston_ht_h){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_FN)) #define ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL) #define ston_ht_size(_HT) ((_HT)->ht_columns << (_HT)->ht_2pow) #define ston_ht_rows(_HT) (0x1 << (_HT)->ht_2pow) @@ -271,21 +271,22 @@ typedef struct ston_dht_header_t void* (*ht_alloc)(size_t); void (*ht_free)(void*); void** page_head; -}* ston_dht; +}ston_dht_h,* ston_dht; #define STON_DHT_HEADERSIZE (sizeof(struct ston_dht_header_t)) STON_FUNC -ston_dht ston_dht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t),void(*)(void*)); +ston_dht ston_dht32_create(struct ston_ht_header_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 -void ston_dht32_free(ston_dht); +size_t ston_dht32_insertx(ston_dht,uint32_t,uint32_t*,size_t,size_t); +STON_FUNC +ston_dht ston_dht32_free(ston_dht); -#define ston_dht32_new(_COL,_N,_F,_FN) ston_dht32_create(_COLS,ston_up2pow(_N << 1),_F,_FN) +#define ston_dht32_new(_COL,_N,_F,_ALLOC,_FREE) (ston_dht32_create((ston_ht_h){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_ALLOC,_FREE)) #define ston_dht32_entry(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL) -#define ston_dht32_insertx(_HT,_KEY,_COL,_VAL) *ston_dht32_col(_HT,_KEY,_COL) = _VAL #define ston_dht_size(_HT) (ston_ht_size(_HT)) #define ston_dht_rows(_HT) (ston_ht_rows(_HT)) #define ston_dht_cols(_HT) (ston_ht_cols(_HT)) @@ -306,24 +307,20 @@ void ston_dht32_free(ston_dht); */ STON_FUNC ston_dht ston_dht32_create -( uint16_t ht_columns, - size_t ht_rows, - uint8_t ht_flags, - void* (*ht_alloc)(size_t), - void (*ht_free)(void*) +( struct ston_ht_header_t ht_header, + void* (*ht_alloc)(size_t), + void (*ht_free)(void*) ) -{ size_t ht_size = ht_rows * ht_columns * sizeof(uint32_t); +{ size_t ht_bytes = ston_dht32_size(&ht_header); ston_dht ht = (ston_dht) ht_alloc(STON_DHT_SIZE); if (ht != NULL) - { for (ht->ht_2pow = 0; ht_size; ht->ht_2pow++) - ht_size = ht_size >> 1; - ht->ht_columns = ht_columns; - ht->ht_flags = ht_flags; + { memcpy(ht, &ht_header, sizeof(ht_header)); ht->ht_alloc = ht_alloc; ht->ht_free = ht_free; ht->page_head = ston_dht_pagestart(ht); - if ((*(ht->page_head) = ht->ht_alloc(ston_dht_size(ht))) == NULL) - ht_free(ht); + if ((*(ht->page_head) = ht->ht_alloc(ht_bytes)) == NULL) + if (ht_free != NULL) + ht_free(ht); } return ht; } @@ -370,7 +367,7 @@ uint32_t* ston_dht32_row page = (uint32_t**)ston_dht_pagestart(ht); goto next_row; } - if (row < row_end) + if (row + ht_cols < row_end) { row += ht_cols; goto next_row; } @@ -405,14 +402,39 @@ uint32_t ston_dht32_insert /* Free the dynamic hash table */ STON_FUNC -void ston_dht32_free +struct ston_dht_header_t* ston_dht32_free ( struct ston_dht_header_t* ht ) { void (*ht_free)(void*) = ht->ht_free; if (ht_free != NULL) { while (ht->page_head >= ston_dht_pagestart(ht)) - ht_free(ht->page_head--); + { ht_free(*(ht->page_head)); + ht->page_head--; + } ht_free(ht); + return NULL; } + return ht; +} + +/* Insert multiple values, returning the number of bytes written */ +STON_FUNC +size_t +ston_dht32_insertx +( struct ston_dht_header_t* ht, + uint32_t key, + uint32_t* data_src, + size_t start_column, + size_t units +) +{ uint32_t* data_row = ston_dht32_row(ht,key); + uint32_t* data_limit = data_row + ston_dht_cols(ht); + 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); } + #endif //_STON_HT_H_ -- 2.18.0