| blob | 162d62d7fbed61074eb0fba158f76e386b9b7613 |
1 .fp 5 CW
2 .de Af
3 .ds ;G \\*(;G\\f\\$1\\$3\\f\\$2
5 ..
6 .de aF
8 .el \{\
9 .ds ;G \&
10 .nr ;G \\n(.f
11 .Af "\\$1" "\\$2" "\\$3" "\\$4" "\\$5" "\\$6" "\\$7" "\\$8" "\\$9"
12 \\*(;G
13 .ft \\n(;G \}
14 ..
15 .de L
16 .aF 5 \\n(.f "\\$1" "\\$2" "\\$3" "\\$4" "\\$5" "\\$6" "\\$7"
17 ..
18 .de LR
19 .aF 5 1 "\\$1" "\\$2" "\\$3" "\\$4" "\\$5" "\\$6" "\\$7"
20 ..
21 .de RL
22 .aF 1 5 "\\$1" "\\$2" "\\$3" "\\$4" "\\$5" "\\$6" "\\$7"
23 ..
24 .de EX \" start example
25 .ta 1i 2i 3i 4i 5i 6i
26 .PP
27 .RS
28 .PD 0
29 .ft 5
30 .nf
31 ..
32 .de EE \" end example
33 .fi
34 .ft
35 .PD
36 .RE
37 .PP
38 ..
39 .TH HASH 3
40 .SH NAME
41 hash \- hash table support (obsolete: use \fBcdt\fP instead)
42 .SH SYNOPSIS
43 .L "#include <hash.h>"
44 .SH DESCRIPTION
45 The
46 .I hash
47 routines manipulate collections of dynamic, scoped hash tables.
48 .PP
49 A hash table provides an association between a
50 .I key
51 and its
52 .IR value .
53 A
54 .I key
55 is a sequence of
56 .L char
57 elements and a
58 .I value
59 is a user supplied pointer to the value.
60 Each hash table has a dynamic number of slots,
61 each pointing to the head of a forward linked
62 .IR "collision chain" .
63 .PP
64 Hashing occurs as follows:
65 a
66 .I "hash function"
67 takes a
68 .I key
69 as an argument and returns a non-negative index.
70 The index modulo the table size produces a
71 slot that points to a
72 .IR "collision chain" .
73 The collision chain is sequentially searched until a match is found for
74 .IR key .
75 The hash tables are automatically resized as new entries are added.
76 .PP
77 Each hash table has one key type.
78 The default key type is a pointer to a null-terminated string.
79 The alternate key type is a pointer to a fixed length byte buffer,
80 declared for a given table by the
81 .L hashalloc()
82 function described below.
83 .PP
84 Hash table information is partitioned into two parts for efficient scoping.
85 The
86 .I root
87 part contains fixed information that is shared among a set of related
88 hash tables.
89 The remaining information is maintained on a per-table basis.
90 .PP
91 These basic types are defined in the header file
92 .B hash.h
93 (alternate names are listed in parenthesis):
94 .TP
95 .L "Hash_table_t (HASHTABLE)"
96 The per-table information.
97 The readonly public elements are:
98 .RS
99 .TP
100 .L "int buckets"
101 The number of table entries.
102 .TP
103 .L "char* name"
104 The hash table name.
105 .TP
106 .L "root"
107 The root information.
108 The public elements are:
109 .RS
110 .TP
111 .L "int root->accesses"
112 The number of lookups.
113 .TP
114 .L "int root->collisions"
115 The number of lookup collisions.
116 .RE
117 .TP
118 .L "Hash_table_t* scope"
119 The table that this scope covers,
120 .L NULL
121 if the table is not a scope.
122 .TP
123 .L "int size"
124 The current hash table size.
125 .RE
126 .TP
127 .L "Hash_bucket_t (HASHBUCKET)"
128 A collision chain hash bucket.
129 The public structure elements are:
130 .RS
131 .TP
132 .L "char* hashname(Hash_bucket_t*)"
133 Returns a pointer to the hash bucket key given the bucket pointer.
134 .TP
135 .L "char* value"
136 The value associated with the key.
137 .RE
138 .TP
139 .L "Hash_header_t (HASHHEADER)"
140 The hash bucket header that must be the first element in all user defined
141 buckets.
142 .L HASH_VALUE
143 may not be used with user defined buckets.
144 .TP
145 .L "Hash_position_t (HASHPOSITION)"
146 Stores the hash table position for
147 .LR hashscan .
148 The public elements are:
149 .RS
150 .TP
151 .L "Hash_bucket_t* bucket"
152 The current hash bucket pointer.
153 .RE
154 .PP
155 The routines are:
156 .TP
157 .L "Hash_table_t* hashalloc(Hash_table_t* ref, int op, ...)"
158 Creates a new hash table and returns a pointer to the table.
159 .IR malloc (3)
160 is used to allocate space for the table.
161 .L NULL
162 is returned if the table cannot be created.
163 .L ref
164 is a pointer to a reference hash table that provides
165 default values for unspecified information.
166 The new hash table and
167 .L ref
168 share the same root information.
169 If
170 .L ref
171 is
172 .L NULL
173 then new root information is created for the new table.
174 The remaining arguments appear in
175 .I op-arg
176 pairs, followed by a final
177 .L 0
178 argument.
179 The
180 .I op-arg
181 pairs are:
182 .RS
183 .TP
184 .L "HASH_alloc, (char(*)()) alloc"
185 .L alloc
186 is a function that is called to process
187 .L Hash_bucket_t
188 .L value
189 assignments.
190 The single argument is
191 .L "char* value"
192 and the processed
193 .L char*
194 value is returned.
195 .TP
196 .L "HASH_clear, int flags"
197 .L flags
198 are the
199 .L ref
200 flags to be cleared in the new hash table.
201 See
202 .L HASH_set
203 below.
204 .TP
205 .L "HASH_compare, (int(*)()) compare"
206 Specifies an alternate
207 .I key
208 comparison function.
209 The arguments and return value for
210 .L compare
211 are the same as for
212 .IR strncmp (3)
213 if
214 .L HASH_namesize
215 is specified and
216 .IR strcmp (3)
217 otherwise.
218 The first argument is the
219 .I key
220 from the current hash bucket on the
221 .I "collision chain"
222 and the second argument is the user supplied
223 .IR key .
224 .TP
225 .L "HASH_free, (int(*)()) free"
226 .L free
227 is a function that is called when a hash bucket is freed.
228 If
229 .L HASH_BUCKET
230 was set in
231 .L hashalloc
232 then the hash bucket pointer is passed, otherwise the bucket
233 .L value
234 pointer is passed.
235 .TP
236 .L "HASH_hash, (int(*)()) hash"
237 Specifies an alternate
238 .I key
239 hash function.
240 A
241 .L char*
242 key argument (and, if
243 .L HASH_namesize
244 is specified, an
245 .L int
246 key size argument) is passed to
247 .LR hash .
248 The return value must be a non-negative
249 .LR int .
250 .TP
251 .L "HASH_meanchain, int meanchain"
252 Specifies the mean collision chain length.
253 The hash table is automatically resized when this value is exceeded.
254 The default mean chain length is 2.
255 .TP
256 .L "HASH_name, char* name"
257 Associates
258 .L name
259 with the hash table.
260 Used by
261 .LR hashdump) .
262 .TP
263 .L "HASH_namesize, int namesize"
264 The fixed size in bytes for
265 .I keys
266 in the table.
267 If
268 .L namesize
269 is 0 (the default) then the
270 .I keys
271 are interpreted as null-terminated strings.
272 .TP
273 .L "HASH_set, int flags"
274 Changes the hash table flags by
275 .IR or ing
276 in
277 .LR flags .
278 The flags, which may be
279 .IR or ed
280 together, are:
281 .RS
282 .TP
283 .L HASH_ALLOCATE
284 Keys for new hash table entries are to be copied to data areas obtained from
285 .IR malloc (3).
286 .TP
287 .L HASH_FIXED
288 Fixes the hash table size, disabling any automatic table resizing.
289 .TP
290 .L HASH_SCOPE
291 The new hash table is a scope that is to be pushed on top of
292 .LR ref .
293 .L ref
294 must be
295 .RL non- NULL .
296 .RE
297 .TP
298 .L "HASH_va_list, va_list ap"
299 .L ap
300 is a
301 .L va_list
302 variable argument list pointer
303 (see
304 .LR <stdarg.h> ).
305 .RE
306 .TP
307 .L "Hash_table_t* hashfree(Hash_table_t* tab)"
308 The hash table
309 .L tab
310 is freed.
311 The scope covered table pointer is returned,
312 .L NULL
313 if
314 .L tab
315 is not a scope.
316 .TP
317 .L "char* hashlook(Hash_table_t* tab, char* name, int flags, char* value)"
318 Operates on the key
319 .L name
320 in the hash table
321 .L tab
322 according to
323 .L flags
324 and
325 .LR value .
326 A
327 .L Hash_bucket_t
328 pointer is returned unless otherwise noted.
329 There are three basic lookup operations:
330 .RS
331 .TP
332 .L HASH_CREATE
333 .L name
334 is entered into the top level scope if it does not already exist.
335 If
336 .L name
337 also appears in a lower scope and
338 .L HASH_ALLOC
339 is set for the table then the new bucket will share the
340 .L name
341 field value with the lower scope.
342 .TP
343 .L HASH_DELETE
344 .L name
345 is deleted from the top level scope if it exists.
346 .L NULL
347 is returned.
348 .TP
349 .L HASH_LOOKUP
350 The scopes are searched in order from top to bottom for
351 .L name .
352 The bucket pointer for the first occurrence is returned.
353 .L NULL
354 is returned if
355 .L name
356 is not found.
357 .RE
358 The basic operations may be qualified by the following
359 (the qualifiers are restricted to the basic operations in
360 the parenthesized list):
361 .RS
362 .TP
363 .L "HASH_BUCKET (HASH_CREATE,HASH_DELETE,HASH_LOOKUP)"
364 .L name
365 is a pointer to a bucket that has already been entered into the table.
366 .TP
367 .L "HASH_FIXED (HASH_CREATE)"
368 .L value
369 is taken to be the size of the hash bucket to be created for
370 .L name
371 in the top level scope.
372 The minimum bucket size is silently restricted to
373 .LR sizeof(Hash_header_t) .
374 .TP
375 .L "HASH_INSTALL (HASH_CREATE)"
376 .L name
377 is a pointer to a bucket that has not been entered into the table.
378 .TP
379 .L "HASH_NOSCOPE (HASH_LOOKUP)"
380 The lookup is restricted to the top level scope.
381 .TP
382 .L "HASH_OPAQUE (HASH_CREATE,HASH_DELETE)"
383 Sets
384 .L (HASH_CREATE)
385 or clears
386 .L (HASH_DELETE)
387 the
388 .I opaque
389 property for the bucket.
390 An opaque bucket is not visible in lower scopes.
391 .TP
392 .L "HASH_SCOPE (HASH_CREATE,HASH_DELETE)"
393 All scopes are searched for the bucket.
394 If the bucket is not found for
395 .L HASH_CREATE
396 then a new bucket is created in the lowest scope.
397 .TP
398 .L "HASH_VALUE (HASH_CREATE,HASH_LOOKUP)"
399 For
400 .L HASH_CREATE
401 the bucket
402 .L value
403 field is set to
404 .L value
405 and the bucket
406 .L name
407 value is returned.
408 For
409 .L HASH_LOOKUP
410 the bucket
411 .L value
412 field is returned,
413 .L NULL
414 if the bucket is not found.
415 .RE
416 If
417 .L name
418 .L NULL
419 then the name from the most recent
420 .L hashlook()
421 is used, avoiding recomputation of some internal parameters.
422 .TP
423 .L "char* hashget(Hash_table_t* tab, char* name)"
424 Returns the value
425 associated with the key
426 .L name
427 in the hash table
428 .LR tab .
429 If
430 .L name
431 is
432 .L NULL
433 then the name from the most recent
434 .L hashget()
435 is used, avoiding recomputation of some internal parameters.
436 .L NULL
437 is returned if
438 .L name
439 is not in the table.
440 All scope covered tables are searched.
441 .TP
442 .L "Hash_bucket_t* hashlast(Hash_table_t* tab)"
443 Returns a pointer to the most recent hash bucket for
444 .LR tab .
445 The value is set by
446 .LR hashlook() ,
447 .L hashscan()
448 and
449 .LR hashwalk() .
450 .TP
451 .L "char* hashput(Hash_table_t* tab, char* name, char* value)"
452 Set the value of the key
453 .L name
454 to
455 .L value
456 in the top level scope of the hash table
457 .LR tab .
458 .L name
459 is entered into the top level scope if necessary.
460 The (possibly re-allocated) key name pointer is returned
461 (see
462 .LR HASH_ALLOCATE ).
463 If
464 .L name
465 is 0 then the most recent lookup
466 .L name
467 to
468 .L hashlook()
469 or
470 .L hashget()
471 is used.
472 This eliminates a re-hash and re-lookup of
473 .LR name .
474 .TP
475 .L "int hashwalk(Hash_table_t* tab, int flags, (int(*)()) walker, char* handle)"
476 The function
477 .L walker
478 is applied to each entry (not covered by a scope starting at
479 .LR tab )
480 in the hash table
481 .LR tab .
482 If
483 .L flags
484 is
485 .L HASH_NOSCOPE
486 then only the top level hash table is used, otherwise the walk includes
487 all scope covered tables.
488 .L walker
489 is called with
490 .L char*
491 .I key
492 as the first argument,
493 .L char*
494 .I value
495 as the second argument, and
496 .L char*
497 .I handle
498 as the third argument.
499 .I handle
500 may be
501 .LR 0 .
502 The walk terminates after the last entry or when
503 .L walker
504 returns a negative value.
505 The return value of the last call to
506 .L walker
507 is returned.
508 Only one walk may be active within a collection of scoped tables.
509 .TP
510 .L "Hash_position_t* hashscan(Hash_table_t* tab, int flags)"
511 Returns a
512 .L Hash_position_t
513 pointer for a sequential scan on the hash table
514 .LR tab .
515 If
516 .L flags
517 is
518 .L HASH_NOSCOPE
519 then only the top level hash table is used, otherwise the scan includes
520 all scope covered tables.
521 Only one scan may be active within a collection of scoped tables.
522 .L hashdone()
523 must be called to terminate the scan.
524 .L 0
525 is returned on error.
526 .TP
527 .L "Hash_bucket_t* hashnext(Hash_position_t* pos)"
528 Returnes a pointer to the next bucket in the sequential scan set up by
529 .L hashscan()
530 on
531 .LR pos .
532 If no elements remain then
533 .L 0
534 is returned.
535 .TP
536 .L "void hashdone(Hash_position_t* pos)"
537 Completes a scan initiated by
538 .L hashscan()
539 on
540 .LR pos .
541 .TP
542 .L "int hashset(Hash_table_t* tab, int flags)"
543 Sets the flags for the hash table
544 .L tab
545 by
546 .IR or ing
547 in
548 .LR flags .
549 Only
550 .L HASH_ALLOCATE
551 and
552 .L HASH_FIXED
553 may be set.
554 .TP
555 .L "int hashclear(Hash_table_t* tab, int flags)"
556 Clears the flags for the hash table
557 .L tab
558 by masking out
559 .LR flags .
560 Only
561 .L HASH_ALLOCATE
562 and
563 .L HASH_FIXED
564 may be cleared.
565 .TP
566 .L "void hashdump(Hash_table_t* tab, int flags)"
567 Dumps hash table accounting info to standard error.
568 If
569 .L tab
570 is
571 .L NULL
572 then all allocated hash tables are dumped, otherwise only information on
573 .L tab
574 is dumped.
575 If
576 .L flags
577 is
578 .L HASH_BUCKET
579 then the hash bucket
580 .I key-value
581 pairs for each collision chain are also dumped.
582 .TP
583 .L "void hashsize(Hash_table_t* tab, int size)"
584 Changes the size of the hash table
585 .L tab
586 to
587 .L size
588 where
589 .L size
590 must be a power of 2.
591 Explicit calls to this routine are not necessary as hash tables
592 are automatically resized.
593 .TP
594 .L "int strhash(char* name)"
595 Hashes the null terminated character string
596 .L name
597 using a linear congruent pseudo-random number generator algorithm
598 and returns a non-negative
599 .L int
600 hash value.
601 .TP
602 .L "int memhash(char* buf, int siz)"
603 Hashes the buffer
604 .L buf
605 of
606 .L siz
607 bytes using a linear congruent pseudo-random number generator algorithm
608 and returns a non-negative
609 .L int
610 hash value.
611 .TP
612 .L "long strsum(char* name, long sum)"
613 Returns a running 31-bit checksum of the string
614 .L name
615 where
616 .L sum
617 is
618 .L 0
619 on the first call and
620 the return value from a previous
621 .L memsum
622 or
623 .L strsum
624 call otherwise.
625 The checksum value is consistent across all implementations.
626 .TP
627 .L "long memsum(char* buf, int siz, long sum)"
628 Returns a running 31-bit checksum of buffer
629 .L buf
630 of
631 .L siz
632 bytes where
633 .L sum
634 is
635 .L 0
636 on the first call and
637 the return value from a previous
638 .L memsum
639 or
640 .L strsum
641 call otherwise.
642 The checksum value is consistent across all implementations.
643 .SH "SEE ALSO"
644 sum(1)