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