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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
/*
--------------------------------------------------------------------
By Bob Jenkins, 1996. hash.h. Public Domain.
This implements a hash table.
* Keys are unique. Adding an item fails if the key is already there.
* Keys and items are pointed at, not copied. If you change the value
of the key after it is inserted then hfind will not be able to find it.
* The hash table maintains a position that can be set and queried.
* The table length doubles dynamically and never shrinks. The insert
that causes table doubling may take a long time.
* The table length splits when the table length equals the number of items
Comparisons usually take 7 instructions.
Computing a hash value takes 35+6n instructions for an n-byte key.
hcreate - create a hash table
hdestroy - destroy a hash table
hcount - The number of items in the hash table
hkey - key at the current position
hkeyl - key length at the current position
hstuff - stuff at the current position
hfind - find an item in the table
hadd - insert an item into the table
hdel - delete an item from the table
hstat - print statistics about the table
hfirst - position at the first item in the table
hnext - move the position to the next item in the table
--------------------------------------------------------------------
*/
#ifndef HASHTAB
#define HASHTAB
#include "mpqlib-stdint.h"
#include <stdlib.h>
/* PRIVATE TYPES AND DEFINITIONS */
struct hitem
{
uint8_t *key; /* key that is hashed */
uint32_t keyl; /* length of key */
void *stuff; /* stuff stored in this hitem */
uint32_t hval; /* hash value */
struct hitem *next; /* next hitem in list */
};
typedef struct hitem hitem;
struct htab
{
struct hitem **table; /* hash table, array of size 2^logsize */
int logsize; /* log of size of table */
size_t mask; /* (hashval & mask) is position in table */
uint32_t count; /* how many items in this hash table so far? */
uint32_t apos; /* position in the array */
struct hitem *ipos; /* current item in the array */
struct reroot *space; /* space for the hitems */
uint32_t bcount; /* # hitems useable in current block */
};
typedef struct htab htab;
#ifdef __cplusplus
extern "C" {
#endif
/* PUBLIC FUNCTIONS */
/* hcreate - create a hash table
ARGUMENTS:
logsize - 1<<logsize will be the initial table length
RETURNS:
the new table
*/
htab *hcreate(int logsize);
/* hdestroy - destroy a hash table
ARGUMENTS:
t - the hash table to be destroyed. Note that the items and keys
will not be freed, the user created them and must destroy
them himself.
RETURNS:
nothing
*/
void hdestroy(htab *t);
/* hcount, hkey, hkeyl, hstuff
ARGUMENTS:
t - the hash table
RETURNS:
hcount - (ub4) The number of items in the hash table
hkey - (ub1 *) key for the current item
hkeyl - (ub4) key length for the current item
hstuff - (void *) stuff for the current item
NOTE:
The current position always has an item as long as there
are items in the table, so hexist can be used to test if the
table is empty.
hkey, hkeyl, and hstuff will crash if hcount returns 0
*/
#define hcount(t) ((t)->count)
#define hkey(t) ((t)->ipos->key)
#define hkeyl(t) ((t)->ipos->keyl)
#define hstuff(t) ((t)->ipos->stuff)
/* hfind - move the current position to a given key
ARGUMENTS:
t - the hash table
key - the key to look for
keyl - length of the key
RETURNS:
TRUE if the item exists, FALSE if it does not.
If the item exists, moves the current position to that item.
*/
int hfind(htab *t, uint8_t *key, uint32_t keyl);
/* hadd - add a new item to the hash table
change the position to point at the item with the key
ARGUMENTS:
t - the hash table
key - the key to look for
keyl - length of the key
stuff - other stuff to be stored in this item
RETURNS:
FALSE if the operation fails (because that key is already there).
*/
int hadd(htab *t, uint8_t *key, uint32_t keyl, void *stuff);
/* hdel - delete the item at the current position
change the position to the following item
ARGUMENTS:
t - the hash table
RETURNS:
FALSE if there is no current item (meaning the table is empty)
NOTE:
This frees the item, but not the key or stuff stored in the item.
If you want these then deal with them first. For example:
if (hfind(tab, key, keyl))
{
free(hkey(tab));
free(hstuff(tab));
hdel(tab);
}
*/
int hdel(htab *t);
/* hfirst - move position to the first item in the table
ARGUMENTS:
t - the hash table
RETURNS:
FALSE if there is no current item (meaning the table is empty)
NOTE:
*/
int hfirst(htab *t);
/* hnext - move position to the next item in the table
ARGUMENTS:
t - the hash table
RETURNS:
FALSE if the position wraps around to the beginning of the table
NOTE:
To see every item in the table, do
if (hfirst(t)) do
{
key = hkey(t);
stuff = hstuff(t);
}
while (hnext(t));
*/
/* int hnext(/o_ htab *t _o/); */
#define hnext(t) \
((!(t)->ipos) ? FALSE : \
((t)->ipos=(t)->ipos->next) ? TRUE : hnbucket(t))
/* hnbucket - PRIVATE - move to first item in the next nonempty bucket
ARGUMENTS:
t - the hash table
RETURNS:
FALSE if the position wraps around to the beginning of the table
NOTE:
This is private to hashtab; do not use it externally.
*/
int hnbucket(htab *t);
/* hstat - print statistics about the hash table
ARGUMENTS:
t - the hash table
NOTE:
items <0>: <#buckets with zero items> buckets
items <1>: <#buckets with 1 item> buckets
...
buckets: #buckets items: #items existing: x
( x is the average length of the list when you look for an
item that exists. When the item does not exists, the average
length is #items/#buckets. )
If you put n items into n buckets, expect 1/(n!)e buckets to
have n items. That is, .3678 0, .3678 1, .1839 2, ...
Also expect "existing" to be about 2.
*/
void hstat(htab *t);
#ifdef __cplusplus
}
#endif
#endif /* HASHTAB */
|
