X-Git-Url: https://www.kengrimes.com/gitweb/?p=henge%2Fapc.git;a=blobdiff_plain;f=ston%2Fston_ht.h;h=6ab03e704a0d58f0f6e86626e56622534533c2a7;hp=e97a589f3cc8eb7c8b8a9eac48c522f34a51fd03;hb=HEAD;hpb=20b718e416aaa44d1faa31b6370263affa4dc1df diff --git a/ston/ston_ht.h b/ston/ston_ht.h index e97a589..6ab03e7 100644 --- a/ston/ston_ht.h +++ b/ston/ston_ht.h @@ -52,6 +52,9 @@ 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 #endif //STON_HT_FREAD @@ -150,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, @@ -183,6 +188,26 @@ ston_ht ston_ht32_fread errno = errno_local; return NULL; } + +/* 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, + long fpos +) +{ 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)) + || fseek(file, fpos_start, SEEK_SET) == 0) + return 0; + return bytes_written; +} #endif /* Returns a pointer to the row of data in the hashtable containing the provided @@ -260,160 +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_FUNC -ston_dht ston_dht_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t),void(*)(void*)); +/* STON DHT API + Primary functions for creating hashtables, retrieving pointers to values, + iterating over all keys and values, and destroying hashtables. */ STON_FUNC -uint32_t* ston_dht32_row(ston_dht,uint32_t); +ston_dht ston_dht_new(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*)); 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); +STON_FUNC +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) -#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. -*/ +/* 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_create -( uint16_t columns, - uint8_t start_depth, - uint8_t unit_bytes, +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; + bucket = *bucketp; + goto next_row; + done: + return (void*) row + sizeof(void*) + key_bytes; } -/* Inserts a value into a hashtable at the specified column, returning the - previous value */ +/* Recursively frees all memory stored in the hashtable, and the hashtable + itself */ STON_FUNC -uint32_t ston_dht32_insert +struct ston_dht_t* ston_dht_free +( struct ston_dht_t* ht ) +{ void (*ht_free)(void*) = ht->ht_free; + if (ht_free == NULL) + return NULL; + ston_dht_free_bucket(ht, ht->bucket_root); + ht_free(ht); + return ht; +} + +/* Recursive free function for nested buckets */ +STON_FUNC_STATIC +STON_FUNC_NOINLINE +void ston_dht_free_bucket ( struct ston_dht_t* ht, - uint32_t key, - uint16_t column, - uint32_t value + void* bucket ) -{ uint32_t* value_location, old_value; - value_location = ston_dht32_entry(ht,key,column); - old_value = *value_location; - *value_location = value; - return old_value; +{ 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); + } + ht->ht_free(bucket); } -/* Insert multiple values, returning the number of bytes written */ +/* 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 -size_t -ston_dht32_insertx +void ston_dht_iterate ( struct ston_dht_t* ht, - uint32_t key, - uint32_t* data_src, - uint16_t start_column, - size_t units + void (*fn)(void*,void*,void*), + void* user_data ) -{ 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); +{ ht->ht_iter = fn; + ht->ht_user_data = user_data; + ston_dht_iterate_r(ht,ht->bucket_root); } -/* Free the dynamic hash table */ -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; +/* 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 +) +{ 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_