1*cd68fb44Swiz /* $NetBSD: hash.h,v 1.4 2003/02/02 10:24:41 wiz Exp $ */ 23fe138c1Sperry 35e9d01f2Sgwr #ifndef HASH_H 45e9d01f2Sgwr #define HASH_H 55e9d01f2Sgwr /* hash.h */ 65e9d01f2Sgwr /************************************************************************ 75e9d01f2Sgwr Copyright 1988, 1991 by Carnegie Mellon University 85e9d01f2Sgwr 95e9d01f2Sgwr All Rights Reserved 105e9d01f2Sgwr 115e9d01f2Sgwr Permission to use, copy, modify, and distribute this software and its 125e9d01f2Sgwr documentation for any purpose and without fee is hereby granted, provided 135e9d01f2Sgwr that the above copyright notice appear in all copies and that both that 145e9d01f2Sgwr copyright notice and this permission notice appear in supporting 155e9d01f2Sgwr documentation, and that the name of Carnegie Mellon University not be used 165e9d01f2Sgwr in advertising or publicity pertaining to distribution of the software 175e9d01f2Sgwr without specific, written prior permission. 185e9d01f2Sgwr 195e9d01f2Sgwr CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS 205e9d01f2Sgwr SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 215e9d01f2Sgwr IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL 225e9d01f2Sgwr DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 235e9d01f2Sgwr PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS 245e9d01f2Sgwr ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 255e9d01f2Sgwr SOFTWARE. 265e9d01f2Sgwr ************************************************************************/ 275e9d01f2Sgwr 285e9d01f2Sgwr /* 295e9d01f2Sgwr * Generalized hash table ADT 305e9d01f2Sgwr * 315e9d01f2Sgwr * Provides multiple, dynamically-allocated, variable-sized hash tables on 325e9d01f2Sgwr * various data and keys. 335e9d01f2Sgwr * 345e9d01f2Sgwr * This package attempts to follow some of the coding conventions suggested 355e9d01f2Sgwr * by Bob Sidebotham and the AFS Clean Code Committee. 365e9d01f2Sgwr */ 375e9d01f2Sgwr 385e9d01f2Sgwr 395e9d01f2Sgwr /* 405e9d01f2Sgwr * The user must supply the following: 415e9d01f2Sgwr * 425e9d01f2Sgwr * 1. A comparison function which is declared as: 435e9d01f2Sgwr * 445e9d01f2Sgwr * int compare(data1, data2) 455e9d01f2Sgwr * hash_datum *data1, *data2; 465e9d01f2Sgwr * 475e9d01f2Sgwr * This function must compare the desired fields of data1 and 485e9d01f2Sgwr * data2 and return TRUE (1) if the data should be considered 495e9d01f2Sgwr * equivalent (i.e. have the same key value) or FALSE (0) 505e9d01f2Sgwr * otherwise. This function is called through a pointer passed to 515e9d01f2Sgwr * the various hashtable functions (thus pointers to different 525e9d01f2Sgwr * functions may be passed to effect different tests on different 535e9d01f2Sgwr * hash tables). 545e9d01f2Sgwr * 555e9d01f2Sgwr * Internally, all the functions of this package always call the 565e9d01f2Sgwr * compare function with the "key" parameter as the first parameter, 575e9d01f2Sgwr * and a full data element as the second parameter. Thus, the key 585e9d01f2Sgwr * and element arguments to functions such as hash_Lookup() may 595e9d01f2Sgwr * actually be of different types and the programmer may provide a 605e9d01f2Sgwr * compare function which compares the two different object types 615e9d01f2Sgwr * as desired. 625e9d01f2Sgwr * 635e9d01f2Sgwr * Example: 645e9d01f2Sgwr * 655e9d01f2Sgwr * int compare(key, element) 665e9d01f2Sgwr * char *key; 675e9d01f2Sgwr * struct some_complex_structure *element; 685e9d01f2Sgwr * { 695e9d01f2Sgwr * return !strcmp(key, element->name); 705e9d01f2Sgwr * } 715e9d01f2Sgwr * 725e9d01f2Sgwr * key = "John C. Doe" 735e9d01f2Sgwr * element = &some_complex_structure 745e9d01f2Sgwr * hash_Lookup(table, hashcode, compare, key); 755e9d01f2Sgwr * 765e9d01f2Sgwr * 2. A hash function yielding an unsigned integer value to be used 775e9d01f2Sgwr * as the hashcode (index into the hashtable). Thus, the user 785e9d01f2Sgwr * may hash on whatever data is desired and may use several 795e9d01f2Sgwr * different hash functions for various different hash tables. 805e9d01f2Sgwr * The actual hash table index will be the passed hashcode modulo 815e9d01f2Sgwr * the hash table size. 825e9d01f2Sgwr * 835e9d01f2Sgwr * A generalized hash function, hash_HashFunction(), is included 845e9d01f2Sgwr * with this package to make things a little easier. It is not 85*cd68fb44Swiz * guaranteed to use the best hash algorithm in existence. . . . 865e9d01f2Sgwr */ 875e9d01f2Sgwr 885e9d01f2Sgwr 895e9d01f2Sgwr 905e9d01f2Sgwr /* 915e9d01f2Sgwr * Various hash table definitions 925e9d01f2Sgwr */ 935e9d01f2Sgwr 945e9d01f2Sgwr 955e9d01f2Sgwr /* 965e9d01f2Sgwr * Define "hash_datum" as a universal data type 975e9d01f2Sgwr */ 985e9d01f2Sgwr typedef void hash_datum; 995e9d01f2Sgwr 1005e9d01f2Sgwr typedef struct hash_memberstruct hash_member; 1015e9d01f2Sgwr typedef struct hash_tblstruct hash_tbl; 1025e9d01f2Sgwr typedef struct hash_tblstruct_hdr hash_tblhdr; 1035e9d01f2Sgwr 1045e9d01f2Sgwr struct hash_memberstruct { 1055e9d01f2Sgwr hash_member *next; 1065e9d01f2Sgwr hash_datum *data; 1075e9d01f2Sgwr }; 1085e9d01f2Sgwr 1095e9d01f2Sgwr struct hash_tblstruct_hdr { 1105e9d01f2Sgwr unsigned size, bucketnum; 1115e9d01f2Sgwr hash_member *member; 1125e9d01f2Sgwr }; 1135e9d01f2Sgwr 1145e9d01f2Sgwr struct hash_tblstruct { 1155e9d01f2Sgwr unsigned size, bucketnum; 1165e9d01f2Sgwr hash_member *member; /* Used for linear dump */ 1175e9d01f2Sgwr hash_member *table[1]; /* Dynamically extended */ 1185e9d01f2Sgwr }; 1195e9d01f2Sgwr 120131109e4Swiz typedef int (*hash_cmpfp)(hash_datum *, hash_datum *); 121131109e4Swiz typedef void (*hash_freefp)(hash_datum *); 1225e9d01f2Sgwr 123131109e4Swiz extern hash_tbl *hash_Init(u_int tablesize); 1245e9d01f2Sgwr 125131109e4Swiz extern void hash_Reset(hash_tbl *tbl, hash_freefp); 1265e9d01f2Sgwr 127131109e4Swiz extern unsigned hash_HashFunction(u_char *str, u_int len); 1285e9d01f2Sgwr 129131109e4Swiz extern int hash_Exists(hash_tbl *, u_int code, 130131109e4Swiz hash_cmpfp, hash_datum *key); 1315e9d01f2Sgwr 132131109e4Swiz extern int hash_Insert(hash_tbl *, u_int code, hash_cmpfp, 133131109e4Swiz hash_datum *key, hash_datum *element); 1345e9d01f2Sgwr 135131109e4Swiz extern int hash_Delete(hash_tbl *, u_int code, 1365e9d01f2Sgwr hash_cmpfp, hash_datum *key, 137131109e4Swiz hash_freefp); 1385e9d01f2Sgwr 139131109e4Swiz extern hash_datum *hash_Lookup(hash_tbl *, u_int code, 140131109e4Swiz hash_cmpfp, hash_datum *key); 1415e9d01f2Sgwr 142131109e4Swiz extern hash_datum *hash_FirstEntry(hash_tbl *); 1435e9d01f2Sgwr 144131109e4Swiz extern hash_datum *hash_NextEntry(hash_tbl *); 1455e9d01f2Sgwr 1465e9d01f2Sgwr #endif /* HASH_H */ 147