2 \brief STON Hash Tables
3 \details Aligned general purpose hash functions and memory definitions
4 whose columns are provided, and whose rows, and sizes, are derived.
6 ht_size = header.ht_columns << header.ht_2pow;
7 ht_rows = 0x1 << header.ht_2pow;
9 All generic hashtables in henge must have a power-of-two number of
10 rows. An ht_columns value that is also a power-of-two will result in
11 a power-of-two sized memory imprint for the structure, making it easy
14 Elements in the columns may be of any arbitrary size.
16 typedef uint32_t my_ht_type;
17 ht_bytes = ht_size * sizeof(my_ht_type);
19 implementation covers only 32-bit unit sizes.
23 ----------------------------------------------------------------------------*/
26 /* Define STON_NOSTATIC to expose included function symbols */
28 #define STON_FUNC_STATIC static
30 #define STON_FUNC_STATIC
31 #endif //STON_NOSTATIC
32 /* If GNUC is detected, uses attributes to stop inlining */
34 #define STON_FUNC_NOINLINE __attribute__ ((noinline))
36 #define STON_FUNC_NOINLINE
38 /* Define STON_NOINLINE to prevent inline compiler hints */
40 #define STON_FUNC_INLINE inline
42 #define STON_FUNC_INLINE
43 #endif //STON_NOINLINE
44 /* Define STON_FUNC to override the default STON Function attributes */
46 #define STON_FUNC STON_FUNC_STATIC STON_FUNC_INLINE
54 ston_ht
ston_ht32_fread(FILE*,long,void*(*)(size_t));
57 size_t ston_ht32_fwrite(ston_ht
,FILE*,long);
60 #endif //STON_HT_FREAD
62 #include <string.h> //mem*
63 /* STON Hashtable Structure
64 Hashtables are stored as dynamically sized two dimensional arrays
66 typedef struct ston_ht_header_t
67 { uint16_t ht_columns
;
68 uint8_t ht_2pow
, ht_flags
;
72 uint32_t ston_up2pow(uint32_t);
74 uint8_t ston_trailing0(uint32_t);
76 ston_ht
ston_ht32_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t));
78 uint32_t* ston_ht32_row(ston_ht
,uint32_t);
80 uint32_t ston_ht32_insert(ston_ht
,uint32_t,uint16_t,uint32_t);
82 size_t ston_ht32_insertx(ston_ht
,uint32_t,uint32_t*,size_t,size_t);
84 #define ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create(_COL,ston_trailing0(ston_up2pow(_N << 1)),_F,_FN))
85 #define ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
86 #define ston_ht_size(_HT) ((_HT)->ht_columns << (_HT)->ht_2pow)
87 #define ston_ht_rows(_HT) (0x1 << (_HT)->ht_2pow)
88 #define ston_ht_cols(_HT) ((_HT)->ht_columns)
89 #define ston_ht_start(_HT) ((uint8_t*)((_HT) + 1))
90 #define ston_ht_keyrow(_HT,_KEY) ((_KEY) & (ston_ht_rows(ht) - 1))
91 #define ston_ht32_start(_HT) ((uint32_t*)ston_ht_start(_HT))
92 #define ston_ht32_end(_HT) (ston_ht32_start(_HT) + ston_ht_size(_HT))
93 #define ston_ht32_size(_HT) (ston_ht_size(_HT) * sizeof(uint32_t))
95 /** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
99 { val
= (val
<< 1) - 1;
108 /** @see https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel */
110 uint8_t ston_trailing0
115 if (v
& 0x0000FFFF) c
-= 16;
116 if (v
& 0x00FF00FF) c
-= 8;
117 if (v
& 0x0F0F0F0F) c
-= 4;
118 if (v
& 0x33333333) c
-= 2;
119 if (v
& 0x55555555) c
-= 1;
123 /* Creates a new hash table, provided a memory allocation function that takes a
124 single size_t bytes, a column count, and a row count which determines the
127 use ston_ht32_new to specify the exact or estimated number of unique keys
128 held in the table. With ston_ht32_new, the provided ht_rows is doubled, and
129 rounded up to the nearest power of two to create a hash table with minimal
133 ston_ht ston_ht32_create
134 ( uint16_t ht_columns
,
137 void* (*alloc_fn
)(size_t)
139 { size_t ht_bytes
= (ht_columns
<< ht_2pow
) * sizeof(uint32_t);
140 ston_ht ht
= (ston_ht
) alloc_fn(sizeof(ston_ht_h
) + ht_bytes
);
142 { ht
->ht_columns
= ht_columns
;
143 ht
->ht_2pow
= ht_2pow
;
144 ht
->ht_flags
= ht_flags
;
145 memset(ht
+ 1, 0, ht_bytes
);
151 /* Reads a 32-bit hash table out of the provided file at the provide fpos, into
152 a buffer allocated by alloc_fn. Memory is allocated to the stack until the
153 entire structure is verified, and all file operations are finished.
154 Returns NULL with properly set errno on failure.
158 ston_ht ston_ht32_fread
161 void* (*alloc_fn
)(size_t)
163 { struct ston_ht_header_t header
;
164 ston_ht stack_ht
, ht
;
166 size_t table_size
, alloc_size
;
168 if ((fpos_start
= ftell(file
)) == -1)
170 if (fread(&header
, sizeof(header
), 1, file
) != 1)
172 table_size
= ston_ht32_size(&header
);
173 alloc_size
= sizeof(header
) + table_size
;
174 stack_ht
= (ston_ht
) alloca(alloc_size
);
175 memcpy(stack_ht
, &header
, sizeof(header
));
176 if (fread(stack_ht
+ sizeof(header
), table_size
, 1, file
) != 1)
178 if (fseek(file
, fpos_start
, SEEK_SET
) != 0)
180 ht
= (ston_ht
) alloc_fn(alloc_size
);
182 memcpy(ht
, stack_ht
, alloc_size
);
185 /* Try to seek the file back to origin without clobbering errno */
187 fseek(file
, fpos_start
, SEEK_SET
);
192 /* Writes a 32-bit hash table from memory into a file at fpos. Returns the
193 number of bytes written to the file, errno is set on error. */
196 size_t ston_ht32_fwrite
197 ( struct ston_ht_header_t
* ht
,
201 { size_t bytes_written
;
203 if ((fpos_start
= ftell(file
)) == NULL
204 || fseek(file
, fpos
, SEEK_SET
) == 0
205 || (bytes_written
= fwrite(file
, 1, sizeof(ston_ht_h
), file
)) < sizeof(ston_ht_h
)
206 || (bytes_written
+= fwrite(file
, 1, ston_ht32_bytes(ht
), file
)) < (sizeof(ston_ht_h
) + ston_ht32_bytes(ht
))
207 || fseek(file
, fpos_start
, SEEK_SET
) == 0)
209 return bytes_written
;
213 /* Returns a pointer to the row of data in the hashtable containing the provided
214 key, inserts if not found. Returns NULL on overflow.
217 uint32_t* ston_ht32_row
218 ( struct ston_ht_header_t
* ht
,
222 uint32_t* row_start
= ston_ht32_start(ht
);
223 uint32_t* row_end
= ston_ht32_end(ht
);
224 uint16_t ht_cols
= ston_ht_cols(ht
);
225 size_t row_number
= ston_ht_keyrow(ht
,key
);
227 row
= row_start
+ (row_number
* ht_cols
);
237 if (row
+ ht_cols
< row_end
)
248 /* Inserts a value into a hashtable at the specified column, returning the
251 uint32_t ston_ht32_insert
252 ( struct ston_ht_header_t
* ht
,
257 { uint32_t* value_location
, old_value
;
258 value_location
= ston_ht32_entry(ht
,key
,column
);
259 old_value
= *value_location
;
260 *value_location
= value
;
264 /* Inserts a row of units into a hashtable, starting with the specified column.
265 Returns the number of elements that were written. This function will not
266 overflow internal buffers, but will return a short count (lower than the
267 provided 'units') when truncation of source data occurs. */
271 ( struct ston_ht_header_t
* ht
,
277 { uint32_t* data_row
= ston_ht32_row(ht
,key
);
278 uint32_t* data_limit
= data_row
+ ston_ht_cols(ht
);
279 uint32_t* data_trg
= data_row
+ start_column
;
280 if (data_row
== NULL
)
282 while (units
-- && data_trg
< data_limit
)
283 *data_trg
++ = *data_src
++;
284 return (size_t)(data_trg
- data_row
);
288 /* STON Dynamic Hashtable Structure
289 A dynamic form of the generic hashtable implementation above which uses
292 typedef struct ston_dht_header_t
293 { uint16_t val_bytes
;
298 typedef struct ston_dht_t
300 void* (*ht_alloc
)(size_t);
301 void (*ht_free
)(void*);
302 void (*ht_iter
)(void*,void*,void*);
305 size_t rowsize
, bucketsize
;
308 Primary functions for creating hashtables, retrieving pointers to values,
309 iterating over all keys and values, and destroying hashtables. */
311 ston_dht
ston_dht_new(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*));
313 void* ston_dht_val(ston_dht
,void*);
315 ston_dht
ston_dht_free(ston_dht
);
317 void ston_dht_iterate(ston_dht
,void(*)(void*,void*,void*),void*);
318 /* Recursive functions intended to be called by other functions, above */
321 void ston_dht_free_bucket(ston_dht
,void*);
324 void ston_dht_iterate_r(ston_dht
,void*);
325 // Compatibility macros - Deprecated
326 #define ston_dht32_new(_COL,_ALOC,_FRE) (ston_dht_new(4 * _COL, 4, _ALOC, _FRE))
327 #define ston_dht32_row(_HT,_K) ((uint32_t*)((uint8_t*)ston_dht_val(_HT,&(_K)) - 4))
328 #define ston_dht32_insertx(_HT,_K,_VP,_OFFS,_N) \
329 memcpy((uint32_t*)((uint8_t*)ston_dht_val(_HT,&(_K)) + ((_OFFS - 1) * 4)),_VP,_N * 4)
331 /* New dynamic hashtable, provided value bytes, key bytes, allocator function,
332 and free function. Value bytes and key bytes are respectively constrained to
333 uint16 and uint8 so they can be aligned to hashtables encoded for
336 ston_dht ston_dht_new
337 ( uint16_t val_bytes
,
339 void* (*ht_alloc
)(size_t),
340 void (*ht_free
)(void*)
342 { ston_dht ht
= (ston_dht
) ht_alloc(sizeof(struct ston_dht_t
));
344 { ht
->header
.val_bytes
= val_bytes
;
345 ht
->header
.key_bytes
= key_bytes
;
346 ht
->rowsize
= sizeof(void*) + key_bytes
+ val_bytes
;
347 ht
->bucketsize
= ht
->rowsize
* 0x100;
348 ht
->ht_alloc
= ht_alloc
;
349 ht
->ht_free
= ht_free
;
350 ht
->bucket_root
= ht_alloc(ht
->bucketsize
);
351 if (ht
->bucket_root
== NULL
&& ht_free
!= NULL
)
354 memset((ht
->bucket_root
), 0, ht
->bucketsize
);
360 /* Returns a pointer to the value in the hashtable matching the provided key,
361 inserting if not found, or NULL if a memory error occurs */
364 ( struct ston_dht_t
* ht
,
367 { size_t key_bytes
= ht
->header
.key_bytes
;
368 uint8_t* key_byte
= (uint8_t*)key
;
369 uint8_t* bucket
= (uint8_t*)ht
->bucket_root
;
371 uint8_t* row
,* a
,* b
;
375 row
= bucket
+ (ht
->rowsize
* (*key_byte
));
376 a
= row
+ sizeof(void*);
379 for (i
= 0; i
< key_bytes
; i
++)
380 { a_not_empty
|= a
[i
];
381 if (a_not_empty
&& a
[i
] != b
[i
])
385 memcpy(row
+ sizeof(void*),key
,key_bytes
);
389 bucketp
= (uint8_t**)row
;
390 if (*bucketp
== NULL
)
391 { if ((*bucketp
= ht
->ht_alloc(ht
->bucketsize
)) == NULL
)
394 memset(*bucketp
,0,ht
->bucketsize
);
399 return (void*) row
+ sizeof(void*) + key_bytes
;
402 /* Recursively frees all memory stored in the hashtable, and the hashtable
405 struct ston_dht_t
* ston_dht_free
406 ( struct ston_dht_t
* ht
)
407 { void (*ht_free
)(void*) = ht
->ht_free
;
410 ston_dht_free_bucket(ht
, ht
->bucket_root
);
415 /* Recursive free function for nested buckets */
418 void ston_dht_free_bucket
419 ( struct ston_dht_t
* ht
,
422 { void** bucket_cur
= (void**)((uint8_t*)bucket
);
423 void** bucket_max
= (void**)((uint8_t*)bucket_cur
+ (ht
->rowsize
* 0x100));
424 while (bucket_cur
< bucket_max
)
425 { if (*bucket_cur
!= NULL
)
426 ston_dht_free_bucket(ht
, *bucket_cur
);
427 bucket_cur
= (void**)((uint8_t*)bucket_cur
+ ht
->rowsize
);
432 /* Iterate over each key/value pair and execut 'fn' with key, value and
433 user_data as its arguments. user_data may be anything, even NULL, and is
434 expected to be referenced inside the body of 'fn' as the third argument of
437 void ston_dht_iterate
438 ( struct ston_dht_t
* ht
,
439 void (*fn
)(void*,void*,void*),
443 ht
->ht_user_data
= user_data
;
444 ston_dht_iterate_r(ht
,ht
->bucket_root
);
447 /* Recursively iterate through the given bucket belonging to hashtable ht */
450 void ston_dht_iterate_r
451 ( struct ston_dht_t
* ht
,
454 { uint8_t* row
= (uint8_t*)bucket
;
455 uint8_t* row_max
= (row
+ (ht
->rowsize
* 0x100));
456 while (row
< row_max
)
457 { if (*(void**)row
!= NULL
)
458 ston_dht_iterate_r(ht
, *(void**)row
);
459 row
+= sizeof(void*);
460 ht
->ht_iter((void*)row
, (void*)(row
+ ht
->header
.key_bytes
),ht
->ht_user_data
);
461 row
+= ht
->header
.key_bytes
+ ht
->header
.val_bytes
;