ef7a363e901201672309103af873b326990c0fdc
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
50 #include <string.h> //memcpy
54 /* STON Hashtable Structure
55 Hashtables are stored as dynamically sized two dimensional arrays
57 typedef struct ston_ht_header_t
58 { uint16_t ht_columns
;
59 uint8_t ht_2pow
, ht_flags
;
63 size_t ston_up2pow(size_t);
66 ston_ht
ston_ht32_fread(FILE*,long,void*(*)(size_t));
68 ston_ht
ston_ht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t));
70 uint32_t* ston_ht32_row(ston_ht
,uint32_t);
72 uint32_t ston_ht32_insert(ston_ht
,uint32_t,uint16_t,uint32_t);
74 #define ston_ht32_new(_COL,_N,_F,_FN) ston_ht32_create(_COLS,ston_up2pow(_N << 1),_F,_FN)
75 #define ston_ht32_col(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
76 #define ston_ht32_insertx(_HT,_KEY,_COL,_VAL) *ston_ht32_col(_HT,_KEY,_COL) = _VAL
77 #define ston_ht_size(_HT) ((_HT)->ht_columns << (_HT)->ht_2pow)
78 #define ston_ht_rows(_HT) (0x1 << (_HT)->ht_2pow)
79 #define ston_ht_cols(_HT) ((_HT)->ht_columns)
80 #define ston_ht_start(_HT) (((uint8_t*)(_HT)) + sizeof(*(_HT)))
81 #define ston_ht_keyrow(_HT,_KEY) ((_KEY) & (ston_ht_rows(ht) - 1))
82 #define ston_ht32_start(_HT) ((uint32_t*)ston_ht_start(_HT))
83 #define ston_ht32_size(_HT) (ston_ht_size(_HT) * sizeof(uint32_t))
85 /** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
89 { val
= (val
<< 1) - 1;
98 /* Creates a new hash table, provided a memory allocation function that takes a
99 single size_t bytes, a column count, and a row count which determines the
102 use ston_ht32_new to specify the exact or estimated number of unique keys
103 held in the table. With ston_ht32_new, the provided ht_rows is doubled, and
104 rounded up to the nearest power of two to create a hash table with minimal
108 ston_ht ston_ht32_create
109 ( uint16_t ht_columns
,
112 void* (*alloc_fn
)(size_t)
114 { size_t ht_size
= ht_rows
* ht_columns
* sizeof(uint32_t);
115 ston_ht ht
= (ston_ht
) alloc_fn(sizeof(struct ston_ht_header_t
) + ht_size
);
117 { for (ht
->ht_2pow
= 0; ht_size
; ht
->ht_2pow
++)
118 ht_size
= ht_size
>> 1;
119 ht
->ht_columns
= ht_columns
;
120 ht
->ht_flags
= ht_flags
;
125 #ifndef STON_NO_STDIO
126 /* Reads a 32-bit hash table out of the provided file at the provide fpos, into
127 a buffer allocated by alloc_fn. Memory is allocated to the stack until the
128 entire structure is verified, and all file operations are finished.
129 Returns NULL with properly set errno on failure.
133 ston_ht ston_ht32_fread
136 void* (*alloc_fn
)(size_t)
138 { struct ston_ht_header_t header
;
139 ston_ht stack_ht
, ht
;
141 size_t table_size
, alloc_size
;
142 if ((fpos_start
= ftell(file
)) == -1)
144 if (fread(&header
, sizeof(header
), 1, file
) != 1)
146 table_size
= ston_ht32_size(&header
);
147 alloc_size
= sizeof(header
) + table_size
;
148 stack_ht
= (ston_ht
) alloca(alloc_size
);
149 memcpy(stack_ht
, &header
, sizeof(header
));
150 if (fread(stack_ht
+ sizeof(header
), table_size
, 1, file
) != 1)
152 if (fseek(file
, fpos_start
, SEEK_SET
) != 0)
154 ht
= (ston_ht
) alloc_fn(alloc_size
);
156 memcpy(ht
, stack_ht
, alloc_size
);
161 /* Returns a pointer to the row of data in the hashtable containing the provided
162 key, inserts if not found. Returns NULL on overflow.
165 uint32_t* ston_ht32_row
166 ( struct ston_ht_header_t
* ht
,
169 { uint32_t* row
,* row_start
= ston_ht32_start(ht
);
170 uint16_t ht_cols
= ston_ht_cols(ht
);
171 size_t row_number
= ston_ht_keyrow(ht
,key
);
172 size_t row_max
= ston_ht_rows(ht
);
175 row
= row_start
+ (row_number
* ht_cols
);
184 if (row_number
< row_max
)
195 /* Inserts a value into a hashtable at the specified column, returning the
198 uint32_t ston_ht32_insert
199 ( struct ston_ht_header_t
* ht
,
204 { uint32_t* value_location
, old_value
;
205 value_location
= ston_ht32_col(ht
,key
,column
);
206 old_value
= *value_location
;
207 *value_location
= value
;
211 /* STON Dynamic Hashtable Structure
212 A dynamic form of the generic hashtable implementation above which uses
215 typedef struct ston_dht_header_t
216 { uint16_t ht_columns
;
217 uint8_t ht_2pow
, ht_flags
;
218 void (*ht_alloc
)(size_t);
222 #define ston_dht_size(_HT) (ston_ht_size(_HT))
223 #define ston_dht_rows(_HT) (ston_ht_rows(_HT))
224 #define ston_dht_cols(_HT) (ston_ht_cols(_HT))
225 #define ston_dht_keyrow(_HT,_KEY) (ston_ht_keyrow(_HT,_KEY))
226 #define ston_dht_start(_HT) (_HT->ht_pages[0])
227 #define ston_dht32_start(_HT) ((_uint32*)ston_dht_start(_HT))
228 ston_dht
ston_dht32_create(uint16_t,size_t,void*(*)(size_t));
229 uint32_t* ston_dht32_row(ston_dht
,uint32_t);
230 #define ston_dht32_col(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL)
231 uint32_t ston_dht32_insert(ston_dht
,uint32_t,uint16_t,uint32_t);
232 #define ston_dht32_insertx(_HT,_KEY,_COL,_VAL) *ston_dht32_col(_HT,_KEY,_COL) = _VAL