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