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 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 * 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 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 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