1 #ifndef Py_INTERNAL_HASHTABLE_H
2 #define Py_INTERNAL_HASHTABLE_H
3 #ifdef __cplusplus
4 extern "C" {
5 #endif
6
7 #ifndef Py_BUILD_CORE
8 # error "this header requires Py_BUILD_CORE define"
9 #endif
10
11 /* Single linked list */
12
13 typedef struct _Py_slist_item_s {
14 struct _Py_slist_item_s *next;
15 } _Py_slist_item_t;
16
17 typedef struct {
18 _Py_slist_item_t *head;
19 } _Py_slist_t;
20
21 #define _Py_SLIST_ITEM_NEXT(ITEM) _Py_RVALUE(((_Py_slist_item_t *)(ITEM))->next)
22
23 #define _Py_SLIST_HEAD(SLIST) _Py_RVALUE(((_Py_slist_t *)(SLIST))->head)
24
25
26 /* _Py_hashtable: table entry */
27
28 typedef struct {
29 /* used by _Py_hashtable_t.buckets to link entries */
30 _Py_slist_item_t _Py_slist_item;
31
32 Py_uhash_t key_hash;
33 void *key;
34 void *value;
35 } _Py_hashtable_entry_t;
36
37
38 /* _Py_hashtable: prototypes */
39
40 /* Forward declaration */
41 struct _Py_hashtable_t;
42 typedef struct _Py_hashtable_t _Py_hashtable_t;
43
44 typedef Py_uhash_t (*_Py_hashtable_hash_func) (const void *key);
45 typedef int (*_Py_hashtable_compare_func) (const void *key1, const void *key2);
46 typedef void (*_Py_hashtable_destroy_func) (void *key);
47 typedef _Py_hashtable_entry_t* (*_Py_hashtable_get_entry_func)(_Py_hashtable_t *ht,
48 const void *key);
49
50 typedef struct {
51 // Allocate a memory block
52 void* (*malloc) (size_t size);
53
54 // Release a memory block
55 void (*free) (void *ptr);
56 } _Py_hashtable_allocator_t;
57
58
59 /* _Py_hashtable: table */
60 struct _Py_hashtable_t {
61 size_t nentries; // Total number of entries in the table
62 size_t nbuckets;
63 _Py_slist_t *buckets;
64
65 _Py_hashtable_get_entry_func get_entry_func;
66 _Py_hashtable_hash_func hash_func;
67 _Py_hashtable_compare_func compare_func;
68 _Py_hashtable_destroy_func key_destroy_func;
69 _Py_hashtable_destroy_func value_destroy_func;
70 _Py_hashtable_allocator_t alloc;
71 };
72
73 // Export _Py_hashtable functions for '_testinternalcapi' shared extension
74 PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new(
75 _Py_hashtable_hash_func hash_func,
76 _Py_hashtable_compare_func compare_func);
77
78 /* Hash a pointer (void*) */
79 PyAPI_FUNC(Py_uhash_t) _Py_hashtable_hash_ptr(const void *key);
80
81 /* Comparison using memcmp() */
82 PyAPI_FUNC(int) _Py_hashtable_compare_direct(
83 const void *key1,
84 const void *key2);
85
86 PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new_full(
87 _Py_hashtable_hash_func hash_func,
88 _Py_hashtable_compare_func compare_func,
89 _Py_hashtable_destroy_func key_destroy_func,
90 _Py_hashtable_destroy_func value_destroy_func,
91 _Py_hashtable_allocator_t *allocator);
92
93 PyAPI_FUNC(void) _Py_hashtable_destroy(_Py_hashtable_t *ht);
94
95 PyAPI_FUNC(void) _Py_hashtable_clear(_Py_hashtable_t *ht);
96
97 typedef int (*_Py_hashtable_foreach_func) (_Py_hashtable_t *ht,
98 const void *key, const void *value,
99 void *user_data);
100
101 /* Call func() on each entry of the hashtable.
102 Iteration stops if func() result is non-zero, in this case it's the result
103 of the call. Otherwise, the function returns 0. */
104 PyAPI_FUNC(int) _Py_hashtable_foreach(
105 _Py_hashtable_t *ht,
106 _Py_hashtable_foreach_func func,
107 void *user_data);
108
109 PyAPI_FUNC(size_t) _Py_hashtable_size(const _Py_hashtable_t *ht);
110 PyAPI_FUNC(size_t) _Py_hashtable_len(const _Py_hashtable_t *ht);
111
112 /* Add a new entry to the hash. The key must not be present in the hash table.
113 Return 0 on success, -1 on memory error. */
114 PyAPI_FUNC(int) _Py_hashtable_set(
115 _Py_hashtable_t *ht,
116 const void *key,
117 void *value);
118
119
120 /* Get an entry.
121 Return NULL if the key does not exist. */
122 static inline _Py_hashtable_entry_t *
_Py_hashtable_get_entry(_Py_hashtable_t * ht,const void * key)123 _Py_hashtable_get_entry(_Py_hashtable_t *ht, const void *key)
124 {
125 return ht->get_entry_func(ht, key);
126 }
127
128
129 /* Get value from an entry.
130 Return NULL if the entry is not found.
131
132 Use _Py_hashtable_get_entry() to distinguish entry value equal to NULL
133 and entry not found. */
134 PyAPI_FUNC(void*) _Py_hashtable_get(_Py_hashtable_t *ht, const void *key);
135
136
137 /* Remove a key and its associated value without calling key and value destroy
138 functions.
139
140 Return the removed value if the key was found.
141 Return NULL if the key was not found. */
142 PyAPI_FUNC(void*) _Py_hashtable_steal(
143 _Py_hashtable_t *ht,
144 const void *key);
145
146
147 #ifdef __cplusplus
148 }
149 #endif
150 #endif /* !Py_INTERNAL_HASHTABLE_H */
151