X-Git-Url: https://www.kengrimes.com/gitweb/?p=henge%2Fapc.git;a=blobdiff_plain;f=ston%2Fston_ht.h;h=6ab03e704a0d58f0f6e86626e56622534533c2a7;hp=50634316aa88adf5ea8945d0c53d4f25eafe2395;hb=HEAD;hpb=6f8c57f8040bf31ebad01119365b416a12c94341 diff --git a/ston/ston_ht.h b/ston/ston_ht.h index 5063431..6ab03e7 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, @@ -195,8 +201,10 @@ size_t ston_ht32_fwrite { size_t bytes_written; long fpos_start; if ((fpos_start = ftell(file)) == NULL + || fseek(file, fpos, SEEK_SET) == 0 || (bytes_written = fwrite(file, 1, sizeof(ston_ht_h), file)) < sizeof(ston_ht_h) - || (bytes_written += fwrite(file, 1, ston_ht32_bytes(ht), file)) < (sizeof(ston_ht_h) + ston_ht32_bytes(ht))) + || (bytes_written += fwrite(file, 1, ston_ht32_bytes(ht), file)) < (sizeof(ston_ht_h) + ston_ht32_bytes(ht)) + || fseek(file, fpos_start, SEEK_SET) == 0) return 0; return bytes_written; } @@ -277,357 +285,181 @@ 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; +{ uint16_t val_bytes; + uint8_t key_bytes; + uint8_t flags; }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*); + void (*ht_iter)(void*,void*,void*); + void* ht_user_data; + void* bucket_root; + size_t rowsize, bucketsize; }* ston_dht; - +/* STON DHT API + Primary functions for creating hashtables, retrieving pointers to values, + iterating over all keys and values, and destroying hashtables. */ STON_FUNC -ston_dht ston_dht_create(uint16_t,uint8_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_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); +void* ston_dht_val(ston_dht,void*); 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 ston_dht_iterate(ston_dht,void(*)(void*,void*,void*),void*); +/* Recursive functions intended to be called by other functions, above */ +STON_FUNC_STATIC +STON_FUNC_NOINLINE +void ston_dht_free_bucket(ston_dht,void*); +STON_FUNC_STATIC +STON_FUNC_NOINLINE +void ston_dht_iterate_r(ston_dht,void*); +// Compatibility macros - Deprecated +#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_val(_HT,&(_K)) - 4)) +#define ston_dht32_insertx(_HT,_K,_VP,_OFFS,_N) \ + memcpy((uint32_t*)((uint8_t*)ston_dht_val(_HT,&(_K)) + ((_OFFS - 1) * 4)),_VP,_N * 4) + +/* New dynamic hashtable, provided value bytes, key bytes, allocator function, + and free function. Value bytes and key bytes are respectively constrained to + uint16 and uint8 so they can be aligned to hashtables encoded for + streaming */ +STON_FUNC +ston_dht ston_dht_new +( uint16_t val_bytes, + uint8_t key_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->header.val_bytes = val_bytes; + ht->header.key_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; - if (ht->pages[start_depth] == 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->pages[start_depth], 0, ston_dht_bytes(ht, start_depth)); + memset((ht->bucket_root), 0, ht->bucketsize); } 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. -*/ + +/* Returns a pointer to the value in the hashtable matching the provided key, + inserting if not found, or NULL if a memory error occurs */ STON_FUNC -uint32_t* ston_dht32_row +void* ston_dht_val ( struct ston_dht_t* ht, - uint32_t key + void* 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)); +{ 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; } - 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; + if (!a_not_empty) + memcpy(row + sizeof(void*),key,key_bytes); + goto done; + next_bucket: + 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); } - 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); + bucket = *bucketp; + goto next_row; + done: + return (void*) row + sizeof(void*) + key_bytes; } -/* Free the dynamic hash table */ +/* Recursively frees all memory stored in the hashtable, and the hashtable + itself */ 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; - -#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; - void* (*ht_alloc)(size_t); - void (*ht_free)(void*); -}* ston_dht2; - -STON_FUNC -ston_dht2 ston_dht2_create(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_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) - - -/* 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 -( 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)); - if (ht != NULL) - { ht->header.val_bytes = val_bytes; - ht->header.key_bytes = key_bytes; - ht->row_bytes = val_bytes + key_bytes; - 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_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; - } - } + if (ht_free == NULL) + return NULL; + ston_dht_free_bucket(ht, ht->bucket_root); + ht_free(ht); return ht; } - -/* 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 +/* Recursive free function for nested buckets */ +STON_FUNC_STATIC +STON_FUNC_NOINLINE +void ston_dht_free_bucket +( struct ston_dht_t* ht, + void* bucket ) -{ 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; - 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; +{ void** bucket_cur = (void**)((uint8_t*)bucket); + void** bucket_max = (void**)((uint8_t*)bucket_cur + (ht->rowsize * 0x100)); + while (bucket_cur < bucket_max) + { if (*bucket_cur != NULL) + ston_dht_free_bucket(ht, *bucket_cur); + bucket_cur = (void**)((uint8_t*)bucket_cur + ht->rowsize); } - /* 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; + ht->ht_free(bucket); } -/* Inserts a value into a hashtable at the specified column, returning the - previous value */ +/* Iterate over each key/value pair and execut 'fn' with key, value and + user_data as its arguments. user_data may be anything, even NULL, and is + expected to be referenced inside the body of 'fn' as the third argument of + 'fn' */ STON_FUNC -uint32_t ston_dht232_insert -( struct ston_dht2_t* ht, - uint32_t key, - uint16_t column, - uint32_t value +void ston_dht_iterate +( struct ston_dht_t* ht, + void (*fn)(void*,void*,void*), + void* user_data ) -{ uint32_t* value_location, old_value; - value_location = ston_dht232_entry(ht,key,column); - old_value = *value_location; - *value_location = value; - return old_value; +{ ht->ht_iter = fn; + ht->ht_user_data = user_data; + ston_dht_iterate_r(ht,ht->bucket_root); } -/* 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 iterate through the given bucket belonging to hashtable ht */ +STON_FUNC_STATIC +STON_FUNC_NOINLINE +void ston_dht_iterate_r +( 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; +{ uint8_t* row = (uint8_t*)bucket; + uint8_t* row_max = (row + (ht->rowsize * 0x100)); + while (row < row_max) + { if (*(void**)row != NULL) + ston_dht_iterate_r(ht, *(void**)row); + row += sizeof(void*); + ht->ht_iter((void*)row, (void*)(row + ht->header.key_bytes),ht->ht_user_data); + row += ht->header.key_bytes + ht->header.val_bytes; } - return ht; } - #endif //_STON_HT_H_