1#ifndef Py_INTERNAL_HASHTABLE_H
2#define Py_INTERNAL_HASHTABLE_H
3#ifdef __cplusplus
4extern "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
13typedef struct _Py_slist_item_s {
14    struct _Py_slist_item_s *next;
15} _Py_slist_item_t;
16
17typedef struct {
18    _Py_slist_item_t *head;
19} _Py_slist_t;
20
21#define _Py_SLIST_ITEM_NEXT(ITEM) (((_Py_slist_item_t *)ITEM)->next)
22
23#define _Py_SLIST_HEAD(SLIST) (((_Py_slist_t *)SLIST)->head)
24
25
26/* _Py_hashtable: table entry */
27
28typedef 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 */
41struct _Py_hashtable_t;
42typedef struct _Py_hashtable_t _Py_hashtable_t;
43
44typedef Py_uhash_t (*_Py_hashtable_hash_func) (const void *key);
45typedef int (*_Py_hashtable_compare_func) (const void *key1, const void *key2);
46typedef void (*_Py_hashtable_destroy_func) (void *key);
47typedef _Py_hashtable_entry_t* (*_Py_hashtable_get_entry_func)(_Py_hashtable_t *ht,
48                                                               const void *key);
49
50typedef 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 */
60struct _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/* Hash a pointer (void*) */
74PyAPI_FUNC(Py_uhash_t) _Py_hashtable_hash_ptr(const void *key);
75
76/* Comparison using memcmp() */
77PyAPI_FUNC(int) _Py_hashtable_compare_direct(
78    const void *key1,
79    const void *key2);
80
81PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new(
82    _Py_hashtable_hash_func hash_func,
83    _Py_hashtable_compare_func compare_func);
84
85PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new_full(
86    _Py_hashtable_hash_func hash_func,
87    _Py_hashtable_compare_func compare_func,
88    _Py_hashtable_destroy_func key_destroy_func,
89    _Py_hashtable_destroy_func value_destroy_func,
90    _Py_hashtable_allocator_t *allocator);
91
92PyAPI_FUNC(void) _Py_hashtable_destroy(_Py_hashtable_t *ht);
93
94PyAPI_FUNC(void) _Py_hashtable_clear(_Py_hashtable_t *ht);
95
96typedef int (*_Py_hashtable_foreach_func) (_Py_hashtable_t *ht,
97                                           const void *key, const void *value,
98                                           void *user_data);
99
100/* Call func() on each entry of the hashtable.
101   Iteration stops if func() result is non-zero, in this case it's the result
102   of the call. Otherwise, the function returns 0. */
103PyAPI_FUNC(int) _Py_hashtable_foreach(
104    _Py_hashtable_t *ht,
105    _Py_hashtable_foreach_func func,
106    void *user_data);
107
108PyAPI_FUNC(size_t) _Py_hashtable_size(const _Py_hashtable_t *ht);
109
110/* Add a new entry to the hash. The key must not be present in the hash table.
111   Return 0 on success, -1 on memory error. */
112PyAPI_FUNC(int) _Py_hashtable_set(
113    _Py_hashtable_t *ht,
114    const void *key,
115    void *value);
116
117
118/* Get an entry.
119   Return NULL if the key does not exist. */
120static inline _Py_hashtable_entry_t *
121_Py_hashtable_get_entry(_Py_hashtable_t *ht, const void *key)
122{
123    return ht->get_entry_func(ht, key);
124}
125
126
127/* Get value from an entry.
128   Return NULL if the entry is not found.
129
130   Use _Py_hashtable_get_entry() to distinguish entry value equal to NULL
131   and entry not found. */
132PyAPI_FUNC(void*) _Py_hashtable_get(_Py_hashtable_t *ht, const void *key);
133
134
135/* Remove a key and its associated value without calling key and value destroy
136   functions.
137
138   Return the removed value if the key was found.
139   Return NULL if the key was not found. */
140PyAPI_FUNC(void*) _Py_hashtable_steal(
141    _Py_hashtable_t *ht,
142    const void *key);
143
144
145#ifdef __cplusplus
146}
147#endif
148#endif   /* !Py_INTERNAL_HASHTABLE_H */
149