1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22 /*
23 * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 #include <stdlib.h>
28 #include <assert.h>
29 #include <pthread.h>
30
31 #include "sip_hash.h"
32
33 /*
34 * This file implements functions that add, search or remove an object
35 * from the hash table. The object is opaque to the hash functions. To add
36 * an object to the hash table, the caller provides the hash table,
37 * the object and the index into the hash table. To search an object,
38 * the caller provides the hash table, the digest (opaque), the index into
39 * the hash table and the function that does the actual match. Similarly,
40 * for removing an object, the caller provides the hash table, the digest
41 * (opaque), the index into the hash table and the function that does
42 * the acutal deletion of the object - if the deletion is successful,
43 * the object is taken off of the hash table.
44 */
45
46 /*
47 * Given an object and the hash index, add it to the given hash table
48 */
49 int
sip_hash_add(sip_hash_t * sip_hash,void * obj,int hindex)50 sip_hash_add(sip_hash_t *sip_hash, void *obj, int hindex)
51 {
52 sip_hash_obj_t *new_obj;
53 sip_hash_t *hash_entry;
54
55 assert(obj != NULL);
56
57 new_obj = (sip_hash_obj_t *)malloc(sizeof (*new_obj));
58 if (new_obj == NULL)
59 return (-1);
60 new_obj->sip_obj = obj;
61 new_obj->next_obj = NULL;
62 new_obj->prev_obj = NULL;
63 hash_entry = &sip_hash[hindex];
64 (void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
65 if (hash_entry->hash_count == 0) {
66 assert(hash_entry->hash_head == NULL);
67 assert(hash_entry->hash_tail == NULL);
68 hash_entry->hash_head = new_obj;
69 } else {
70 hash_entry->hash_tail->next_obj = new_obj;
71 new_obj->prev_obj = hash_entry->hash_tail;
72 }
73 hash_entry->hash_tail = new_obj;
74 hash_entry->hash_count++;
75 (void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
76 return (0);
77 }
78
79 /*
80 * Given the hash table, the digest to be searched for, index into the hash
81 * table and the function to do the actual matching, return the object,
82 * if found.
83 */
84 void *
sip_hash_find(sip_hash_t * sip_hash,void * digest,int hindex,boolean_t (* match_func)(void *,void *))85 sip_hash_find(sip_hash_t *sip_hash, void *digest, int hindex,
86 boolean_t (*match_func)(void *, void *))
87 {
88 int count;
89 sip_hash_obj_t *tmp;
90 sip_hash_t *hash_entry;
91
92 hash_entry = &sip_hash[hindex];
93 (void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
94 tmp = hash_entry->hash_head;
95 for (count = 0; count < hash_entry->hash_count; count++) {
96 if (match_func(tmp->sip_obj, digest)) {
97 (void) pthread_mutex_unlock(
98 &hash_entry->sip_hash_mutex);
99 return (tmp->sip_obj);
100 }
101 tmp = tmp->next_obj;
102 }
103 (void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
104 return (NULL);
105 }
106
107 /*
108 * Walk the hash table and invoke func on each object. 'arg' is passed
109 * to 'func'
110 */
111 void
sip_walk_hash(sip_hash_t * sip_hash,void (* func)(void *,void *),void * arg)112 sip_walk_hash(sip_hash_t *sip_hash, void (*func)(void *, void *), void *arg)
113 {
114 sip_hash_t *hash_entry;
115 int count;
116 int hcount;
117 sip_hash_obj_t *tmp;
118
119 for (count = 0; count < SIP_HASH_SZ; count++) {
120 hash_entry = &sip_hash[count];
121 (void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
122 tmp = hash_entry->hash_head;
123 for (hcount = 0; hcount < hash_entry->hash_count; hcount++) {
124 assert(tmp->sip_obj != NULL);
125 func(tmp->sip_obj, arg);
126 tmp = tmp->next_obj;
127 }
128 (void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
129 }
130 }
131
132 /*
133 * Given the hash table, the digest to be searched for, the index into the
134 * hash table and the delete function provided to do the actual deletion,
135 * remove the object from the hash table (i.e. only if the object is deleted).
136 */
137 void
sip_hash_delete(sip_hash_t * sip_hash,void * digest,int hindex,boolean_t (* del_func)(void *,void *,int *))138 sip_hash_delete(sip_hash_t *sip_hash, void *digest, int hindex,
139 boolean_t (*del_func)(void *, void *, int *))
140 {
141 sip_hash_t *hash_entry;
142 int count;
143 sip_hash_obj_t *tmp;
144 int found;
145
146 hash_entry = &sip_hash[hindex];
147 (void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
148 tmp = hash_entry->hash_head;
149 for (count = 0; count < hash_entry->hash_count; count++) {
150 if (del_func(tmp->sip_obj, digest, &found)) {
151 if (tmp == hash_entry->hash_head) {
152 if (tmp->next_obj != NULL) {
153 hash_entry->hash_head = tmp->next_obj;
154 tmp->next_obj->prev_obj = NULL;
155 } else {
156 assert(hash_entry->hash_tail ==
157 hash_entry->hash_head);
158 hash_entry->hash_head = NULL;
159 hash_entry->hash_tail = NULL;
160 }
161 } else {
162 sip_hash_obj_t *next = tmp->next_obj;
163
164 if (next != NULL) {
165 tmp->prev_obj->next_obj = next;
166 next->prev_obj = tmp->prev_obj;
167 } else {
168 assert(hash_entry->hash_tail == tmp);
169 tmp->prev_obj->next_obj = NULL;
170 hash_entry->hash_tail =
171 tmp->prev_obj;
172 }
173 }
174 tmp->prev_obj = NULL;
175 tmp->next_obj = NULL;
176 free(tmp);
177 hash_entry->hash_count--;
178 (void) pthread_mutex_unlock(
179 &hash_entry->sip_hash_mutex);
180 return;
181 /*
182 * If we found the object, we are done
183 */
184 } else if (found == 1) {
185 (void) pthread_mutex_unlock(
186 &hash_entry->sip_hash_mutex);
187 return;
188 }
189 tmp = tmp->next_obj;
190 }
191 (void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
192 }
193