PS2SDK
PS2 Homebrew Libraries
Loading...
Searching...
No Matches
hashtab.h
1/*
2--------------------------------------------------------------------
3By Bob Jenkins, 1996. hash.h. Public Domain.
4
5This 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 HASHTAB_H
32#define HASHTAB_H
33
34#include "standard.h"
35
36#ifdef __cplusplus
37extern "C" {
38#endif
39
40/* PRIVATE TYPES AND DEFINITIONS */
41
42struct hitem
43{
44 const char *key; /* key that is hashed */
45 size_t keyl; /* length of key */
46 void *stuff; /* stuff stored in this hitem */
47 size_t hval; /* hash value */
48 struct hitem *next; /* next hitem in list */
49};
50typedef struct hitem hitem;
51
52
53struct htab
54{
55 struct hitem **table; /* hash table, array of size 2^logsize */
56 int logsize; /* log of size of table */
57 size_t mask; /* (hashval & mask) is position in table */
58 size_t count; /* how many items in this hash table so far? */
59 size_t apos; /* position in the array */
60 struct hitem *ipos; /* current item in the array */
61 struct reroot *space; /* space for the hitems */
62 size_t bcount; /* # hitems useable in current block */
63};
64typedef struct htab htab;
65
66
67
68
69
70/* PUBLIC FUNCTIONS */
71
72/* hcreate - create a hash table
73 ARGUMENTS:
74 logsize - 1<<logsize will be the initial table length
75 RETURNS:
76 the new table
77 */
78extern htab *hcreate(int logsize);
79
80
81/* hdestroy - destroy a hash table
82 ARGUMENTS:
83 t - the hash table to be destroyed. Note that the items and keys
84 will not be freed, the user created them and must destroy
85 them himself.
86 RETURNS:
87 nothing
88 */
89extern void hdestroy(htab *t);
90
91
92/* hcount, hkey, hkeyl, hstuff
93 ARGUMENTS:
94 t - the hash table
95 RETURNS:
96 hcount - (size_t) The number of items in the hash table
97 hkey - (const char *) key for the current item
98 hkeyl - (size_t) key length for the current item
99 hstuff - (void *) stuff for the current item
100 NOTE:
101 The current position always has an item as long as there
102 are items in the table, so hexist can be used to test if the
103 table is empty.
104 hkey, hkeyl, and hstuff will crash if hcount returns 0
105 */
106#define hcount(t) ((t)->count)
107#define hkey(t) ((t)->ipos->key)
108#define hkeyl(t) ((t)->ipos->keyl)
109#define hstuff(t) ((t)->ipos->stuff)
110
111
112
113/* hfind - move the current position to a given key
114 ARGUMENTS:
115 t - the hash table
116 key - the key to look for
117 keyl - length of the key
118 RETURNS:
119 TRUE if the item exists, FALSE if it does not.
120 If the item exists, moves the current position to that item.
121 */
122extern int hfind(htab *t, const char *key, size_t keyl);
123
124
125/* hadd - add a new item to the hash table
126 change the position to point at the item with the key
127 ARGUMENTS:
128 t - the hash table
129 key - the key to look for
130 keyl - length of the key
131 stuff - other stuff to be stored in this item
132 RETURNS:
133 FALSE if the operation fails (because that key is already there).
134 */
135extern int hadd(htab *t, const char *key, size_t keyl, void *stuff);
136
137
138/* hdel - delete the item at the current position
139 change the position to the following item
140 ARGUMENTS:
141 t - the hash table
142 RETURNS:
143 FALSE if there is no current item (meaning the table is empty)
144 NOTE:
145 This frees the item, but not the key or stuff stored in the item.
146 If you want these then deal with them first. For example:
147 if (hfind(tab, key, keyl))
148 {
149 free(hkey(tab));
150 free(hstuff(tab));
151 hdel(tab);
152 }
153 */
154extern int hdel(htab *t);
155
156
157/* hfirst - move position to the first item in the table
158 ARGUMENTS:
159 t - the hash table
160 RETURNS:
161 FALSE if there is no current item (meaning the table is empty)
162 NOTE:
163 */
164extern int hfirst(htab *t);
165
166
167/* hnext - move position to the next item in the table
168 ARGUMENTS:
169 t - the hash table
170 RETURNS:
171 FALSE if the position wraps around to the beginning of the table
172 NOTE:
173 To see every item in the table, do
174 if (hfirst(t)) do
175 {
176 key = hkey(t);
177 stuff = hstuff(t);
178 }
179 while (hnext(t));
180 */
181/* word hnext(/o_ htab *t _o/); */
182#define hnext(t) \
183 ((!(t)->ipos) ? FALSE : \
184 ((t)->ipos=(t)->ipos->next) ? TRUE : hnbucket(t))
185
186/* hnbucket - PRIVATE - move to first item in the next nonempty bucket
187 ARGUMENTS:
188 t - the hash table
189 RETURNS:
190 FALSE if the position wraps around to the beginning of the table
191 NOTE:
192 This is private to hashtab; do not use it externally.
193 */
194extern int hnbucket(htab *t);
195
196
197/* hstat - print statistics about the hash table
198 ARGUMENTS:
199 t - the hash table
200 NOTE:
201 items <0>: <#buckets with zero items> buckets
202 items <1>: <#buckets with 1 item> buckets
203 ...
204 buckets: #buckets items: #items existing: x
205 ( x is the average length of the list when you look for an
206 item that exists. When the item does not exists, the average
207 length is #items/#buckets. )
208
209 If you put n items into n buckets, expect 1/(n!)e buckets to
210 have n items. That is, .3678 0, .3678 1, .1839 2, ...
211 Also expect "existing" to be about 2.
212 */
213extern void hstat(/*_ htab *t _*/);
214
215#ifdef __cplusplus
216}
217#endif
218
219#endif /* HASHTAB_H */
Definition hashtab.h:54
u32 count
start sector of fragmented bd/file