1 #ifndef HASH_H 2 #define HASH_H 3 /* hash.h */ 4 /************************************************************************ 5 Copyright 1988, 1991 by Carnegie Mellon University 6 7 All Rights Reserved 8 9 Permission to use, copy, modify, and distribute this software and its 10 documentation for any purpose and without fee is hereby granted, provided 11 that the above copyright notice appear in all copies and that both that 12 copyright notice and this permission notice appear in supporting 13 documentation, and that the name of Carnegie Mellon University not be used 14 in advertising or publicity pertaining to distribution of the software 15 without specific, written prior permission. 16 17 CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS 18 SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 19 IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL 20 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 21 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS 22 ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 23 SOFTWARE. 24 ************************************************************************/ 25 26 /* 27 * Generalized hash table ADT 28 * 29 * Provides multiple, dynamically-allocated, variable-sized hash tables on 30 * various data and keys. 31 * 32 * This package attempts to follow some of the coding conventions suggested 33 * by Bob Sidebotham and the AFS Clean Code Committee. 34 */ 35 36 37 /* 38 * The user must supply the following: 39 * 40 * 1. A comparison function which is declared as: 41 * 42 * int compare(data1, data2) 43 * hash_datum *data1, *data2; 44 * 45 * This function must compare the desired fields of data1 and 46 * data2 and return TRUE (1) if the data should be considered 47 * equivalent (i.e. have the same key value) or FALSE (0) 48 * otherwise. This function is called through a pointer passed to 49 * the various hashtable functions (thus pointers to different 50 * functions may be passed to effect different tests on different 51 * hash tables). 52 * 53 * Internally, all the functions of this package always call the 54 * compare function with the "key" parameter as the first parameter, 55 * and a full data element as the second parameter. Thus, the key 56 * and element arguments to functions such as hash_Lookup() may 57 * actually be of different types and the programmer may provide a 58 * compare function which compares the two different object types 59 * as desired. 60 * 61 * Example: 62 * 63 * int compare(key, element) 64 * char *key; 65 * struct some_complex_structure *element; 66 * { 67 * return !strcmp(key, element->name); 68 * } 69 * 70 * key = "John C. Doe" 71 * element = &some_complex_structure 72 * hash_Lookup(table, hashcode, compare, key); 73 * 74 * 2. A hash function yielding an unsigned integer value to be used 75 * as the hashcode (index into the hashtable). Thus, the user 76 * may hash on whatever data is desired and may use several 77 * different hash functions for various different hash tables. 78 * The actual hash table index will be the passed hashcode modulo 79 * the hash table size. 80 * 81 * A generalized hash function, hash_HashFunction(), is included 82 * with this package to make things a little easier. It is not 83 * guarenteed to use the best hash algorithm in existence. . . . 84 */ 85 86 87 88 /* 89 * Various hash table definitions 90 */ 91 92 93 /* 94 * Define "hash_datum" as a universal data type 95 */ 96 #ifdef __STDC__ 97 typedef void hash_datum; 98 #else 99 typedef char hash_datum; 100 #endif 101 102 typedef struct hash_memberstruct hash_member; 103 typedef struct hash_tblstruct hash_tbl; 104 typedef struct hash_tblstruct_hdr hash_tblhdr; 105 106 struct hash_memberstruct { 107 hash_member *next; 108 hash_datum *data; 109 }; 110 111 struct hash_tblstruct_hdr { 112 unsigned size, bucketnum; 113 hash_member *member; 114 }; 115 116 struct hash_tblstruct { 117 unsigned size, bucketnum; 118 hash_member *member; /* Used for linear dump */ 119 hash_member *table[1]; /* Dynamically extended */ 120 }; 121 122 typedef int (*hash_cmpfp)(hash_datum *, hash_datum *); 123 typedef void (*hash_freefp)(hash_datum *); 124 125 extern hash_tbl *hash_Init(u_int tablesize); 126 127 extern void hash_Reset(hash_tbl *tbl, hash_freefp); 128 129 extern unsigned hash_HashFunction(u_char *str, u_int len); 130 131 extern int hash_Exists(hash_tbl *, u_int code, 132 hash_cmpfp, hash_datum *key); 133 134 extern int hash_Insert(hash_tbl *, u_int code, 135 hash_cmpfp, hash_datum *key, 136 hash_datum *element); 137 138 extern int hash_Delete(hash_tbl *, u_int code, 139 hash_cmpfp, hash_datum *key, 140 hash_freefp); 141 142 extern hash_datum *hash_Lookup(hash_tbl *, u_int code, 143 hash_cmpfp, hash_datum *key); 144 145 extern hash_datum *hash_FirstEntry(hash_tbl *); 146 147 extern hash_datum *hash_NextEntry(hash_tbl *); 148 149 #endif /* HASH_H */ 150