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 #endif //STON_HT_FREAD
59 #include <string.h> //mem*
60 /* STON Hashtable Structure
61 Hashtables are stored as dynamically sized two dimensional arrays
63 typedef struct ston_ht_header_t
64 { uint16_t ht_columns
;
65 uint8_t ht_2pow
, ht_flags
;
67 #define STON_HT_HEADERSIZE (sizeof(struct ston_ht_header_t))
70 uint32_t ston_up2pow(uint32_t);
72 uint8_t ston_trailing0(uint32_t);
74 ston_ht
ston_ht32_create(struct ston_ht_header_t
,void*(*)(size_t));
76 uint32_t* ston_ht32_row(ston_ht
,uint32_t);
78 uint32_t ston_ht32_insert(ston_ht
,uint32_t,uint16_t,uint32_t);
80 size_t ston_ht32_insertx(ston_ht
,uint32_t,uint32_t*,size_t,size_t);
82 #define ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create((struct ston_ht_header_t){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_FN))
83 #define ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
84 #define ston_ht_size(_HT) ((_HT)->ht_columns << (_HT)->ht_2pow)
85 #define ston_ht_rows(_HT) (0x1 << (_HT)->ht_2pow)
86 #define ston_ht_cols(_HT) ((_HT)->ht_columns)
87 #define ston_ht_start(_HT) ((uint8_t*)((_HT) + 1))
88 #define ston_ht_keyrow(_HT,_KEY) ((_KEY) & (ston_ht_rows(ht) - 1))
89 #define ston_ht32_start(_HT) ((uint32_t*)ston_ht_start(_HT))
90 #define ston_ht32_end(_HT) (ston_ht32_start(_HT) + ston_ht_size(_HT))
91 #define ston_ht32_size(_HT) (ston_ht_size(_HT) * sizeof(uint32_t))
93 /** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
97 { val
= (val
<< 1) - 1;
106 /** @see https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel */
108 uint8_t ston_trailing0
113 if (v
& 0x0000FFFF) c
-= 16;
114 if (v
& 0x00FF00FF) c
-= 8;
115 if (v
& 0x0F0F0F0F) c
-= 4;
116 if (v
& 0x33333333) c
-= 2;
117 if (v
& 0x55555555) c
-= 1;
121 /* Creates a new hash table, provided a memory allocation function that takes a
122 single size_t bytes, a column count, and a row count which determines the
125 use ston_ht32_new to specify the exact or estimated number of unique keys
126 held in the table. With ston_ht32_new, the provided ht_rows is doubled, and
127 rounded up to the nearest power of two to create a hash table with minimal
131 ston_ht ston_ht32_create
132 ( struct ston_ht_header_t ht_header
,
133 void* (*alloc_fn
)(size_t)
135 { size_t ht_bytes
= ston_ht32_size(&ht_header
);
136 ston_ht ht
= (ston_ht
) alloc_fn(STON_HT_HEADERSIZE
+ ht_bytes
);
138 { memcpy(ht
,&ht_header
,STON_HT_HEADERSIZE
);
139 memset(ht
+ 1, 0, ht_bytes
);
145 /* Reads a 32-bit hash table out of the provided file at the provide fpos, into
146 a buffer allocated by alloc_fn. Memory is allocated to the stack until the
147 entire structure is verified, and all file operations are finished.
148 Returns NULL with properly set errno on failure.
150 ston_ht ston_ht32_fread
153 void* (*alloc_fn
)(size_t)
155 { struct ston_ht_header_t header
;
156 ston_ht stack_ht
, ht
;
158 size_t table_size
, alloc_size
;
160 if ((fpos_start
= ftell(file
)) == -1)
162 if (fread(&header
, sizeof(header
), 1, file
) != 1)
164 table_size
= ston_ht32_size(&header
);
165 alloc_size
= sizeof(header
) + table_size
;
166 stack_ht
= (ston_ht
) alloca(alloc_size
);
167 memcpy(stack_ht
, &header
, sizeof(header
));
168 if (fread(stack_ht
+ sizeof(header
), table_size
, 1, file
) != 1)
170 if (fseek(file
, fpos_start
, SEEK_SET
) != 0)
172 ht
= (ston_ht
) alloc_fn(alloc_size
);
174 memcpy(ht
, stack_ht
, alloc_size
);
177 /* Try to seek the file back to origin without clobbering errno */
179 fseek(file
, fpos_start
, SEEK_SET
);
185 /* Returns a pointer to the row of data in the hashtable containing the provided
186 key, inserts if not found. Returns NULL on overflow.
189 uint32_t* ston_ht32_row
190 ( struct ston_ht_header_t
* ht
,
194 uint32_t* row_start
= ston_ht32_start(ht
);
195 uint32_t* row_end
= ston_ht32_end(ht
);
196 uint16_t ht_cols
= ston_ht_cols(ht
);
197 size_t row_number
= ston_ht_keyrow(ht
,key
);
199 row
= row_start
+ (row_number
* ht_cols
);
209 if (row
+ ht_cols
< row_end
)
220 /* Inserts a value into a hashtable at the specified column, returning the
223 uint32_t ston_ht32_insert
224 ( struct ston_ht_header_t
* ht
,
229 { uint32_t* value_location
, old_value
;
230 value_location
= ston_ht32_entry(ht
,key
,column
);
231 old_value
= *value_location
;
232 *value_location
= value
;
236 /* Inserts a row of units into a hashtable, starting with the specified column.
237 Returns the number of elements that were written. This function will not
238 overflow internal buffers, but will return a short count (lower than the
239 provided 'units') when truncation of source data occurs. */
243 ( struct ston_ht_header_t
* ht
,
249 { uint32_t* data_row
= ston_ht32_row(ht
,key
);
250 uint32_t* data_limit
= data_row
+ ston_ht_cols(ht
);
251 uint32_t* data_trg
= data_row
+ start_column
;
252 if (data_row
== NULL
)
254 while (units
-- && data_trg
< data_limit
)
255 *data_trg
++ = *data_src
++;
256 return (size_t)(data_trg
- data_row
);
260 #ifndef STON_DHT_SIZE
261 #define STON_DHT_SIZE 4096
264 /* STON Dynamic Hashtable Structure
265 A dynamic form of the generic hashtable implementation above which uses
268 typedef struct ston_dht_header_t
269 { uint16_t ht_columns
;
270 uint8_t ht_2pow
, ht_flags
;
271 void* (*ht_alloc
)(size_t);
272 void (*ht_free
)(void*);
275 #define STON_DHT_HEADERSIZE (sizeof(struct ston_dht_header_t))
278 ston_dht
ston_dht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t),void(*)(void*));
280 uint32_t* ston_dht32_row(ston_dht
,uint32_t);
282 uint32_t ston_dht32_insert(ston_dht
,uint32_t,uint16_t,uint32_t);
284 void ston_dht32_free(ston_dht
);
286 #define ston_dht32_new(_COL,_N,_F,_FN) ston_dht32_create(_COLS,ston_up2pow(_N << 1),_F,_FN)
287 #define ston_dht32_entry(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL)
288 #define ston_dht32_insertx(_HT,_KEY,_COL,_VAL) *ston_dht32_col(_HT,_KEY,_COL) = _VAL
289 #define ston_dht_size(_HT) (ston_ht_size(_HT))
290 #define ston_dht_rows(_HT) (ston_ht_rows(_HT))
291 #define ston_dht_cols(_HT) (ston_ht_cols(_HT))
292 #define ston_dht_keyrow(_HT,_KEY) (ston_ht_keyrow(_HT,_KEY))
293 #define ston_dht_pagestart(_HT) ((void**)(((uint8_t*)(_HT)) + STON_DHT_HEADERSIZE))
294 #define ston_dht_pagehead(_HT) ((_HT)->page_head)
295 #define ston_dht_pagemax(_HT) ((void**)((uint8_t*)(_HT) + STON_DHT_SIZE - sizeof(void**)))
296 #define ston_dht_start(_HT,_DEPTH) ((uint8_t*)*(ston_dht_pagestart(_HT) + _DEPTH))
297 #define ston_dht32_start(_HT,_DEPTH) ((uint32_t*)ston_dht_start(_HT,_DEPTH))
298 #define ston_dht32_end(_HT,_DEPTH) (ston_ht32_start(_HT,_DEPTH) + ston_ht_size(_HT))
299 #define ston_dht32_size(_HT) (ston_dht_size(_HT) * sizeof(uint32_t))
300 #define ston_dht32_pagepush(_HT) ((*(++((_HT)->page_head)) = (_HT)->ht_alloc(ston_dht32_size(_HT))))
301 #define ston_dht32_pagepop(_HT) ((_HT)->ht_free((_HT)->page_head--))
303 /* Creates a new bucketted hash table, provided a memory allocation function
304 that takes a single size_t bytes, a memory free function, a column count, and
305 a row count which determines the size of the buckets.
308 ston_dht ston_dht32_create
309 ( uint16_t ht_columns
,
312 void* (*ht_alloc
)(size_t),
313 void (*ht_free
)(void*)
315 { size_t ht_size
= ht_rows
* ht_columns
* sizeof(uint32_t);
316 ston_dht ht
= (ston_dht
) ht_alloc(STON_DHT_SIZE
);
318 { for (ht
->ht_2pow
= 0; ht_size
; ht
->ht_2pow
++)
319 ht_size
= ht_size
>> 1;
320 ht
->ht_columns
= ht_columns
;
321 ht
->ht_flags
= ht_flags
;
322 ht
->ht_alloc
= ht_alloc
;
323 ht
->ht_free
= ht_free
;
324 ht
->page_head
= ston_dht_pagestart(ht
);
325 if ((*(ht
->page_head
) = ht
->ht_alloc(ston_dht_size(ht
))) == NULL
)
331 /* Returns a pointer to the row of data in the hashtable containing the provided
332 key, inserts if not found. Returns NULL on overflow.
335 uint32_t* ston_dht32_row
336 ( struct ston_dht_header_t
* ht
,
339 { uint16_t ht_cols
= ston_dht_cols(ht
);
340 size_t row_number
= ston_dht_keyrow(ht
,key
);
341 uint32_t** page
= (uint32_t**)ston_dht_pagestart(ht
);
342 uint32_t** pagemax
= (uint32_t**)ston_dht_pagemax(ht
);
345 uint32_t* row
,* row_end
;
347 row
= *page
+ (row_number
* ht_cols
);
348 row_end
= *page
+ (ston_dht_size(ht
) - 1);
359 { if (page
< pagemax
)
360 { if (page
== (uint32_t**)ston_dht_pagehead(ht
))
361 if (ston_dht32_pagepush(ht
) == NULL
)
362 { ston_dht32_free(ht
);
369 row_number
= (row_number
+ 1) % ston_dht_rows(ht
);
370 page
= (uint32_t**)ston_dht_pagestart(ht
);
390 /* Inserts a value into a hashtable at the specified column, returning the
393 uint32_t ston_dht32_insert
394 ( struct ston_dht_header_t
* ht
,
399 { uint32_t* value_location
, old_value
;
400 value_location
= ston_dht32_entry(ht
,key
,column
);
401 old_value
= *value_location
;
402 *value_location
= value
;
406 /* Free the dynamic hash table */
409 ( struct ston_dht_header_t
* ht
)
410 { void (*ht_free
)(void*) = ht
->ht_free
;
412 { while (ht
->page_head
>= ston_dht_pagestart(ht
))
413 ht_free(ht
->page_head
--);