| 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 * |
| 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 */ |