1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
/*
* 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 {
hash_member *next; /* hash next pointer */
hash_datum *data; /* hash data */
time_t h_time; /* hash dynamic free time */
int h_count; /* hash reference count */
mutex_t h_mtx; /* hash mutex */
};
struct hash_tblstruct;
struct hash_bucketstruct {
hash_member *next;
struct hash_tblstruct *table;
rwlock_t rwlock;
};
struct hash_tblstruct_hdr {
unsigned size;
unsigned bucketnum;
hash_member *member;
};
struct hash_tblstruct {
unsigned size;
unsigned bucketnum;
hash_member *member; /* Used for linear dump */
boolean_t (*dfree_data)(); /* Used for dynamic free */
boolean_t dfree_lck; /* Use for dynamic free locking */
time_t dfree_time; /* Unused time to dynamically free */
hash_bucket *table; /* Dynamically Extend */
hash_bucket data[1];
};
extern unsigned hash_Size(unsigned int);
extern hash_tbl *hash_Init(unsigned, boolean_t (*)(), time_t, boolean_t);
extern void hash_Reset(hash_tbl *, boolean_t (*)());
extern void *hash_Insert(hash_tbl *, void *, unsigned, int (*)(),
hash_datum *, hash_datum *);
extern hash_datum *hash_Lookup(hash_tbl *, void *, unsigned, int (*)(),
hash_datum *, boolean_t);
extern boolean_t hash_Delete(hash_tbl *, void *, unsigned, int (*)(),
hash_datum *, boolean_t (*)());
extern void hash_Reap(hash_tbl *, boolean_t (*)());
extern void hash_Age(void *);
extern void hash_Dtime(void *, time_t);
extern int hash_Refcount(void *);
extern int hash_Htime(void *);
extern void hash_Rele(void *, boolean_t);
#ifdef __cplusplus
}
#endif
#endif /* _HASH_H */
|
