"Fossies" - the Fresh Open Source Software Archive

Member "ponyc-0.33.2/src/libponyrt/ds/hash.h" (3 Feb 2020, 8076 Bytes) of package /linux/misc/ponyc-0.33.2.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "hash.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 0.33.1_vs_0.33.2.

    1 #ifndef ds_hash_h
    2 #define ds_hash_h
    3 
    4 #include "fun.h"
    5 #include "../pony.h"
    6 #include <stdint.h>
    7 #include <stdbool.h>
    8 #include <stddef.h>
    9 #include <platform.h>
   10 
   11 PONY_EXTERN_C_BEGIN
   12 
   13 #define HASHMAP_BEGIN ((size_t)-1)
   14 #define HASHMAP_UNKNOWN ((size_t)-1)
   15 
   16 typedef size_t bitmap_t;
   17 #ifdef PLATFORM_IS_ILP32
   18   #define HASHMAP_BITMAP_TYPE_BITS 5 // 2^5 = 32
   19 #else
   20   #define HASHMAP_BITMAP_TYPE_BITS 6 // 2^6 = 64
   21 #endif
   22 
   23 #define HASHMAP_BITMAP_TYPE_SIZE (1 << HASHMAP_BITMAP_TYPE_BITS)
   24 #define HASHMAP_BITMAP_TYPE_MASK (HASHMAP_BITMAP_TYPE_SIZE - 1)
   25 
   26 /** Definition of a hash map entry for uintptr_t.
   27  */
   28 typedef struct hashmap_entry_t
   29 {
   30   void* ptr;         /* pointer */
   31   size_t hash;       /* hash */
   32 } hashmap_entry_t;
   33 
   34 /** Definition of a linear probing robin hood hash map
   35  *  with backward shift deletion.
   36  *
   37  *  Do not access the fields of this type.
   38  */
   39 typedef struct hashmap_t
   40 {
   41   size_t count;   /* number of elements in the map */
   42   size_t size;    /* size of the buckets array */
   43   bitmap_t* item_bitmap;   /* Item bitarray to keep track items for optimized scanning */
   44   hashmap_entry_t* buckets;
   45 } hashmap_t;
   46 
   47 /** Initializes a new hash map.
   48  *
   49  *  This is a quadratic probing hash map.
   50  */
   51 void ponyint_hashmap_init(hashmap_t* map, size_t size);
   52 
   53 /** Destroys a hash map.
   54  *
   55  */
   56 void ponyint_hashmap_destroy(hashmap_t* map, free_fn free_elem);
   57 
   58 /** Optimize hashmap by iterating hashmap and calling optimize_item for each entry.
   59  */
   60 void ponyint_hashmap_optimize(hashmap_t* map, cmp_fn cmp);
   61 
   62 /** Retrieve an element from a hash map.
   63  *
   64  *  Returns a pointer to the element, or NULL.
   65  */
   66 void* ponyint_hashmap_get(hashmap_t* map, void* key, size_t hash, cmp_fn cmp, size_t* index);
   67 
   68 /** Put a new element in a hash map.
   69  *
   70  *  If the element (according to cmp_fn) is already in the hash map, the old
   71  *  element is overwritten and returned to the caller.
   72  */
   73 void* ponyint_hashmap_put(hashmap_t* map, void* entry, size_t hash, cmp_fn cmp);
   74 
   75 
   76 /** Put a new element in a hash map at a specific index (shifting other elements
   77  *  if necessary).
   78  */
   79 void ponyint_hashmap_putindex(hashmap_t* map, void* entry, size_t hash, cmp_fn cmp,
   80   size_t index);
   81 
   82 /** Removes a given entry from a hash map.
   83  *
   84  *  Returns the element removed (if any).
   85  */
   86 void* ponyint_hashmap_remove(hashmap_t* map, void* entry, size_t hash,
   87   cmp_fn cmp);
   88 
   89 /** Removes a given entry from a hash map by index.
   90  *
   91  *  Returns the element removed (if any).
   92  */
   93 void ponyint_hashmap_removeindex(hashmap_t* map, size_t index);
   94 
   95 /** Clears a given entry from a hash map by index.
   96  *
   97  *  Returns the element clear (if any).
   98  */
   99 void ponyint_hashmap_clearindex(hashmap_t* map, size_t index);
  100 
  101 /** Get the number of elements in the map.
  102  */
  103 size_t ponyint_hashmap_size(hashmap_t* map);
  104 
  105 /** Get the current fill ratio of the map.
  106  */
  107 double ponyint_hashmap_fill_ratio(hashmap_t* map);
  108 
  109 /** Get the memory used by the map.
  110  */
  111 size_t ponyint_hashmap_mem_size(hashmap_t* map);
  112 
  113 /** Get the memory allocated by the map.
  114  */
  115 size_t ponyint_hashmap_alloc_size(hashmap_t* map);
  116 
  117 /** Hashmap iterator.
  118  *
  119  *  Set i to HASHMAP_BEGIN, then call until this returns NULL.
  120  */
  121 void* ponyint_hashmap_next(size_t* i, size_t count, bitmap_t* item_bitmap,
  122   size_t size, hashmap_entry_t* buckets);
  123 
  124 void ponyint_hashmap_serialise_trace(pony_ctx_t* ctx, void* object,
  125   pony_type_t* elem_type);
  126 
  127 void ponyint_hashmap_serialise(pony_ctx_t* ctx, void* object, void* buf,
  128   size_t offset);
  129 
  130 void ponyint_hashmap_deserialise(pony_ctx_t* ctx, void* object,
  131   pony_type_t* elem_type);
  132 
  133 #define DECLARE_HASHMAP(name, name_t, type) \
  134   typedef struct name_t { hashmap_t contents; } name_t; \
  135   void name##_init(name_t* map, size_t size); \
  136   void name##_destroy(name_t* map); \
  137   void name##_optimize(name_t* map); \
  138   type* name##_get(name_t* map, type* key, size_t* index); \
  139   type* name##_put(name_t* map, type* entry); \
  140   void name##_putindex(name_t* map, type* entry, size_t index); \
  141   type* name##_remove(name_t* map, type* entry); \
  142   void name##_removeindex(name_t* map, size_t index); \
  143   void name##_clearindex(name_t* map, size_t index); \
  144   size_t name##_size(name_t* map); \
  145   double name##_fill_ratio(hashmap_t* map); \
  146   size_t name##_mem_size(name_t* map); \
  147   size_t name##_alloc_size(name_t* map); \
  148   type* name##_next(name_t* map, size_t* i); \
  149 
  150 #define DECLARE_HASHMAP_SERIALISE(name, name_t, type) \
  151   DECLARE_HASHMAP(name, name_t, type) \
  152   void name##_serialise_trace(pony_ctx_t* ctx, void* object); \
  153   void name##_serialise(pony_ctx_t* ctx, void* object, void* buf, \
  154     size_t offset, int mutability); \
  155   void name##_deserialise(pony_ctx_t* ctx, void* object); \
  156   const pony_type_t* name##_pony_type(); \
  157 
  158 #define DEFINE_HASHMAP(name, name_t, type, hash, cmp, free_elem) \
  159   typedef struct name_t name_t; \
  160   typedef bool (*name##_cmp_fn)(type* a, type* b); \
  161   typedef void (*name##_free_fn)(type* a); \
  162   \
  163   void name##_init(name_t* map, size_t size) \
  164   { \
  165     ponyint_hashmap_init((hashmap_t*)map, size); \
  166   } \
  167   void name##_destroy(name_t* map) \
  168   { \
  169     name##_free_fn freef = free_elem; \
  170     ponyint_hashmap_destroy((hashmap_t*)map, (free_fn)freef); \
  171   } \
  172   void name##_optimize(name_t* map) \
  173   { \
  174     name##_cmp_fn cmpf = cmp; \
  175     return ponyint_hashmap_optimize((hashmap_t*)map, (cmp_fn)cmpf); \
  176   } \
  177   type* name##_get(name_t* map, type* key, size_t* index) \
  178   { \
  179     name##_cmp_fn cmpf = cmp; \
  180     return (type*)ponyint_hashmap_get((hashmap_t*)map, (void*)key, \
  181       hash(key), (cmp_fn)cmpf, index); \
  182   } \
  183   type* name##_put(name_t* map, type* entry) \
  184   { \
  185     name##_cmp_fn cmpf = cmp; \
  186     return (type*)ponyint_hashmap_put((hashmap_t*)map, (void*)entry, \
  187       hash(entry), (cmp_fn)cmpf); \
  188   } \
  189   void name##_putindex(name_t* map, type* entry, size_t index) \
  190   { \
  191     name##_cmp_fn cmpf = cmp; \
  192     ponyint_hashmap_putindex((hashmap_t*)map, (void*)entry, \
  193       hash(entry), (cmp_fn)cmpf, index); \
  194   } \
  195   type* name##_remove(name_t* map, type* entry) \
  196   { \
  197     name##_cmp_fn cmpf = cmp; \
  198     return (type*)ponyint_hashmap_remove((hashmap_t*) map, (void*)entry, \
  199       hash(entry), (cmp_fn)cmpf); \
  200   } \
  201   void name##_removeindex(name_t* map, size_t index) \
  202   { \
  203     ponyint_hashmap_removeindex((hashmap_t*) map, index); \
  204   } \
  205   void name##_clearindex(name_t* map, size_t index) \
  206   { \
  207     ponyint_hashmap_clearindex((hashmap_t*) map, index); \
  208   } \
  209   size_t name##_size(name_t* map) \
  210   { \
  211     return ponyint_hashmap_size((hashmap_t*)map); \
  212   } \
  213   double name##_fill_ratio(hashmap_t* map) \
  214   { \
  215     return ponyint_hashmap_fill_ratio((hashmap_t*)map); \
  216   } \
  217   size_t name##_mem_size(name_t* map) \
  218   { \
  219     return ponyint_hashmap_mem_size((hashmap_t*)map); \
  220   } \
  221   size_t name##_alloc_size(name_t* map) \
  222   { \
  223     return ponyint_hashmap_alloc_size((hashmap_t*)map); \
  224   } \
  225   type* name##_next(name_t* map, size_t* i) \
  226   { \
  227     hashmap_t* h = (hashmap_t*)map; \
  228     return (type*)ponyint_hashmap_next(i, h->count, h->item_bitmap, \
  229       h->size, h->buckets); \
  230   } \
  231 
  232 #define DEFINE_HASHMAP_SERIALISE(name, name_t, type, hash, cmp, free_elem, elem_type) \
  233   DEFINE_HASHMAP(name, name_t, type, hash, cmp, free_elem) \
  234   void name##_serialise_trace(pony_ctx_t* ctx, void* object) \
  235   { \
  236     ponyint_hashmap_serialise_trace(ctx, object, elem_type); \
  237   } \
  238   void name##_serialise(pony_ctx_t* ctx, void* object, void* buf, \
  239     size_t offset, int mutability) \
  240   { \
  241     (void)mutability; \
  242     ponyint_hashmap_serialise(ctx, object, buf, offset); \
  243   } \
  244   void name##_deserialise(pony_ctx_t* ctx, void* object) \
  245   { \
  246     ponyint_hashmap_deserialise(ctx, object, elem_type); \
  247   } \
  248   static pony_type_t name##_pony = \
  249   { \
  250     0, \
  251     sizeof(name_t), \
  252     0, \
  253     0, \
  254     NULL, \
  255     NULL, \
  256     name##_serialise_trace, \
  257     name##_serialise, \
  258     name##_deserialise, \
  259     NULL, \
  260     NULL, \
  261     NULL, \
  262     NULL, \
  263     0, \
  264     NULL, \
  265     NULL, \
  266     NULL, \
  267   }; \
  268   const pony_type_t* name##_pony_type() \
  269   { \
  270     return &name##_pony; \
  271   } \
  272 
  273 #define HASHMAP_INIT {0, 0, NULL}
  274 
  275 PONY_EXTERN_C_END
  276 
  277 #endif