· 5 years ago · Feb 07, 2020, 08:58 PM
1#ifndef GS_CONTAINERS_H
2#define GS_CONTAINERS_H
3
4#include "common/gs_types.h"
5#include "common/gs_util.h"
6
7/*===================================
8// Dynamic Array
9===================================*/
10
11/*
12 - HEAVILY lifted from Sean Barret's 'stretchy buffer' implementation
13
14 TODO(john): illustrate basic usage example
15*/
16
17typedef struct
18{
19 s32 size;
20 s32 capacity;
21} gs_dyn_array;
22
23#define gs_dyn_array_head( arr )\
24 ( ( gs_dyn_array* )( ( u8* )arr - sizeof( gs_dyn_array ) ) )
25
26#define gs_dyn_array_size( arr )\
27 gs_dyn_array_head( arr )->size
28
29#define gs_dyn_array_capacity( arr )\
30 gs_dyn_array_head( arr )->capacity
31
32#define gs_dyn_array_full( arr )\
33 ( ( gs_dyn_array_size( arr ) == gs_dyn_array_capacity( arr ) ) )
34
35// Should also be the grow implementation
36_inline void* gs_dyn_array_resize_impl( void* arr, usize sz, usize amount )
37{
38 usize capacity;
39
40 if ( arr ) {
41 capacity = amount;
42 } else {
43 capacity = 0;
44 }
45
46 // Create new gs_dyn_array with just the header information
47 gs_dyn_array* data = ( gs_dyn_array* )gs_realloc( arr ? gs_dyn_array_head( arr ) : 0, capacity * sz + sizeof( gs_dyn_array ) );
48 if ( data )
49 {
50 // Set size
51 if ( !arr )
52 {
53 data->size = 0;
54 }
55
56 data->capacity = capacity;
57
58 // Return actual data position in buffer
59 return ( ( s32* )data + 2 );
60 }
61
62 return NULL;
63}
64
65#define gs_dyn_array_grow( arr )\
66 gs_dyn_array_resize_impl( arr, sizeof( *( arr ) ), gs_dyn_array_capacity( arr ) ? gs_dyn_array_capacity( arr ) * 2 : 1 )
67
68#define gs_dyn_array_push( arr, val )\
69 do {\
70 if ( !( arr ) || ( ( arr ) && gs_dyn_array_full( arr ) ) ) {\
71 *( ( void ** )&( arr ) ) = gs_dyn_array_grow( arr ); \
72 }\
73 ( arr )[ gs_dyn_array_size( arr ) ] = ( val );\
74 gs_dyn_array_size( arr ) += 1;\
75 } while( 0 )
76
77#define gs_dyn_array_reserve( arr, amount )\
78 do {\
79 if ( ( !arr ) || amount > gs_dyn_array_capacity( arr ) ) {\
80 *( ( void ** )&( arr ) ) = gs_dyn_array_resize_impl( arr, sizeof( *arr ), amount );\
81 }\
82 } while( 0 )
83
84#define gs_dyn_array_empty( arr )\
85 ( arr && ( gs_dyn_array_size( arr ) == 0 ) )
86
87#define gs_dyn_array_pop( arr )\
88 do {\
89 if ( arr && !gs_dyn_array_empty( arr ) ) {\
90 gs_dyn_array_size( arr ) -= 1;\
91 }\
92 } while ( 0 )
93
94#define gs_dyn_array_back( arr )\
95 ( arr + ( gs_dyn_array_size( arr ) ? gs_dyn_array_size( arr ) - 1 : 0 ) )
96
97#define gs_dyn_array_for( arr, type, iter_name )\
98 for ( type* iter_name = arr; iter_name != gs_dyn_array_back( arr ); ++iter_name )
99
100#define gs_dyn_array_new( type )\
101 ( type* )gs_dyn_array_resize_impl( NULL, sizeof( type ), 0 )
102
103#define gs_dyn_array_clear( arr )\
104 gs_dyn_array_size( arr ) = 0
105
106#define gs_dyn_array( type ) type*
107
108#define gs_dyn_array_free( arr )\
109 do {\
110 if ( arr ) {\
111 gs_free( gs_dyn_array_head( arr ) );\
112 arr = 0;\
113 }\
114 } while ( 0 )
115
116/*===================================
117// Hash Table
118===================================*/
119
120// TODO(john): Need to improve the hash table a lot ( round robin should help linear probing )
121
122/*
123 NOTE(john): Hash Function References: http://www.cse.yorku.ca/~oz/hash.html
124
125 Want to have syntax like this:
126 gs_hash_table table = gs_hash_table( u32, object* );
127 gs_hash_table_get( &table, key );
128 gs_hash_table_put( &table, key, val );
129 gs_hash_table_exists( &table, key );
130 gs_hash_table_size( &table );
131 gs_hash_table_clear( &table );
132
133 typedef struct
134 {
135 size_t key_type_size;
136 size_t val_type_size; // Not sure if this is necessary, but it might be
137 void* data_array;
138 hash_func_ptr;
139 hash_eq_func_ptr;
140 } gs_hash_table;
141
142// Will NOT work for const char*, however ( must define new type, I imagine )
143#define hash_table( key_type, val_type )\
144 { .key_type_size = sizeof( key_type ), .val_type_size = sizeof( val_type ) };
145
146 // Is this possible? ( I think so, if sizes are used )
147*/
148
149#define gs_hash_key_comp_str( a, b ) ( gs_string_compare_equal( a, b ) )
150
151#define gs_hash_key_comp_std_type( a, b ) ( a == b )
152
153#define gs_hash_table_valid_idx( idx )\
154 ( idx < ( UINT_MAX - 1 ) )
155
156typedef enum
157{
158 hash_table_entry_inactive = 0,
159 hash_table_entry_active = 1
160} gs_hash_table_entry_state;
161
162#define gs_hash_table_decl( key_type, val_type, _hash_func, _hash_comp_key_func )\
163 typedef struct\
164 {\
165 key_type key;\
166 val_type val;\
167 gs_hash_table_entry_state entry_state;\
168 } gs_ht_entry_##key_type##_##val_type;\
169\
170 typedef struct\
171 {\
172 gs_ht_entry_##key_type##_##val_type *data;\
173 u32 ( * hash_func )();\
174 u32 ( * hash_key_idx_func )( void*, key_type );\
175 val_type ( * hash_get_val_func )( void*, key_type );\
176 val_type* ( * hash_get_val_ptr_func )( void*, key_type );\
177 b8 ( * hash_comp_key_func )( key_type, key_type );\
178 void ( * hash_grow_func )( void*, u32 );\
179 } gs_ht_##key_type##_##val_type;\
180\
181 _inline u32 gs_ht_##key_type##_##val_type##_key_idx_func( void* tbl_ptr, key_type key )\
182 {\
183 gs_ht_##key_type##_##val_type* tbl = ( gs_ht_##key_type##_##val_type* )tbl_ptr;\
184 u32 capacity = gs_hash_table_capacity( ( *tbl ) );\
185 u32 idx = tbl->hash_func( key ) % capacity;\
186 for ( u32 i = idx, c = 0; c < capacity; ++c, i = ( ( i + 1 ) % capacity ) )\
187 {\
188 if ( _hash_comp_key_func( tbl->data[ i ].key, key ) )\
189 {\
190 return i;\
191 }\
192 }\
193 return UINT_MAX - 1;\
194 }\
195 _inline val_type gs_ht_##key_type##_##val_type##_get_func( void* tbl_ptr, key_type key )\
196 {\
197 val_type out = { 0 };\
198 gs_ht_##key_type##_##val_type* tbl = ( gs_ht_##key_type##_##val_type* )tbl_ptr;\
199 if ( gs_dyn_array_empty( tbl->data ) ) \
200 {\
201 return out;\
202 }\
203 u32 capacity = gs_hash_table_capacity( ( *tbl ) );\
204 u32 val = UINT_MAX - 1;\
205 u32 idx = tbl->hash_func( key ) % capacity;\
206 gs_ht_entry_##key_type##_##val_type* data = tbl->data;\
207 for ( u32 i = idx, c = 0; c < capacity; ++c, i = ( ( i + 1 ) % capacity ) )\
208 {\
209 if ( _hash_comp_key_func( data[ i ].key, key ) )\
210 {\
211 val = i;\
212 break;\
213 }\
214 }\
215 if ( gs_hash_table_valid_idx( val ) )\
216 {\
217 out = data[ val ].val;\
218 }\
219 return out;\
220 }\
221 _inline val_type* gs_ht_##key_type##_##val_type##_get_ptr_func( void* tbl_ptr, key_type key )\
222 {\
223 val_type* out = NULL;\
224 gs_ht_##key_type##_##val_type* tbl = ( gs_ht_##key_type##_##val_type* )tbl_ptr;\
225 if ( gs_dyn_array_empty( tbl->data ) ) \
226 {\
227 return out;\
228 }\
229 u32 capacity = gs_hash_table_capacity( ( *tbl ) );\
230 u32 val = UINT_MAX - 1;\
231 u32 idx = tbl->hash_func( key ) % capacity;\
232 gs_ht_entry_##key_type##_##val_type* data = tbl->data;\
233 for ( u32 i = idx, c = 0; c < capacity; ++c, i = ( ( i + 1 ) % capacity ) )\
234 {\
235 if ( _hash_comp_key_func( data[ i ].key, key ) )\
236 {\
237 val = i;\
238 break;\
239 }\
240 }\
241 if ( gs_hash_table_valid_idx( val ) )\
242 {\
243 out = &data[ val ].val;\
244 }\
245 return out;\
246 }\
247 _inline b8 gs_ht_##key_type##_##val_type##_comp_key_func( key_type k0, key_type k1 )\
248 {\
249 if ( _hash_comp_key_func( k0, k1 ) )\
250 {\
251 return true;\
252 }\
253 return false;\
254 }\
255\
256 _inline void gs_ht_##key_type##_##val_type##_grow_func( void* tbl_ptr, u32 new_sz );\
257\
258 _inline gs_ht_##key_type##_##val_type gs_ht_##key_type##_##val_type##_new()\
259 {\
260 gs_ht_##key_type##_##val_type ht = {\
261 .data = gs_dyn_array_new( gs_ht_entry_##key_type##_##val_type ),\
262 .hash_func = &_hash_func,\
263 .hash_key_idx_func = gs_ht_##key_type##_##val_type##_key_idx_func,\
264 .hash_get_val_func = gs_ht_##key_type##_##val_type##_get_func,\
265 .hash_get_val_ptr_func = gs_ht_##key_type##_##val_type##_get_ptr_func,\
266 .hash_comp_key_func = gs_ht_##key_type##_##val_type##_comp_key_func,\
267 .hash_grow_func = gs_ht_##key_type##_##val_type##_grow_func\
268 };\
269 return ht;\
270 }\
271\
272 _inline void gs_ht_##key_type##_##val_type##_grow_func( void* tbl_ptr, u32 new_sz )\
273 {\
274 gs_ht_##key_type##_##val_type* tbl = ( gs_ht_##key_type##_##val_type* )tbl_ptr;\
275 gs_ht_##key_type##_##val_type new_tbl = gs_ht_##key_type##_##val_type##_new();\
276 gs_dyn_array_reserve( new_tbl.data, new_sz );\
277 memset( new_tbl.data, 0, new_sz * sizeof( gs_ht_entry_##key_type##_##val_type ) );\
278 for ( u32 i = 0; i < gs_dyn_array_capacity( tbl->data ); ++i ) {\
279 if ( tbl->data[ i ].entry_state == hash_table_entry_active ) {\
280 gs_hash_table_insert( new_tbl, tbl->data[ i ].key, tbl->data[ i ].val );\
281 }\
282 }\
283 gs_dyn_array_free( tbl->data );\
284 tbl->data = new_tbl.data;\
285 }
286
287#define gs_hash_table_key_idx_func( tbl, key, val, _hash_comp_key_func )\
288 do {\
289 u32 capacity = gs_hash_table_capacity( ( *tbl ) );\
290 u32 idx = tbl->hash_func( key ) % capacity;\
291 val = UINT_MAX - 1;\
292 for ( u32 i = idx, c = 0; c < capacity; ++c, i = ( ( i + 1 ) % capacity ) )\
293 {\
294 gs_println( "i: %d, capacity: %d", i, capacity );\
295 if ( _hash_comp_key_func( tbl->data[ i ].key, key ) )\
296 {\
297 val = i;\
298 break;\
299 }\
300 }\
301 } while( 0 )
302
303
304#define gs_hash_table_exists( tbl, k )\
305 gs_hash_table_valid_idx( tbl.hash_key_idx_func( &tbl, k ) )
306
307#define gs_hash_table_key_idx( tbl, k )\
308 tbl.hash_key_idx_func( &tbl, k )
309
310#define gs_hash_table_reserve( tbl, sz )\
311 __gs_hash_table_grow( tbl, sz )
312
313#define gs_hash_table_size( tbl )\
314 gs_dyn_array_size( tbl.data )
315
316#define gs_hash_table_empty( tbl )\
317 !gs_dyn_array_size( tbl.data )
318
319#define gs_hash_table_capacity( tbl )\
320 gs_dyn_array_capacity( tbl.data )
321
322#define gs_hash_table_load_factor( tbl )\
323 gs_hash_table_capacity( tbl ) ? (f32)gs_hash_table_size( tbl ) / (f32)gs_hash_table_capacity( tbl ) : 0.0f
324
325// Should this grow to be sizes equal to primes?
326#define __gs_hash_table_grow( tbl, sz )\
327 do {\
328 tbl.hash_grow_func( &tbl, sz );\
329 } while ( 0 )
330
331// Need to check load factor for this
332// If the load factor grows beyond max, then need to grow data array and rehash
333// If shrinks beyond min, then shrink data array and rehash
334// Need to handle collisions between keys ( preferrably robin hood hash with linear prob )
335// Need a way to determine whether or not a key exists
336// TODO(john): Fix bug with load factor ( for some reason, anything higher than 0.5 causes incorrect placement of values in slots )
337// TODO(john): Implement Robin Hood hashing for collision resolution
338#define gs_hash_table_insert( tbl, k, v )\
339 do {\
340 u32 capacity = gs_hash_table_capacity( tbl );\
341 f32 load_factor = gs_hash_table_load_factor( tbl );\
342 if ( load_factor >= 0.5f || !capacity )\
343 {\
344 __gs_hash_table_grow( tbl, capacity ? capacity * 2 : 1 );\
345 capacity = gs_hash_table_capacity( tbl );\
346 }\
347 u32 hash_idx = tbl.hash_func( k ) % gs_hash_table_capacity( tbl );\
348 u32 c = 0;\
349 while ( c < capacity && !tbl.hash_comp_key_func( tbl.data[ hash_idx ].key, k ) && tbl.data[ hash_idx ].entry_state == hash_table_entry_active ) {\
350 hash_idx = ( ( hash_idx + 1 ) % capacity );\
351 c++;\
352 }\
353 tbl.data[ hash_idx ].key = k;\
354 tbl.data[ hash_idx ].val = v;\
355 tbl.data[ hash_idx ].entry_state = hash_table_entry_active;\
356 gs_dyn_array_size( tbl.data )++;\
357 } while ( 0 )
358
359#define gs_hash_table_get( tbl, k )\
360 tbl.hash_get_val_func( ( void* )&( tbl ), ( k ) )
361
362#define gs_hash_table_get_ptr( tbl, k )\
363 tbl.hash_get_val_ptr_func( ( void* )&( tbl ), ( k ) )
364
365#define gs_hash_table( key_type, val_type )\
366 gs_ht_##key_type##_##val_type
367
368#define gs_hash_table_entry( key_type, val_type )\
369 gs_ht_entry_##key_type##_##val_type
370
371#define gs_hash_table_new( key_type, val_type )\
372 gs_ht_##key_type##_##val_type##_new()
373
374#define gs_hash_table_clear( tbl )\
375 gs_dyn_array_clear( tbl.data )
376
377
378// Some typical hash tables
379
380// Hash table := key: u32, val: u32
381gs_hash_table_decl( u32, u32, gs_hash_u32, gs_hash_key_comp_std_type );
382
383
384/*===================================
385// Slot Array
386===================================*/
387
388#define gs_slot_array_invalid_handle u32_max
389
390typedef struct
391gs_slot_array_base
392{
393 gs_dyn_array( u32 ) handle_indices;
394 gs_dyn_array( u32 ) reverse_indirection_indices;
395 gs_dyn_array( u32 ) index_free_list;
396} gs_slot_array_base;
397
398#define gs_slot_array_decl( T )\
399 typedef struct gs_sa_##T\
400 {\
401 gs_slot_array_base _base;\
402 gs_dyn_array( T ) data;\
403 u32 ( * insert_func )( struct gs_sa_##T*, T );\
404 } gs_sa_##T;\
405\
406 _force_inline u32\
407 gs_sa_##T##_insert_func( struct gs_sa_##T* s, T v )\
408 {\
409 u32 free_idx = gs_slot_array_find_next_available_index( ( gs_slot_array_base* )s );\
410 gs_dyn_array_push( s->data, v );\
411 gs_dyn_array_push( s->_base.reverse_indirection_indices, free_idx );\
412 s->_base.handle_indices[ free_idx ] = gs_dyn_array_size( s->data ) - 1;\
413 return free_idx;\
414 }\
415\
416 _force_inline\
417 gs_sa_##T __gs_sa_##T##_new()\
418 {\
419 gs_sa_##T sa = {\
420 .data = gs_dyn_array_new( T ),\
421 ._base.handle_indices = gs_dyn_array_new( u32 ),\
422 ._base.reverse_indirection_indices = gs_dyn_array_new( u32 ),\
423 ._base.index_free_list = gs_dyn_array_new( u32 ),\
424 .insert_func = &gs_sa_##T##_insert_func,\
425 };\
426 return sa;\
427 }
428
429_force_inline u32
430gs_slot_array_find_next_available_index( gs_slot_array_base* sa )
431{
432 if ( gs_dyn_array_empty( sa->index_free_list ) ) {
433 gs_dyn_array_push( sa->handle_indices, 0 );
434 return ( gs_dyn_array_size( sa->handle_indices ) - 1 );
435 }
436 u32 idx = sa->index_free_list[ 0 ];
437 if ( gs_dyn_array_size( sa->index_free_list ) > 1 ) {
438 u32 sz = gs_dyn_array_size( sa->index_free_list );
439 u32 tmp = sa->index_free_list[ sz - 1 ];
440 sa->index_free_list[ 0 ] = tmp;
441 gs_dyn_array_pop( sa->index_free_list );
442 } else {
443 gs_dyn_array_clear( sa->index_free_list );
444 }
445
446 return idx;
447}
448
449#define gs_slot_array_clear( s )\
450 do {\
451 gs_dyn_array_clear( s._base.handle_indices );\
452 gs_dyn_array_clear( s._base.index_free_list );\
453 gs_dyn_array_clear( s._base.reverse_indirection_indices );\
454 gs_dyn_array_clear( s.data );\
455 } while ( 0 )
456
457#define gs_slot_array_size( s )\
458 gs_dyn_array_size( (s).data )
459
460#define gs_slot_array_new( type )\
461 __gs_sa_##type##_new()
462
463#define gs_slot_array_insert( s, v )\
464 s.insert_func( &( s ), ( v ) )
465
466#define gs_slot_array_get( s, handle )\
467 ( s.data[ s._base.handle_indices[ handle ] ] )
468
469#define gs_slot_array_get_unsafe( s, handle )\
470 ( &s.data[ s._base.handle_indices[ handle ] ] )
471
472#define gs_slot_array_handle_valid( s, handle )\
473 ( handle < gs_slot_array_size( s ) )
474
475#define gs_slot_array( T )\
476 gs_sa_##T
477
478
479#endif