1 #ifndef CGNS_HASHMAP_H 2 #define CGNS_HASHMAP_H 3 4 #include "vtk_cgns_mangle.h" 5 #include "cg_hash_types.h" 6 7 /* This is a simple hashmap inspired by cpython dict 8 * It maps a char[33] name to its array index. 9 * The indexing struct is compact to be cache friendly. 10 * One of the difficulty is to keep the hash table indices in sync 11 * with the cgns_zone list when there is deletion. 12 */ 13 #define MAP_MINSIZE 8 14 15 typedef struct { 16 /* Cached hash code of me_key. */ 17 map_ssize_t me_hash; /* signed integer same size as size_t */ 18 map_ssize_t me_value; /* index of key in mapped vector */ 19 char_name me_key; /* zone name */ 20 } cgns_hashmap_entry; 21 22 #define MAPIX_EMPTY (-1) 23 #define MAPIX_DUMMY (-2) 24 #define MAPIX_ERROR (-3) 25 26 struct _hashmapobject { 27 28 /* Size of the hash table (map_indices). It must be a power of 2. */ 29 map_ssize_t table_size; 30 31 /* Function to lookup in the hash table (dk_indices): 32 33 - lookdict_unicode(): specialized to Unicode string keys, comparison of 34 which can never raise an exception; that function can never return 35 DKIX_ERROR. 36 37 - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further 38 specialized for Unicode string keys that cannot be the <dummy> value.*/ 39 40 /* Number of usable entries in map_entries. */ 41 map_ssize_t map_usable; 42 43 /* Number of used entries in map_entries. */ 44 map_ssize_t map_nentries; 45 46 /* Actual hash table of map_size entries. It holds indices in map_entries, 47 or MAPIX_EMPTY(-1) or MAPIX_DUMMY(-2). 48 49 Indices must be: 0 <= indice < USABLE_FRACTION(map_size). 50 51 The size in bytes of an indice depends on map_size: 52 53 - 1 byte if map_size <= 0xff (char*) 54 - 2 bytes if map_size <= 0xffff (int16_t*) 55 - 4 bytes if map_size <= 0xffffffff (int32_t*) 56 - 8 bytes otherwise (int64_t*) 57 58 Dynamically sized, SIZEOF_VOID_P is minimum. */ 59 char map_indices[]; /* char is required to avoid strict aliasing. */ 60 61 /* "HashMapKeyEntry map_entries[dk_usable];" array follows: 62 see the MAP_ENTRIES() macro */ 63 }; 64 65 typedef struct _hashmapobject cgns_hashmap_keyobject; 66 67 typedef struct { 68 69 /* Number of items in the hashmap */ 70 map_ssize_t ma_used; 71 72 /* Key and values are stored in a combined continuous struct 73 to be cache friendly. */ 74 cgns_hashmap_keyobject *ma_keys; 75 76 } cgns_hashmap_object; 77 78 cgns_hashmap_object* cgi_new_hashmap(void); 79 cgns_hashmap_object* cgi_new_presized_hashmap(map_ssize_t minused); 80 void cgi_hashmap_clear(cgns_hashmap_object* op); 81 82 map_ssize_t cgi_map_get_item(cgns_hashmap_object* op, const char* key); 83 int cgi_map_set_item(cgns_hashmap_object* op, const char* key, map_ssize_t value); 84 int cgi_map_contains(cgns_hashmap_object* op, const char* key); 85 int cgi_map_del_shift_item(cgns_hashmap_object* op, const char* key); 86 87 #endif 88