From 30e125e6bcfa71297ef4d592b0c80346f5688a1d Mon Sep 17 00:00:00 2001 From: ken Date: Wed, 1 Mar 2017 12:29:41 -0800 Subject: [PATCH] non-dynamic hashtables finished testing --- src/testston.c | 111 +++++++++++++++++++++++++++++++++++++++++++++---- ston/ston_ht.h | 81 ++++++++++++++++++++++++++---------- 2 files changed, 161 insertions(+), 31 deletions(-) diff --git a/src/testston.c b/src/testston.c index 71c0110..32910b0 100644 --- a/src/testston.c +++ b/src/testston.c @@ -1,16 +1,109 @@ -#include "../ston/ston.h" #include //malloc #include //print +#include //memcpy +#include "../ston/ston.h" + +/* ansi terminal colors */ +#define RED "\x1b[31m" +#define GREEN "\x1b[32m" +#define YELLOW "\x1b[33m" +#define BLUE "\x1b[34m" +#define MAGENTA "\x1b[35m" +#define CYAN "\x1b[36m" +#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)); \ + int main(int argc, char* argv[]) -{ ston_ht ht; - uint32_t* htval; - - if ((ht = ston_ht32_new(2,1,0,malloc)) == NULL) - fprintf(stderr,"Could not allocate ht32\n"); - ston_ht32_insertx(ht,50,1,200); - htval = ston_ht32_entry(ht,50,1); - printf("[50][1] = %i\n",*htval); +{ static ston_ht ht; + uint32_t* htval, previous_val; + uint32_t val[255], key; + size_t idx; + size_t i; + size_t elements; + uint16_t columns; + + printf("up2pow [5] = [%i]\n",ston_up2pow(5)); + for (i = 0; i < 255; 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 entries\n"); + 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; + for(key = 0xCEED; elements--; key *= 7) + { htval = ston_ht32_row(ht,key); + printf("[%s%x"CLRC"]",(*htval == key) ? GREEN : RED,*htval); + for(i = 1; i < columns; i++) + printf("[%s%x"CLRC"]",(htval[i] == (uint32_t)(i * key)) ? GREEN : RED,htval[i]); + putchar('\n'); + } + int max_capacity = ston_up2pow(20 << 1) - 20; + printf("Overfilling hashtable with %i entries\n", max_capacity); + int 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\n"); + cap = max_capacity; + for(key = 0xCEED2; cap--; key *= 13) + { htval = ston_ht32_row(ht,key); + printf("[%s%x"CLRC"]",(*htval == key) ? GREEN : RED,*htval); + for(i = 1; i < columns; i++) + printf("[%s%x"CLRC"]",(htval[i] == (uint32_t)(key * -i)) ? GREEN : RED,htval[i]); + printf("\n"); + } + free(ht); return 0; } diff --git a/ston/ston_ht.h b/ston/ston_ht.h index 11454b3..b17e18e 100644 --- a/ston/ston_ht.h +++ b/ston/ston_ht.h @@ -47,7 +47,6 @@ #endif //STON_FUNC #ifdef STON_HT_FREAD #include -#include //memcpy #include #include STON_FUNC_STATIC @@ -57,6 +56,7 @@ ston_ht ston_ht32_fread(FILE*,long,void*(*)(size_t)); #include #endif //STON_HT_FREAD #include +#include //mem* /* STON Hashtable Structure Hashtables are stored as dynamically sized two dimensional arrays */ @@ -64,23 +64,27 @@ typedef struct ston_ht_header_t { uint16_t ht_columns; uint8_t ht_2pow, ht_flags; }* ston_ht; +#define STON_HT_HEADERSIZE (sizeof(struct ston_ht_header_t)) STON_FUNC -size_t ston_up2pow(size_t); +uint32_t ston_up2pow(uint32_t); STON_FUNC -ston_ht ston_ht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t)); +uint8_t ston_trailing0(uint32_t); +STON_FUNC +ston_ht ston_ht32_create(struct ston_ht_header_t,void*(*)(size_t)); STON_FUNC uint32_t* ston_ht32_row(ston_ht,uint32_t); STON_FUNC 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(_COL,ston_up2pow(_N << 1),_F,_FN) -#define ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL) -#define ston_ht32_insertx(_HT,_KEY,_COL,_VAL) *ston_ht32_entry(_HT,_KEY,_COL) = _VAL +#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_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) #define ston_ht_cols(_HT) ((_HT)->ht_columns) -#define ston_ht_start(_HT) (((uint8_t*)(_HT)) + sizeof(*(_HT))) +#define ston_ht_start(_HT) ((uint8_t*)((_HT) + 1)) #define ston_ht_keyrow(_HT,_KEY) ((_KEY) & (ston_ht_rows(ht) - 1)) #define ston_ht32_start(_HT) ((uint32_t*)ston_ht_start(_HT)) #define ston_ht32_end(_HT) (ston_ht32_start(_HT) + ston_ht_size(_HT)) @@ -88,8 +92,8 @@ uint32_t ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t); /** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */ STON_FUNC -size_t ston_up2pow -( size_t val ) +uint32_t ston_up2pow +( uint32_t val ) { val = (val << 1) - 1; val |= val >> 1; val |= val >> 2; @@ -99,6 +103,21 @@ size_t ston_up2pow return ++val; } +/** @see https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel */ +STON_FUNC +uint8_t ston_trailing0 +( uint32_t v ) +{ uint8_t c = 32; + v &= -(int32_t)v; + if (v) c--; + if (v & 0x0000FFFF) c -= 16; + if (v & 0x00FF00FF) c -= 8; + if (v & 0x0F0F0F0F) c -= 4; + if (v & 0x33333333) c -= 2; + if (v & 0x55555555) c -= 1; + return c; +} + /* Creates a new hash table, provided a memory allocation function that takes a single size_t bytes, a column count, and a row count which determines the size of the table. @@ -110,18 +129,14 @@ size_t ston_up2pow */ STON_FUNC ston_ht ston_ht32_create -( uint16_t ht_columns, - size_t ht_rows, - uint8_t ht_flags, - void* (*alloc_fn)(size_t) +( struct ston_ht_header_t ht_header, + void* (*alloc_fn)(size_t) ) -{ size_t ht_size = ht_rows * ht_columns * sizeof(uint32_t); - ston_ht ht = (ston_ht) alloc_fn(sizeof(struct ston_ht_header_t) + ht_size); +{ size_t ht_bytes = ston_ht32_size(&ht_header); + ston_ht ht = (ston_ht) alloc_fn(STON_HT_HEADERSIZE + ht_bytes); 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,STON_HT_HEADERSIZE); + memset(ht + 1, 0, ht_bytes); } return ht; } @@ -132,8 +147,6 @@ 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, @@ -193,7 +206,7 @@ uint32_t* ston_ht32_row populated: if (row[0] == key) goto write_position; - if (row < row_end) + if (row + ht_cols < row_end) row += ht_cols; else if (looped) return NULL; @@ -220,6 +233,30 @@ uint32_t ston_ht32_insert return old_value; } +/* Inserts a row of units into a hashtable, starting with the specified column. + Returns the number of elements that were written. This function will not + overflow internal buffers, but will return a short count (lower than the + provided 'units') when truncation of source data occurs. */ +STON_FUNC +size_t +ston_ht32_insertx +( struct ston_ht_header_t* ht, + uint32_t key, + uint32_t* data_src, + size_t start_column, + size_t units +) +{ uint32_t* data_row = ston_ht32_row(ht,key); + uint32_t* data_limit = data_row + ston_ht_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); +} + + #ifndef STON_DHT_SIZE #define STON_DHT_SIZE 4096 #endif -- 2.18.0