1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
// 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.
/* 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];
};
struct hash_gciter_data
{
struct hash_subtable *st; /* subtable pointer, or nil */
uint8 *key_data; /* key data, or nil */
uint8 *val_data; /* value data, or nil */
bool indirectkey; /* storing pointers to keys */
bool indirectval; /* storing pointers to values */
};
bool hash_gciter_init (struct Hmap *h, struct hash_gciter *it);
bool hash_gciter_next (struct hash_gciter *it, struct hash_gciter_data *data);
|
