"Fossies" - the Fresh Open Source Software Archive

Member "ponyc-0.33.2/src/libponyrt/ds/hash.c" (3 Feb 2020, 18047 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.c" 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 #include "hash.h"
    2 #include "../gc/serialise.h"
    3 #include "ponyassert.h"
    4 #include <stdlib.h>
    5 #include <string.h>
    6 
    7 // Minimum HASHMAP size allowed
    8 #define MIN_HASHMAP_SIZE 8
    9 
   10 static size_t get_probe_length(hashmap_t* map, size_t hash, size_t current,
   11   size_t mask)
   12 {
   13   return (current + map->size - (hash & mask)) & mask;
   14 }
   15 
   16 static void* search(hashmap_t* map, size_t* pos, void* key, size_t hash,
   17   cmp_fn cmp, size_t* probe_length, size_t* oi_probe_length)
   18 {
   19   size_t mask = map->size - 1;
   20 
   21   size_t p_length = *probe_length;
   22   size_t oi_p_length = 0;
   23   size_t index = ((hash & mask) + p_length) & mask;
   24   void* elem;
   25   size_t elem_hash;
   26   size_t ib_index;
   27   size_t ib_offset;
   28 
   29   for(size_t i = 0; i <= mask; i++)
   30   {
   31     ib_index = index >> HASHMAP_BITMAP_TYPE_BITS;
   32     ib_offset = index & HASHMAP_BITMAP_TYPE_MASK;
   33 
   34     // if bucket is empty
   35     if((map->item_bitmap[ib_index] & ((bitmap_t)1 << ib_offset)) == 0)
   36     {
   37       // empty bucket found
   38       *pos = index;
   39       *probe_length = p_length;
   40       return NULL;
   41     }
   42 
   43     elem_hash = map->buckets[index].hash;
   44 
   45     if(p_length >
   46         (oi_p_length = get_probe_length(map, elem_hash, index, mask))) {
   47       // our probe length is greater than the elements probe length
   48       // we would normally have swapped so return this position
   49       *pos = index;
   50       *probe_length = p_length;
   51       *oi_probe_length = oi_p_length;
   52       return NULL;
   53     }
   54 
   55     if(hash == elem_hash) {
   56       elem = map->buckets[index].ptr;
   57       if(cmp(key, elem)) {
   58         // element found
   59         *pos = index;
   60         *probe_length = p_length;
   61         return elem;
   62       }
   63     }
   64 
   65     index = (index + 1) & mask;
   66     p_length++;
   67   }
   68 
   69   *pos = map->size;
   70   *probe_length = p_length;
   71   return NULL;
   72 }
   73 
   74 static void resize(hashmap_t* map, cmp_fn cmp)
   75 {
   76   size_t s = map->size;
   77   size_t c = map->count;
   78   hashmap_entry_t* b = map->buckets;
   79   bitmap_t* old_item_bitmap = map->item_bitmap;
   80   void* curr = NULL;
   81 
   82   map->count = 0;
   83   map->size = (s < MIN_HASHMAP_SIZE) ? MIN_HASHMAP_SIZE : s << 3;
   84 
   85   // use a single memory allocation to exploit spatial memory/cache locality
   86   size_t bitmap_size = (map->size >> HASHMAP_BITMAP_TYPE_BITS) +
   87     ((map->size& HASHMAP_BITMAP_TYPE_MASK)==0?0:1);
   88   void* mem_alloc = ponyint_pool_alloc_size((bitmap_size * sizeof(bitmap_t)) +
   89     (map->size * sizeof(hashmap_entry_t)));
   90   memset(mem_alloc, 0, (bitmap_size * sizeof(bitmap_t)));
   91   map->item_bitmap = (bitmap_t*)mem_alloc;
   92   map->buckets = (hashmap_entry_t*)((char *)mem_alloc +
   93     (bitmap_size * sizeof(bitmap_t)));
   94 
   95   // use hashmap scan to efficiently copy all items to new bucket array
   96   size_t i = HASHMAP_BEGIN;
   97   while((curr = ponyint_hashmap_next(&i, c, old_item_bitmap,
   98     s, b)) != NULL)
   99   {
  100     ponyint_hashmap_put(map, curr, b[i].hash, cmp);
  101   }
  102 
  103   if(b != NULL)
  104   {
  105     size_t old_bitmap_size = (s >> HASHMAP_BITMAP_TYPE_BITS) +
  106       ((s & HASHMAP_BITMAP_TYPE_MASK)==0?0:1);
  107     ponyint_pool_free_size((old_bitmap_size * sizeof(bitmap_t)) +
  108       (s * sizeof(hashmap_entry_t)), old_item_bitmap);
  109   }
  110 
  111   pony_assert(map->count == c);
  112 }
  113 
  114 static size_t optimize_item(hashmap_t* map, cmp_fn cmp, size_t old_index)
  115 {
  116   size_t mask = map->size - 1;
  117 
  118   size_t h = map->buckets[old_index].hash;
  119   void* entry = map->buckets[old_index].ptr;
  120   size_t index = h & mask;
  121 
  122   size_t ib_index;
  123   size_t ib_offset;
  124 
  125   for(size_t i = 0; i <= mask; i++)
  126   {
  127     // if next bucket index is current position, item is already in optimal spot
  128     if(index == old_index)
  129       break;
  130 
  131     ib_index = index >> HASHMAP_BITMAP_TYPE_BITS;
  132     ib_offset = index & HASHMAP_BITMAP_TYPE_MASK;
  133 
  134     // Reconstute our invariants
  135     //
  136     // During the process of removing "dead" items from our hash, it is
  137     // possible to violate the invariants of our map. We will now proceed to
  138     // detect and fix those violations.
  139     //
  140     // There are 2 possible invariant violations that we need to handle. One
  141     // is fairly simple, the other rather more complicated
  142     //
  143     // 1. We are no longer at our natural hash location AND that location is
  144     // empty. If that violation were allowed to continue then when searching
  145     // later, we'd find the empty bucket and stop looking for this hashed item.
  146     // Fixing this violation is handled by our `if` statement
  147     //
  148     // 2. Is a bit more complicated and is handled in our `else`
  149     // statement. It's possible while restoring invariants for our most
  150     // important invariant to get violated. That is, that items with a lower
  151     // probe count should appear before those with a higher probe count.
  152     // The else statement checks for this condition and repairs it.
  153     if((map->item_bitmap[ib_index] & ((bitmap_t)1 << ib_offset)) == 0)
  154     {
  155       ponyint_hashmap_clearindex(map, old_index);
  156       ponyint_hashmap_putindex(map, entry, h, cmp, index);
  157       return 1;
  158     }
  159     else
  160     {
  161       size_t item_probe_length =
  162         get_probe_length(map, h, index, mask);
  163       size_t there_probe_length =
  164         get_probe_length(map, map->buckets[index].hash, index, mask);
  165 
  166       if (item_probe_length > there_probe_length)
  167       {
  168         ponyint_hashmap_clearindex(map, old_index);
  169         ponyint_hashmap_putindex(map, entry, h, cmp, index);
  170         return 1;
  171       }
  172     }
  173     // find next bucket index
  174     index = (index + 1) & mask;
  175   }
  176 
  177   return 0;
  178 }
  179 
  180 void ponyint_hashmap_init(hashmap_t* map, size_t size)
  181 {
  182   // make sure we have room for this many elements without resizing
  183   size <<= 1;
  184 
  185   if(size < MIN_HASHMAP_SIZE)
  186     size = MIN_HASHMAP_SIZE;
  187   else
  188     size = ponyint_next_pow2(size);
  189 
  190   map->count = 0;
  191   map->size = size;
  192 
  193   // use a single memory allocation to exploit spatial memory/cache locality
  194   size_t bitmap_size = (size >> HASHMAP_BITMAP_TYPE_BITS) +
  195     ((size & HASHMAP_BITMAP_TYPE_MASK)==0?0:1);
  196   void* mem_alloc = ponyint_pool_alloc_size((bitmap_size * sizeof(bitmap_t)) +
  197     (size * sizeof(hashmap_entry_t)));
  198   memset(mem_alloc, 0, (bitmap_size * sizeof(bitmap_t)));
  199   map->item_bitmap = (bitmap_t*)mem_alloc;
  200   map->buckets = (hashmap_entry_t*)((char *)mem_alloc +
  201     (bitmap_size * sizeof(bitmap_t)));
  202 }
  203 
  204 void ponyint_hashmap_destroy(hashmap_t* map, free_fn free_elem)
  205 {
  206   if(free_elem != NULL)
  207   {
  208     void* curr = NULL;
  209 
  210     // use hashmap scan to efficiently free all items
  211     size_t i = HASHMAP_BEGIN;
  212     while((curr = ponyint_hashmap_next(&i, map->count, map->item_bitmap,
  213       map->size, map->buckets)) != NULL)
  214     {
  215       free_elem(curr);
  216     }
  217   }
  218 
  219   if(map->size > 0)
  220   {
  221     size_t bitmap_size = (map->size >> HASHMAP_BITMAP_TYPE_BITS) +
  222       ((map->size & HASHMAP_BITMAP_TYPE_MASK)==0?0:1);
  223     ponyint_pool_free_size((bitmap_size * sizeof(bitmap_t)) +
  224       (map->size * sizeof(hashmap_entry_t)), map->item_bitmap);
  225   }
  226 
  227   map->count = 0;
  228   map->size = 0;
  229   map->buckets = NULL;
  230   map->item_bitmap = NULL;
  231 }
  232 
  233 void* ponyint_hashmap_get(hashmap_t* map, void* key, size_t hash, cmp_fn cmp,
  234   size_t* pos)
  235 {
  236   if(map->count == 0)
  237     return NULL;
  238 
  239   size_t probe_length = 0;
  240   size_t oi_probe_length = 0;
  241   return search(map, pos, key, hash, cmp, &probe_length, &oi_probe_length);
  242 }
  243 
  244 static void shift_put(hashmap_t* map, void* entry, size_t hash, cmp_fn cmp,
  245   size_t index, size_t pl, size_t oi_pl, void *e)
  246 {
  247   void* elem = e;
  248 
  249   size_t ci_hash = hash;
  250   void* ci_entry = entry;
  251   size_t oi_hash = 0;
  252   void* oi_entry = NULL;
  253   size_t pos = index;
  254   size_t probe_length = pl;
  255   size_t oi_probe_length = oi_pl;
  256   size_t ib_index = pos >> HASHMAP_BITMAP_TYPE_BITS;
  257   size_t ib_offset = pos & HASHMAP_BITMAP_TYPE_MASK;
  258 
  259   pony_assert(probe_length > oi_probe_length ||
  260     (probe_length == oi_probe_length && probe_length == 0));
  261 
  262   while(true) {
  263     pony_assert(pos < map->size);
  264 
  265     // need to swap elements
  266     if(elem == NULL &&
  267       (map->item_bitmap[ib_index] & ((bitmap_t)1 << ib_offset)) != 0)
  268     {
  269       // save old element info
  270       oi_entry = map->buckets[pos].ptr;
  271       oi_hash = map->buckets[pos].hash;
  272 
  273       // put new element
  274       map->buckets[pos].ptr = ci_entry;
  275       map->buckets[pos].hash = ci_hash;
  276 
  277       // set currenty entry we're putting to be old entry
  278       ci_entry = oi_entry;
  279       ci_hash = oi_hash;
  280 
  281       // get old entry probe count
  282       probe_length = oi_probe_length;
  283 
  284       // find next item
  285       elem = search(map, &pos, ci_entry, ci_hash, cmp, &probe_length,
  286         &oi_probe_length);
  287 
  288       ib_index = pos >> HASHMAP_BITMAP_TYPE_BITS;
  289       ib_offset = pos & HASHMAP_BITMAP_TYPE_MASK;
  290 
  291       // keep going
  292       continue;
  293     }
  294 
  295     // put item into bucket
  296     map->buckets[pos].ptr = ci_entry;
  297     map->buckets[pos].hash = ci_hash;
  298 
  299     // we put a new item in an empty bucket
  300     if(elem == NULL)
  301     {
  302       map->count++;
  303 
  304       // update item bitmap
  305       map->item_bitmap[ib_index] |= ((bitmap_t)1 << ib_offset);
  306 
  307       if((map->count << 1) > map->size)
  308         resize(map, cmp);
  309     }
  310 
  311     return;
  312   }
  313 }
  314 
  315 void* ponyint_hashmap_put(hashmap_t* map, void* entry, size_t hash, cmp_fn cmp)
  316 {
  317   if(map->size == 0)
  318     ponyint_hashmap_init(map, 4);
  319 
  320   size_t pos;
  321   size_t probe_length = 0;
  322   size_t oi_probe_length = 0;
  323 
  324   void* elem = search(map, &pos, entry, hash, cmp, &probe_length,
  325     &oi_probe_length);
  326 
  327   shift_put(map, entry, hash, cmp, pos, probe_length, oi_probe_length, elem);
  328 
  329   return elem;
  330 }
  331 
  332 void ponyint_hashmap_putindex(hashmap_t* map, void* entry, size_t hash,
  333   cmp_fn cmp, size_t pos)
  334 {
  335   if(pos == HASHMAP_UNKNOWN)
  336   {
  337     ponyint_hashmap_put(map, entry, hash, cmp);
  338     return;
  339   }
  340 
  341   if(map->size == 0)
  342     ponyint_hashmap_init(map, 4);
  343 
  344   pony_assert(pos < map->size);
  345 
  346   size_t ib_index = pos >> HASHMAP_BITMAP_TYPE_BITS;
  347   size_t ib_offset = pos & HASHMAP_BITMAP_TYPE_MASK;
  348 
  349   // if bucket is empty
  350   if((map->item_bitmap[ib_index] & ((bitmap_t)1 << ib_offset)) == 0)
  351   {
  352     map->buckets[pos].ptr = entry;
  353     map->buckets[pos].hash = hash;
  354     map->count++;
  355 
  356     // update item bitmap
  357     map->item_bitmap[ib_index] |= ((bitmap_t)1 << ib_offset);
  358 
  359     if((map->count << 1) > map->size)
  360       resize(map, cmp);
  361   } else {
  362     size_t mask = map->size - 1;
  363 
  364     // save old item info
  365     size_t oi_hash = map->buckets[pos].hash;
  366     size_t oi_probe_length = get_probe_length(map, oi_hash, pos, mask);
  367 
  368     size_t ci_probe_length = get_probe_length(map, hash, pos, mask);
  369 
  370     // if item to be put has a greater probe length
  371     if(ci_probe_length > oi_probe_length)
  372     {
  373       // use shift_put to bump existing item
  374       shift_put(map, entry, hash, cmp, pos, ci_probe_length, oi_probe_length,
  375         NULL);
  376     } else {
  377       // we would break our smallest probe length wins guarantee
  378       // and so cannot bump existing element and need to put
  379       // new item via normal put operation
  380       ponyint_hashmap_put(map, entry, hash, cmp);
  381     }
  382   }
  383 }
  384 
  385 static void shift_delete(hashmap_t* map, size_t index)
  386 {
  387   pony_assert(index < map->size);
  388   size_t pos = index;
  389   size_t mask = map->size - 1;
  390   size_t next_pos = (pos + 1) & mask;
  391   size_t ni_hash = map->buckets[next_pos].hash;
  392   size_t ni_ib_index = next_pos >> HASHMAP_BITMAP_TYPE_BITS;
  393   size_t ni_ib_offset = next_pos & HASHMAP_BITMAP_TYPE_MASK;
  394 
  395   while((map->item_bitmap[ni_ib_index] & ((bitmap_t)1 << ni_ib_offset)) != 0
  396     && get_probe_length(map, ni_hash, next_pos, mask) != 0)
  397   {
  398     // shift item back into now empty bucket
  399     map->buckets[pos].ptr = map->buckets[next_pos].ptr;
  400     map->buckets[pos].hash = map->buckets[next_pos].hash;
  401 
  402     // increment position
  403     pos = next_pos;
  404     next_pos = (pos + 1) & mask;
  405 
  406     // get next item info
  407     ni_hash = map->buckets[next_pos].hash;
  408 
  409     ni_ib_index = next_pos >> HASHMAP_BITMAP_TYPE_BITS;
  410     ni_ib_offset = next_pos & HASHMAP_BITMAP_TYPE_MASK;
  411   }
  412 
  413   // done shifting all required elements; set current position as empty
  414   // and decrement count
  415   map->buckets[pos].ptr = NULL;
  416   map->count--;
  417 
  418   // update item bitmap
  419   size_t ib_index = pos >> HASHMAP_BITMAP_TYPE_BITS;
  420   size_t ib_offset = pos & HASHMAP_BITMAP_TYPE_MASK;
  421   map->item_bitmap[ib_index] &= ~((bitmap_t)1 << ib_offset);
  422 }
  423 
  424 void* ponyint_hashmap_remove(hashmap_t* map, void* entry, size_t hash,
  425   cmp_fn cmp)
  426 {
  427   if(map->count == 0)
  428     return NULL;
  429 
  430   size_t pos;
  431   size_t probe_length = 0;
  432   size_t oi_probe_length = 0;
  433   void* elem = search(map, &pos, entry, hash, cmp, &probe_length,
  434     &oi_probe_length);
  435 
  436   if(elem != NULL)
  437     shift_delete(map, pos);
  438 
  439   return elem;
  440 }
  441 
  442 void ponyint_hashmap_removeindex(hashmap_t* map, size_t index)
  443 {
  444   if(map->size <= index)
  445     return;
  446 
  447   size_t ib_index = index >> HASHMAP_BITMAP_TYPE_BITS;
  448   size_t ib_offset = index & HASHMAP_BITMAP_TYPE_MASK;
  449 
  450   // if bucket is not empty
  451   if((map->item_bitmap[ib_index] & ((bitmap_t)1 << ib_offset)) != 0)
  452     shift_delete(map, index);
  453 }
  454 
  455 void* ponyint_hashmap_next(size_t* i, size_t count, bitmap_t* item_bitmap,
  456   size_t size, hashmap_entry_t* buckets)
  457 {
  458   if(count == 0)
  459     return NULL;
  460 
  461   size_t index = *i + 1;
  462   size_t ib_index = index >> HASHMAP_BITMAP_TYPE_BITS;
  463   size_t ib_offset = index & HASHMAP_BITMAP_TYPE_MASK;
  464   size_t ffs_offset = 0;
  465 
  466   // get bitmap entry
  467   // right shift to get rid of old 1 bits we don't care about
  468   bitmap_t ib = item_bitmap[ib_index] >> ib_offset;
  469 
  470   while(index < size)
  471   {
  472     // find first set bit using ffs
  473     ffs_offset = __pony_ffszu(ib);
  474 
  475     // if no bits set; increment index to next item bitmap entry
  476     if(ffs_offset == 0)
  477     {
  478       index += (HASHMAP_BITMAP_TYPE_SIZE - ib_offset);
  479       ib_index++;
  480       ib_offset = 0;
  481       ib = item_bitmap[ib_index];
  482       continue;
  483     } else {
  484       // found a set bit for valid element
  485       index += (ffs_offset - 1);
  486 
  487       // no need to check if valid element because item bitmap keeps track of it
  488       pony_assert(buckets[index].ptr != NULL);
  489 
  490       *i = index;
  491       return buckets[index].ptr;
  492     }
  493   }
  494 
  495   // searched through bitmap and didn't find any more valid elements.
  496   // index could be bigger than size due to use of ffs
  497   *i = size;
  498   return NULL;
  499 }
  500 
  501 size_t ponyint_hashmap_size(hashmap_t* map)
  502 {
  503   return map->count;
  504 }
  505 
  506 double ponyint_hashmap_fill_ratio(hashmap_t* map)
  507 {
  508   return ((double)map->count/(double)map->size);
  509 }
  510 
  511 // mem_size == size of bitmap + size of all buckets.. this is regardless of
  512 // number of filled buckets as the memory is used once allocated
  513 size_t ponyint_hashmap_mem_size(hashmap_t* map)
  514 {
  515   size_t bitmap_size = (map->size >> HASHMAP_BITMAP_TYPE_BITS) +
  516     ((map->size & HASHMAP_BITMAP_TYPE_MASK)==0?0:1);
  517   return (bitmap_size * sizeof(bitmap_t)) +
  518     (map->size * sizeof(hashmap_entry_t));
  519 }
  520 
  521 // alloc_size == size of bitmap + size of all buckets
  522 size_t ponyint_hashmap_alloc_size(hashmap_t* map)
  523 {
  524   size_t size = ponyint_hashmap_mem_size(map);
  525   if(size == 0)
  526     return 0;
  527 
  528   return ponyint_pool_used_size(size);
  529 }
  530 
  531 void ponyint_hashmap_clearindex(hashmap_t* map, size_t index)
  532 {
  533   if(map->size <= index)
  534     return;
  535 
  536   size_t ib_index = index >> HASHMAP_BITMAP_TYPE_BITS;
  537   size_t ib_offset = index & HASHMAP_BITMAP_TYPE_MASK;
  538 
  539   // if bucket is empty
  540   if((map->item_bitmap[ib_index] & ((bitmap_t)1 << ib_offset)) == 0)
  541     return;
  542 
  543   map->buckets[index].ptr = NULL;
  544   map->count--;
  545 
  546   // update item bitmap
  547   map->item_bitmap[ib_index] &= ~((bitmap_t)1 << ib_offset);
  548 }
  549 
  550 void ponyint_hashmap_optimize(hashmap_t* map, cmp_fn cmp)
  551 {
  552   size_t count = 0;
  553   size_t num_iters = 0;
  554   size_t i = HASHMAP_BEGIN;
  555   void* elem;
  556 
  557   do
  558   {
  559     count = 0;
  560     i = HASHMAP_BEGIN;
  561     while((elem = ponyint_hashmap_next(&i, map->count, map->item_bitmap,
  562       map->size, map->buckets)) != NULL)
  563     {
  564       count += optimize_item(map, cmp, i);
  565     }
  566     num_iters++;
  567   } while(count > 0);
  568 }
  569 
  570 void ponyint_hashmap_serialise_trace(pony_ctx_t* ctx, void* object,
  571   pony_type_t* elem_type)
  572 {
  573   hashmap_t* map = (hashmap_t*)object;
  574 
  575   size_t bitmap_size = (map->size >> HASHMAP_BITMAP_TYPE_BITS) +
  576     ((map->size & HASHMAP_BITMAP_TYPE_MASK)==0?0:1);
  577   pony_serialise_reserve(ctx, map->item_bitmap,
  578     (bitmap_size * sizeof(bitmap_t)) + (map->size * sizeof(hashmap_entry_t)));
  579 
  580   size_t i = HASHMAP_BEGIN;
  581   void* elem;
  582 
  583   while((elem = ponyint_hashmap_next(&i, map->count, map->item_bitmap,
  584     map->size, map->buckets)) != NULL)
  585   {
  586     pony_traceknown(ctx, elem, elem_type, PONY_TRACE_MUTABLE);
  587   }
  588 }
  589 
  590 void ponyint_hashmap_serialise(pony_ctx_t* ctx, void* object, void* buf,
  591   size_t offset)
  592 {
  593   hashmap_t* map = (hashmap_t*)object;
  594   hashmap_t* dst = (hashmap_t*)((uintptr_t)buf + offset);
  595 
  596   uintptr_t bitmap_offset = pony_serialise_offset(ctx, map->item_bitmap);
  597 
  598   dst->count = map->count;
  599   dst->size = map->size;
  600   dst->item_bitmap = (bitmap_t*)bitmap_offset;
  601   dst->buckets = NULL;
  602 
  603   size_t bitmap_size = (map->size >> HASHMAP_BITMAP_TYPE_BITS) +
  604     ((map->size & HASHMAP_BITMAP_TYPE_MASK)==0?0:1);
  605   memcpy((void*)((uintptr_t)buf + bitmap_offset), map->item_bitmap,
  606     (bitmap_size * sizeof(bitmap_t)) + (map->size * sizeof(hashmap_entry_t)));
  607 
  608   hashmap_entry_t* dst_buckets = (hashmap_entry_t*)
  609     ((uintptr_t)buf + bitmap_offset + (bitmap_size * sizeof(bitmap_t)));
  610 
  611   size_t i = HASHMAP_BEGIN;
  612   void* elem;
  613 
  614   while((elem = ponyint_hashmap_next(&i, map->count, map->item_bitmap,
  615     map->size, map->buckets)) != NULL)
  616   {
  617     dst_buckets[i].ptr = (void*)pony_serialise_offset(ctx, elem);
  618     dst_buckets[i].hash = map->buckets[i].hash;
  619   }
  620 }
  621 
  622 void ponyint_hashmap_deserialise(pony_ctx_t* ctx, void* object,
  623   pony_type_t* elem_type)
  624 {
  625   hashmap_t* map = (hashmap_t*)object;
  626 
  627   size_t bitmap_size = (map->size >> HASHMAP_BITMAP_TYPE_BITS) +
  628     ((map->size & HASHMAP_BITMAP_TYPE_MASK)==0?0:1);
  629   map->item_bitmap =
  630     (bitmap_t*)pony_deserialise_block(ctx, (uintptr_t)map->item_bitmap,
  631       (bitmap_size * sizeof(bitmap_t)) + (map->size * sizeof(hashmap_entry_t)));
  632   map->buckets = (hashmap_entry_t*)((char*)map->item_bitmap +
  633     (bitmap_size * sizeof(bitmap_t)));
  634 
  635   size_t i = HASHMAP_BEGIN;
  636   void* elem;
  637 
  638   while((elem = ponyint_hashmap_next(&i, map->count, map->item_bitmap,
  639     map->size, map->buckets)) != NULL)
  640   {
  641     map->buckets[i].ptr = pony_deserialise_offset(ctx, elem_type,
  642       (uintptr_t)elem);
  643   }
  644 }