1 #ifndef Py_HASHTABLE_H 2 #define Py_HASHTABLE_H 3 /* The whole API is private */ 4 #ifndef Py_LIMITED_API 5 6 /* Single linked list */ 7 8 typedef struct _Py_slist_item_s { 9 struct _Py_slist_item_s *next; 10 } _Py_slist_item_t; 11 12 typedef struct { 13 _Py_slist_item_t *head; 14 } _Py_slist_t; 15 16 #define _Py_SLIST_ITEM_NEXT(ITEM) (((_Py_slist_item_t *)ITEM)->next) 17 18 #define _Py_SLIST_HEAD(SLIST) (((_Py_slist_t *)SLIST)->head) 19 20 21 /* _Py_hashtable: table entry */ 22 23 typedef struct { 24 /* used by _Py_hashtable_t.buckets to link entries */ 25 _Py_slist_item_t _Py_slist_item; 26 27 Py_uhash_t key_hash; 28 29 /* key (key_size bytes) and then data (data_size bytes) follows */ 30 } _Py_hashtable_entry_t; 31 32 #define _Py_HASHTABLE_ENTRY_PKEY(ENTRY) \ 33 ((const void *)((char *)(ENTRY) \ 34 + sizeof(_Py_hashtable_entry_t))) 35 36 #define _Py_HASHTABLE_ENTRY_PDATA(TABLE, ENTRY) \ 37 ((const void *)((char *)(ENTRY) \ 38 + sizeof(_Py_hashtable_entry_t) \ 39 + (TABLE)->key_size)) 40 41 /* Get a key value from pkey: use memcpy() rather than a pointer dereference 42 to avoid memory alignment issues. */ 43 #define _Py_HASHTABLE_READ_KEY(TABLE, PKEY, DST_KEY) \ 44 do { \ 45 assert(sizeof(DST_KEY) == (TABLE)->key_size); \ 46 memcpy(&(DST_KEY), (PKEY), sizeof(DST_KEY)); \ 47 } while (0) 48 49 #define _Py_HASHTABLE_ENTRY_READ_KEY(TABLE, ENTRY, KEY) \ 50 do { \ 51 assert(sizeof(KEY) == (TABLE)->key_size); \ 52 memcpy(&(KEY), _Py_HASHTABLE_ENTRY_PKEY(ENTRY), sizeof(KEY)); \ 53 } while (0) 54 55 #define _Py_HASHTABLE_ENTRY_READ_DATA(TABLE, ENTRY, DATA) \ 56 do { \ 57 assert(sizeof(DATA) == (TABLE)->data_size); \ 58 memcpy(&(DATA), _Py_HASHTABLE_ENTRY_PDATA(TABLE, (ENTRY)), \ 59 sizeof(DATA)); \ 60 } while (0) 61 62 #define _Py_HASHTABLE_ENTRY_WRITE_DATA(TABLE, ENTRY, DATA) \ 63 do { \ 64 assert(sizeof(DATA) == (TABLE)->data_size); \ 65 memcpy((void *)_Py_HASHTABLE_ENTRY_PDATA((TABLE), (ENTRY)), \ 66 &(DATA), sizeof(DATA)); \ 67 } while (0) 68 69 70 /* _Py_hashtable: prototypes */ 71 72 /* Forward declaration */ 73 struct _Py_hashtable_t; 74 75 typedef Py_uhash_t (*_Py_hashtable_hash_func) (struct _Py_hashtable_t *ht, 76 const void *pkey); 77 typedef int (*_Py_hashtable_compare_func) (struct _Py_hashtable_t *ht, 78 const void *pkey, 79 const _Py_hashtable_entry_t *he); 80 81 typedef struct { 82 /* allocate a memory block */ 83 void* (*malloc) (size_t size); 84 85 /* release a memory block */ 86 void (*free) (void *ptr); 87 } _Py_hashtable_allocator_t; 88 89 90 /* _Py_hashtable: table */ 91 92 typedef struct _Py_hashtable_t { 93 size_t num_buckets; 94 size_t entries; /* Total number of entries in the table. */ 95 _Py_slist_t *buckets; 96 size_t key_size; 97 size_t data_size; 98 99 _Py_hashtable_hash_func hash_func; 100 _Py_hashtable_compare_func compare_func; 101 _Py_hashtable_allocator_t alloc; 102 } _Py_hashtable_t; 103 104 /* hash a pointer (void*) */ 105 PyAPI_FUNC(Py_uhash_t) _Py_hashtable_hash_ptr( 106 struct _Py_hashtable_t *ht, 107 const void *pkey); 108 109 /* comparison using memcmp() */ 110 PyAPI_FUNC(int) _Py_hashtable_compare_direct( 111 _Py_hashtable_t *ht, 112 const void *pkey, 113 const _Py_hashtable_entry_t *entry); 114 115 PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new( 116 size_t key_size, 117 size_t data_size, 118 _Py_hashtable_hash_func hash_func, 119 _Py_hashtable_compare_func compare_func); 120 121 PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new_full( 122 size_t key_size, 123 size_t data_size, 124 size_t init_size, 125 _Py_hashtable_hash_func hash_func, 126 _Py_hashtable_compare_func compare_func, 127 _Py_hashtable_allocator_t *allocator); 128 129 PyAPI_FUNC(void) _Py_hashtable_destroy(_Py_hashtable_t *ht); 130 131 /* Return a copy of the hash table */ 132 PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_copy(_Py_hashtable_t *src); 133 134 PyAPI_FUNC(void) _Py_hashtable_clear(_Py_hashtable_t *ht); 135 136 typedef int (*_Py_hashtable_foreach_func) (_Py_hashtable_t *ht, 137 _Py_hashtable_entry_t *entry, 138 void *arg); 139 140 /* Call func() on each entry of the hashtable. 141 Iteration stops if func() result is non-zero, in this case it's the result 142 of the call. Otherwise, the function returns 0. */ 143 PyAPI_FUNC(int) _Py_hashtable_foreach( 144 _Py_hashtable_t *ht, 145 _Py_hashtable_foreach_func func, 146 void *arg); 147 148 PyAPI_FUNC(size_t) _Py_hashtable_size(_Py_hashtable_t *ht); 149 150 /* Add a new entry to the hash. The key must not be present in the hash table. 151 Return 0 on success, -1 on memory error. 152 153 Don't call directly this function, 154 but use _Py_HASHTABLE_SET() and _Py_HASHTABLE_SET_NODATA() macros */ 155 PyAPI_FUNC(int) _Py_hashtable_set( 156 _Py_hashtable_t *ht, 157 size_t key_size, 158 const void *pkey, 159 size_t data_size, 160 const void *data); 161 162 #define _Py_HASHTABLE_SET(TABLE, KEY, DATA) \ 163 _Py_hashtable_set(TABLE, sizeof(KEY), &(KEY), sizeof(DATA), &(DATA)) 164 165 #define _Py_HASHTABLE_SET_NODATA(TABLE, KEY) \ 166 _Py_hashtable_set(TABLE, sizeof(KEY), &(KEY), 0, NULL) 167 168 169 /* Get an entry. 170 Return NULL if the key does not exist. 171 172 Don't call directly this function, but use _Py_HASHTABLE_GET_ENTRY() 173 macro */ 174 PyAPI_FUNC(_Py_hashtable_entry_t*) _Py_hashtable_get_entry( 175 _Py_hashtable_t *ht, 176 size_t key_size, 177 const void *pkey); 178 179 #define _Py_HASHTABLE_GET_ENTRY(TABLE, KEY) \ 180 _Py_hashtable_get_entry(TABLE, sizeof(KEY), &(KEY)) 181 182 183 /* Get data from an entry. Copy entry data into data and return 1 if the entry 184 exists, return 0 if the entry does not exist. 185 186 Don't call directly this function, but use _Py_HASHTABLE_GET() macro */ 187 PyAPI_FUNC(int) _Py_hashtable_get( 188 _Py_hashtable_t *ht, 189 size_t key_size, 190 const void *pkey, 191 size_t data_size, 192 void *data); 193 194 #define _Py_HASHTABLE_GET(TABLE, KEY, DATA) \ 195 _Py_hashtable_get(TABLE, sizeof(KEY), &(KEY), sizeof(DATA), &(DATA)) 196 197 198 /* Don't call directly this function, but use _Py_HASHTABLE_POP() macro */ 199 PyAPI_FUNC(int) _Py_hashtable_pop( 200 _Py_hashtable_t *ht, 201 size_t key_size, 202 const void *pkey, 203 size_t data_size, 204 void *data); 205 206 #define _Py_HASHTABLE_POP(TABLE, KEY, DATA) \ 207 _Py_hashtable_pop(TABLE, sizeof(KEY), &(KEY), sizeof(DATA), &(DATA)) 208 209 210 #endif /* Py_LIMITED_API */ 211 #endif 212