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  /* 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  _Py_hashtable_get_entry(_Py_hashtable_t *ht, const void *key)
     122  {
     123      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 */