1 /* go-map-index.c -- find or insert an entry in a map.
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. */
11 #include "go-assert.h"
15 /* Rehash MAP to a larger size. */
18 __go_map_rehash (struct __go_map *map)
20 const struct __go_map_descriptor *descriptor;
21 const struct __go_type_descriptor *key_descriptor;
24 size_t (*hashfn) (const void *, size_t);
25 uintptr_t old_bucket_count;
27 uintptr_t new_bucket_count;
31 descriptor = map->__descriptor;
33 key_descriptor = descriptor->__map_descriptor->__key_type;
34 key_offset = descriptor->__key_offset;
35 key_size = key_descriptor->__size;
36 hashfn = key_descriptor->__hashfn;
38 old_bucket_count = map->__bucket_count;
39 old_buckets = map->__buckets;
41 new_bucket_count = __go_map_next_prime (old_bucket_count * 2);
42 new_buckets = (void **) __go_alloc (new_bucket_count * sizeof (void *));
43 __builtin_memset (new_buckets, 0, new_bucket_count * sizeof (void *));
45 for (i = 0; i < old_bucket_count; ++i)
50 for (entry = old_buckets[i]; entry != NULL; entry = next)
53 size_t new_bucket_index;
55 /* We could speed up rehashing at the cost of memory space
56 by caching the hash code. */
57 key_hash = hashfn (entry + key_offset, key_size);
58 new_bucket_index = key_hash % new_bucket_count;
60 next = *(char **) entry;
61 *(char **) entry = new_buckets[new_bucket_index];
62 new_buckets[new_bucket_index] = entry;
66 __go_free (old_buckets);
68 map->__bucket_count = new_bucket_count;
69 map->__buckets = new_buckets;
72 /* Find KEY in MAP, return a pointer to the value. If KEY is not
73 present, then if INSERT is false, return NULL, and if INSERT is
74 true, insert a new value and zero-initialize it before returning a
78 __go_map_index (struct __go_map *map, const void *key, _Bool insert)
80 const struct __go_map_descriptor *descriptor;
81 const struct __go_type_descriptor *key_descriptor;
83 _Bool (*equalfn) (const void*, const void*, size_t);
92 __go_panic_msg ("assignment to entry in nil map");
96 descriptor = map->__descriptor;
98 key_descriptor = descriptor->__map_descriptor->__key_type;
99 key_offset = descriptor->__key_offset;
100 key_size = key_descriptor->__size;
101 __go_assert (key_size != 0 && key_size != -1UL);
102 equalfn = key_descriptor->__equalfn;
104 key_hash = key_descriptor->__hashfn (key, key_size);
105 bucket_index = key_hash % map->__bucket_count;
107 entry = (char *) map->__buckets[bucket_index];
108 while (entry != NULL)
110 if (equalfn (key, entry + key_offset, key_size))
111 return entry + descriptor->__val_offset;
112 entry = *(char **) entry;
118 if (map->__element_count >= map->__bucket_count)
120 __go_map_rehash (map);
121 bucket_index = key_hash % map->__bucket_count;
124 entry = (char *) __go_alloc (descriptor->__entry_size);
125 __builtin_memset (entry, 0, descriptor->__entry_size);
127 __builtin_memcpy (entry + key_offset, key, key_size);
129 *(char **) entry = map->__buckets[bucket_index];
130 map->__buckets[bucket_index] = entry;
132 map->__element_count += 1;
134 return entry + descriptor->__val_offset;