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