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