hash.h revision 97416
1219019Sgabor#ifndef HASH_H 2219019Sgabor#define HASH_H 3219019Sgabor/* hash.h */ 4219019Sgabor/************************************************************************ 5219019Sgabor Copyright 1988, 1991 by Carnegie Mellon University 6219019Sgabor 7219019Sgabor All Rights Reserved 8219019Sgabor 9219019SgaborPermission to use, copy, modify, and distribute this software and its 10219019Sgabordocumentation for any purpose and without fee is hereby granted, provided 11219019Sgaborthat the above copyright notice appear in all copies and that both that 12219019Sgaborcopyright notice and this permission notice appear in supporting 13219019Sgabordocumentation, and that the name of Carnegie Mellon University not be used 14219019Sgaborin advertising or publicity pertaining to distribution of the software 15219019Sgaborwithout specific, written prior permission. 16219019Sgabor 17219019SgaborCARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS 18219019SgaborSOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 19219019SgaborIN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL 20219019SgaborDAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 21219019SgaborPROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS 22219019SgaborACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 23219019SgaborSOFTWARE. 24219019Sgabor************************************************************************/ 25219019Sgabor 26219019Sgabor/* 27219019Sgabor * Generalized hash table ADT 28219019Sgabor * $FreeBSD: head/libexec/bootpd/hash.h 97416 2002-05-28 18:31:41Z alfred $ 29219019Sgabor * 30219019Sgabor * Provides multiple, dynamically-allocated, variable-sized hash tables on 31219019Sgabor * various data and keys. 32219019Sgabor * 33219019Sgabor * This package attempts to follow some of the coding conventions suggested 34219019Sgabor * by Bob Sidebotham and the AFS Clean Code Committee. 35219019Sgabor */ 36219019Sgabor 37219019Sgabor 38219019Sgabor/* 39219019Sgabor * The user must supply the following: 40219019Sgabor * 41219019Sgabor * 1. A comparison function which is declared as: 42219019Sgabor * 43219019Sgabor * int compare(data1, data2) 44219019Sgabor * hash_datum *data1, *data2; 45219019Sgabor * 46219019Sgabor * This function must compare the desired fields of data1 and 47219019Sgabor * data2 and return TRUE (1) if the data should be considered 48219019Sgabor * equivalent (i.e. have the same key value) or FALSE (0) 49219019Sgabor * otherwise. This function is called through a pointer passed to 50219019Sgabor * the various hashtable functions (thus pointers to different 51219019Sgabor * functions may be passed to effect different tests on different 52219019Sgabor * hash tables). 53219019Sgabor * 54219019Sgabor * Internally, all the functions of this package always call the 55219019Sgabor * compare function with the "key" parameter as the first parameter, 56219019Sgabor * and a full data element as the second parameter. Thus, the key 57219019Sgabor * and element arguments to functions such as hash_Lookup() may 58219019Sgabor * actually be of different types and the programmer may provide a 59219019Sgabor * compare function which compares the two different object types 60219019Sgabor * as desired. 61219019Sgabor * 62219019Sgabor * Example: 63219019Sgabor * 64219019Sgabor * int compare(key, element) 65219019Sgabor * char *key; 66219019Sgabor * struct some_complex_structure *element; 67219019Sgabor * { 68219019Sgabor * return !strcmp(key, element->name); 69219019Sgabor * } 70219019Sgabor * 71219019Sgabor * key = "John C. Doe" 72219019Sgabor * element = &some_complex_structure 73219019Sgabor * hash_Lookup(table, hashcode, compare, key); 74219019Sgabor * 75219019Sgabor * 2. A hash function yielding an unsigned integer value to be used 76219019Sgabor * as the hashcode (index into the hashtable). Thus, the user 77219019Sgabor * may hash on whatever data is desired and may use several 78219019Sgabor * different hash functions for various different hash tables. 79219019Sgabor * The actual hash table index will be the passed hashcode modulo 80219019Sgabor * the hash table size. 81219019Sgabor * 82219019Sgabor * A generalized hash function, hash_HashFunction(), is included 83219019Sgabor * with this package to make things a little easier. It is not 84219019Sgabor * guarenteed to use the best hash algorithm in existence. . . . 85219019Sgabor */ 86219019Sgabor 87219019Sgabor 88219019Sgabor 89219019Sgabor/* 90219019Sgabor * Various hash table definitions 91219019Sgabor */ 92219019Sgabor 93219019Sgabor 94219019Sgabor/* 95219019Sgabor * Define "hash_datum" as a universal data type 96219019Sgabor */ 97219019Sgabortypedef void hash_datum; 98219019Sgabor 99219019Sgabortypedef struct hash_memberstruct hash_member; 100219019Sgabortypedef struct hash_tblstruct hash_tbl; 101219019Sgabortypedef struct hash_tblstruct_hdr hash_tblhdr; 102219019Sgabor 103219019Sgaborstruct hash_memberstruct { 104219019Sgabor hash_member *next; 105219019Sgabor hash_datum *data; 106219019Sgabor}; 107219019Sgabor 108219019Sgaborstruct hash_tblstruct_hdr { 109219019Sgabor unsigned size, bucketnum; 110219019Sgabor hash_member *member; 111219019Sgabor}; 112219019Sgabor 113219019Sgaborstruct hash_tblstruct { 114219019Sgabor unsigned size, bucketnum; 115219019Sgabor hash_member *member; /* Used for linear dump */ 116219019Sgabor hash_member *table[1]; /* Dynamically extended */ 117219019Sgabor}; 118219019Sgabor 119219019Sgabor/* ANSI function prototypes or empty arg list? */ 120219019Sgabor#define P(args) args 121219019Sgabor 122219019Sgabortypedef int (*hash_cmpfp) P((hash_datum *, hash_datum *)); 123219019Sgabortypedef void (*hash_freefp) P((hash_datum *)); 124219019Sgabor 125219019Sgaborextern hash_tbl *hash_Init P((u_int tablesize)); 126219019Sgabor 127219019Sgaborextern void hash_Reset P((hash_tbl *tbl, hash_freefp)); 128219019Sgabor 129219019Sgaborextern unsigned hash_HashFunction P((u_char *str, u_int len)); 130219019Sgabor 131219019Sgaborextern int hash_Exists P((hash_tbl *, u_int code, 132219019Sgabor hash_cmpfp, hash_datum *key)); 133219019Sgabor 134219019Sgaborextern int hash_Insert P((hash_tbl *, u_int code, 135219019Sgabor hash_cmpfp, hash_datum *key, 136219019Sgabor hash_datum *element)); 137219019Sgabor 138219019Sgaborextern int hash_Delete P((hash_tbl *, u_int code, 139219019Sgabor hash_cmpfp, hash_datum *key, 140219019Sgabor hash_freefp)); 141219019Sgabor 142219019Sgaborextern hash_datum *hash_Lookup P((hash_tbl *, u_int code, 143219019Sgabor hash_cmpfp, hash_datum *key)); 144219019Sgabor 145219019Sgaborextern hash_datum *hash_FirstEntry P((hash_tbl *)); 146219019Sgabor 147219019Sgaborextern hash_datum *hash_NextEntry P((hash_tbl *)); 148219019Sgabor 149219019Sgabor#undef P 150219019Sgabor 151219019Sgabor#endif /* HASH_H */ 152219019Sgabor