13229Spst#ifndef HASH_H 23229Spst#define HASH_H 33229Spst/* hash.h */ 43229Spst/************************************************************************ 53229Spst Copyright 1988, 1991 by Carnegie Mellon University 63229Spst 73229Spst All Rights Reserved 83229Spst 93229SpstPermission to use, copy, modify, and distribute this software and its 103229Spstdocumentation for any purpose and without fee is hereby granted, provided 113229Spstthat the above copyright notice appear in all copies and that both that 123229Spstcopyright notice and this permission notice appear in supporting 133229Spstdocumentation, and that the name of Carnegie Mellon University not be used 143229Spstin advertising or publicity pertaining to distribution of the software 153229Spstwithout specific, written prior permission. 163229Spst 173229SpstCARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS 183229SpstSOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 193229SpstIN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL 203229SpstDAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 213229SpstPROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS 223229SpstACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 233229SpstSOFTWARE. 243229Spst************************************************************************/ 253229Spst 263229Spst/* 273229Spst * Generalized hash table ADT 2897416Salfred * $FreeBSD$ 293229Spst * 303229Spst * Provides multiple, dynamically-allocated, variable-sized hash tables on 313229Spst * various data and keys. 323229Spst * 333229Spst * This package attempts to follow some of the coding conventions suggested 343229Spst * by Bob Sidebotham and the AFS Clean Code Committee. 353229Spst */ 363229Spst 373229Spst 383229Spst/* 393229Spst * The user must supply the following: 403229Spst * 413229Spst * 1. A comparison function which is declared as: 423229Spst * 433229Spst * int compare(data1, data2) 443229Spst * hash_datum *data1, *data2; 453229Spst * 463229Spst * This function must compare the desired fields of data1 and 473229Spst * data2 and return TRUE (1) if the data should be considered 483229Spst * equivalent (i.e. have the same key value) or FALSE (0) 493229Spst * otherwise. This function is called through a pointer passed to 503229Spst * the various hashtable functions (thus pointers to different 513229Spst * functions may be passed to effect different tests on different 523229Spst * hash tables). 533229Spst * 543229Spst * Internally, all the functions of this package always call the 553229Spst * compare function with the "key" parameter as the first parameter, 563229Spst * and a full data element as the second parameter. Thus, the key 573229Spst * and element arguments to functions such as hash_Lookup() may 583229Spst * actually be of different types and the programmer may provide a 593229Spst * compare function which compares the two different object types 603229Spst * as desired. 613229Spst * 623229Spst * Example: 633229Spst * 643229Spst * int compare(key, element) 653229Spst * char *key; 663229Spst * struct some_complex_structure *element; 673229Spst * { 683229Spst * return !strcmp(key, element->name); 693229Spst * } 703229Spst * 713229Spst * key = "John C. Doe" 723229Spst * element = &some_complex_structure 733229Spst * hash_Lookup(table, hashcode, compare, key); 743229Spst * 753229Spst * 2. A hash function yielding an unsigned integer value to be used 763229Spst * as the hashcode (index into the hashtable). Thus, the user 773229Spst * may hash on whatever data is desired and may use several 783229Spst * different hash functions for various different hash tables. 793229Spst * The actual hash table index will be the passed hashcode modulo 803229Spst * the hash table size. 813229Spst * 823229Spst * A generalized hash function, hash_HashFunction(), is included 833229Spst * with this package to make things a little easier. It is not 84229780Suqs * guaranteed to use the best hash algorithm in existence. . . . 853229Spst */ 863229Spst 873229Spst 883229Spst 893229Spst/* 903229Spst * Various hash table definitions 913229Spst */ 923229Spst 933229Spst 943229Spst/* 953229Spst * Define "hash_datum" as a universal data type 963229Spst */ 973229Spsttypedef void hash_datum; 983229Spst 993229Spsttypedef struct hash_memberstruct hash_member; 1003229Spsttypedef struct hash_tblstruct hash_tbl; 1013229Spsttypedef struct hash_tblstruct_hdr hash_tblhdr; 1023229Spst 1033229Spststruct hash_memberstruct { 1043229Spst hash_member *next; 1053229Spst hash_datum *data; 1063229Spst}; 1073229Spst 1083229Spststruct hash_tblstruct_hdr { 1093229Spst unsigned size, bucketnum; 1103229Spst hash_member *member; 1113229Spst}; 1123229Spst 1133229Spststruct hash_tblstruct { 1143229Spst unsigned size, bucketnum; 1153229Spst hash_member *member; /* Used for linear dump */ 1163229Spst hash_member *table[1]; /* Dynamically extended */ 1173229Spst}; 1183229Spst 1193229Spst/* ANSI function prototypes or empty arg list? */ 1203229Spst 12197417Salfredtypedef int (*hash_cmpfp)(hash_datum *, hash_datum *); 12297417Salfredtypedef void (*hash_freefp)(hash_datum *); 1233229Spst 12497417Salfredextern hash_tbl *hash_Init(u_int tablesize); 1253229Spst 12697417Salfredextern void hash_Reset(hash_tbl *tbl, hash_freefp); 1273229Spst 12897417Salfredextern unsigned hash_HashFunction(u_char *str, u_int len); 1293229Spst 13097417Salfredextern int hash_Exists(hash_tbl *, u_int code, 13197417Salfred hash_cmpfp, hash_datum *key); 1323229Spst 13397417Salfredextern int hash_Insert(hash_tbl *, u_int code, 1343229Spst hash_cmpfp, hash_datum *key, 13597417Salfred hash_datum *element); 1363229Spst 13797417Salfredextern int hash_Delete(hash_tbl *, u_int code, 1383229Spst hash_cmpfp, hash_datum *key, 13997417Salfred hash_freefp); 1403229Spst 14197417Salfredextern hash_datum *hash_Lookup(hash_tbl *, u_int code, 14297417Salfred hash_cmpfp, hash_datum *key); 1433229Spst 14497417Salfredextern hash_datum *hash_FirstEntry(hash_tbl *); 1453229Spst 14697417Salfredextern hash_datum *hash_NextEntry(hash_tbl *); 1473229Spst 1483229Spst#endif /* HASH_H */ 149