python3.13/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 // Export _Py_hashtable functions for '_testinternalcapi' shared extension
0074 PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new(
0075     _Py_hashtable_hash_func hash_func,
0076     _Py_hashtable_compare_func compare_func);
0077
0078 /* Hash a pointer (void*) */
0079 PyAPI_FUNC(Py_uhash_t) _Py_hashtable_hash_ptr(const void *key);
0080
0081 /* Comparison using memcmp() */
0082 PyAPI_FUNC(int) _Py_hashtable_compare_direct(
0083     const void *key1,
0084     const void *key2);
0085
0086 PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new_full(
0087     _Py_hashtable_hash_func hash_func,
0088     _Py_hashtable_compare_func compare_func,
0089     _Py_hashtable_destroy_func key_destroy_func,
0090     _Py_hashtable_destroy_func value_destroy_func,
0091     _Py_hashtable_allocator_t *allocator);
0092
0093 PyAPI_FUNC(void) _Py_hashtable_destroy(_Py_hashtable_t *ht);
0094
0095 PyAPI_FUNC(void) _Py_hashtable_clear(_Py_hashtable_t *ht);
0096
0097 typedef int (*_Py_hashtable_foreach_func) (_Py_hashtable_t *ht,
0098                                            const void *key, const void *value,
0099                                            void *user_data);
0100
0101 /* Call func() on each entry of the hashtable.
0102    Iteration stops if func() result is non-zero, in this case it's the result
0103    of the call. Otherwise, the function returns 0. */
0104 PyAPI_FUNC(int) _Py_hashtable_foreach(
0105     _Py_hashtable_t *ht,
0106     _Py_hashtable_foreach_func func,
0107     void *user_data);
0108
0109 PyAPI_FUNC(size_t) _Py_hashtable_size(const _Py_hashtable_t *ht);
0110 PyAPI_FUNC(size_t) _Py_hashtable_len(const _Py_hashtable_t *ht);
0111
0112 /* Add a new entry to the hash. The key must not be present in the hash table.
0113    Return 0 on success, -1 on memory error. */
0114 PyAPI_FUNC(int) _Py_hashtable_set(
0115     _Py_hashtable_t *ht,
0116     const void *key,
0117     void *value);
0118
0119
0120 /* Get an entry.
0121    Return NULL if the key does not exist. */
0122 static inline _Py_hashtable_entry_t *
0123 _Py_hashtable_get_entry(_Py_hashtable_t *ht, const void *key)
0124 {
0125     return ht->get_entry_func(ht, key);
0126 }
0127
0128
0129 /* Get value from an entry.
0130    Return NULL if the entry is not found.
0131
0132    Use _Py_hashtable_get_entry() to distinguish entry value equal to NULL
0133    and entry not found. */
0134 PyAPI_FUNC(void*) _Py_hashtable_get(_Py_hashtable_t *ht, const void *key);
0135
0136
0137 /* Remove a key and its associated value without calling key and value destroy
0138    functions.
0139
0140    Return the removed value if the key was found.
0141    Return NULL if the key was not found. */
0142 PyAPI_FUNC(void*) _Py_hashtable_steal(
0143     _Py_hashtable_t *ht,
0144     const void *key);
0145
0146
0147 #ifdef __cplusplus
0148 }
0149 #endif
0150 #endif   /* !Py_INTERNAL_HASHTABLE_H */