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 #pragma ident "%Z%%M% %I% %E% SMI"
28
29 #include <stdlib.h>
30 #include <assert.h>
31 #include <pthread.h>
32
33 #include "sip_hash.h"
34
35 /*
36 * This file implements functions that add, search or remove an object
37 * from the hash table. The object is opaque to the hash functions. To add
38 * an object to the hash table, the caller provides the hash table,
39 * the object and the index into the hash table. To search an object,
40 * the caller provides the hash table, the digest (opaque), the index into
41 * the hash table and the function that does the actual match. Similarly,
42 * for removing an object, the caller provides the hash table, the digest
43 * (opaque), the index into the hash table and the function that does
44 * the acutal deletion of the object - if the deletion is successful,
45 * the object is taken off of the hash table.
46 */
47
48 /*
49 * Given an object and the hash index, add it to the given hash table
50 */
51 int
sip_hash_add(sip_hash_t * sip_hash,void * obj,int hindex)52 sip_hash_add(sip_hash_t *sip_hash, void *obj, int hindex)
53 {
54 sip_hash_obj_t *new_obj;
55 sip_hash_t *hash_entry;
56
57 assert(obj != NULL);
58
59 new_obj = (sip_hash_obj_t *)malloc(sizeof (*new_obj));
60 if (new_obj == NULL)
61 return (-1);
62 new_obj->sip_obj = obj;
63 new_obj->next_obj = NULL;
64 new_obj->prev_obj = NULL;
65 hash_entry = &sip_hash[hindex];
66 (void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
67 if (hash_entry->hash_count == 0) {
68 assert(hash_entry->hash_head == NULL);
69 assert(hash_entry->hash_tail == NULL);
70 hash_entry->hash_head = new_obj;
71 } else {
72 hash_entry->hash_tail->next_obj = new_obj;
73 new_obj->prev_obj = hash_entry->hash_tail;
74 }
75 hash_entry->hash_tail = new_obj;
76 hash_entry->hash_count++;
77 (void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
78 return (0);
79 }
80
81 /*
82 * Given the hash table, the digest to be searched for, index into the hash
83 * table and the function to do the actual matching, return the object,
84 * if found.
85 */
86 void *
sip_hash_find(sip_hash_t * sip_hash,void * digest,int hindex,boolean_t (* match_func)(void *,void *))87 sip_hash_find(sip_hash_t *sip_hash, void *digest, int hindex,
88 boolean_t (*match_func)(void *, void *))
89 {
90 int count;
91 sip_hash_obj_t *tmp;
92 sip_hash_t *hash_entry;
93
94 hash_entry = &sip_hash[hindex];
95 (void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
96 tmp = hash_entry->hash_head;
97 for (count = 0; count < hash_entry->hash_count; count++) {
98 if (match_func(tmp->sip_obj, digest)) {
99 (void) pthread_mutex_unlock(
100 &hash_entry->sip_hash_mutex);
101 return (tmp->sip_obj);
102 }
103 tmp = tmp->next_obj;
104 }
105 (void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
106 return (NULL);
107 }
108
109 /*
110 * Walk the hash table and invoke func on each object. 'arg' is passed
111 * to 'func'
112 */
113 void
sip_walk_hash(sip_hash_t * sip_hash,void (* func)(void *,void *),void * arg)114 sip_walk_hash(sip_hash_t *sip_hash, void (*func)(void *, void *), void *arg)
115 {
116 sip_hash_t *hash_entry;
117 int count;
118 int hcount;
119 sip_hash_obj_t *tmp;
120
121 for (count = 0; count < SIP_HASH_SZ; count++) {
122 hash_entry = &sip_hash[count];
123 (void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
124 tmp = hash_entry->hash_head;
125 for (hcount = 0; hcount < hash_entry->hash_count; hcount++) {
126 assert(tmp->sip_obj != NULL);
127 func(tmp->sip_obj, arg);
128 tmp = tmp->next_obj;
129 }
130 (void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
131 }
132 }
133
134 /*
135 * Given the hash table, the digest to be searched for, the index into the
136 * hash table and the delete function provided to do the actual deletion,
137 * remove the object from the hash table (i.e. only if the object is deleted).
138 */
139 void
sip_hash_delete(sip_hash_t * sip_hash,void * digest,int hindex,boolean_t (* del_func)(void *,void *,int *))140 sip_hash_delete(sip_hash_t *sip_hash, void *digest, int hindex,
141 boolean_t (*del_func)(void *, void *, int *))
142 {
143 sip_hash_t *hash_entry;
144 int count;
145 sip_hash_obj_t *tmp;
146 int found;
147
148 hash_entry = &sip_hash[hindex];
149 (void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
150 tmp = hash_entry->hash_head;
151 for (count = 0; count < hash_entry->hash_count; count++) {
152 if (del_func(tmp->sip_obj, digest, &found)) {
153 if (tmp == hash_entry->hash_head) {
154 if (tmp->next_obj != NULL) {
155 hash_entry->hash_head = tmp->next_obj;
156 tmp->next_obj->prev_obj = NULL;
157 } else {
158 assert(hash_entry->hash_tail ==
159 hash_entry->hash_head);
160 hash_entry->hash_head = NULL;
161 hash_entry->hash_tail = NULL;
162 }
163 } else {
164 sip_hash_obj_t *next = tmp->next_obj;
165
166 if (next != NULL) {
167 tmp->prev_obj->next_obj = next;
168 next->prev_obj = tmp->prev_obj;
169 } else {
170 assert(hash_entry->hash_tail == tmp);
171 tmp->prev_obj->next_obj = NULL;
172 hash_entry->hash_tail =
173 tmp->prev_obj;
174 }
175 }
176 tmp->prev_obj = NULL;
177 tmp->next_obj = NULL;
178 free(tmp);
179 hash_entry->hash_count--;
180 (void) pthread_mutex_unlock(
181 &hash_entry->sip_hash_mutex);
182 return;
183 /*
184 * If we found the object, we are done
185 */
186 } else if (found == 1) {
187 (void) pthread_mutex_unlock(
188 &hash_entry->sip_hash_mutex);
189 return;
190 }
191 tmp = tmp->next_obj;
192 }
193 (void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
194 }
195