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
;
309 ston_dht
ston_dht_new(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*));
311 ston_dht
ston_dht_free(ston_dht
);
313 void* ston_dht_val(ston_dht
,void*);
316 void ston_dht_free_bucket(ston_dht
,void*);
318 void ston_dht_iterate(ston_dht
,void(*)(void*,void*,void*),void*);
321 void ston_dht_iterate_r(ston_dht
,void*);
323 // Compatibility macros
324 #define ston_dht32_new(_COL,_ALOC,_FRE) (ston_dht_new(4 * _COL, 4, _ALOC, _FRE))
325 #define ston_dht32_row(_HT,_K) ((uint32_t*)((uint8_t*)ston_dht_val(_HT,&(_K)) - 4))
326 #define ston_dht32_insertx(_HT,_K,_VP,_OFFS,_N) \
327 memcpy((uint32_t*)((uint8_t*)ston_dht_val(_HT,&(_K)) + ((_OFFS - 1) * 4)),_VP,_N * 4)
329 /* Creates a new bucketted hash table, provided a memory allocation function
330 that takes a single size_t bytes, a memory free function, a column count, and
331 a row count which determines the size of the buckets.
334 ston_dht ston_dht_new
335 ( uint16_t val_bytes
,
337 void* (*ht_alloc
)(size_t),
338 void (*ht_free
)(void*)
340 { ston_dht ht
= (ston_dht
) ht_alloc(sizeof(struct ston_dht_t
));
342 { ht
->header
.val_bytes
= val_bytes
;
343 ht
->header
.key_bytes
= key_bytes
;
344 ht
->rowsize
= sizeof(void*) + key_bytes
+ val_bytes
;
345 ht
->bucketsize
= ht
->rowsize
* 0x100;
346 ht
->ht_alloc
= ht_alloc
;
347 ht
->ht_free
= ht_free
;
348 ht
->bucket_root
= ht_alloc(ht
->bucketsize
);
349 if (ht
->bucket_root
== NULL
&& ht_free
!= NULL
)
352 memset((ht
->bucket_root
), 0, ht
->bucketsize
);
358 /* Returns a pointer to the value in the hashtable matching the provided key,
359 inserting if not found, or NULL if a memory error occurs */
362 ( struct ston_dht_t
* ht
,
365 { size_t key_bytes
= ht
->header
.key_bytes
;
366 uint8_t* key_byte
= (uint8_t*)key
;
367 uint8_t* bucket
= (uint8_t*)ht
->bucket_root
;
369 uint8_t* row
,* a
,* b
;
373 row
= bucket
+ (ht
->rowsize
* (*key_byte
));
374 a
= row
+ sizeof(void*);
377 for (i
= 0; i
< key_bytes
; i
++)
378 { a_not_empty
|= a
[i
];
379 if (a_not_empty
&& a
[i
] != b
[i
])
383 memcpy(row
+ sizeof(void*),key
,key_bytes
);
387 bucketp
= (uint8_t**)row
;
388 if (*bucketp
== NULL
)
389 { if ((*bucketp
= ht
->ht_alloc(ht
->bucketsize
)) == NULL
)
392 memset(*bucketp
,0,ht
->bucketsize
);
397 return (void*) row
+ sizeof(void*) + key_bytes
;
400 /* Free the dynamic hash table */
402 struct ston_dht_t
* ston_dht_free
403 ( struct ston_dht_t
* ht
)
404 { void (*ht_free
)(void*) = ht
->ht_free
;
407 ston_dht_free_bucket(ht
, ht
->bucket_root
);
412 /* Recursively free pages by lookup */
415 void ston_dht_free_bucket
416 ( struct ston_dht_t
* ht
,
419 { void** bucket_cur
= (void**)((uint8_t*)bucket
);
420 void** bucket_max
= (void**)((uint8_t*)bucket_cur
+ (ht
->rowsize
* 0x100));
421 while (bucket_cur
< bucket_max
)
422 { if (*bucket_cur
!= NULL
)
423 ston_dht_free_bucket(ht
, *bucket_cur
);
424 bucket_cur
= (void**)((uint8_t*)bucket_cur
+ ht
->rowsize
);
429 /* Iterate over each key/value pair and execut 'fn' with key and value as
432 void ston_dht_iterate
433 ( struct ston_dht_t
* ht
,
434 void (*fn
)(void*,void*,void*),
438 ht
->ht_user_data
= user_data
;
439 ston_dht_iterate_r(ht
,(void**)ht
->bucket_root
);
442 /* Recursively iterate through the given bucket belonging to hashtable ht */
445 void ston_dht_iterate_r
446 ( struct ston_dht_t
* ht
,
449 { uint8_t* row
= (uint8_t*)bucket
;
450 uint8_t* row_max
= (row
+ (ht
->rowsize
* 0x100));
451 while (row
< row_max
)
452 { if (*(void**)row
!= NULL
)
453 ston_dht_iterate_r(ht
, *(void**)row
);
454 row
+= sizeof(void*);
455 ht
->ht_iter((void*)row
, (void*)(row
+ ht
->header
.key_bytes
),ht
->ht_user_data
);
456 row
+= ht
->header
.key_bytes
+ ht
->header
.val_bytes
;