diff options
Diffstat (limited to 'src/pkg/runtime/hashmap.h')
| -rw-r--r-- | src/pkg/runtime/hashmap.h | 180 |
1 files changed, 14 insertions, 166 deletions
diff --git a/src/pkg/runtime/hashmap.h b/src/pkg/runtime/hashmap.h index 9b82f299e..2988417f6 100644 --- a/src/pkg/runtime/hashmap.h +++ b/src/pkg/runtime/hashmap.h @@ -2,180 +2,28 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -/* A hash table. - Example, hashing nul-terminated char*s: - hash_hash_t str_hash (void *v) { - char *s; - hash_hash_t hash = 0; - for (s = *(char **)v; *s != 0; s++) { - hash = (hash ^ *s) * 2654435769U; - } - return (hash); - } - int str_eq (void *a, void *b) { - return (strcmp (*(char **)a, *(char **)b) == 0); - } - void str_del (void *arg, void *data) { - *(char **)arg = *(char **)data; - } - - struct hash *h = hash_new (sizeof (char *), &str_hash, &str_eq, &str_del, 3, 12, 15); - ... 3=> 2**3 entries initial size - ... 12=> 2**12 entries before sprouting sub-tables - ... 15=> number of adjacent probes to attempt before growing - - Example lookup: - char *key = "foobar"; - char **result_ptr; - if (hash_lookup (h, &key, (void **) &result_ptr)) { - printf ("found in table: %s\n", *result_ptr); - } else { - printf ("not found in table\n"); - } - - Example insertion: - char *key = strdup ("foobar"); - char **result_ptr; - if (hash_lookup (h, &key, (void **) &result_ptr)) { - printf ("found in table: %s\n", *result_ptr); - printf ("to overwrite, do *result_ptr = key\n"); - } else { - printf ("not found in table; inserted as %s\n", *result_ptr); - assert (*result_ptr == key); - } - - Example deletion: - char *key = "foobar"; - char *result; - if (hash_remove (h, &key, &result)) { - printf ("key found and deleted from table\n"); - printf ("called str_del (&result, data) to copy data to result: %s\n", result); - } else { - printf ("not found in table\n"); - } - - Example iteration over the elements of *h: - char **data; - struct hash_iter it; - hash_iter_init (h, &it); - for (data = hash_next (&it); data != 0; data = hash_next (&it)) { - printf ("%s\n", *data); - } - */ - -#define memset(a,b,c) runtime·memclr((byte*)(a), (uint32)(c)) -#define memcpy(a,b,c) runtime·memmove((byte*)(a),(byte*)(b),(uint32)(c)) -#define assert(a) if(!(a)) runtime·throw("hashmap assert") -#define free(x) runtime·free(x) -#define memmove(a,b,c) runtime·memmove(a, b, c) - struct Hmap; /* opaque */ -struct hash_subtable; /* opaque */ -struct hash_entry; /* opaque */ - -typedef uintptr uintptr_t; -typedef uintptr_t hash_hash_t; - -struct hash_iter { - uint8* data; /* returned from next */ - int32 elemsize; /* size of elements in table */ - int32 changes; /* number of changes observed last time */ - int32 i; /* stack pointer in subtable_state */ - bool cycled; /* have reached the end and wrapped to 0 */ - hash_hash_t last_hash; /* last hash value returned */ - hash_hash_t cycle; /* hash value where we started */ - struct Hmap *h; /* the hash table */ - MapType *t; /* the map type */ - struct hash_iter_sub { - struct hash_entry *e; /* pointer into subtable */ - struct hash_entry *start; /* start of subtable */ - struct hash_entry *last; /* last entry in subtable */ - } subtable_state[4]; /* Should be large enough unless the hashing is - so bad that many distinct data values hash - to the same hash value. */ -}; - -/* Return a hashtable h 2**init_power empty entries, each with - "datasize" data bytes. - (*data_hash)(a) should return the hash value of data element *a. - (*data_eq)(a,b) should return whether the data at "a" and the data at "b" - are equal. - (*data_del)(arg, a) will be invoked when data element *a is about to be removed - from the table. "arg" is the argument passed to "hash_remove()". - - Growing is accomplished by resizing if the current tables size is less than - a threshold, and by adding subtables otherwise. hint should be set - the expected maximum size of the table. - "datasize" should be in [sizeof (void*), ..., 255]. If you need a - bigger "datasize", store a pointer to another piece of memory. */ - -//struct hash *hash_new (int32 datasize, -// hash_hash_t (*data_hash) (void *), -// int32 (*data_eq) (void *, void *), -// void (*data_del) (void *, void *), -// int64 hint); - -/* Lookup *data in *h. If the data is found, return 1 and place a pointer to - the found element in *pres. Otherwise return 0 and place 0 in *pres. */ -// int32 hash_lookup (struct hash *h, void *data, void **pres); - -/* Lookup *data in *h. If the data is found, execute (*data_del) (arg, p) - where p points to the data in the table, then remove it from *h and return - 1. Otherwise return 0. */ -// int32 hash_remove (struct hash *h, void *data, void *arg); - -/* Lookup *data in *h. If the data is found, return 1, and place a pointer - to the found element in *pres. Otherwise, return 0, allocate a region - for the data to be inserted, and place a pointer to the inserted element - in *pres; it is the caller's responsibility to copy the data to be - inserted to the pointer returned in *pres in this case. - - If using garbage collection, it is the caller's responsibility to - add references for **pres if HASH_ADDED is returned. */ -// int32 hash_insert (struct hash *h, void *data, void **pres); - -/* Return the number of elements in the table. */ -// uint32 hash_count (struct hash *h); - -/* The following call is useful only if not using garbage collection on the - table. - Remove all sub-tables associated with *h. - This undoes the effects of hash_init(). - If other memory pointed to by user data must be freed, the caller is - responsible for doing so by iterating over *h first; see - hash_iter_init()/hash_next(). */ -// void hash_destroy (struct hash *h); - -/*----- iteration -----*/ - -/* Initialize *it from *h. */ -// void hash_iter_init (struct hash *h, struct hash_iter *it); - -/* Return the next used entry in the table with which *it was initialized. */ -// void *hash_next (struct hash_iter *it); - -/*---- test interface ----*/ -/* Call (*data_visit) (arg, level, data) for every data entry in the table, - whether used or not. "level" is the subtable level, 0 means first level. */ -/* TESTING ONLY: DO NOT USE THIS ROUTINE IN NORMAL CODE */ -// void hash_visit (struct hash *h, void (*data_visit) (void *arg, int32 level, void *data), void *arg); /* Used by the garbage collector */ struct hash_gciter { - int32 elemsize; - uint8 flag; - uint8 valoff; - uint32 i; /* stack pointer in subtable_state */ - struct hash_subtable *st; - struct hash_gciter_sub { - struct hash_entry *e; /* pointer into subtable */ - struct hash_entry *last; /* last entry in subtable */ - } subtable_state[4]; + Hmap *h; + int32 phase; + uintptr bucket; + struct Bucket *b; + uintptr i; }; + +// this data is used by the garbage collector to keep the map's +// internal structures from being reclaimed. The iterator must +// return in st every live object (ones returned by mallocgc) so +// that those objects won't be collected, and it must return +// every key & value in key_data/val_data so they can get scanned +// for pointers they point to. Note that if you malloc storage +// for keys and values, you need to do both. struct hash_gciter_data { - struct hash_subtable *st; /* subtable pointer, or nil */ + uint8 *st; /* internal structure, or nil */ uint8 *key_data; /* key data, or nil */ uint8 *val_data; /* value data, or nil */ bool indirectkey; /* storing pointers to keys */ |