Home | History | Annotate | Line # | Download | only in common
hash.h revision 1.1 
      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 
     89 /*
     90  * Various hash table definitions
     91  */
     92 
     93 
     94 /*
     95  * Define "hash_datum" as a universal data type
     96  */
     97 #ifdef __STDC__
     98 typedef void hash_datum;
     99 #else
    100 typedef char hash_datum;
    101 #endif
    102 
    103 typedef struct hash_memberstruct  hash_member;
    104 typedef struct hash_tblstruct     hash_tbl;
    105 typedef struct hash_tblstruct_hdr hash_tblhdr;
    106 
    107 struct hash_memberstruct {
    108     hash_member *next;
    109     hash_datum  *data;
    110 };
    111 
    112 struct hash_tblstruct_hdr {
    113     unsigned	size, bucketnum;
    114     hash_member *member;
    115 };
    116 
    117 struct hash_tblstruct {
    118     unsigned	size, bucketnum;
    119     hash_member *member;		/* Used for linear dump */
    120     hash_member	*table[1];		/* Dynamically extended */
    121 };
    122 
    123 /* ANSI function prototypes or empty arg list? */
    124 #ifdef	__STDC__
    125 #define P(args) args
    126 #else
    127 #define P(args) ()
    128 #endif
    129 
    130 typedef int (*hash_cmpfp) P((hash_datum *, hash_datum *));
    131 typedef void (*hash_freefp) P((hash_datum *));
    132 
    133 extern hash_tbl	  *hash_Init P((u_int tablesize));
    134 
    135 extern void	   hash_Reset P((hash_tbl *tbl, hash_freefp));
    136 
    137 extern unsigned	   hash_HashFunction P((u_char *str, u_int len));
    138 
    139 extern int	   hash_Exists P((hash_tbl *, u_int code,
    140 				  hash_cmpfp, hash_datum *key));
    141 
    142 extern int	   hash_Insert P((hash_tbl *, u_int code,
    143 				  hash_cmpfp, hash_datum *key,
    144 				  hash_datum *element));
    145 
    146 extern int	   hash_Delete P((hash_tbl *, u_int code,
    147 				  hash_cmpfp, hash_datum *key,
    148 				  hash_freefp));
    149 
    150 extern hash_datum *hash_Lookup P((hash_tbl *, u_int code,
    151 				  hash_cmpfp, hash_datum *key));
    152 
    153 extern hash_datum *hash_FirstEntry P((hash_tbl *));
    154 
    155 extern hash_datum *hash_NextEntry P((hash_tbl *));
    156 
    157 #undef P
    158 
    159 #endif	/* HASH_H */
    160