1*9e39c5baSBill Taylor /*
2*9e39c5baSBill Taylor * CDDL HEADER START
3*9e39c5baSBill Taylor *
4*9e39c5baSBill Taylor * The contents of this file are subject to the terms of the
5*9e39c5baSBill Taylor * Common Development and Distribution License (the "License").
6*9e39c5baSBill Taylor * You may not use this file except in compliance with the License.
7*9e39c5baSBill Taylor *
8*9e39c5baSBill Taylor * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9*9e39c5baSBill Taylor * or http://www.opensolaris.org/os/licensing.
10*9e39c5baSBill Taylor * See the License for the specific language governing permissions
11*9e39c5baSBill Taylor * and limitations under the License.
12*9e39c5baSBill Taylor *
13*9e39c5baSBill Taylor * When distributing Covered Code, include this CDDL HEADER in each
14*9e39c5baSBill Taylor * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15*9e39c5baSBill Taylor * If applicable, add the following below this CDDL HEADER, with the
16*9e39c5baSBill Taylor * fields enclosed by brackets "[]" replaced with your own identifying
17*9e39c5baSBill Taylor * information: Portions Copyright [yyyy] [name of copyright owner]
18*9e39c5baSBill Taylor *
19*9e39c5baSBill Taylor * CDDL HEADER END
20*9e39c5baSBill Taylor */
21*9e39c5baSBill Taylor
22*9e39c5baSBill Taylor /*
23*9e39c5baSBill Taylor * Copyright (c) 2002-2003, Network Appliance, Inc. All rights reserved.
24*9e39c5baSBill Taylor */
25*9e39c5baSBill Taylor
26*9e39c5baSBill Taylor /*
27*9e39c5baSBill Taylor * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
28*9e39c5baSBill Taylor * Use is subject to license terms.
29*9e39c5baSBill Taylor */
30*9e39c5baSBill Taylor
31*9e39c5baSBill Taylor /*
32*9e39c5baSBill Taylor *
33*9e39c5baSBill Taylor * MODULE: dapl_hash.c
34*9e39c5baSBill Taylor *
35*9e39c5baSBill Taylor * PURPOSE: Hash Table
36*9e39c5baSBill Taylor * Description:
37*9e39c5baSBill Taylor *
38*9e39c5baSBill Taylor * Provides a generic hash table with chaining.
39*9e39c5baSBill Taylor *
40*9e39c5baSBill Taylor * $Id: dapl_hash.c,v 1.10 2003/07/11 18:42:17 hobie16 Exp $
41*9e39c5baSBill Taylor */
42*9e39c5baSBill Taylor
43*9e39c5baSBill Taylor #include "dapl_hash.h"
44*9e39c5baSBill Taylor
45*9e39c5baSBill Taylor /*
46*9e39c5baSBill Taylor *
47*9e39c5baSBill Taylor * Structures
48*9e39c5baSBill Taylor *
49*9e39c5baSBill Taylor */
50*9e39c5baSBill Taylor
51*9e39c5baSBill Taylor /*
52*9e39c5baSBill Taylor * A hash table element
53*9e39c5baSBill Taylor */
54*9e39c5baSBill Taylor typedef struct DAPL_HASH_ELEM
55*9e39c5baSBill Taylor {
56*9e39c5baSBill Taylor struct DAPL_HASH_ELEM *next_element;
57*9e39c5baSBill Taylor DAPL_HASH_KEY key;
58*9e39c5baSBill Taylor void *datum;
59*9e39c5baSBill Taylor } DAPL_HASH_ELEM;
60*9e39c5baSBill Taylor
61*9e39c5baSBill Taylor /*
62*9e39c5baSBill Taylor * The hash table
63*9e39c5baSBill Taylor */
64*9e39c5baSBill Taylor struct dapl_hash_table
65*9e39c5baSBill Taylor {
66*9e39c5baSBill Taylor unsigned long num_entries;
67*9e39c5baSBill Taylor unsigned long tbl_size;
68*9e39c5baSBill Taylor DAPL_HASH_ELEM *table;
69*9e39c5baSBill Taylor DAT_BOOLEAN locking_required; /* internal locking reqd */
70*9e39c5baSBill Taylor DAPL_OS_LOCK lock;
71*9e39c5baSBill Taylor unsigned long iterator_bucket;
72*9e39c5baSBill Taylor DAPL_HASH_ELEM *iterator;
73*9e39c5baSBill Taylor /*
74*9e39c5baSBill Taylor * statistics - we tally on insert operations, counting
75*9e39c5baSBill Taylor * the number of entries in the whole hash table, as
76*9e39c5baSBill Taylor * well as the length of chains we walk to insert. This
77*9e39c5baSBill Taylor * ignores empty buckets, giving us data on overall table
78*9e39c5baSBill Taylor * occupancy, as well as max/average chain length for
79*9e39c5baSBill Taylor * the buckets used. If our hash function results in
80*9e39c5baSBill Taylor * hot buckets, this will show it.
81*9e39c5baSBill Taylor */
82*9e39c5baSBill Taylor uint64_t hash_tbl_inserts; /* total inserts ops */
83*9e39c5baSBill Taylor uint64_t hash_tbl_max; /* max in entire table */
84*9e39c5baSBill Taylor uint64_t hash_tbl_total; /* total in table */
85*9e39c5baSBill Taylor uint64_t hash_chn_max; /* longest chain */
86*9e39c5baSBill Taylor uint64_t hash_chn_total; /* total non-0 lenghts */
87*9e39c5baSBill Taylor };
88*9e39c5baSBill Taylor
89*9e39c5baSBill Taylor
90*9e39c5baSBill Taylor /*
91*9e39c5baSBill Taylor *
92*9e39c5baSBill Taylor * Defines
93*9e39c5baSBill Taylor *
94*9e39c5baSBill Taylor */
95*9e39c5baSBill Taylor
96*9e39c5baSBill Taylor /* The hash function */
97*9e39c5baSBill Taylor #define DAPL_DOHASH(key, hashsize) ((uint64_t)((key) % (hashsize)))
98*9e39c5baSBill Taylor
99*9e39c5baSBill Taylor /* datum value in empty table slots (use 0UL or ~0UL as appropriate) */
100*9e39c5baSBill Taylor #define NO_DATUM_VALUE ((void *) 0UL)
101*9e39c5baSBill Taylor #define NO_DATUM(value) ((value) == NO_DATUM_VALUE)
102*9e39c5baSBill Taylor
103*9e39c5baSBill Taylor /* Lookup macro (which falls back to function to rehash) */
104*9e39c5baSBill Taylor #define DAPL_HASHLOOKUP(p_table, in_key, out_datum, bucket_head) \
105*9e39c5baSBill Taylor { \
106*9e39c5baSBill Taylor DAPL_HASH_ELEM *element = \
107*9e39c5baSBill Taylor &((p_table)->table)[DAPL_DOHASH(in_key, (p_table)->tbl_size)]; \
108*9e39c5baSBill Taylor if (NO_DATUM(element->datum)) { \
109*9e39c5baSBill Taylor (bucket_head) = (void *)0; \
110*9e39c5baSBill Taylor } else if (element->key == (DAPL_HASH_KEY) (in_key)) { \
111*9e39c5baSBill Taylor (out_datum) = element->datum; \
112*9e39c5baSBill Taylor (bucket_head) = (void *)element; \
113*9e39c5baSBill Taylor } else if (element->next_element) { \
114*9e39c5baSBill Taylor dapli_hash_rehash(element, \
115*9e39c5baSBill Taylor (in_key), \
116*9e39c5baSBill Taylor (void **)&(out_datum), \
117*9e39c5baSBill Taylor (DAPL_HASH_ELEM **)&(bucket_head)); \
118*9e39c5baSBill Taylor } else { \
119*9e39c5baSBill Taylor (bucket_head) = (void *)0; \
120*9e39c5baSBill Taylor }\
121*9e39c5baSBill Taylor }
122*9e39c5baSBill Taylor
123*9e39c5baSBill Taylor
124*9e39c5baSBill Taylor /*
125*9e39c5baSBill Taylor *
126*9e39c5baSBill Taylor * Internal Functions
127*9e39c5baSBill Taylor *
128*9e39c5baSBill Taylor */
129*9e39c5baSBill Taylor
130*9e39c5baSBill Taylor /*
131*9e39c5baSBill Taylor * Rehash the key (used by add and lookup functions)
132*9e39c5baSBill Taylor *
133*9e39c5baSBill Taylor * Inputs: element element to rehash key
134*9e39c5baSBill Taylor * key, datum datum for key head
135*9e39c5baSBill Taylor * head head for list
136*9e39c5baSBill Taylor */
137*9e39c5baSBill Taylor static void
dapli_hash_rehash(DAPL_HASH_ELEM * element,DAPL_HASH_KEY key,void ** datum,DAPL_HASH_ELEM ** head)138*9e39c5baSBill Taylor dapli_hash_rehash(
139*9e39c5baSBill Taylor DAPL_HASH_ELEM *element,
140*9e39c5baSBill Taylor DAPL_HASH_KEY key,
141*9e39c5baSBill Taylor void **datum,
142*9e39c5baSBill Taylor DAPL_HASH_ELEM ** head)
143*9e39c5baSBill Taylor {
144*9e39c5baSBill Taylor /*
145*9e39c5baSBill Taylor * assume we looked at the contents of element already,
146*9e39c5baSBill Taylor * and start with the next element.
147*9e39c5baSBill Taylor */
148*9e39c5baSBill Taylor dapl_os_assert(element->next_element);
149*9e39c5baSBill Taylor dapl_os_assert(!NO_DATUM(element->datum));
150*9e39c5baSBill Taylor
151*9e39c5baSBill Taylor *head = element;
152*9e39c5baSBill Taylor /*CONSTCOND*/
153*9e39c5baSBill Taylor while (1) {
154*9e39c5baSBill Taylor element = element->next_element;
155*9e39c5baSBill Taylor if (!element) {
156*9e39c5baSBill Taylor break;
157*9e39c5baSBill Taylor }
158*9e39c5baSBill Taylor if (element->key == key) {
159*9e39c5baSBill Taylor *datum = element->datum;
160*9e39c5baSBill Taylor return;
161*9e39c5baSBill Taylor }
162*9e39c5baSBill Taylor }
163*9e39c5baSBill Taylor *head = 0;
164*9e39c5baSBill Taylor }
165*9e39c5baSBill Taylor
166*9e39c5baSBill Taylor /*
167*9e39c5baSBill Taylor * Add a new key to the hash table
168*9e39c5baSBill Taylor *
169*9e39c5baSBill Taylor * Inputs:
170*9e39c5baSBill Taylor * table, key and datum to be added
171*9e39c5baSBill Taylor * allow_dup - DAT_TRUE if dups are allowed
172*9e39c5baSBill Taylor * Outputs:
173*9e39c5baSBill Taylor * report_dup - should you care to know
174*9e39c5baSBill Taylor * Returns:
175*9e39c5baSBill Taylor * DAT_TRUE on success
176*9e39c5baSBill Taylor */
177*9e39c5baSBill Taylor static DAT_BOOLEAN
dapli_hash_add(DAPL_HASH_TABLEP p_table,DAPL_HASH_KEY key,void * datum,DAT_BOOLEAN allow_dup,DAT_BOOLEAN * report_dup)178*9e39c5baSBill Taylor dapli_hash_add(
179*9e39c5baSBill Taylor DAPL_HASH_TABLEP p_table,
180*9e39c5baSBill Taylor DAPL_HASH_KEY key,
181*9e39c5baSBill Taylor void *datum,
182*9e39c5baSBill Taylor DAT_BOOLEAN allow_dup,
183*9e39c5baSBill Taylor DAT_BOOLEAN *report_dup)
184*9e39c5baSBill Taylor {
185*9e39c5baSBill Taylor void *olddatum;
186*9e39c5baSBill Taylor DAPL_HASH_KEY hashValue;
187*9e39c5baSBill Taylor DAPL_HASH_ELEM *found;
188*9e39c5baSBill Taylor DAT_BOOLEAN status = DAT_FALSE;
189*9e39c5baSBill Taylor unsigned int chain_len = 0;
190*9e39c5baSBill Taylor
191*9e39c5baSBill Taylor if (report_dup) {
192*9e39c5baSBill Taylor (*report_dup) = DAT_FALSE;
193*9e39c5baSBill Taylor }
194*9e39c5baSBill Taylor
195*9e39c5baSBill Taylor if (NO_DATUM(datum)) {
196*9e39c5baSBill Taylor /*
197*9e39c5baSBill Taylor * Reserved value used for datum
198*9e39c5baSBill Taylor */
199*9e39c5baSBill Taylor dapl_dbg_log(
200*9e39c5baSBill Taylor DAPL_DBG_TYPE_ERR,
201*9e39c5baSBill Taylor "dapli_hash_add () called with magic NO_DATA value "
202*9e39c5baSBill Taylor "(%p) used as datum!\n", datum);
203*9e39c5baSBill Taylor return (DAT_FALSE);
204*9e39c5baSBill Taylor }
205*9e39c5baSBill Taylor
206*9e39c5baSBill Taylor DAPL_HASHLOOKUP(p_table, key, olddatum, found);
207*9e39c5baSBill Taylor
208*9e39c5baSBill Taylor if (found) {
209*9e39c5baSBill Taylor /*
210*9e39c5baSBill Taylor * key exists already
211*9e39c5baSBill Taylor */
212*9e39c5baSBill Taylor if (report_dup) {
213*9e39c5baSBill Taylor *report_dup = DAT_TRUE;
214*9e39c5baSBill Taylor }
215*9e39c5baSBill Taylor
216*9e39c5baSBill Taylor if (!allow_dup) {
217*9e39c5baSBill Taylor dapl_dbg_log(DAPL_DBG_TYPE_ERR,
218*9e39c5baSBill Taylor "dapli_hash_add () called with duplicate key "
219*9e39c5baSBill Taylor "(" F64x ")\n", key);
220*9e39c5baSBill Taylor return (DAT_FALSE);
221*9e39c5baSBill Taylor }
222*9e39c5baSBill Taylor }
223*9e39c5baSBill Taylor
224*9e39c5baSBill Taylor hashValue = DAPL_DOHASH(key, p_table->tbl_size);
225*9e39c5baSBill Taylor if (NO_DATUM(p_table->table[hashValue].datum)) {
226*9e39c5baSBill Taylor /*
227*9e39c5baSBill Taylor * Empty head - just fill it in
228*9e39c5baSBill Taylor */
229*9e39c5baSBill Taylor p_table->table[hashValue].key = key;
230*9e39c5baSBill Taylor p_table->table[hashValue].datum = datum;
231*9e39c5baSBill Taylor p_table->table[hashValue].next_element = 0;
232*9e39c5baSBill Taylor p_table->num_entries++;
233*9e39c5baSBill Taylor status = DAT_TRUE;
234*9e39c5baSBill Taylor } else {
235*9e39c5baSBill Taylor DAPL_HASH_ELEM *newelement = (DAPL_HASH_ELEM *)
236*9e39c5baSBill Taylor dapl_os_alloc(sizeof (DAPL_HASH_ELEM));
237*9e39c5baSBill Taylor /*
238*9e39c5baSBill Taylor * Add an element to the end of the chain
239*9e39c5baSBill Taylor */
240*9e39c5baSBill Taylor if (newelement) {
241*9e39c5baSBill Taylor DAPL_HASH_ELEM *lastelement;
242*9e39c5baSBill Taylor newelement->key = key;
243*9e39c5baSBill Taylor newelement->datum = datum;
244*9e39c5baSBill Taylor newelement->next_element = 0;
245*9e39c5baSBill Taylor for (lastelement = &p_table->table[hashValue];
246*9e39c5baSBill Taylor lastelement->next_element;
247*9e39c5baSBill Taylor lastelement = lastelement->next_element) {
248*9e39c5baSBill Taylor /* Walk to the end of the chain */
249*9e39c5baSBill Taylor chain_len++;
250*9e39c5baSBill Taylor }
251*9e39c5baSBill Taylor lastelement->next_element = newelement;
252*9e39c5baSBill Taylor p_table->num_entries++;
253*9e39c5baSBill Taylor status = DAT_TRUE;
254*9e39c5baSBill Taylor } else {
255*9e39c5baSBill Taylor /* allocation failed - should not happen */
256*9e39c5baSBill Taylor status = DAT_FALSE;
257*9e39c5baSBill Taylor }
258*9e39c5baSBill Taylor }
259*9e39c5baSBill Taylor
260*9e39c5baSBill Taylor /*
261*9e39c5baSBill Taylor * Tally up our counters. chain_len is one less than current chain
262*9e39c5baSBill Taylor * length.
263*9e39c5baSBill Taylor */
264*9e39c5baSBill Taylor chain_len++;
265*9e39c5baSBill Taylor p_table->hash_tbl_inserts++;
266*9e39c5baSBill Taylor p_table->hash_tbl_total += p_table->num_entries;
267*9e39c5baSBill Taylor p_table->hash_chn_total += chain_len;
268*9e39c5baSBill Taylor if (p_table->num_entries > p_table->hash_tbl_max) {
269*9e39c5baSBill Taylor p_table->hash_tbl_max = p_table->num_entries;
270*9e39c5baSBill Taylor }
271*9e39c5baSBill Taylor if (chain_len > p_table->hash_chn_max) {
272*9e39c5baSBill Taylor p_table->hash_chn_max = chain_len;
273*9e39c5baSBill Taylor }
274*9e39c5baSBill Taylor
275*9e39c5baSBill Taylor return (status);
276*9e39c5baSBill Taylor }
277*9e39c5baSBill Taylor
278*9e39c5baSBill Taylor
279*9e39c5baSBill Taylor /*
280*9e39c5baSBill Taylor * Remove element from hash bucket
281*9e39c5baSBill Taylor *
282*9e39c5baSBill Taylor * Inputs:
283*9e39c5baSBill Taylor * element, key to be deleted
284*9e39c5baSBill Taylor * Returns:
285*9e39c5baSBill Taylor * DAT_TRUE on success
286*9e39c5baSBill Taylor */
287*9e39c5baSBill Taylor static DAT_BOOLEAN
dapl_hash_delete_element(DAPL_HASH_ELEM * element,DAPL_HASH_KEY key,DAPL_HASH_DATA * p_datum)288*9e39c5baSBill Taylor dapl_hash_delete_element(DAPL_HASH_ELEM * element,
289*9e39c5baSBill Taylor DAPL_HASH_KEY key,
290*9e39c5baSBill Taylor DAPL_HASH_DATA *p_datum)
291*9e39c5baSBill Taylor {
292*9e39c5baSBill Taylor DAPL_HASH_ELEM *curelement;
293*9e39c5baSBill Taylor DAPL_HASH_ELEM *lastelement;
294*9e39c5baSBill Taylor
295*9e39c5baSBill Taylor lastelement = NULL;
296*9e39c5baSBill Taylor for (curelement = element; curelement;
297*9e39c5baSBill Taylor lastelement = curelement,
298*9e39c5baSBill Taylor curelement = curelement->next_element) {
299*9e39c5baSBill Taylor if (curelement->key == key) {
300*9e39c5baSBill Taylor if (p_datum) {
301*9e39c5baSBill Taylor *p_datum = curelement->datum;
302*9e39c5baSBill Taylor }
303*9e39c5baSBill Taylor if (lastelement) {
304*9e39c5baSBill Taylor /*
305*9e39c5baSBill Taylor * curelement was malloc'd; free it
306*9e39c5baSBill Taylor */
307*9e39c5baSBill Taylor lastelement->next_element =
308*9e39c5baSBill Taylor curelement->next_element;
309*9e39c5baSBill Taylor dapl_os_free((void *) curelement,
310*9e39c5baSBill Taylor sizeof (DAPL_HASH_ELEM));
311*9e39c5baSBill Taylor } else {
312*9e39c5baSBill Taylor /*
313*9e39c5baSBill Taylor * curelement is static list head
314*9e39c5baSBill Taylor */
315*9e39c5baSBill Taylor DAPL_HASH_ELEM *n = curelement->next_element;
316*9e39c5baSBill Taylor if (n) {
317*9e39c5baSBill Taylor /*
318*9e39c5baSBill Taylor * If there is a next element, copy its
319*9e39c5baSBill Taylor * contents into the head and free the
320*9e39c5baSBill Taylor * original next element.
321*9e39c5baSBill Taylor */
322*9e39c5baSBill Taylor curelement->key = n->key;
323*9e39c5baSBill Taylor curelement->datum = n->datum;
324*9e39c5baSBill Taylor curelement->next_element =
325*9e39c5baSBill Taylor n->next_element;
326*9e39c5baSBill Taylor dapl_os_free((void *) n,
327*9e39c5baSBill Taylor sizeof (DAPL_HASH_ELEM));
328*9e39c5baSBill Taylor } else {
329*9e39c5baSBill Taylor curelement->datum = NO_DATUM_VALUE;
330*9e39c5baSBill Taylor }
331*9e39c5baSBill Taylor }
332*9e39c5baSBill Taylor break;
333*9e39c5baSBill Taylor }
334*9e39c5baSBill Taylor }
335*9e39c5baSBill Taylor
336*9e39c5baSBill Taylor return (curelement != NULL ? DAT_TRUE : DAT_FALSE);
337*9e39c5baSBill Taylor }
338*9e39c5baSBill Taylor
339*9e39c5baSBill Taylor
340*9e39c5baSBill Taylor /*
341*9e39c5baSBill Taylor *
342*9e39c5baSBill Taylor * External Functions
343*9e39c5baSBill Taylor *
344*9e39c5baSBill Taylor */
345*9e39c5baSBill Taylor
346*9e39c5baSBill Taylor
347*9e39c5baSBill Taylor /*
348*9e39c5baSBill Taylor * Create a new hash table with at least 'table_size' hash buckets.
349*9e39c5baSBill Taylor */
350*9e39c5baSBill Taylor DAT_RETURN
dapls_hash_create(IN DAT_COUNT table_size,IN DAT_BOOLEAN locking_required,OUT DAPL_HASH_TABLE ** pp_table)351*9e39c5baSBill Taylor dapls_hash_create(
352*9e39c5baSBill Taylor IN DAT_COUNT table_size,
353*9e39c5baSBill Taylor IN DAT_BOOLEAN locking_required,
354*9e39c5baSBill Taylor OUT DAPL_HASH_TABLE **pp_table)
355*9e39c5baSBill Taylor {
356*9e39c5baSBill Taylor DAPL_HASH_TABLE *p_table;
357*9e39c5baSBill Taylor DAT_COUNT table_length = table_size * sizeof (DAPL_HASH_ELEM);
358*9e39c5baSBill Taylor DAT_RETURN dat_status;
359*9e39c5baSBill Taylor DAT_COUNT i;
360*9e39c5baSBill Taylor
361*9e39c5baSBill Taylor dapl_os_assert(pp_table);
362*9e39c5baSBill Taylor dat_status = DAT_SUCCESS;
363*9e39c5baSBill Taylor
364*9e39c5baSBill Taylor /* Allocate hash table */
365*9e39c5baSBill Taylor p_table = dapl_os_alloc(sizeof (DAPL_HASH_TABLE));
366*9e39c5baSBill Taylor if (NULL == p_table) {
367*9e39c5baSBill Taylor dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
368*9e39c5baSBill Taylor DAT_RESOURCE_MEMORY);
369*9e39c5baSBill Taylor goto bail;
370*9e39c5baSBill Taylor }
371*9e39c5baSBill Taylor
372*9e39c5baSBill Taylor /* Init hash table, allocate and init and buckets */
373*9e39c5baSBill Taylor (void) dapl_os_memzero(p_table, sizeof (DAPL_HASH_TABLE));
374*9e39c5baSBill Taylor p_table->tbl_size = table_size;
375*9e39c5baSBill Taylor p_table->table = (DAPL_HASH_ELEM *)dapl_os_alloc(table_length);
376*9e39c5baSBill Taylor if (NULL == p_table->table) {
377*9e39c5baSBill Taylor dapl_os_free(p_table, sizeof (DAPL_HASH_TABLE));
378*9e39c5baSBill Taylor dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
379*9e39c5baSBill Taylor DAT_RESOURCE_MEMORY);
380*9e39c5baSBill Taylor goto bail;
381*9e39c5baSBill Taylor }
382*9e39c5baSBill Taylor /* Init the lock anyways */
383*9e39c5baSBill Taylor dapl_os_lock_init(&p_table->lock);
384*9e39c5baSBill Taylor p_table->locking_required = locking_required;
385*9e39c5baSBill Taylor
386*9e39c5baSBill Taylor for (i = 0; i < table_size; i++) {
387*9e39c5baSBill Taylor p_table->table[i].datum = NO_DATUM_VALUE;
388*9e39c5baSBill Taylor p_table->table[i].key = 0;
389*9e39c5baSBill Taylor p_table->table[i].next_element = 0;
390*9e39c5baSBill Taylor }
391*9e39c5baSBill Taylor
392*9e39c5baSBill Taylor *pp_table = p_table;
393*9e39c5baSBill Taylor
394*9e39c5baSBill Taylor bail:
395*9e39c5baSBill Taylor return (dat_status);
396*9e39c5baSBill Taylor }
397*9e39c5baSBill Taylor
398*9e39c5baSBill Taylor
399*9e39c5baSBill Taylor /*
400*9e39c5baSBill Taylor * Destroy a hash table
401*9e39c5baSBill Taylor */
402*9e39c5baSBill Taylor DAT_RETURN
dapls_hash_free(IN DAPL_HASH_TABLE * p_table)403*9e39c5baSBill Taylor dapls_hash_free(
404*9e39c5baSBill Taylor IN DAPL_HASH_TABLE *p_table)
405*9e39c5baSBill Taylor {
406*9e39c5baSBill Taylor dapl_os_assert(p_table && p_table->table);
407*9e39c5baSBill Taylor
408*9e39c5baSBill Taylor dapl_os_lock_destroy(&p_table->lock);
409*9e39c5baSBill Taylor dapl_os_free(p_table->table,
410*9e39c5baSBill Taylor sizeof (DAPL_HASH_ELEM) * p_table->tbl_size);
411*9e39c5baSBill Taylor dapl_os_free(p_table, sizeof (DAPL_HASH_TABLE));
412*9e39c5baSBill Taylor
413*9e39c5baSBill Taylor return (DAT_SUCCESS);
414*9e39c5baSBill Taylor }
415*9e39c5baSBill Taylor
416*9e39c5baSBill Taylor
417*9e39c5baSBill Taylor /*
418*9e39c5baSBill Taylor * Returns the number of elements stored in the table
419*9e39c5baSBill Taylor */
420*9e39c5baSBill Taylor
421*9e39c5baSBill Taylor DAT_RETURN
dapls_hash_size(IN DAPL_HASH_TABLE * p_table,OUT DAT_COUNT * p_size)422*9e39c5baSBill Taylor dapls_hash_size(
423*9e39c5baSBill Taylor IN DAPL_HASH_TABLE *p_table,
424*9e39c5baSBill Taylor OUT DAT_COUNT *p_size)
425*9e39c5baSBill Taylor {
426*9e39c5baSBill Taylor dapl_os_assert(p_table && p_size);
427*9e39c5baSBill Taylor
428*9e39c5baSBill Taylor *p_size = p_table->num_entries;
429*9e39c5baSBill Taylor
430*9e39c5baSBill Taylor return (DAT_SUCCESS);
431*9e39c5baSBill Taylor }
432*9e39c5baSBill Taylor
433*9e39c5baSBill Taylor
434*9e39c5baSBill Taylor /*
435*9e39c5baSBill Taylor * Inserts the specified data into the table with the given key.
436*9e39c5baSBill Taylor * Duplicates are not expected, and return in error, having done nothing.
437*9e39c5baSBill Taylor */
438*9e39c5baSBill Taylor
439*9e39c5baSBill Taylor DAT_RETURN
dapls_hash_insert(IN DAPL_HASH_TABLE * p_table,IN DAPL_HASH_KEY key,IN DAPL_HASH_DATA data)440*9e39c5baSBill Taylor dapls_hash_insert(
441*9e39c5baSBill Taylor IN DAPL_HASH_TABLE *p_table,
442*9e39c5baSBill Taylor IN DAPL_HASH_KEY key,
443*9e39c5baSBill Taylor IN DAPL_HASH_DATA data)
444*9e39c5baSBill Taylor {
445*9e39c5baSBill Taylor DAT_RETURN dat_status;
446*9e39c5baSBill Taylor
447*9e39c5baSBill Taylor dapl_os_assert(p_table);
448*9e39c5baSBill Taylor dat_status = DAT_SUCCESS;
449*9e39c5baSBill Taylor
450*9e39c5baSBill Taylor if (p_table->locking_required) {
451*9e39c5baSBill Taylor dapl_os_lock(&p_table->lock);
452*9e39c5baSBill Taylor }
453*9e39c5baSBill Taylor
454*9e39c5baSBill Taylor if (!dapli_hash_add(p_table, key, data, DAT_FALSE, NULL)) {
455*9e39c5baSBill Taylor dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
456*9e39c5baSBill Taylor DAT_RESOURCE_MEMORY);
457*9e39c5baSBill Taylor }
458*9e39c5baSBill Taylor
459*9e39c5baSBill Taylor if (p_table->locking_required) {
460*9e39c5baSBill Taylor dapl_os_unlock(&p_table->lock);
461*9e39c5baSBill Taylor }
462*9e39c5baSBill Taylor
463*9e39c5baSBill Taylor return (dat_status);
464*9e39c5baSBill Taylor }
465*9e39c5baSBill Taylor
466*9e39c5baSBill Taylor
467*9e39c5baSBill Taylor /*
468*9e39c5baSBill Taylor * Searches for the given key. If found,
469*9e39c5baSBill Taylor * DAT_SUCCESS is returned and the associated
470*9e39c5baSBill Taylor * data is returned in the DAPL_HASH_DATA
471*9e39c5baSBill Taylor * pointer if that pointer is not NULL.
472*9e39c5baSBill Taylor */
473*9e39c5baSBill Taylor DAT_RETURN
dapls_hash_search(IN DAPL_HASH_TABLE * p_table,IN DAPL_HASH_KEY key,OUT DAPL_HASH_DATA * p_data)474*9e39c5baSBill Taylor dapls_hash_search(
475*9e39c5baSBill Taylor IN DAPL_HASH_TABLE *p_table,
476*9e39c5baSBill Taylor IN DAPL_HASH_KEY key,
477*9e39c5baSBill Taylor OUT DAPL_HASH_DATA *p_data)
478*9e39c5baSBill Taylor {
479*9e39c5baSBill Taylor DAT_RETURN dat_status;
480*9e39c5baSBill Taylor void *olddatum;
481*9e39c5baSBill Taylor DAPL_HASH_ELEM *found;
482*9e39c5baSBill Taylor
483*9e39c5baSBill Taylor dapl_os_assert(p_table);
484*9e39c5baSBill Taylor dat_status = DAT_ERROR(DAT_INVALID_PARAMETER, 0);
485*9e39c5baSBill Taylor
486*9e39c5baSBill Taylor if (p_table->locking_required) {
487*9e39c5baSBill Taylor dapl_os_lock(&p_table->lock);
488*9e39c5baSBill Taylor DAPL_HASHLOOKUP(p_table, key, olddatum, found);
489*9e39c5baSBill Taylor dapl_os_unlock(&p_table->lock);
490*9e39c5baSBill Taylor } else {
491*9e39c5baSBill Taylor DAPL_HASHLOOKUP(p_table, key, olddatum, found);
492*9e39c5baSBill Taylor }
493*9e39c5baSBill Taylor
494*9e39c5baSBill Taylor if (found) {
495*9e39c5baSBill Taylor if (p_data) {
496*9e39c5baSBill Taylor *p_data = olddatum;
497*9e39c5baSBill Taylor }
498*9e39c5baSBill Taylor dat_status = DAT_SUCCESS;
499*9e39c5baSBill Taylor }
500*9e39c5baSBill Taylor
501*9e39c5baSBill Taylor return (dat_status);
502*9e39c5baSBill Taylor }
503*9e39c5baSBill Taylor
504*9e39c5baSBill Taylor
505*9e39c5baSBill Taylor DAT_RETURN
dapls_hash_remove(IN DAPL_HASH_TABLE * p_table,IN DAPL_HASH_KEY key,OUT DAPL_HASH_DATA * p_data)506*9e39c5baSBill Taylor dapls_hash_remove(
507*9e39c5baSBill Taylor IN DAPL_HASH_TABLE *p_table,
508*9e39c5baSBill Taylor IN DAPL_HASH_KEY key,
509*9e39c5baSBill Taylor OUT DAPL_HASH_DATA *p_data)
510*9e39c5baSBill Taylor {
511*9e39c5baSBill Taylor DAT_RETURN dat_status;
512*9e39c5baSBill Taylor DAPL_HASH_KEY hashValue;
513*9e39c5baSBill Taylor
514*9e39c5baSBill Taylor dapl_os_assert(p_table);
515*9e39c5baSBill Taylor dat_status = DAT_ERROR(DAT_INVALID_PARAMETER, 0);
516*9e39c5baSBill Taylor
517*9e39c5baSBill Taylor if (p_table->num_entries == 0) {
518*9e39c5baSBill Taylor dapl_dbg_log(DAPL_DBG_TYPE_ERR,
519*9e39c5baSBill Taylor "dapls_hash_remove () called on empty hash table!\n");
520*9e39c5baSBill Taylor return (dat_status);
521*9e39c5baSBill Taylor }
522*9e39c5baSBill Taylor
523*9e39c5baSBill Taylor hashValue = DAPL_DOHASH(key, p_table->tbl_size);
524*9e39c5baSBill Taylor if (p_table->locking_required) {
525*9e39c5baSBill Taylor dapl_os_lock(&p_table->lock);
526*9e39c5baSBill Taylor }
527*9e39c5baSBill Taylor if (dapl_hash_delete_element(&p_table->table[hashValue], key, p_data)) {
528*9e39c5baSBill Taylor p_table->num_entries--;
529*9e39c5baSBill Taylor dat_status = DAT_SUCCESS;
530*9e39c5baSBill Taylor }
531*9e39c5baSBill Taylor if (p_table->locking_required) {
532*9e39c5baSBill Taylor dapl_os_unlock(&p_table->lock);
533*9e39c5baSBill Taylor }
534*9e39c5baSBill Taylor return (dat_status);
535*9e39c5baSBill Taylor }
536*9e39c5baSBill Taylor /*
537*9e39c5baSBill Taylor * Iterates through the entire hash table return one element at a time.
538*9e39c5baSBill Taylor * Note: this is not a threadsafe routine and hence consumers that
539*9e39c5baSBill Taylor * rely on the hash-tables internal locking are not allowed to use this.
540*9e39c5baSBill Taylor */
541*9e39c5baSBill Taylor DAT_RETURN
dapls_hash_iterate(IN DAPL_HASH_TABLE * p_table,IN DAPL_HASH_ITERATOR op,OUT DAPL_HASH_DATA * p_data)542*9e39c5baSBill Taylor dapls_hash_iterate(
543*9e39c5baSBill Taylor IN DAPL_HASH_TABLE *p_table,
544*9e39c5baSBill Taylor IN DAPL_HASH_ITERATOR op,
545*9e39c5baSBill Taylor OUT DAPL_HASH_DATA *p_data)
546*9e39c5baSBill Taylor {
547*9e39c5baSBill Taylor DAPL_HASH_ELEM *curr;
548*9e39c5baSBill Taylor
549*9e39c5baSBill Taylor dapl_os_assert(p_table);
550*9e39c5baSBill Taylor /*
551*9e39c5baSBill Taylor * sorry iterate is supported only for consumers that do their
552*9e39c5baSBill Taylor * own locking
553*9e39c5baSBill Taylor */
554*9e39c5baSBill Taylor if (p_table->locking_required) {
555*9e39c5baSBill Taylor return (DAT_ERROR(DAT_INVALID_PARAMETER, 0));
556*9e39c5baSBill Taylor }
557*9e39c5baSBill Taylor if (op == DAPL_HASH_ITERATE_INIT) {
558*9e39c5baSBill Taylor /* the hash table is empty */
559*9e39c5baSBill Taylor if (p_table->num_entries == 0) {
560*9e39c5baSBill Taylor *p_data = NULL;
561*9e39c5baSBill Taylor return (DAT_SUCCESS);
562*9e39c5baSBill Taylor }
563*9e39c5baSBill Taylor /* find the first bucket with valid data */
564*9e39c5baSBill Taylor p_table->iterator_bucket = 0;
565*9e39c5baSBill Taylor while (p_table->iterator_bucket < p_table->tbl_size) {
566*9e39c5baSBill Taylor curr = &p_table->table[p_table->iterator_bucket];
567*9e39c5baSBill Taylor if (NO_DATUM(curr->datum)) {
568*9e39c5baSBill Taylor /* empty bucket - move on */
569*9e39c5baSBill Taylor p_table->iterator_bucket++;
570*9e39c5baSBill Taylor } else {
571*9e39c5baSBill Taylor break;
572*9e39c5baSBill Taylor }
573*9e39c5baSBill Taylor }
574*9e39c5baSBill Taylor /* should not be empty if num_entries is non-zero */
575*9e39c5baSBill Taylor dapl_os_assert(!NO_DATUM(curr->datum));
576*9e39c5baSBill Taylor if (p_table->iterator_bucket == p_table->tbl_size) {
577*9e39c5baSBill Taylor p_table->iterator = NULL;
578*9e39c5baSBill Taylor } else {
579*9e39c5baSBill Taylor p_table->iterator = curr;
580*9e39c5baSBill Taylor }
581*9e39c5baSBill Taylor } else {
582*9e39c5baSBill Taylor dapl_os_assert(op == DAPL_HASH_ITERATE_NEXT);
583*9e39c5baSBill Taylor }
584*9e39c5baSBill Taylor /* iterator points to the element to be returned */
585*9e39c5baSBill Taylor if (p_table->iterator == NULL) {
586*9e39c5baSBill Taylor /* nothing more left in the hashtable */
587*9e39c5baSBill Taylor *p_data = NULL;
588*9e39c5baSBill Taylor return (DAT_SUCCESS);
589*9e39c5baSBill Taylor }
590*9e39c5baSBill Taylor
591*9e39c5baSBill Taylor dapl_dbg_log(DAPL_DBG_TYPE_EP,
592*9e39c5baSBill Taylor "dapls_hash_iterate: entry found=(%p), bucket(%d)\n",
593*9e39c5baSBill Taylor p_table->iterator, p_table->iterator_bucket);
594*9e39c5baSBill Taylor *p_data = p_table->iterator->datum;
595*9e39c5baSBill Taylor curr = p_table->iterator;
596*9e39c5baSBill Taylor
597*9e39c5baSBill Taylor /* re-position iterator to point to the next valid element */
598*9e39c5baSBill Taylor if (curr->next_element != NULL) { /* found the next element */
599*9e39c5baSBill Taylor p_table->iterator = curr->next_element;
600*9e39c5baSBill Taylor dapl_os_assert(!NO_DATUM(p_table->iterator->datum));
601*9e39c5baSBill Taylor } else {
602*9e39c5baSBill Taylor p_table->iterator = NULL;
603*9e39c5baSBill Taylor /*
604*9e39c5baSBill Taylor * We are here means we've hit the end of the current bucket,
605*9e39c5baSBill Taylor * so start searching for next bucket with a valid entry -
606*9e39c5baSBill Taylor * we only need to look at the head of the bucket
607*9e39c5baSBill Taylor */
608*9e39c5baSBill Taylor p_table->iterator_bucket++;
609*9e39c5baSBill Taylor while (p_table->iterator_bucket < p_table->tbl_size) {
610*9e39c5baSBill Taylor curr = &p_table->table[p_table->iterator_bucket];
611*9e39c5baSBill Taylor if (NO_DATUM(curr->datum)) {
612*9e39c5baSBill Taylor p_table->iterator_bucket++;
613*9e39c5baSBill Taylor } else {
614*9e39c5baSBill Taylor p_table->iterator = curr;
615*9e39c5baSBill Taylor break;
616*9e39c5baSBill Taylor }
617*9e39c5baSBill Taylor }
618*9e39c5baSBill Taylor }
619*9e39c5baSBill Taylor return (DAT_SUCCESS);
620*9e39c5baSBill Taylor }
621