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