URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [tags/] [gnu-dev/] [fsf-gcc-snapshot-1-mar-12/] [or1k-gcc/] [libgo/] [runtime/] [go-map-index.c] - Rev 783
Compare with Previous | Blame | View Log
/* go-map-index.c -- find or insert an entry in a map. Copyright 2009 The Go Authors. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file. */ #include <stddef.h> #include <stdlib.h> #include "runtime.h" #include "go-alloc.h" #include "go-assert.h" #include "map.h" /* Rehash MAP to a larger size. */ static void __go_map_rehash (struct __go_map *map) { const struct __go_map_descriptor *descriptor; const struct __go_type_descriptor *key_descriptor; uintptr_t key_offset; size_t key_size; uintptr_t (*hashfn) (const void *, uintptr_t); uintptr_t old_bucket_count; void **old_buckets; uintptr_t new_bucket_count; void **new_buckets; uintptr_t i; descriptor = map->__descriptor; key_descriptor = descriptor->__map_descriptor->__key_type; key_offset = descriptor->__key_offset; key_size = key_descriptor->__size; hashfn = key_descriptor->__hashfn; old_bucket_count = map->__bucket_count; old_buckets = map->__buckets; new_bucket_count = __go_map_next_prime (old_bucket_count * 2); new_buckets = (void **) __go_alloc (new_bucket_count * sizeof (void *)); __builtin_memset (new_buckets, 0, new_bucket_count * sizeof (void *)); for (i = 0; i < old_bucket_count; ++i) { char* entry; char* next; for (entry = old_buckets[i]; entry != NULL; entry = next) { size_t key_hash; size_t new_bucket_index; /* We could speed up rehashing at the cost of memory space by caching the hash code. */ key_hash = hashfn (entry + key_offset, key_size); new_bucket_index = key_hash % new_bucket_count; next = *(char **) entry; *(char **) entry = new_buckets[new_bucket_index]; new_buckets[new_bucket_index] = entry; } } __go_free (old_buckets); map->__bucket_count = new_bucket_count; map->__buckets = new_buckets; } /* Find KEY in MAP, return a pointer to the value. If KEY is not present, then if INSERT is false, return NULL, and if INSERT is true, insert a new value and zero-initialize it before returning a pointer to it. */ void * __go_map_index (struct __go_map *map, const void *key, _Bool insert) { const struct __go_map_descriptor *descriptor; const struct __go_type_descriptor *key_descriptor; uintptr_t key_offset; _Bool (*equalfn) (const void*, const void*, uintptr_t); size_t key_hash; size_t key_size; size_t bucket_index; char *entry; if (map == NULL) { if (insert) runtime_panicstring ("assignment to entry in nil map"); return NULL; } descriptor = map->__descriptor; key_descriptor = descriptor->__map_descriptor->__key_type; key_offset = descriptor->__key_offset; key_size = key_descriptor->__size; __go_assert (key_size != 0 && key_size != -1UL); equalfn = key_descriptor->__equalfn; key_hash = key_descriptor->__hashfn (key, key_size); bucket_index = key_hash % map->__bucket_count; entry = (char *) map->__buckets[bucket_index]; while (entry != NULL) { if (equalfn (key, entry + key_offset, key_size)) return entry + descriptor->__val_offset; entry = *(char **) entry; } if (!insert) return NULL; if (map->__element_count >= map->__bucket_count) { __go_map_rehash (map); bucket_index = key_hash % map->__bucket_count; } entry = (char *) __go_alloc (descriptor->__entry_size); __builtin_memset (entry, 0, descriptor->__entry_size); __builtin_memcpy (entry + key_offset, key, key_size); *(char **) entry = map->__buckets[bucket_index]; map->__buckets[bucket_index] = entry; map->__element_count += 1; return entry + descriptor->__val_offset; }