summaryrefslogtreecommitdiff
path: root/src/pkg/runtime/hashmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/runtime/hashmap.c')
-rw-r--r--src/pkg/runtime/hashmap.c1166
1 files changed, 0 insertions, 1166 deletions
diff --git a/src/pkg/runtime/hashmap.c b/src/pkg/runtime/hashmap.c
deleted file mode 100644
index 5ba1eb20a..000000000
--- a/src/pkg/runtime/hashmap.c
+++ /dev/null
@@ -1,1166 +0,0 @@
-// 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 "runtime.h"
-#include "hashmap.h"
-#include "type.h"
-
-/* Return a pointer to the struct/union of type "type"
- whose "field" field is addressed by pointer "p". */
-
-struct Hmap { /* a hash table; initialize with hash_init() */
- uint32 count; /* elements in table - must be first */
-
- uint8 datasize; /* amount of data to store in entry */
- uint8 max_power; /* max power of 2 to create sub-tables */
- uint8 max_probes; /* max entries to probe before rehashing */
- uint8 indirectval; /* storing pointers to values */
- int32 changes; /* inc'ed whenever a subtable is created/grown */
- hash_hash_t (*data_hash) (uint32, void *a); /* return hash of *a */
- uint32 (*data_eq) (uint32, void *a, void *b); /* return whether *a == *b */
- void (*data_del) (uint32, void *arg, void *data); /* invoked on deletion */
- struct hash_subtable *st; /* first-level table */
-
- uint32 keysize;
- uint32 valsize;
- uint32 datavo;
-
- // three sets of offsets: the digit counts how many
- // of key, value are passed as inputs:
- // 0 = func() (key, value)
- // 1 = func(key) (value)
- // 2 = func(key, value)
- uint32 ko0;
- uint32 vo0;
- uint32 ko1;
- uint32 vo1;
- uint32 po1;
- uint32 ko2;
- uint32 vo2;
- uint32 po2;
- Alg* keyalg;
- Alg* valalg;
-};
-
-struct hash_entry {
- hash_hash_t hash; /* hash value of data */
- byte data[1]; /* user data has "datasize" bytes */
-};
-
-struct hash_subtable {
- uint8 power; /* bits used to index this table */
- uint8 used; /* bits in hash used before reaching this table */
- uint8 datasize; /* bytes of client data in an entry */
- uint8 max_probes; /* max number of probes when searching */
- int16 limit_bytes; /* max_probes * (datasize+sizeof (hash_hash_t)) */
- struct hash_entry *end; /* points just past end of entry[] */
- struct hash_entry entry[1]; /* 2**power+max_probes-1 elements of elemsize bytes */
-};
-
-#define HASH_DATA_EQ(h,x,y) ((*h->data_eq) (h->keysize, (x), (y)))
-
-#define HASH_REHASH 0x2 /* an internal flag */
-/* the number of bits used is stored in the flags word too */
-#define HASH_USED(x) ((x) >> 2)
-#define HASH_MAKE_USED(x) ((x) << 2)
-
-#define HASH_LOW 6
-#define HASH_ONE (((hash_hash_t)1) << HASH_LOW)
-#define HASH_MASK (HASH_ONE - 1)
-#define HASH_ADJUST(x) (((x) < HASH_ONE) << HASH_LOW)
-
-#define HASH_BITS (sizeof (hash_hash_t) * 8)
-
-#define HASH_SUBHASH HASH_MASK
-#define HASH_NIL 0
-#define HASH_NIL_MEMSET 0
-
-#define HASH_OFFSET(base, byte_offset) \
- ((struct hash_entry *) (((byte *) (base)) + (byte_offset)))
-
-
-/* return a hash layer with 2**power empty entries */
-static struct hash_subtable *
-hash_subtable_new (Hmap *h, int32 power, int32 used)
-{
- int32 elemsize = h->datasize + offsetof (struct hash_entry, data[0]);
- int32 bytes = elemsize << power;
- struct hash_subtable *st;
- int32 limit_bytes = h->max_probes * elemsize;
- int32 max_probes = h->max_probes;
-
- if (bytes < limit_bytes) {
- limit_bytes = bytes;
- max_probes = 1 << power;
- }
- bytes += limit_bytes - elemsize;
- st = malloc (offsetof (struct hash_subtable, entry[0]) + bytes);
- st->power = power;
- st->used = used;
- st->datasize = h->datasize;
- st->max_probes = max_probes;
- st->limit_bytes = limit_bytes;
- st->end = HASH_OFFSET (st->entry, bytes);
- memset (st->entry, HASH_NIL_MEMSET, bytes);
- return (st);
-}
-
-static void
-init_sizes (int64 hint, int32 *init_power, int32 *max_power)
-{
- int32 log = 0;
- int32 i;
-
- for (i = 32; i != 0; i >>= 1) {
- if ((hint >> (log + i)) != 0) {
- log += i;
- }
- }
- log += 1 + (((hint << 3) >> log) >= 11); /* round up for utilization */
- if (log <= 14) {
- *init_power = log;
- } else {
- *init_power = 12;
- }
- *max_power = 12;
-}
-
-static void
-hash_init (Hmap *h,
- int32 datasize,
- hash_hash_t (*data_hash) (uint32, void *),
- uint32 (*data_eq) (uint32, void *, void *),
- void (*data_del) (uint32, void *, void *),
- int64 hint)
-{
- int32 init_power;
- int32 max_power;
-
- if(datasize < sizeof (void *))
- datasize = sizeof (void *);
- datasize = runtime·rnd(datasize, sizeof (void *));
- init_sizes (hint, &init_power, &max_power);
- h->datasize = datasize;
- h->max_power = max_power;
- h->max_probes = 15;
- assert (h->datasize == datasize);
- assert (h->max_power == max_power);
- assert (sizeof (void *) <= h->datasize || h->max_power == 255);
- h->count = 0;
- h->changes = 0;
- h->data_hash = data_hash;
- h->data_eq = data_eq;
- h->data_del = data_del;
- h->st = hash_subtable_new (h, init_power, 0);
-}
-
-static void
-hash_remove_n (struct hash_subtable *st, struct hash_entry *dst_e, int32 n)
-{
- int32 elemsize = st->datasize + offsetof (struct hash_entry, data[0]);
- struct hash_entry *src_e = HASH_OFFSET (dst_e, n * elemsize);
- struct hash_entry *end_e = st->end;
- int32 shift = HASH_BITS - (st->power + st->used);
- int32 index_mask = (((hash_hash_t)1) << st->power) - 1;
- int32 dst_i = (((byte *) dst_e) - ((byte *) st->entry)) / elemsize;
- int32 src_i = dst_i + n;
- hash_hash_t hash;
- int32 skip;
- int32 bytes;
-
- while (dst_e != src_e) {
- if (src_e != end_e) {
- struct hash_entry *cp_e = src_e;
- int32 save_dst_i = dst_i;
- while (cp_e != end_e && (hash = cp_e->hash) != HASH_NIL &&
- ((hash >> shift) & index_mask) <= dst_i) {
- cp_e = HASH_OFFSET (cp_e, elemsize);
- dst_i++;
- }
- bytes = ((byte *) cp_e) - (byte *) src_e;
- memmove (dst_e, src_e, bytes);
- dst_e = HASH_OFFSET (dst_e, bytes);
- src_e = cp_e;
- src_i += dst_i - save_dst_i;
- if (src_e != end_e && (hash = src_e->hash) != HASH_NIL) {
- skip = ((hash >> shift) & index_mask) - dst_i;
- } else {
- skip = src_i - dst_i;
- }
- } else {
- skip = src_i - dst_i;
- }
- bytes = skip * elemsize;
- memset (dst_e, HASH_NIL_MEMSET, bytes);
- dst_e = HASH_OFFSET (dst_e, bytes);
- dst_i += skip;
- }
-}
-
-static int32
-hash_insert_internal (struct hash_subtable **pst, int32 flags, hash_hash_t hash,
- Hmap *h, void *data, void **pres);
-
-static void
-hash_conv (Hmap *h,
- struct hash_subtable *st, int32 flags,
- hash_hash_t hash,
- struct hash_entry *e)
-{
- int32 new_flags = (flags + HASH_MAKE_USED (st->power)) | HASH_REHASH;
- int32 shift = HASH_BITS - HASH_USED (new_flags);
- hash_hash_t prefix_mask = (-(hash_hash_t)1) << shift;
- int32 elemsize = h->datasize + offsetof (struct hash_entry, data[0]);
- void *dummy_result;
- struct hash_entry *de;
- int32 index_mask = (1 << st->power) - 1;
- hash_hash_t e_hash;
- struct hash_entry *pe = HASH_OFFSET (e, -elemsize);
-
- while (e != st->entry && (e_hash = pe->hash) != HASH_NIL && (e_hash & HASH_MASK) != HASH_SUBHASH) {
- e = pe;
- pe = HASH_OFFSET (pe, -elemsize);
- }
-
- de = e;
- while (e != st->end &&
- (e_hash = e->hash) != HASH_NIL &&
- (e_hash & HASH_MASK) != HASH_SUBHASH) {
- struct hash_entry *target_e = HASH_OFFSET (st->entry, ((e_hash >> shift) & index_mask) * elemsize);
- struct hash_entry *ne = HASH_OFFSET (e, elemsize);
- hash_hash_t current = e_hash & prefix_mask;
- if (de < target_e) {
- memset (de, HASH_NIL_MEMSET, ((byte *) target_e) - (byte *) de);
- de = target_e;
- }
- if ((hash & prefix_mask) == current ||
- (ne != st->end && (e_hash = ne->hash) != HASH_NIL &&
- (e_hash & prefix_mask) == current)) {
- struct hash_subtable *new_st = hash_subtable_new (h, 1, HASH_USED (new_flags));
- int32 rc = hash_insert_internal (&new_st, new_flags, e->hash, h, e->data, &dummy_result);
- assert (rc == 0);
- memcpy(dummy_result, e->data, h->datasize);
- e = ne;
- while (e != st->end && (e_hash = e->hash) != HASH_NIL && (e_hash & prefix_mask) == current) {
- assert ((e_hash & HASH_MASK) != HASH_SUBHASH);
- rc = hash_insert_internal (&new_st, new_flags, e_hash, h, e->data, &dummy_result);
- assert (rc == 0);
- memcpy(dummy_result, e->data, h->datasize);
- e = HASH_OFFSET (e, elemsize);
- }
- memset (de->data, HASH_NIL_MEMSET, h->datasize);
- *(struct hash_subtable **)de->data = new_st;
- de->hash = current | HASH_SUBHASH;
- } else {
- if (e != de) {
- memcpy (de, e, elemsize);
- }
- e = HASH_OFFSET (e, elemsize);
- }
- de = HASH_OFFSET (de, elemsize);
- }
- if (e != de) {
- hash_remove_n (st, de, (((byte *) e) - (byte *) de) / elemsize);
- }
-}
-
-static void
-hash_grow (Hmap *h, struct hash_subtable **pst, int32 flags)
-{
- struct hash_subtable *old_st = *pst;
- int32 elemsize = h->datasize + offsetof (struct hash_entry, data[0]);
- *pst = hash_subtable_new (h, old_st->power + 1, HASH_USED (flags));
- struct hash_entry *end_e = old_st->end;
- struct hash_entry *e;
- void *dummy_result;
- int32 used = 0;
-
- flags |= HASH_REHASH;
- for (e = old_st->entry; e != end_e; e = HASH_OFFSET (e, elemsize)) {
- hash_hash_t hash = e->hash;
- if (hash != HASH_NIL) {
- int32 rc = hash_insert_internal (pst, flags, e->hash, h, e->data, &dummy_result);
- assert (rc == 0);
- memcpy(dummy_result, e->data, h->datasize);
- used++;
- }
- }
- free (old_st);
-}
-
-static int32
-hash_lookup (Hmap *h, void *data, void **pres)
-{
- int32 elemsize = h->datasize + offsetof (struct hash_entry, data[0]);
- hash_hash_t hash = (*h->data_hash) (h->keysize, data) & ~HASH_MASK;
- struct hash_subtable *st = h->st;
- int32 used = 0;
- hash_hash_t e_hash;
- struct hash_entry *e;
- struct hash_entry *end_e;
-
- hash += HASH_ADJUST (hash);
- for (;;) {
- int32 shift = HASH_BITS - (st->power + used);
- int32 index_mask = (1 << st->power) - 1;
- int32 i = (hash >> shift) & index_mask; /* i is the natural position of hash */
-
- e = HASH_OFFSET (st->entry, i * elemsize); /* e points to element i */
- e_hash = e->hash;
- if ((e_hash & HASH_MASK) != HASH_SUBHASH) { /* a subtable */
- break;
- }
- used += st->power;
- st = *(struct hash_subtable **)e->data;
- }
- end_e = HASH_OFFSET (e, st->limit_bytes);
- while (e != end_e && (e_hash = e->hash) != HASH_NIL && e_hash < hash) {
- e = HASH_OFFSET (e, elemsize);
- }
- while (e != end_e && ((e_hash = e->hash) ^ hash) < HASH_SUBHASH) {
- if (HASH_DATA_EQ (h, data, e->data)) { /* a match */
- *pres = e->data;
- return (1);
- }
- e = HASH_OFFSET (e, elemsize);
- }
- USED(e_hash);
- *pres = 0;
- return (0);
-}
-
-static int32
-hash_remove (Hmap *h, void *data, void *arg)
-{
- int32 elemsize = h->datasize + offsetof (struct hash_entry, data[0]);
- hash_hash_t hash = (*h->data_hash) (h->keysize, data) & ~HASH_MASK;
- struct hash_subtable *st = h->st;
- int32 used = 0;
- hash_hash_t e_hash;
- struct hash_entry *e;
- struct hash_entry *end_e;
-
- hash += HASH_ADJUST (hash);
- for (;;) {
- int32 shift = HASH_BITS - (st->power + used);
- int32 index_mask = (1 << st->power) - 1;
- int32 i = (hash >> shift) & index_mask; /* i is the natural position of hash */
-
- e = HASH_OFFSET (st->entry, i * elemsize); /* e points to element i */
- e_hash = e->hash;
- if ((e_hash & HASH_MASK) != HASH_SUBHASH) { /* a subtable */
- break;
- }
- used += st->power;
- st = *(struct hash_subtable **)e->data;
- }
- end_e = HASH_OFFSET (e, st->limit_bytes);
- while (e != end_e && (e_hash = e->hash) != HASH_NIL && e_hash < hash) {
- e = HASH_OFFSET (e, elemsize);
- }
- while (e != end_e && ((e_hash = e->hash) ^ hash) < HASH_SUBHASH) {
- if (HASH_DATA_EQ (h, data, e->data)) { /* a match */
- (*h->data_del) (h->datavo, arg, e->data);
- hash_remove_n (st, e, 1);
- h->count--;
- return (1);
- }
- e = HASH_OFFSET (e, elemsize);
- }
- USED(e_hash);
- return (0);
-}
-
-static int32
-hash_insert_internal (struct hash_subtable **pst, int32 flags, hash_hash_t hash,
- Hmap *h, void *data, void **pres)
-{
- int32 elemsize = h->datasize + offsetof (struct hash_entry, data[0]);
-
- if ((flags & HASH_REHASH) == 0) {
- hash += HASH_ADJUST (hash);
- hash &= ~HASH_MASK;
- }
- for (;;) {
- struct hash_subtable *st = *pst;
- int32 shift = HASH_BITS - (st->power + HASH_USED (flags));
- int32 index_mask = (1 << st->power) - 1;
- int32 i = (hash >> shift) & index_mask; /* i is the natural position of hash */
- struct hash_entry *start_e =
- HASH_OFFSET (st->entry, i * elemsize); /* start_e is the pointer to element i */
- struct hash_entry *e = start_e; /* e is going to range over [start_e, end_e) */
- struct hash_entry *end_e;
- hash_hash_t e_hash = e->hash;
-
- if ((e_hash & HASH_MASK) == HASH_SUBHASH) { /* a subtable */
- pst = (struct hash_subtable **) e->data;
- flags += HASH_MAKE_USED (st->power);
- continue;
- }
- end_e = HASH_OFFSET (start_e, st->limit_bytes);
- while (e != end_e && (e_hash = e->hash) != HASH_NIL && e_hash < hash) {
- e = HASH_OFFSET (e, elemsize);
- i++;
- }
- if (e != end_e && e_hash != HASH_NIL) {
- /* ins_e ranges over the elements that may match */
- struct hash_entry *ins_e = e;
- int32 ins_i = i;
- hash_hash_t ins_e_hash;
- while (ins_e != end_e && ((e_hash = ins_e->hash) ^ hash) < HASH_SUBHASH) {
- if (HASH_DATA_EQ (h, data, ins_e->data)) { /* a match */
- *pres = ins_e->data;
- return (1);
- }
- assert (e_hash != hash || (flags & HASH_REHASH) == 0);
- hash += (e_hash == hash); /* adjust hash if it collides */
- ins_e = HASH_OFFSET (ins_e, elemsize);
- ins_i++;
- if (e_hash <= hash) { /* set e to insertion point */
- e = ins_e;
- i = ins_i;
- }
- }
- /* set ins_e to the insertion point for the new element */
- ins_e = e;
- ins_i = i;
- ins_e_hash = 0;
- /* move ins_e to point at the end of the contiguous block, but
- stop if any element can't be moved by one up */
- while (ins_e != st->end && (ins_e_hash = ins_e->hash) != HASH_NIL &&
- ins_i + 1 - ((ins_e_hash >> shift) & index_mask) < st->max_probes &&
- (ins_e_hash & HASH_MASK) != HASH_SUBHASH) {
- ins_e = HASH_OFFSET (ins_e, elemsize);
- ins_i++;
- }
- if (e == end_e || ins_e == st->end || ins_e_hash != HASH_NIL) {
- e = end_e; /* can't insert; must grow or convert to subtable */
- } else { /* make space for element */
- memmove (HASH_OFFSET (e, elemsize), e, ((byte *) ins_e) - (byte *) e);
- }
- }
- if (e != end_e) {
- e->hash = hash;
- *pres = e->data;
- return (0);
- }
- h->changes++;
- if (st->power < h->max_power) {
- hash_grow (h, pst, flags);
- } else {
- hash_conv (h, st, flags, hash, start_e);
- }
- }
-}
-
-static int32
-hash_insert (Hmap *h, void *data, void **pres)
-{
- int32 rc = hash_insert_internal (&h->st, 0, (*h->data_hash) (h->keysize, data), h, data, pres);
-
- h->count += (rc == 0); /* increment count if element didn't previously exist */
- return (rc);
-}
-
-static uint32
-hash_count (Hmap *h)
-{
- return (h->count);
-}
-
-static void
-iter_restart (struct hash_iter *it, struct hash_subtable *st, int32 used)
-{
- int32 elemsize = it->elemsize;
- hash_hash_t last_hash = it->last_hash;
- struct hash_entry *e;
- hash_hash_t e_hash;
- struct hash_iter_sub *sub = &it->subtable_state[it->i];
- struct hash_entry *end;
-
- for (;;) {
- int32 shift = HASH_BITS - (st->power + used);
- int32 index_mask = (1 << st->power) - 1;
- int32 i = (last_hash >> shift) & index_mask;
-
- end = st->end;
- e = HASH_OFFSET (st->entry, i * elemsize);
- sub->start = st->entry;
- sub->end = end;
-
- if ((e->hash & HASH_MASK) != HASH_SUBHASH) {
- break;
- }
- sub->e = HASH_OFFSET (e, elemsize);
- sub = &it->subtable_state[++(it->i)];
- used += st->power;
- st = *(struct hash_subtable **)e->data;
- }
- while (e != end && ((e_hash = e->hash) == HASH_NIL || e_hash <= last_hash)) {
- e = HASH_OFFSET (e, elemsize);
- }
- sub->e = e;
-}
-
-static void *
-hash_next (struct hash_iter *it)
-{
- int32 elemsize = it->elemsize;
- struct hash_iter_sub *sub = &it->subtable_state[it->i];
- struct hash_entry *e = sub->e;
- struct hash_entry *end = sub->end;
- hash_hash_t e_hash = 0;
-
- if (it->changes != it->h->changes) { /* hash table's structure changed; recompute */
- it->changes = it->h->changes;
- it->i = 0;
- iter_restart (it, it->h->st, 0);
- sub = &it->subtable_state[it->i];
- e = sub->e;
- end = sub->end;
- }
- if (e != sub->start && it->last_hash != HASH_OFFSET (e, -elemsize)->hash) {
- struct hash_entry *start = HASH_OFFSET (e, -(elemsize * it->h->max_probes));
- struct hash_entry *pe = HASH_OFFSET (e, -elemsize);
- hash_hash_t last_hash = it->last_hash;
- if (start < sub->start) {
- start = sub->start;
- }
- while (e != start && ((e_hash = pe->hash) == HASH_NIL || last_hash < e_hash)) {
- e = pe;
- pe = HASH_OFFSET (pe, -elemsize);
- }
- while (e != end && ((e_hash = e->hash) == HASH_NIL || e_hash <= last_hash)) {
- e = HASH_OFFSET (e, elemsize);
- }
- }
-
- for (;;) {
- while (e != end && (e_hash = e->hash) == HASH_NIL) {
- e = HASH_OFFSET (e, elemsize);
- }
- if (e == end) {
- if (it->i == 0) {
- it->last_hash = HASH_OFFSET (e, -elemsize)->hash;
- sub->e = e;
- return (0);
- } else {
- it->i--;
- sub = &it->subtable_state[it->i];
- e = sub->e;
- end = sub->end;
- }
- } else if ((e_hash & HASH_MASK) != HASH_SUBHASH) {
- it->last_hash = e->hash;
- sub->e = HASH_OFFSET (e, elemsize);
- return (e->data);
- } else {
- struct hash_subtable *st =
- *(struct hash_subtable **)e->data;
- sub->e = HASH_OFFSET (e, elemsize);
- it->i++;
- assert (it->i < sizeof (it->subtable_state) /
- sizeof (it->subtable_state[0]));
- sub = &it->subtable_state[it->i];
- sub->e = e = st->entry;
- sub->start = st->entry;
- sub->end = end = st->end;
- }
- }
-}
-
-static void
-hash_iter_init (Hmap *h, struct hash_iter *it)
-{
- it->elemsize = h->datasize + offsetof (struct hash_entry, data[0]);
- it->changes = h->changes;
- it->i = 0;
- it->h = h;
- it->last_hash = 0;
- it->subtable_state[0].e = h->st->entry;
- it->subtable_state[0].start = h->st->entry;
- it->subtable_state[0].end = h->st->end;
-}
-
-static void
-clean_st (struct hash_subtable *st, int32 *slots, int32 *used)
-{
- int32 elemsize = st->datasize + offsetof (struct hash_entry, data[0]);
- struct hash_entry *e = st->entry;
- struct hash_entry *end = st->end;
- int32 lslots = (((byte *) end) - (byte *) e) / elemsize;
- int32 lused = 0;
-
- while (e != end) {
- hash_hash_t hash = e->hash;
- if ((hash & HASH_MASK) == HASH_SUBHASH) {
- clean_st (*(struct hash_subtable **)e->data, slots, used);
- } else {
- lused += (hash != HASH_NIL);
- }
- e = HASH_OFFSET (e, elemsize);
- }
- free (st);
- *slots += lslots;
- *used += lused;
-}
-
-static void
-hash_destroy (Hmap *h)
-{
- int32 slots = 0;
- int32 used = 0;
-
- clean_st (h->st, &slots, &used);
- free (h);
-}
-
-static void
-hash_visit_internal (struct hash_subtable *st,
- int32 used, int32 level,
- void (*data_visit) (void *arg, int32 level, void *data),
- void *arg)
-{
- int32 elemsize = st->datasize + offsetof (struct hash_entry, data[0]);
- struct hash_entry *e = st->entry;
- int32 shift = HASH_BITS - (used + st->power);
- int32 i = 0;
-
- while (e != st->end) {
- int32 index = ((e->hash >> (shift - 1)) >> 1) & ((1 << st->power) - 1);
- if ((e->hash & HASH_MASK) == HASH_SUBHASH) {
- (*data_visit) (arg, level, e->data);
- hash_visit_internal (*(struct hash_subtable **)e->data,
- used + st->power, level + 1, data_visit, arg);
- } else {
- (*data_visit) (arg, level, e->data);
- }
- if (e->hash != HASH_NIL) {
- assert (i < index + st->max_probes);
- assert (index <= i);
- }
- e = HASH_OFFSET (e, elemsize);
- i++;
- }
-}
-
-static void
-hash_visit (Hmap *h, void (*data_visit) (void *arg, int32 level, void *data), void *arg)
-{
- hash_visit_internal (h->st, 0, 0, data_visit, arg);
-}
-
-//
-/// interfaces to go runtime
-//
-
-// hash requires < 256 bytes of data (key+value) stored inline.
-// Only basic types can be key - biggest is complex128 (16 bytes).
-// Leave some room to grow, just in case.
-enum {
- MaxValsize = 256 - 64
-};
-
-static void
-donothing(uint32 s, void *a, void *b)
-{
- USED(s);
- USED(a);
- USED(b);
-}
-
-static void
-freedata(uint32 datavo, void *a, void *b)
-{
- void *p;
-
- USED(a);
- p = *(void**)((byte*)b + datavo);
- free(p);
-}
-
-static void**
-hash_indirect(Hmap *h, void *p)
-{
- if(h->indirectval)
- p = *(void**)p;
- return p;
-}
-
-static int32 debug = 0;
-
-// makemap(key, val *Type, hint uint32) (hmap *map[any]any);
-Hmap*
-runtime·makemap_c(Type *key, Type *val, int64 hint)
-{
- Hmap *h;
- int32 keyalg, valalg, keysize, valsize, valsize_in_hash;
- void (*data_del)(uint32, void*, void*);
-
- if(hint < 0 || (int32)hint != hint)
- runtime·panicstring("makemap: size out of range");
-
- keyalg = key->alg;
- valalg = val->alg;
- keysize = key->size;
- valsize = val->size;
-
- if(keyalg >= nelem(runtime·algarray) || runtime·algarray[keyalg].hash == runtime·nohash) {
- runtime·printf("map(keyalg=%d)\n", keyalg);
- runtime·throw("runtime.makemap: unsupported map key type");
- }
-
- if(valalg >= nelem(runtime·algarray)) {
- runtime·printf("map(valalg=%d)\n", valalg);
- runtime·throw("runtime.makemap: unsupported map value type");
- }
-
- h = runtime·mal(sizeof(*h));
-
- valsize_in_hash = valsize;
- data_del = donothing;
- if (valsize > MaxValsize) {
- h->indirectval = 1;
- data_del = freedata;
- valsize_in_hash = sizeof(void*);
- }
-
- // align value inside data so that mark-sweep gc can find it.
- // might remove in the future and just assume datavo == keysize.
- h->datavo = keysize;
- if(valsize_in_hash >= sizeof(void*))
- h->datavo = runtime·rnd(keysize, sizeof(void*));
-
- hash_init(h, h->datavo+valsize_in_hash,
- runtime·algarray[keyalg].hash,
- runtime·algarray[keyalg].equal,
- data_del,
- hint);
-
- h->keysize = keysize;
- h->valsize = valsize;
- h->keyalg = &runtime·algarray[keyalg];
- h->valalg = &runtime·algarray[valalg];
-
- // these calculations are compiler dependent.
- // figure out offsets of map call arguments.
-
- // func() (key, val)
- h->ko0 = runtime·rnd(sizeof(h), Structrnd);
- h->vo0 = runtime·rnd(h->ko0+keysize, val->align);
-
- // func(key) (val[, pres])
- h->ko1 = runtime·rnd(sizeof(h), key->align);
- h->vo1 = runtime·rnd(h->ko1+keysize, Structrnd);
- h->po1 = runtime·rnd(h->vo1+valsize, 1);
-
- // func(key, val[, pres])
- h->ko2 = runtime·rnd(sizeof(h), key->align);
- h->vo2 = runtime·rnd(h->ko2+keysize, val->align);
- h->po2 = runtime·rnd(h->vo2+valsize, 1);
-
- if(debug) {
- runtime·printf("makemap: map=%p; keysize=%d; valsize=%d; keyalg=%d; valalg=%d; offsets=%d,%d; %d,%d,%d; %d,%d,%d\n",
- h, keysize, valsize, keyalg, valalg, h->ko0, h->vo0, h->ko1, h->vo1, h->po1, h->ko2, h->vo2, h->po2);
- }
-
- return h;
-}
-
-// makemap(key, val *Type, hint int64) (hmap *map[any]any);
-void
-runtime·makemap(Type *key, Type *val, int64 hint, Hmap *ret)
-{
- ret = runtime·makemap_c(key, val, hint);
- FLUSH(&ret);
-}
-
-// For reflect:
-// func makemap(Type *mapType) (hmap *map)
-void
-reflect·makemap(MapType *t, Hmap *ret)
-{
- ret = runtime·makemap_c(t->key, t->elem, 0);
- FLUSH(&ret);
-}
-
-void
-runtime·mapaccess(Hmap *h, byte *ak, byte *av, bool *pres)
-{
- byte *res;
-
- if(h == nil)
- runtime·panicstring("lookup in nil map");
-
- if(runtime·gcwaiting)
- runtime·gosched();
-
- res = nil;
- if(hash_lookup(h, ak, (void**)&res)) {
- *pres = true;
- h->valalg->copy(h->valsize, av, hash_indirect(h, res+h->datavo));
- } else {
- *pres = false;
- h->valalg->copy(h->valsize, av, nil);
- }
-}
-
-// mapaccess1(hmap *map[any]any, key any) (val any);
-#pragma textflag 7
-void
-runtime·mapaccess1(Hmap *h, ...)
-{
- byte *ak, *av;
- bool pres;
-
- if(h == nil)
- runtime·panicstring("lookup in nil map");
-
- ak = (byte*)&h + h->ko1;
- av = (byte*)&h + h->vo1;
-
- runtime·mapaccess(h, ak, av, &pres);
-
- if(debug) {
- runtime·prints("runtime.mapaccess1: map=");
- runtime·printpointer(h);
- runtime·prints("; key=");
- h->keyalg->print(h->keysize, ak);
- runtime·prints("; val=");
- h->valalg->print(h->valsize, av);
- runtime·prints("; pres=");
- runtime·printbool(pres);
- runtime·prints("\n");
- }
-}
-
-// mapaccess2(hmap *map[any]any, key any) (val any, pres bool);
-#pragma textflag 7
-void
-runtime·mapaccess2(Hmap *h, ...)
-{
- byte *ak, *av, *ap;
-
- if(h == nil)
- runtime·panicstring("lookup in nil map");
-
- ak = (byte*)&h + h->ko1;
- av = (byte*)&h + h->vo1;
- ap = (byte*)&h + h->po1;
-
- runtime·mapaccess(h, ak, av, ap);
-
- if(debug) {
- runtime·prints("runtime.mapaccess2: map=");
- runtime·printpointer(h);
- runtime·prints("; key=");
- h->keyalg->print(h->keysize, ak);
- runtime·prints("; val=");
- h->valalg->print(h->valsize, av);
- runtime·prints("; pres=");
- runtime·printbool(*ap);
- runtime·prints("\n");
- }
-}
-
-// For reflect:
-// func mapaccess(h map, key iword) (val iword, pres bool)
-// where an iword is the same word an interface value would use:
-// the actual data if it fits, or else a pointer to the data.
-void
-reflect·mapaccess(Hmap *h, uintptr key, uintptr val, bool pres)
-{
- byte *ak, *av;
-
- if(h == nil)
- runtime·panicstring("lookup in nil map");
- if(h->keysize <= sizeof(key))
- ak = (byte*)&key;
- else
- ak = (byte*)key;
- val = 0;
- pres = false;
- if(h->valsize <= sizeof(val))
- av = (byte*)&val;
- else {
- av = runtime·mal(h->valsize);
- val = (uintptr)av;
- }
- runtime·mapaccess(h, ak, av, &pres);
- FLUSH(&val);
- FLUSH(&pres);
-}
-
-void
-runtime·mapassign(Hmap *h, byte *ak, byte *av)
-{
- byte *res;
- int32 hit;
-
- if(h == nil)
- runtime·panicstring("assignment to entry in nil map");
-
- if(runtime·gcwaiting)
- runtime·gosched();
-
- res = nil;
- if(av == nil) {
- hash_remove(h, ak, (void**)&res);
- return;
- }
-
- hit = hash_insert(h, ak, (void**)&res);
- if(!hit && h->indirectval)
- *(void**)(res+h->datavo) = runtime·mal(h->valsize);
- h->keyalg->copy(h->keysize, res, ak);
- h->valalg->copy(h->valsize, hash_indirect(h, res+h->datavo), av);
-
- if(debug) {
- runtime·prints("mapassign: map=");
- runtime·printpointer(h);
- runtime·prints("; key=");
- h->keyalg->print(h->keysize, ak);
- runtime·prints("; val=");
- h->valalg->print(h->valsize, av);
- runtime·prints("; hit=");
- runtime·printint(hit);
- runtime·prints("; res=");
- runtime·printpointer(res);
- runtime·prints("\n");
- }
-}
-
-// mapassign1(hmap *map[any]any, key any, val any);
-#pragma textflag 7
-void
-runtime·mapassign1(Hmap *h, ...)
-{
- byte *ak, *av;
-
- if(h == nil)
- runtime·panicstring("assignment to entry in nil map");
-
- ak = (byte*)&h + h->ko2;
- av = (byte*)&h + h->vo2;
-
- runtime·mapassign(h, ak, av);
-}
-
-// mapassign2(hmap *map[any]any, key any, val any, pres bool);
-#pragma textflag 7
-void
-runtime·mapassign2(Hmap *h, ...)
-{
- byte *ak, *av, *ap;
-
- if(h == nil)
- runtime·panicstring("assignment to entry in nil map");
-
- ak = (byte*)&h + h->ko2;
- av = (byte*)&h + h->vo2;
- ap = (byte*)&h + h->po2;
-
- if(*ap == false)
- av = nil; // delete
-
- runtime·mapassign(h, ak, av);
-
- if(debug) {
- runtime·prints("mapassign2: map=");
- runtime·printpointer(h);
- runtime·prints("; key=");
- h->keyalg->print(h->keysize, ak);
- runtime·prints("\n");
- }
-}
-
-// For reflect:
-// func mapassign(h map, key, val iword, pres bool)
-// where an iword is the same word an interface value would use:
-// the actual data if it fits, or else a pointer to the data.
-void
-reflect·mapassign(Hmap *h, uintptr key, uintptr val, bool pres)
-{
- byte *ak, *av;
-
- if(h == nil)
- runtime·panicstring("lookup in nil map");
- if(h->keysize <= sizeof(key))
- ak = (byte*)&key;
- else
- ak = (byte*)key;
- if(h->valsize <= sizeof(val))
- av = (byte*)&val;
- else
- av = (byte*)val;
- if(!pres)
- av = nil;
- runtime·mapassign(h, ak, av);
-}
-
-// mapiterinit(hmap *map[any]any, hiter *any);
-void
-runtime·mapiterinit(Hmap *h, struct hash_iter *it)
-{
- if(h == nil) {
- it->data = nil;
- return;
- }
- hash_iter_init(h, it);
- it->data = hash_next(it);
- if(debug) {
- runtime·prints("runtime.mapiterinit: map=");
- runtime·printpointer(h);
- runtime·prints("; iter=");
- runtime·printpointer(it);
- runtime·prints("; data=");
- runtime·printpointer(it->data);
- runtime·prints("\n");
- }
-}
-
-// For reflect:
-// func mapiterinit(h map) (it iter)
-void
-reflect·mapiterinit(Hmap *h, struct hash_iter *it)
-{
- it = runtime·mal(sizeof *it);
- FLUSH(&it);
- runtime·mapiterinit(h, it);
-}
-
-// mapiternext(hiter *any);
-void
-runtime·mapiternext(struct hash_iter *it)
-{
- if(runtime·gcwaiting)
- runtime·gosched();
-
- it->data = hash_next(it);
- if(debug) {
- runtime·prints("runtime.mapiternext: iter=");
- runtime·printpointer(it);
- runtime·prints("; data=");
- runtime·printpointer(it->data);
- runtime·prints("\n");
- }
-}
-
-// For reflect:
-// func mapiternext(it iter)
-void
-reflect·mapiternext(struct hash_iter *it)
-{
- runtime·mapiternext(it);
-}
-
-// mapiter1(hiter *any) (key any);
-#pragma textflag 7
-void
-runtime·mapiter1(struct hash_iter *it, ...)
-{
- Hmap *h;
- byte *ak, *res;
-
- h = it->h;
- ak = (byte*)&it + h->ko0;
-
- res = it->data;
- if(res == nil)
- runtime·throw("runtime.mapiter1: key:val nil pointer");
-
- h->keyalg->copy(h->keysize, ak, res);
-
- if(debug) {
- runtime·prints("mapiter2: iter=");
- runtime·printpointer(it);
- runtime·prints("; map=");
- runtime·printpointer(h);
- runtime·prints("\n");
- }
-}
-
-bool
-runtime·mapiterkey(struct hash_iter *it, void *ak)
-{
- Hmap *h;
- byte *res;
-
- h = it->h;
- res = it->data;
- if(res == nil)
- return false;
- h->keyalg->copy(h->keysize, ak, res);
- return true;
-}
-
-// For reflect:
-// func mapiterkey(h map) (key iword, ok bool)
-// where an iword is the same word an interface value would use:
-// the actual data if it fits, or else a pointer to the data.
-void
-reflect·mapiterkey(struct hash_iter *it, uintptr key, bool ok)
-{
- Hmap *h;
- byte *res;
-
- key = 0;
- ok = false;
- h = it->h;
- res = it->data;
- if(res == nil) {
- key = 0;
- ok = false;
- } else {
- key = 0;
- if(h->keysize <= sizeof(key))
- h->keyalg->copy(h->keysize, (byte*)&key, res);
- else
- key = (uintptr)res;
- ok = true;
- }
- FLUSH(&key);
- FLUSH(&ok);
-}
-
-// For reflect:
-// func maplen(h map) (len int32)
-// Like len(m) in the actual language, we treat the nil map as length 0.
-void
-reflect·maplen(Hmap *h, int32 len)
-{
- if(h == nil)
- len = 0;
- else
- len = h->count;
- FLUSH(&len);
-}
-
-// mapiter2(hiter *any) (key any, val any);
-#pragma textflag 7
-void
-runtime·mapiter2(struct hash_iter *it, ...)
-{
- Hmap *h;
- byte *ak, *av, *res;
-
- h = it->h;
- ak = (byte*)&it + h->ko0;
- av = (byte*)&it + h->vo0;
-
- res = it->data;
- if(res == nil)
- runtime·throw("runtime.mapiter2: key:val nil pointer");
-
- h->keyalg->copy(h->keysize, ak, res);
- h->valalg->copy(h->valsize, av, hash_indirect(h, res+h->datavo));
-
- if(debug) {
- runtime·prints("mapiter2: iter=");
- runtime·printpointer(it);
- runtime·prints("; map=");
- runtime·printpointer(h);
- runtime·prints("\n");
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2025-05-14 13:43:07 +0000