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