Annotation of embedaddon/trafshow/hashtab.h, revision 1.1.1.1
1.1 misho 1: /*
2: --------------------------------------------------------------------
3: By Bob Jenkins, 1996. hash.h. Public Domain.
4:
5: This implements a hash table.
6: * Keys are unique. Adding an item fails if the key is already there.
7: * Keys and items are pointed at, not copied. If you change the value
8: of the key after it is inserted then hfind will not be able to find it.
9: * The hash table maintains a position that can be set and queried.
10: * The table length doubles dynamically and never shrinks. The insert
11: that causes table doubling may take a long time.
12: * The table length splits when the table length equals the number of items
13: Comparisons usually take 7 instructions.
14: Computing a hash value takes 35+6n instructions for an n-byte key.
15:
16: hcreate - create a hash table
17: hdestroy - destroy a hash table
18: hcount - The number of items in the hash table
19: hkey - key at the current position
20: hkeyl - key length at the current position
21: hstuff - stuff at the current position
22: hfind - find an item in the table
23: hadd - insert an item into the table
24: hdel - delete an item from the table
25: hstat - print statistics about the table
26: hfirst - position at the first item in the table
27: hnext - move the position to the next item in the table
28: --------------------------------------------------------------------
29: */
30:
31: #ifndef STANDARD
32: #include "standard.h"
33: #endif
34:
35: #ifndef HASHTAB
36: #define HASHTAB
37:
38: /* PRIVATE TYPES AND DEFINITIONS */
39:
40: struct hitem
41: {
42: ub1 *key; /* key that is hashed */
43: ub4 keyl; /* length of key */
44: void *stuff; /* stuff stored in this hitem */
45: ub4 hval; /* hash value */
46: struct hitem *next; /* next hitem in list */
47: };
48: typedef struct hitem hitem;
49:
50:
51: struct htab
52: {
53: struct hitem **table; /* hash table, array of size 2^logsize */
54: word logsize; /* log of size of table */
55: size_t mask; /* (hashval & mask) is position in table */
56: ub4 count; /* how many items in this hash table so far? */
57: ub4 apos; /* position in the array */
58: struct hitem *ipos; /* current item in the array */
59: struct reroot *space; /* space for the hitems */
60: ub4 bcount; /* # hitems useable in current block */
61: };
62: typedef struct htab htab;
63:
64:
65:
66:
67:
68: /* PUBLIC FUNCTIONS */
69:
70: /* hcreate - create a hash table
71: ARGUMENTS:
72: logsize - 1<<logsize will be the initial table length
73: RETURNS:
74: the new table
75: */
76: htab *hcreate(word logsize);
77:
78:
79: /* hdestroy - destroy a hash table
80: ARGUMENTS:
81: t - the hash table to be destroyed. Note that the items and keys
82: will not be freed, the user created them and must destroy
83: them himself.
84: RETURNS:
85: nothing
86: */
87: void hdestroy(htab *t);
88:
89:
90: /* hcount, hkey, hkeyl, hstuff
91: ARGUMENTS:
92: t - the hash table
93: RETURNS:
94: hcount - (ub4) The number of items in the hash table
95: hkey - (ub1 *) key for the current item
96: hkeyl - (ub4) key length for the current item
97: hstuff - (void *) stuff for the current item
98: NOTE:
99: The current position always has an item as long as there
100: are items in the table, so hexist can be used to test if the
101: table is empty.
102: hkey, hkeyl, and hstuff will crash if hcount returns 0
103: */
104: #define hcount(t) ((t)->count)
105: #define hkey(t) ((t)->ipos->key)
106: #define hkeyl(t) ((t)->ipos->keyl)
107: #define hstuff(t) ((t)->ipos->stuff)
108:
109:
110:
111: /* hfind - move the current position to a given key
112: ARGUMENTS:
113: t - the hash table
114: key - the key to look for
115: keyl - length of the key
116: RETURNS:
117: TRUE if the item exists, FALSE if it does not.
118: If the item exists, moves the current position to that item.
119: */
120: word hfind(htab *t, ub1 *key, ub4 keyl);
121:
122:
123: /* hadd - add a new item to the hash table
124: change the position to point at the item with the key
125: ARGUMENTS:
126: t - the hash table
127: key - the key to look for
128: keyl - length of the key
129: stuff - other stuff to be stored in this item
130: RETURNS:
131: FALSE if the operation fails (because that key is already there).
132: */
133: word hadd(htab *t, ub1 *key, ub4 keyl, void *stuff);
134:
135:
136: /* hdel - delete the item at the current position
137: change the position to the following item
138: ARGUMENTS:
139: t - the hash table
140: RETURNS:
141: FALSE if there is no current item (meaning the table is empty)
142: NOTE:
143: This frees the item, but not the key or stuff stored in the item.
144: If you want these then deal with them first. For example:
145: if (hfind(tab, key, keyl))
146: {
147: free(hkey(tab));
148: free(hstuff(tab));
149: hdel(tab);
150: }
151: */
152: word hdel(htab *t);
153:
154:
155: /* hfirst - move position to the first item in the table
156: ARGUMENTS:
157: t - the hash table
158: RETURNS:
159: FALSE if there is no current item (meaning the table is empty)
160: NOTE:
161: */
162: word hfirst(htab *t);
163:
164:
165: /* hnext - move position to the next item in the table
166: ARGUMENTS:
167: t - the hash table
168: RETURNS:
169: FALSE if the position wraps around to the beginning of the table
170: NOTE:
171: To see every item in the table, do
172: if (hfirst(t)) do
173: {
174: key = hkey(t);
175: stuff = hstuff(t);
176: }
177: while (hnext(t));
178: */
179: /* word hnext(htab *t); */
180: #define hnext(t) \
181: ((!(t)->ipos) ? FALSE : \
182: ((t)->ipos=(t)->ipos->next) ? TRUE : hnbucket(t))
183:
184: /* hnbucket - PRIVATE - move to first item in the next nonempty bucket
185: ARGUMENTS:
186: t - the hash table
187: RETURNS:
188: FALSE if the position wraps around to the beginning of the table
189: NOTE:
190: This is private to hashtab; do not use it externally.
191: */
192: word hnbucket(htab *t);
193:
194:
195: /* hstat - print statistics about the hash table
196: ARGUMENTS:
197: t - the hash table
198: NOTE:
199: items <0>: <#buckets with zero items> buckets
200: items <1>: <#buckets with 1 item> buckets
201: ...
202: buckets: #buckets items: #items existing: x
203: ( x is the average length of the list when you look for an
204: item that exists. When the item does not exists, the average
205: length is #items/#buckets. )
206:
207: If you put n items into n buckets, expect 1/(n!)e buckets to
208: have n items. That is, .3678 0, .3678 1, .1839 2, ...
209: Also expect "existing" to be about 2.
210: */
211: void hstat(FILE *fp, htab *t);
212:
213: #endif /* HASHTAB */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hashtab.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / trafshow