1ALL_HASH(3) LAM INTERNALS ALL_HASH(3)
2
6 all_hash, all_shash - general purpose hash table management (LAM)
7
9 #include <all_hash.h>
10 HASH *ah_init (int size, int elemsize, int nullkey, int mode);
12 int ah_delete (HASH *ahd, int key);
13 int ah_delete_elm (HASH *ahd, void *cmpelm);
14 int ah_expand (HASH *ahd, int newsize);
15 int ah_insert (HASH *ahd, void *elem);
16 int ah_kick (HASH *ahd, void *elem);
17 int ah_count (HASH *ahd);
18 int ah_size (HASH *ahd);
19 void *ah_find (HASH *ahd, int key);
20 void *ah_find_elm (HASH *ahd, void *cmpelm);
21 void *ah_top (HASH *ahd);
22 void *ah_next (HASH *ahd, void *elem);
23 void ah_free (HASH *ahd);
24 void ah_setcmp (HASH *ahd, int (*cmp)(void *e1, void *e2));
25 SHASH *ahs_init (int size, int elemsize, int nullkey, int mode,
27 void *htable, int *lru, SHASH *ahsd);
28 int ahs_delete (SHASH *ahsd, int key);
29 int ahs_delete_elm (SHASH *ahsd, void *cmpelm);
30 int ahs_insert (SHASH *ahsd, void *elem);
31 int ahs_kick (SHASH *ahsd, void *elem);
32 int ahs_count (SHASH *ahsd);
33 int ahs_size (SHASH *ahsd);
34 void *ahs_find (SHASH *ahsd, int key);
35 void *ahs_find_elm (SHASH *ahsd, void *cmpelm);
36 void *ahs_top (SHASH *ahsd);
37 void *ahs_next (SHASH *ahsd, void *elem);
38 void ahs_setcmp (HASH *ahsd, int (*cmp)(void *e1, void *e2));
39
41 The all_hash and all_shash packages provide general purpose hash table
42 management. They differ only in the way memory is allocated for a hash
43 table. The dynamic package, all_hash, obtains memory from malloc(3)
44 whenever a new hash table is created or its size expanded, and returns
45 memory with free(3) whenever a hash table is destroyed. The static
46 package, all_shash, requires that the caller provide memory for the
47 maximum number of hash table entries when the table is first created.
48 Functions that operate on a dynamic hash table are named ah_* and func‐
49 tions that operate on a static hash table are named ahs_*.
50 A hash table is created and initialized with the ah_init() or
52 ahs_init() functions. These functions return a pointer to a hash table
53 descriptor, typedef HASH or SHASH respectively. The hash table
54 descriptor pointer is used in all subsequent hash table operation. In
55 the static function, ahs_init(), the caller supplies space not only for
56 the maximum number of hash table entries, but for the hash table
57 descriptor and the LRU counters when this mode of operation is used.
58 The LRU (Least Recently Used) counters keep track of the number of
59 accesses made to each hash table entry and are used when the AHLRU mode
60 is chosen. This enables ah_kick() to choose, when the hash table is
61 full, the least recently used entry as a good candidate to be replaced
62 by the new entry to be stored in the table. If the AHLRU mode is not
63 chosen, the LRU counters are not required. In this case, if the hash
64 table is full, a new entry replaces the old entry at the optimal hash
65 location. The mode argument is a bit-mapped flag, each flag control‐
66 ling some characteristic of the hash table. Mode values are con‐
67 structed by ORing flags from the following list:
68 AHLRU The least recently used entry is overwritten if the hash
70 table is full when ah_kick() is called, otherwise the first
71 (optimal) hashed location is overwritten.
72 AHNOINIT The hash table is not initialized. Usually, if the data
74 structures are properly designed (data hiding), this mode
75 of operation would not be required. If used, the burden of
76 properly initializing the hash table entries rests on the
77 user.
78 A dynamic hash table is freed with the ah_free() function. A static
80 hash table is simply forgotten, since the caller is responsible for all
81 the memory involved. Allocating the space for a static hash table is
82 straight forward. The user needs to allocate two separate arrays of
83 equal number of entries. One, htable, is the actual hash table and
84 each of its entries is a user-defined structure. The second, lru, is
85 only used if the AHLRU mode is chosen and consists of an array of inte‐
86 gers (32-bit integers) each being used as a counter for an entry in the
87 hash table. If the AHLRU mode is not chosen, there is no need to allo‐
88 cate the lru array. An example of how to allocate space for a static
89 hash table for the AHLRU mode of operation is given below:
90 struct myelement htable[31];
92 int lru[31];
93 SHASH ahsd;
94 #define ELEMSIZE sizeof(struct myelement)
95 ahs_init(31, ELEMSIZE, -1, AHLRU, htable, lru, &ahsd);
96 Thirty one elements of type myelement are allocated and named htable,
98 and thirty one 32-bit counters are allocated and named lru.
99 Hash Key and Comparison Function
101 A hash table entry can be any user-defined structure as long as its
102 first structure member is a 32-bit integer, known as the key. The user
103 has to choose one key value, nullkey, to represent an invalid key and
104 specify it during initialization. This special key value is used to
105 distinguish between empty and full hash table entries. The key values
106 are used to insert, delete, and locate entries in the hash table. This
107 is sufficient in the case where each table entry has a unique key
108 value.
109 In some cases, different entries may have equal key values (e.g. hash‐
111 ing strings). Such a case requires a more general mechanism to distin‐
112 guish between the different same-key entries. A user-defined compari‐
113 son function, cmp(), has to be provided to enable searching and delet‐
114 ing the proper entry among several having the same key value. The user
115 still has to provide the key value to insert elements, but searching
116 and deleting are done by using both the hashed key for speed, and the
117 comparison function to make sure only the right entry is affected. The
118 comparison function takes two pointers to hash table entries and
119 returns 0 only if the entries are equal.
120 Dynamic Hash Table Operators
122 The following functions operate on dynamic hash tables:
123 ah_init() Allocate and initialize a dynamic hash table. A hash
125 table descriptor pointer is returned, or NULL if alloca‐
126 tion fails. The caller supplies the total number of
127 entries in the hash table, the size of each element, the
128 value in the key of an empty element, and the mode of
129 operation. The size of the element must be at least the
130 size of an integer (32 bits) in order to be able to con‐
131 tain the hashing key, which must be the first 32 bits of
132 the element.
133 ah_setcmp() Set the comparison function. This function is called
135 right after ah_init() and is needed when key values are
136 not unique to each element.
137 ah_delete() Delete an existing element from a hash table. The ele‐
139 ment is specified by its key. The function returns -1
140 and sets errno to EDELETE if the element could not be
141 found in the given hash table. Otherwise it returns 0.
142 ah_delete_elm()
144 Delete an existing element from a hash table. The ele‐
145 ment is specified by providing a pointer to an equal
146 element, as determined by the comparison function. The
147 key of the comparison element must be filled, in addi‐
148 tion to other user-defined comparison parameters.
149 Return values are similar to those of ah_delete().
150 ah_insert() Insert a new element into a hash table. The caller pre‐
152 pares and supplies a pointer to the new element. The
153 function copies the contents of the caller supplied ele‐
154 ment into the appropriate space in the hash table. The
155 caller can reuse the element. ah_insert() returns -1
156 and sets errno to EFULL if the hash table has no empty
157 slots to store the element. Otherwise it returns 0.
158 ah_kick() Like ah_insert() if the hash table is not full. If the
160 hash table is full, a slot is chosen and overwritten
161 with the new information. If the AHLRU mode is used,
162 the least recently used slot is chosen, otherwise the
163 first hashed location is overwritten.
164 ah_free() Free all allocated memory in a dynamic hash table
166 including the hash table descriptor. The hash table is
167 effectively blown away. The hash table descriptor
168 pointer is no longer valid.
169 ah_find() Find an existing element in the hash table. The caller
171 provides the search key for the element. A pointer to
172 the found element is returned, or NULL if the element is
173 not found.
174 ah_find_elm() Find an existing element in the hash table. As done in
176 the case of ah_delete_elm(), the element is specified by
177 providing a pointer to an equal element. Return values
178 are similar to those of ah_find().
179 ah_top() Find the first element in the hash table. A pointer to
181 the element is returned, or NULL if the hash table is
182 empty.
183 ah_next() Find the next element in the hash table. A pointer to
185 the element is returned, or NULL if the hash table is
186 empty or the end of the table has been reached. This
187 function is typically used in conjunction with ah_top()
188 in order to access all the elements in the hash table
189 with no prior knowledge of their contents (keys or com‐
190 parison parameters).
191 ah_count() A count of all elements in a given hash table is
193 returned.
194 ah_size() The size of the given hash table is returned.
196 ah_expand() Expand the size of a dynamic hash table in order to
198 accommodate more elements. The caller provides the
199 desired new hash table size. The new size has to be
200 larger than the current size. The new hash table inher‐
201 its the operation mode of the previous hash table except
202 for the AHNOINIT status which is always turned off, and
203 the new hash table is initialized. If the AHLRU mode
204 was set, the LRU counters are reset to zero. This gives
205 all entries equal chance to be kicked out once the
206 expanded hash table fills up again. The function
207 returns -1 if a new hash table could not be allocated.
208 Otherwise it returns 0.
209 Static Hash Table Operators
211 The static hash table functions are very similar. The differences are
212 listed below.
213 ahs_init() As explained above, this function requires the caller to
215 allocate all the memory used by the hash table, includ‐
216 ing the descriptor.
217 ahs_free() This function does not exist.
219 ahs_expand() This function does not exist.
221
223 all_list(3), all_queue(3)
224LAM 7.1.2 March, 2006 ALL_HASH(3)