hash.h revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* Copyright (c) 1993-2001 by Sun Microsystems, Inc.
* All rights reserved.
*/
/*
* Copyright 1988, 1991 by Carnegie Mellon University
* All Rights Reserved
*
* Permission to use, copy, modify, and distribute this software and its
* documentation for any purpose and without fee is hereby granted, provided
* that the above copyright notice appear in all copies and that both that
* copyright notice and this permission notice appear in supporting
* documentation, and that the name of Carnegie Mellon University not be used
* in advertising or publicity pertaining to distribution of the software
* without specific, written prior permission.
*
* CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
* SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
* IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
* DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
* PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
* ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
* THIS SOFTWARE.
*/
#ifndef _HASH_H
#define _HASH_H
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* Generalized hash table ADT
*
* Provides multiple, dynamically-allocated, variable-sized hash tables on
* various data and keys.
*
* This package attempts to follow some of the coding conventions suggested
* by Bob Sidebotham and the AFS Clean Code Committee.
*/
/*
* The user must supply the following:
*
* 1. A comparison function which is declared as:
*
* int compare(data1, data2)
* hash_datum *data1, *data2;
*
* This function must compare the desired fields of data1 and
* data2 and return B_TRUE (1) if the data should be considered
* equivalent (i.e. have the same key value) or B_FALSE (0)
* otherwise. This function is called through a pointer passed to
* the various hashtable functions (thus pointers to different
* functions may be passed to effect different tests on different
* hash tables).
*
* Internally, all the functions of this package always call the
* compare function with the "key" parameter as the first parameter,
* and a full data element as the second parameter. Thus, the key
* and element arguments to functions such as hash_Lookup() may
* actually be of different types and the programmer may provide a
* compare function which compares the two different object types
* as desired.
*
* Example:
*
* int compare(key, element)
* char *key;
* struct some_complex_structure *element;
* {
* return !strcmp(key, element->name);
* }
*
* key = "John C. Doe"
* element = &some_complex_structure
* hash_Lookup(table, hashptr, hashlen, compare, key, free_rec, B_TRUE);
*
* 2. A hash function yielding an unsigned integer value to be used
* as the hashcode (index into the hashtable). Thus, the user
* may hash on whatever data is desired and may use several
* different hash functions for various different hash tables.
* The actual hash table index will be the passed hashcode modulo
* the hash table size.
*
* A generalized hash function, hash_HashFunction(), is included
* with this package to make things a little easier. It is not
* guarenteed to use the best hash algorithm in existence. . . .
*
* 3. An ability to garbage collect data has been added. Timed garbage
* collection of hash members is provided to relieve the interface and worker
* threads of explicit data structure management. Expired data structures
* are pruned during hash insertion and deletion, or by explicit calls
* to Delete and Reap functions.
*/
#ifdef __cplusplus
extern "C" {
#endif
/*
* Various hash table definitions
*/
/*
* Define "hash_datum" as a universal data type
*/
typedef void hash_datum;
typedef void *hash_handle;
typedef struct hash_memberstruct hash_member;
typedef struct hash_bucketstruct hash_bucket;
typedef struct hash_tblstruct hash_tbl;
typedef struct hash_tblstruct_hdr hash_tblhdr;
struct hash_memberstruct {
int h_count; /* hash reference count */
};
struct hash_tblstruct;
struct hash_bucketstruct {
struct hash_tblstruct *table;
};
struct hash_tblstruct_hdr {
unsigned size;
unsigned bucketnum;
};
struct hash_tblstruct {
unsigned size;
unsigned bucketnum;
};
extern unsigned hash_Size(unsigned int);
extern void *hash_Insert(hash_tbl *, void *, unsigned, int (*)(),
hash_datum *, hash_datum *);
hash_datum *, boolean_t);
hash_datum *, boolean_t (*)());
extern void hash_Age(void *);
extern void hash_Dtime(void *, time_t);
extern int hash_Refcount(void *);
extern int hash_Htime(void *);
#ifdef __cplusplus
}
#endif
#endif /* _HASH_H */