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