usr/src/lib/libsip/common/sip_hash.c

   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 }