5JkRCgZ9

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_swap( type, arr, idx_a, idx_b )\
95	do {\
96		type tmp = arr[ idx_a ];\
97		arr[ idx_a ] = arr[ idx_b ];\
98		arr[ idx_b ] = tmp;\
99	} while ( 0 )
100
101#define gs_dyn_array_swap_back( type, arr, idx_a )\
102	do {\
103		type tmp = arr[ idx_a ];\
104		arr[ idx_a ] = arr[ gs_dyn_array_size( arr ) - 1 ];\
105		arr[ gs_dyn_array_size( arr ) - 1 ] = tmp;\
106	} while ( 0 )
107
108#define gs_dyn_array_back( arr )\
109	( arr + ( gs_dyn_array_size( arr ) ? gs_dyn_array_size( arr ) - 1 : 0 ) )
110
111#define gs_dyn_array_for( arr, type, iter_name )\
112	for ( type* iter_name = arr; iter_name != gs_dyn_array_back( arr ); ++iter_name )
113
114#define gs_dyn_array_new( type )\
115	( type* )gs_dyn_array_resize_impl( NULL, sizeof( type ), 0 )
116
117#define gs_dyn_array_clear( arr )\
118	gs_dyn_array_size( arr ) = 0
119
120#define gs_dyn_array( type )	type*
121
122#define gs_dyn_array_free( arr )\
123	do {\
124		if ( arr ) {\
125			gs_free( gs_dyn_array_head( arr ) );\
126			arr = 0;\
127		}\
128	} while ( 0 )
129
130/*===================================
131// Hash Table
132===================================*/
133
134// TODO(john): Need to improve the hash table a lot ( round robin should help linear probing )
135
136/*
137	NOTE(john): Hash Function References: http://www.cse.yorku.ca/~oz/hash.html
138
139	Want to have syntax like this:
140		gs_hash_table table = gs_hash_table( u32, object* );
141		gs_hash_table_get( &table, key );
142		gs_hash_table_put( &table, key, val );
143		gs_hash_table_exists( &table, key );
144		gs_hash_table_size( &table );
145		gs_hash_table_clear( &table );
146
147	typedef struct
148	{
149		size_t key_type_size;	
150		size_t val_type_size;			// Not sure if this is necessary, but it might be
151		void* data_array;
152		hash_func_ptr;
153		hash_eq_func_ptr;
154	} gs_hash_table;
155
156// Will NOT work for const char*, however ( must define new type, I imagine )
157#define hash_table( key_type, val_type )\
158	{ .key_type_size = sizeof( key_type ), .val_type_size = sizeof( val_type ) };
159
160	// Is this possible? ( I think so, if sizes are used )
161*/
162
163#define gs_hash_key_comp_str( a, b ) ( gs_string_compare_equal( a, b ) )
164
165#define gs_hash_key_comp_std_type( a, b ) ( a == b )
166
167#define gs_hash_table_valid_idx( idx )\
168	( idx < ( UINT_MAX - 1 ) )
169
170typedef enum
171{
172	hash_table_entry_inactive 	= 0,
173	hash_table_entry_active 	= 1
174} gs_hash_table_entry_state;
175
176#define gs_hash_table_decl( key_type, val_type, _hash_func, _hash_comp_key_func, _invalid_key_func, _invalid_val_func )\
177	typedef struct\
178	{\
179		key_type key;\
180		val_type val;\
181		gs_hash_table_entry_state entry_state;\
182	} gs_ht_entry_##key_type##_##val_type;\
183\
184	typedef struct\
185	{\
186		gs_ht_entry_##key_type##_##val_type *data;\
187		u32 ( * hash_func )( key_type );\
188		u32 ( * hash_key_idx_func )( void*, key_type );\
189		val_type ( * hash_get_val_func )( void*, key_type );\
190		val_type* ( * hash_get_val_ptr_func )( void*, key_type );\
191		void ( * hash_remove_func )( void*, key_type );\
192		b8 ( * hash_comp_key_func )( key_type, key_type );\
193		void ( * hash_grow_func )( void*, u32 );\
194	} gs_ht_##key_type##_##val_type;\
195\
196	_inline u32 gs_ht_##key_type##_##val_type##_key_idx_func( void* tbl_ptr, key_type key )\
197	{\
198		gs_ht_##key_type##_##val_type* tbl = ( gs_ht_##key_type##_##val_type* )tbl_ptr;\
199		u32 size = gs_hash_table_size( ( *tbl ) );\
200		u32 capacity = gs_hash_table_capacity( ( *tbl ) );\
201		if ( !size || !capacity ) return (UINT_MAX - 1);\
202		u32 idx = tbl->hash_func( key ) % capacity;\
203		for ( u32 i = idx, c = 0; c < capacity; ++c, i = ( ( i + 1 ) % capacity ) )\
204		{\
205			if ( _hash_comp_key_func( tbl->data[ i ].key, key ) )\
206			{\
207				return i;\
208			}\
209		}\
210		return UINT_MAX - 1;\
211	}\
212	_inline void gs_ht_##key_type##_##val_type##_remove_func( void* tbl_ptr, key_type key )\
213	{\
214		gs_ht_##key_type##_##val_type* tbl = ( gs_ht_##key_type##_##val_type* )tbl_ptr;\
215		if ( gs_dyn_array_empty( tbl->data ) ) \
216		{\
217			return;\
218		}\
219		u32 size = gs_hash_table_size( ( *tbl ) );\
220		u32 capacity = gs_hash_table_capacity( ( *tbl ) );\
221		if ( !size || !capacity ) return;\
222		u32 idx = tbl->hash_func( key ) % capacity;\
223		gs_ht_entry_##key_type##_##val_type* data = tbl->data;\
224		for ( u32 i = idx, c = 0; c < capacity; ++c, i = ( ( i + 1 ) % capacity ) )\
225		{\
226			if ( _hash_comp_key_func( tbl->data[ i ].key, key ) )\
227			{\
228				tbl->data[ i ].key = _invalid_key_func;\
229				break;\
230			}\
231		}\
232	}\
233	_inline val_type gs_ht_##key_type##_##val_type##_get_func( void* tbl_ptr, key_type key )\
234	{\
235		val_type out = _invalid_val_func;\
236		gs_ht_##key_type##_##val_type* tbl = ( gs_ht_##key_type##_##val_type* )tbl_ptr;\
237		if ( gs_dyn_array_empty( tbl->data ) ) \
238		{\
239			return out;\
240		}\
241		u32 capacity = gs_hash_table_capacity( ( *tbl ) );\
242		u32 val = UINT_MAX - 1;\
243		u32 idx = tbl->hash_func( key ) % capacity;\
244		gs_ht_entry_##key_type##_##val_type* data = tbl->data;\
245		for ( u32 i = idx, c = 0; c < capacity; ++c, i = ( ( i + 1 ) % capacity ) )\
246		{\
247			if ( _hash_comp_key_func( data[ i ].key, key ) )\
248			{\
249				val = i;\
250				break;\
251			}\
252		}\
253		if ( gs_hash_table_valid_idx( val ) )\
254		{\
255			out = data[ val ].val;\
256		}\
257		return out;\
258	}\
259	_inline val_type* gs_ht_##key_type##_##val_type##_get_ptr_func( void* tbl_ptr, key_type key )\
260	{\
261		val_type* out = NULL;\
262		gs_ht_##key_type##_##val_type* tbl = ( gs_ht_##key_type##_##val_type* )tbl_ptr;\
263		if ( gs_dyn_array_empty( tbl->data ) ) \
264		{\
265			return out;\
266		}\
267		u32 capacity = gs_hash_table_capacity( ( *tbl ) );\
268		u32 val = UINT_MAX - 1;\
269		u32 idx = tbl->hash_func( key ) % capacity;\
270		gs_ht_entry_##key_type##_##val_type* data = tbl->data;\
271		for ( u32 i = idx, c = 0; c < capacity; ++c, i = ( ( i + 1 ) % capacity ) )\
272		{\
273			if ( _hash_comp_key_func( data[ i ].key, key ) )\
274			{\
275				val = i;\
276				break;\
277			}\
278		}\
279		if ( gs_hash_table_valid_idx( val ) )\
280		{\
281			out = &data[ val ].val;\
282		}\
283		return out;\
284	}\
285	_inline b8 gs_ht_##key_type##_##val_type##_comp_key_func( key_type k0, key_type k1 )\
286	{\
287		if ( _hash_comp_key_func( k0, k1 ) )\
288		{\
289			return true;\
290		}\
291		return false;\
292	}\
293\
294	_inline void gs_ht_##key_type##_##val_type##_grow_func( void* tbl_ptr, u32 new_sz );\
295\
296	_inline gs_ht_##key_type##_##val_type gs_ht_##key_type##_##val_type##_new()\
297	{\
298		gs_ht_##key_type##_##val_type ht;\
299		ht.data 					= gs_dyn_array_new( gs_ht_entry_##key_type##_##val_type );\
300		ht.hash_func 				= &_hash_func;\
301		ht.hash_key_idx_func 		= gs_ht_##key_type##_##val_type##_key_idx_func;\
302		ht.hash_get_val_func 		= gs_ht_##key_type##_##val_type##_get_func;\
303		ht.hash_get_val_ptr_func 	= gs_ht_##key_type##_##val_type##_get_ptr_func;\
304		ht.hash_comp_key_func 		= gs_ht_##key_type##_##val_type##_comp_key_func;\
305		ht.hash_grow_func 			= gs_ht_##key_type##_##val_type##_grow_func;\
306		ht.hash_remove_func 		= gs_ht_##key_type##_##val_type##_remove_func;\
307		gs_for_range_i( gs_dyn_array_capacity( ht.data ) ) {\
308			ht.data[ i ].key = _invalid_key_func;\
309		}\
310		return ht;\
311	}\
312\
313	_inline void gs_ht_##key_type##_##val_type##_grow_func( void* tbl_ptr, u32 new_sz )\
314	{\
315		gs_ht_##key_type##_##val_type* tbl = ( gs_ht_##key_type##_##val_type* )tbl_ptr;\
316		gs_ht_##key_type##_##val_type new_tbl = gs_ht_##key_type##_##val_type##_new();\
317		gs_dyn_array_reserve( new_tbl.data, new_sz );\
318		memset( new_tbl.data, 0, new_sz * sizeof( gs_ht_entry_##key_type##_##val_type ) );\
319		for ( u32 i = 0; i < gs_dyn_array_capacity( tbl->data ); ++i ) {\
320			if ( tbl->data[ i ].entry_state == hash_table_entry_active ) {\
321				gs_hash_table_insert( new_tbl, tbl->data[ i ].key, tbl->data[ i ].val );\
322			} else {\
323				new_tbl.data[ i ].key = _invalid_key_func;\
324			}\
325		}\
326		gs_dyn_array_free( tbl->data );\
327		tbl->data = new_tbl.data;\
328	}
329
330#define gs_hash_table_exists( tbl, k )\
331	gs_hash_table_valid_idx( tbl.hash_key_idx_func( &tbl, k ) )
332
333#define gs_hash_table_key_idx( tbl, k )\
334	tbl.hash_key_idx_func( &tbl, k )
335
336#define gs_hash_table_reserve( tbl, sz )\
337	__gs_hash_table_grow( tbl, sz )
338
339#define gs_hash_table_size( tbl )\
340	gs_dyn_array_size( tbl.data )
341
342#define gs_hash_table_empty( tbl )\
343	!gs_dyn_array_size( tbl.data )
344
345#define gs_hash_table_capacity( tbl )\
346	gs_dyn_array_capacity( tbl.data )
347
348#define gs_hash_table_load_factor( tbl )\
349	gs_hash_table_capacity( tbl ) ? (f32)gs_hash_table_size( tbl ) / (f32)gs_hash_table_capacity( tbl ) : 0.0f
350
351// Should this grow to be sizes equal to primes?
352#define __gs_hash_table_grow( tbl, sz )\
353	do {\
354		tbl.hash_grow_func( &tbl, sz );\
355	} while ( 0 )
356
357// Need to check load factor for this
358// If the load factor grows beyond max, then need to grow data array and rehash
359// If shrinks beyond min, then shrink data array and rehash
360// Need to handle collisions between keys ( preferrably robin hood hash with linear prob )
361// Need a way to determine whether or not a key exists
362// TODO(john): Fix bug with load factor ( for some reason, anything higher than 0.5 causes incorrect placement of values in slots )
363// TODO(john): Implement Robin Hood hashing for collision resolution
364#define gs_hash_table_insert( tbl, k, v )\
365	do {\
366		u32 capacity = gs_hash_table_capacity( tbl );\
367		f32 load_factor = gs_hash_table_load_factor( tbl );\
368		if ( load_factor >= 0.5f || !capacity )\
369		{\
370			__gs_hash_table_grow( tbl, capacity ? capacity * 2 : 1 );\
371			capacity = gs_hash_table_capacity( tbl );\
372		}\
373		u32 hash_idx = tbl.hash_func( k ) % gs_hash_table_capacity( tbl );\
374		u32 c = 0;\
375		while ( c < capacity && !tbl.hash_comp_key_func( tbl.data[ hash_idx ].key, k ) && tbl.data[ hash_idx ].entry_state == hash_table_entry_active ) {\
376			hash_idx = ( ( hash_idx + 1 ) % capacity );\
377			c++;\
378		}\
379		tbl.data[ hash_idx ].key = k;\
380		tbl.data[ hash_idx ].val = v;\
381		tbl.data[ hash_idx ].entry_state = hash_table_entry_active;\
382		gs_dyn_array_size( tbl.data )++;\
383	} while ( 0 )
384
385#define gs_hash_table_get( tbl, k )\
386	tbl.hash_get_val_func( ( void* )&( tbl ), ( k ) )
387
388#define gs_hash_table_get_ptr( tbl, k )\
389	tbl.hash_get_val_ptr_func( ( void* )&( tbl ), ( k ) )
390
391#define gs_hash_table( key_type, val_type )\
392	gs_ht_##key_type##_##val_type
393
394#define gs_hash_table_entry( key_type, val_type )\
395	gs_ht_entry_##key_type##_##val_type
396
397#define gs_hash_table_new( key_type, val_type )\
398	gs_ht_##key_type##_##val_type##_new()
399
400#define gs_hash_table_clear( tbl )\
401	gs_dyn_array_clear( tbl.data )
402
403#define gs_hash_table_remove( tbl, k )\
404	tbl.hash_remove_func( (void*)&(tbl), (k) )
405
406
407// Some typical hash tables
408
409// Hash table := key: u32, val: u32
410gs_hash_table_decl( u32, u32, gs_hash_u32, gs_hash_key_comp_std_type, (u32_max - 1), (u32_max - 1) );
411
412/*===================================
413// Slot Array
414===================================*/
415
416#define gs_slot_array_invalid_handle 	u32_max
417
418typedef struct 
419gs_slot_array_base
420{
421	gs_dyn_array( u32 )	handle_indices;
422	gs_dyn_array( u32 )	reverse_indirection_indices;
423	gs_dyn_array( u32 )	index_free_list;
424} gs_slot_array_base;
425
426#define gs_slot_array_decl( T )\
427	typedef struct gs_sa_##T\
428	{\
429		gs_slot_array_base _base;\
430		gs_dyn_array( T ) data;\
431		u32 ( * insert_func )( struct gs_sa_##T*, T );\
432		void ( * remove_func )( struct gs_sa_##T*, u32 );\
433	} gs_sa_##T;\
434\
435	_force_inline u32\
436	gs_sa_##T##_insert_func( struct gs_sa_##T* s, T v )\
437	{\
438		u32 free_idx = gs_slot_array_find_next_available_index( ( gs_slot_array_base* )s );\
439		gs_dyn_array_push( s->data, v );\
440		gs_dyn_array_push( s->_base.reverse_indirection_indices, free_idx );\
441		s->_base.handle_indices[ free_idx ] = gs_dyn_array_size( s->data ) - 1;\
442		return free_idx;\
443	}\
444\
445	_force_inline void\
446	gs_sa_##T##_remove_func( struct gs_sa_##T* s, u32 handle )\
447	{\
448		if ( gs_slot_array_handle_valid( *(s), handle ) ) {\
449			u32 idx = s->_base.handle_indices[ handle ];\
450			s->_base.handle_indices[ handle ] = gs_slot_array_invalid_handle;\
451			if ( gs_dyn_array_size( s->data ) > 1 ) {\
452				gs_dyn_array_swap( T, s->data, idx, gs_dyn_array_size( s->data ) - 1 );\
453				gs_dyn_array_swap( u32, s->_base.reverse_indirection_indices, idx, gs_dyn_array_size( s->_base.reverse_indirection_indices ) - 1 );\
454			}\
455			if ( !gs_dyn_array_empty( s->data ) ) {\
456				s->_base.handle_indices[ s->_base.reverse_indirection_indices[ idx ] ] = idx;\
457				gs_dyn_array_pop( s->data );\
458				gs_dyn_array_pop( s->_base.reverse_indirection_indices );\
459			}\
460			gs_dyn_array_push( s->_base.index_free_list, handle );\
461		}\
462	}\
463\
464	_force_inline\
465	gs_sa_##T __gs_sa_##T##_new()\
466	{\
467		gs_sa_##T sa;\
468		sa.data 								= gs_dyn_array_new( T );\
469		sa._base.handle_indices 				= gs_dyn_array_new( u32 );\
470		sa._base.reverse_indirection_indices 	= gs_dyn_array_new( u32 );\
471		sa._base.index_free_list 				= gs_dyn_array_new( u32 );\
472		sa.insert_func 							= &gs_sa_##T##_insert_func;\
473		sa.remove_func 							= &gs_sa_##T##_remove_func;\
474		return sa;\
475	}
476
477_force_inline u32
478gs_slot_array_find_next_available_index( gs_slot_array_base* sa )
479{
480	if ( gs_dyn_array_empty( sa->index_free_list ) ) {
481		gs_dyn_array_push( sa->handle_indices, 0 );
482		return ( gs_dyn_array_size( sa->handle_indices ) - 1 );
483	}
484	u32 idx = sa->index_free_list[ 0 ];
485	if ( gs_dyn_array_size( sa->index_free_list ) > 1 ) {
486		u32 sz = gs_dyn_array_size( sa->index_free_list );
487		u32 tmp = sa->index_free_list[ sz - 1 ];
488		sa->index_free_list[ 0 ] = tmp;
489		gs_dyn_array_pop( sa->index_free_list );
490	} else {
491		gs_dyn_array_clear( sa->index_free_list );	
492	}
493
494	return idx;
495}
496
497#define gs_slot_array_clear( s )\
498	do {\
499		gs_dyn_array_clear( s._base.handle_indices );\
500		gs_dyn_array_clear( s._base.index_free_list );\
501		gs_dyn_array_clear( s._base.reverse_indirection_indices );\
502		gs_dyn_array_clear( s.data );\
503	} while ( 0 )
504
505#define gs_slot_array_empty( s )\
506	gs_dyn_array_empty( (s) )
507
508#define gs_slot_array_size( s )\
509	gs_dyn_array_size( (s).data )
510
511#define gs_slot_array_handle_index( s, handle )\
512	s._base.handle_indices[ handle ]
513
514#define gs_slot_array_handle_size( s )\
515	gs_dyn_array_size( (s)._base.handle_indices )
516
517#define gs_slot_array_new( type )\
518	__gs_sa_##type##_new()
519
520#define gs_slot_array_insert( s, v )\
521	s.insert_func( &( s ), ( v ) )
522
523#define gs_slot_array_remove( s, handle )\
524	s.remove_func( &( s ), ( handle ) )
525
526#define gs_slot_array_handle_valid( s, handle )\
527	( handle >= 0 && handle < gs_slot_array_handle_size( (s) ) && gs_slot_array_handle_index( (s), handle ) < gs_slot_array_size( (s) ) )
528
529#define gs_slot_array_get( s, handle )\
530	( s.data[ s._base.handle_indices[ handle ] ] )
531
532#define gs_slot_array_get_unsafe( s, handle )\
533	( &s.data[ s._base.handle_indices[ handle ] ] )
534
535#define gs_slot_array_valid( s )\
536	( (s).data != NULL )
537
538#define gs_slot_array( T )\
539	gs_sa_##T
540
541
542#endif