X-Git-Url: https://git.kengrimes.com/?p=henge%2Fapc.git;a=blobdiff_plain;f=ston%2Fston_ht.h;h=fb5d5669d4b6a5e65b7d026a1b2bdccb3a18754c;hp=a0bf05f680eb2169a168bcab6136f69f41443950;hb=16091722cd675ef3e48a56c22fc827eb5cde352e;hpb=8cae1f16c2a4294dddd26b21f03d594eca97ea8a diff --git a/ston/ston_ht.h b/ston/ston_ht.h index a0bf05f..fb5d566 100644 --- a/ston/ston_ht.h +++ b/ston/ston_ht.h @@ -45,39 +45,46 @@ #ifndef STON_FUNC #define STON_FUNC STON_FUNC_STATIC STON_FUNC_INLINE #endif //STON_FUNC -#ifndef STON_NOSTDIO +#ifdef STON_HT_FREAD #include -#include //memcpy +#include #include -#endif //STON_NOSTDIO +STON_FUNC_STATIC +STON_FUNC_NOINLINE +ston_ht ston_ht32_fread(FILE*,long,void*(*)(size_t)); +#else +#include +#endif //STON_HT_FREAD #include +#include //mem* /* STON Hashtable Structure Hashtables are stored as dynamically sized two dimensional arrays */ 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 -size_t ston_up2pow(size_t); -STON_FUNC_STATIC -STON_FUNC_NOINLINE -ston_ht ston_ht32_fread(FILE*,long,void*(*)(size_t)); +uint32_t ston_up2pow(uint32_t); +STON_FUNC +uint8_t ston_trailing0(uint32_t); STON_FUNC -ston_ht ston_ht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t)); +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(_COLS,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((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) #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)) @@ -85,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; @@ -96,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. @@ -107,30 +129,24 @@ 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; } -#ifndef STON_NO_STDIO +#ifdef STON_HT_FREAD /* Reads a 32-bit hash table out of the provided file at the provide fpos, into a buffer allocated by alloc_fn. Memory is allocated to the stack until the 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, @@ -190,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; @@ -217,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 @@ -231,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)) @@ -266,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; } @@ -330,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; } @@ -365,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_