Branch data     Line data    Source code

       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_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                 :            : 
      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                 :            : /* Hash a pointer (void*) */
      74                 :            : PyAPI_FUNC(Py_uhash_t) _Py_hashtable_hash_ptr(const void *key);
      75                 :            : 
      76                 :            : /* Comparison using memcmp() */
      77                 :            : PyAPI_FUNC(int) _Py_hashtable_compare_direct(
      78                 :            :     const void *key1,
      79                 :            :     const void *key2);
      80                 :            : 
      81                 :            : PyAPI_FUNC(_Py_hashtable_t *) _Py_hashtable_new(
      82                 :            :     _Py_hashtable_hash_func hash_func,
      83                 :            :     _Py_hashtable_compare_func compare_func);
      84                 :            : 
      85                 :            : PyAPI_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                 :            : 
      92                 :            : PyAPI_FUNC(void) _Py_hashtable_destroy(_Py_hashtable_t *ht);
      93                 :            : 
      94                 :            : PyAPI_FUNC(void) _Py_hashtable_clear(_Py_hashtable_t *ht);
      95                 :            : 
      96                 :            : typedef 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. */
     103                 :            : PyAPI_FUNC(int) _Py_hashtable_foreach(
     104                 :            :     _Py_hashtable_t *ht,
     105                 :            :     _Py_hashtable_foreach_func func,
     106                 :            :     void *user_data);
     107                 :            : 
     108                 :            : PyAPI_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. */
     112                 :            : PyAPI_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. */
     120                 :            : static inline _Py_hashtable_entry_t *
     121                 :   12009204 : _Py_hashtable_get_entry(_Py_hashtable_t *ht, const void *key)
     122                 :            : {
     123                 :   12009204 :     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. */
     132                 :            : PyAPI_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. */
     140                 :            : PyAPI_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 */