libgo/runtime/go-map-index.c

   1 /* go-map-index.c -- find or insert an entry in a map.
   2
   3    Copyright 2009 The Go Authors. All rights reserved.
   4    Use of this source code is governed by a BSD-style
   5    license that can be found in the LICENSE file.  */
   6
   7 #include <stddef.h>
   8 #include <stdlib.h>
   9
  10 #include "runtime.h"
  11 #include "malloc.h"
  12 #include "go-alloc.h"
  13 #include "go-assert.h"
  14 #include "map.h"
  15
  16 /* Rehash MAP to a larger size.  */
  17
  18 static void
  19 __go_map_rehash (struct __go_map *map)
  20 {
  21   const struct __go_map_descriptor *descriptor;
  22   const struct __go_type_descriptor *key_descriptor;
  23   uintptr_t key_offset;
  24   size_t key_size;
  25   const FuncVal *hashfn;
  26   uintptr_t old_bucket_count;
  27   void **old_buckets;
  28   uintptr_t new_bucket_count;
  29   void **new_buckets;
  30   uintptr_t i;
  31
  32   descriptor = map->__descriptor;
  33
  34   key_descriptor = descriptor->__map_descriptor->__key_type;
  35   key_offset = descriptor->__key_offset;
  36   key_size = key_descriptor->__size;
  37   hashfn = key_descriptor->__hashfn;
  38
  39   old_bucket_count = map->__bucket_count;
  40   old_buckets = map->__buckets;
  41
  42   new_bucket_count = __go_map_next_prime (old_bucket_count * 2);
  43   new_buckets = (void **) __go_alloc (new_bucket_count * sizeof (void *));
  44   __builtin_memset (new_buckets, 0, new_bucket_count * sizeof (void *));
  45
  46   for (i = 0; i < old_bucket_count; ++i)
  47     {
  48       char* entry;
  49       char* next;
  50
  51       for (entry = old_buckets[i]; entry != NULL; entry = next)
  52         {
  53           size_t key_hash;
  54           size_t new_bucket_index;
  55
  56           /* We could speed up rehashing at the cost of memory space
  57              by caching the hash code.  */
  58           key_hash = __go_call_hashfn (hashfn, entry + key_offset, key_size);
  59           new_bucket_index = key_hash % new_bucket_count;
  60
  61           next = *(char **) entry;
  62           *(char **) entry = new_buckets[new_bucket_index];
  63           new_buckets[new_bucket_index] = entry;
  64         }
  65     }
  66
  67   if (old_bucket_count * sizeof (void *) >= TinySize)
  68     __go_free (old_buckets);
  69
  70   map->__bucket_count = new_bucket_count;
  71   map->__buckets = new_buckets;
  72 }
  73
  74 /* Find KEY in MAP, return a pointer to the value.  If KEY is not
  75    present, then if INSERT is false, return NULL, and if INSERT is
  76    true, insert a new value and zero-initialize it before returning a
  77    pointer to it.  */
  78
  79 void *
  80 __go_map_index (struct __go_map *map, const void *key, _Bool insert)
  81 {
  82   const struct __go_map_descriptor *descriptor;
  83   const struct __go_type_descriptor *key_descriptor;
  84   uintptr_t key_offset;
  85   const FuncVal *equalfn;
  86   size_t key_hash;
  87   size_t key_size;
  88   size_t bucket_index;
  89   char *entry;
  90
  91   if (map == NULL)
  92     {
  93       if (insert)
  94         runtime_panicstring ("assignment to entry in nil map");
  95       return NULL;
  96     }
  97
  98   descriptor = map->__descriptor;
  99
 100   key_descriptor = descriptor->__map_descriptor->__key_type;
 101   key_offset = descriptor->__key_offset;
 102   key_size = key_descriptor->__size;
 103   __go_assert (key_size != -1UL);
 104   equalfn = key_descriptor->__equalfn;
 105
 106   key_hash = __go_call_hashfn (key_descriptor->__hashfn, key, key_size);
 107   bucket_index = key_hash % map->__bucket_count;
 108
 109   entry = (char *) map->__buckets[bucket_index];
 110   while (entry != NULL)
 111     {
 112       if (__go_call_equalfn (equalfn, key, entry + key_offset, key_size))
 113         return entry + descriptor->__val_offset;
 114       entry = *(char **) entry;
 115     }
 116
 117   if (!insert)
 118     return NULL;
 119
 120   if (map->__element_count >= map->__bucket_count)
 121     {
 122       __go_map_rehash (map);
 123       bucket_index = key_hash % map->__bucket_count;
 124     }
 125
 126   entry = (char *) __go_alloc (descriptor->__entry_size);
 127   __builtin_memset (entry, 0, descriptor->__entry_size);
 128
 129   __builtin_memcpy (entry + key_offset, key, key_size);
 130
 131   *(char **) entry = map->__buckets[bucket_index];
 132   map->__buckets[bucket_index] = entry;
 133
 134   map->__element_count += 1;
 135
 136   return entry + descriptor->__val_offset;
 137 }