From: ken Date: Sat, 25 Feb 2017 21:33:53 +0000 (-0800) Subject: dynamic hashtables added X-Git-Url: https://git.kengrimes.com/?p=henge%2Fapc.git;a=commitdiff_plain;h=8cae1f16c2a4294dddd26b21f03d594eca97ea8a dynamic hashtables added --- diff --git a/ston/ston_ht.h b/ston/ston_ht.h index ef7a363..a0bf05f 100644 --- a/ston/ston_ht.h +++ b/ston/ston_ht.h @@ -72,14 +72,15 @@ STON_FUNC uint32_t ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t); #define ston_ht32_new(_COL,_N,_F,_FN) ston_ht32_create(_COLS,ston_up2pow(_N << 1),_F,_FN) -#define ston_ht32_col(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL) -#define ston_ht32_insertx(_HT,_KEY,_COL,_VAL) *ston_ht32_col(_HT,_KEY,_COL) = _VAL +#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_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_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)) #define ston_ht32_size(_HT) (ston_ht_size(_HT) * sizeof(uint32_t)) /** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */ @@ -139,40 +140,48 @@ ston_ht ston_ht32_fread ston_ht stack_ht, ht; long fpos_start; size_t table_size, alloc_size; + int errno_local; if ((fpos_start = ftell(file)) == -1) return NULL; if (fread(&header, sizeof(header), 1, file) != 1) - return NULL; + goto fail_seekback; table_size = ston_ht32_size(&header); alloc_size = sizeof(header) + table_size; stack_ht = (ston_ht) alloca(alloc_size); memcpy(stack_ht, &header, sizeof(header)); if (fread(stack_ht + sizeof(header), table_size, 1, file) != 1) - return NULL; + goto fail_seekback; if (fseek(file, fpos_start, SEEK_SET) != 0) return NULL; ht = (ston_ht) alloc_fn(alloc_size); if (ht != NULL) memcpy(ht, stack_ht, alloc_size); return ht; + fail_seekback: + /* Try to seek the file back to origin without clobbering errno */ + errno_local = errno; + fseek(file, fpos_start, SEEK_SET); + errno = errno_local; + return NULL; } #endif /* 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_STATIC +STON_FUNC uint32_t* ston_ht32_row ( struct ston_ht_header_t* ht, uint32_t key ) -{ uint32_t* row,* row_start = ston_ht32_start(ht); +{ uint32_t* row; + uint32_t* row_start = ston_ht32_start(ht); + uint32_t* row_end = ston_ht32_end(ht); uint16_t ht_cols = ston_ht_cols(ht); size_t row_number = ston_ht_keyrow(ht,key); - size_t row_max = ston_ht_rows(ht); uint8_t looped = 0; - next_row: row = row_start + (row_number * ht_cols); + next_row: if (row[0] != 0) goto populated; write_position: @@ -181,13 +190,13 @@ uint32_t* ston_ht32_row populated: if (row[0] == key) goto write_position; - if (row_number < row_max) - row_number++; + if (row < row_end) + row += ht_cols; else if (looped) return NULL; else { looped++; - row_number = 0; + row = row_start; } goto next_row; } @@ -202,34 +211,168 @@ uint32_t ston_ht32_insert uint32_t value ) { uint32_t* value_location, old_value; - value_location = ston_ht32_col(ht,key,column); + value_location = ston_ht32_entry(ht,key,column); old_value = *value_location; *value_location = value; return old_value; } +#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 ht_columns; - uint8_t ht_2pow, ht_flags; - void (*ht_alloc)(size_t); - void* ht_pages[]; +{ uint16_t ht_columns; + uint8_t ht_2pow, ht_flags; + void* (*ht_alloc)(size_t); + void (*ht_free)(void*); + void** page_head; }* ston_dht; +#define STON_DHT_HEADERSIZE (sizeof(struct ston_dht_header_t)) -#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)) -#define ston_dht_keyrow(_HT,_KEY) (ston_ht_keyrow(_HT,_KEY)) -#define ston_dht_start(_HT) (_HT->ht_pages[0]) -#define ston_dht32_start(_HT) ((_uint32*)ston_dht_start(_HT)) -ston_dht ston_dht32_create(uint16_t,size_t,void*(*)(size_t)); +STON_FUNC +ston_dht ston_dht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t),void(*)(void*)); +STON_FUNC uint32_t* ston_dht32_row(ston_dht,uint32_t); -#define ston_dht32_col(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL) +STON_FUNC uint32_t ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t); +STON_FUNC +void 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_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)) +#define ston_dht_keyrow(_HT,_KEY) (ston_ht_keyrow(_HT,_KEY)) +#define ston_dht_pagestart(_HT) ((void**)(((uint8_t*)(_HT)) + STON_DHT_HEADERSIZE)) +#define ston_dht_pagehead(_HT) ((_HT)->page_head) +#define ston_dht_pagemax(_HT) ((void**)((uint8_t*)(_HT) + STON_DHT_SIZE - sizeof(void**))) +#define ston_dht_start(_HT,_DEPTH) ((uint8_t*)*(ston_dht_pagestart(_HT) + _DEPTH)) +#define ston_dht32_start(_HT,_DEPTH) ((uint32_t*)ston_dht_start(_HT,_DEPTH)) +#define ston_dht32_end(_HT,_DEPTH) (ston_ht32_start(_HT,_DEPTH) + ston_ht_size(_HT)) +#define ston_dht32_size(_HT) (ston_dht_size(_HT) * sizeof(uint32_t)) +#define ston_dht32_pagepush(_HT) ((*(++((_HT)->page_head)) = (_HT)->ht_alloc(ston_dht32_size(_HT)))) +#define ston_dht32_pagepop(_HT) ((_HT)->ht_free((_HT)->page_head--)) + +/* 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_dht32_create +( uint16_t ht_columns, + size_t ht_rows, + uint8_t ht_flags, + void* (*ht_alloc)(size_t), + void (*ht_free)(void*) +) +{ size_t ht_size = ht_rows * ht_columns * sizeof(uint32_t); + 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; + 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); + } + 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_header_t* ht, + uint32_t key +) +{ uint16_t ht_cols = ston_dht_cols(ht); + size_t row_number = ston_dht_keyrow(ht,key); + uint32_t** page = (uint32_t**)ston_dht_pagestart(ht); + uint32_t** pagemax = (uint32_t**)ston_dht_pagemax(ht); + uint8_t loop_x = 0; + uint8_t loop_y = 0; + uint32_t* row,* row_end; + next_page: + row = *page + (row_number * ht_cols); + row_end = *page + (ston_dht_size(ht) - 1); + next_row: + if (row[0] != 0) + goto populated; + write_position: + row[0] = key; + return row; + populated: + if (row[0] == key) + goto write_position; + if (!loop_x) + { if (page < pagemax) + { if (page == (uint32_t**)ston_dht_pagehead(ht)) + if (ston_dht32_pagepush(ht) == NULL) + { ston_dht32_free(ht); + return NULL; + } + ++page; + goto next_row; + } + loop_x = 1; + row_number = (row_number + 1) % ston_dht_rows(ht); + page = (uint32_t**)ston_dht_pagestart(ht); + goto next_row; + } + if (row < row_end) + { row += ht_cols; + goto next_row; + } + else if (!loop_y) + { loop_y = 1; + row = *page; + goto next_row; + } + if (page < pagemax) + { loop_y = 0; + page++; + goto next_page; + } + return NULL; +} + +/* Inserts a value into a hashtable at the specified column, returning the + previous value */ +STON_FUNC +uint32_t ston_dht32_insert +( struct ston_dht_header_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; +} + +/* Free the dynamic hash table */ +STON_FUNC +void 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); + } +} #endif //_STON_HT_H_