python3.12/internal/pycore_hashtable.h

0001 #ifndef Py_INTERNAL_HASHTABLE_H
0002 #define Py_INTERNAL_HASHTABLE_H
0003 #ifdef __cplusplus
0004 extern "C" {
0005 #endif
0006
0007 #ifndef Py_BUILD_CORE
0008 #  error "this header requires Py_BUILD_CORE define"
0009 #endif
0010
0011 /* Single linked list */
0012
0013 typedef struct _Py_slist_item_s {
0014     struct _Py_slist_item_s *next;
0015 } _Py_slist_item_t;
0016
0017 typedef struct {
0018     _Py_slist_item_t *head;
0019 } _Py_slist_t;
0020
0021 #define _Py_SLIST_ITEM_NEXT(ITEM) _Py_RVALUE(((_Py_slist_item_t *)(ITEM))->next)
0022
0023 #define _Py_SLIST_HEAD(SLIST) _Py_RVALUE(((_Py_slist_t *)(SLIST))->head)
0024
0025
0026 /* _Py_hashtable: table entry */
0027
0028 typedef struct {
0029     /* used by _Py_hashtable_t.buckets to link entries */
0030     _Py_slist_item_t _Py_slist_item;
0031
0032     Py_uhash_t key_hash;
0033     void *key;
0034     void *value;
0035 } _Py_hashtable_entry_t;
0036
0037
0038 /* _Py_hashtable: prototypes */
0039
0040 /* Forward declaration */
0041 struct _Py_hashtable_t;
0042 typedef struct _Py_hashtable_t _Py_hashtable_t;
0043
0044 typedef Py_uhash_t (*_Py_hashtable_hash_func) (const void *key);
0045 typedef int (*_Py_hashtable_compare_func) (const void *key1, const void *key2);
0046 typedef void (*_Py_hashtable_destroy_func) (void *key);
0047 typedef _Py_hashtable_entry_t* (*_Py_hashtable_get_entry_func)(_Py_hashtable_t *ht,
0048                                                                const void *key);
0049
0050 typedef struct {
0051     // Allocate a memory block
0052     void* (*malloc) (size_t size);
0053
0054     // Release a memory block
0055     void (*free) (void *ptr);
0056 } _Py_hashtable_allocator_t;
0057
0058
0059 /* _Py_hashtable: table */
0060 struct _Py_hashtable_t {
0061     size_t nentries; // Total number of entries in the table
0062     size_t nbuckets;
0063     _Py_slist_t *buckets;
0064
0065     _Py_hashtable_get_entry_func get_entry_func;
0066     _Py_hashtable_hash_func hash_func;
0067     _Py_hashtable_compare_func compare_func;
0068     _Py_hashtable_destroy_func key_destroy_func;
0069     _Py_hashtable_destroy_func value_destroy_func;
0070     _Py_hashtable_allocator_t alloc;
0071 };
0072
0073 /* Hash a pointer (void*) */
0074 PyAPI_FUNC(Py_uhash_t) _Py_hashtable_hash_ptr(const void *key);
0075
0076 /* Comparison using memcmp() */
0077 PyAPI_FUNC(int) _Py_hashtable_compare_direct(
0078     const void *key1,
0079     const void *key2);
0080
0081 PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new(
0082     _Py_hashtable_hash_func hash_func,
0083     _Py_hashtable_compare_func compare_func);
0084
0085 PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new_full(
0086     _Py_hashtable_hash_func hash_func,
0087     _Py_hashtable_compare_func compare_func,
0088     _Py_hashtable_destroy_func key_destroy_func,
0089     _Py_hashtable_destroy_func value_destroy_func,
0090     _Py_hashtable_allocator_t *allocator);
0091
0092 PyAPI_FUNC(void) _Py_hashtable_destroy(_Py_hashtable_t *ht);
0093
0094 PyAPI_FUNC(void) _Py_hashtable_clear(_Py_hashtable_t *ht);
0095
0096 typedef int (*_Py_hashtable_foreach_func) (_Py_hashtable_t *ht,
0097                                            const void *key, const void *value,
0098                                            void *user_data);
0099
0100 /* Call func() on each entry of the hashtable.
0101    Iteration stops if func() result is non-zero, in this case it's the result
0102    of the call. Otherwise, the function returns 0. */
0103 PyAPI_FUNC(int) _Py_hashtable_foreach(
0104     _Py_hashtable_t *ht,
0105     _Py_hashtable_foreach_func func,
0106     void *user_data);
0107
0108 PyAPI_FUNC(size_t) _Py_hashtable_size(const _Py_hashtable_t *ht);
0109 PyAPI_FUNC(size_t) _Py_hashtable_len(const _Py_hashtable_t *ht);
0110
0111 /* Add a new entry to the hash. The key must not be present in the hash table.
0112    Return 0 on success, -1 on memory error. */
0113 PyAPI_FUNC(int) _Py_hashtable_set(
0114     _Py_hashtable_t *ht,
0115     const void *key,
0116     void *value);
0117
0118
0119 /* Get an entry.
0120    Return NULL if the key does not exist. */
0121 static inline _Py_hashtable_entry_t *
0122 _Py_hashtable_get_entry(_Py_hashtable_t *ht, const void *key)
0123 {
0124     return ht->get_entry_func(ht, key);
0125 }
0126
0127
0128 /* Get value from an entry.
0129    Return NULL if the entry is not found.
0130
0131    Use _Py_hashtable_get_entry() to distinguish entry value equal to NULL
0132    and entry not found. */
0133 PyAPI_FUNC(void*) _Py_hashtable_get(_Py_hashtable_t *ht, const void *key);
0134
0135
0136 /* Remove a key and its associated value without calling key and value destroy
0137    functions.
0138
0139    Return the removed value if the key was found.
0140    Return NULL if the key was not found. */
0141 PyAPI_FUNC(void*) _Py_hashtable_steal(
0142     _Py_hashtable_t *ht,
0143     const void *key);
0144
0145
0146 #ifdef __cplusplus
0147 }
0148 #endif
0149 #endif   /* !Py_INTERNAL_HASHTABLE_H */