usr/src/lib/libnsctl/common/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  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25
  26 #include <string.h>
  27 #include <stdlib.h>
  28 #include <sys/nsctl/nsc_hash.h>
  29
  30 #define HASH_PRIME 2039
  31
  32 static int calc_hash(const char *);
  33
  34 hash_node_t **
  35 nsc_create_hash()
  36 {
  37         hash_node_t **hash;
  38
  39         hash = (hash_node_t **)calloc(HASH_PRIME, sizeof (hash_node_t *));
  40         return (hash);
  41 }
  42
  43 int
  44 nsc_insert_node(hash_node_t **hash, void *data, const char *key)
  45 {
  46         int index;
  47         hash_node_t *node;
  48
  49         node = (hash_node_t *)malloc(sizeof (hash_node_t));
  50         if (!node) {
  51                 return (-1);
  52         }
  53         node->key = strdup(key);
  54         node->data = data;
  55
  56         /*
  57          * possible enhancement would be to search
  58          * in this index for a duplicate
  59          */
  60         index = calc_hash(key);
  61         node->next = hash[ index ];
  62         hash[ index ] = node;
  63
  64         return (0);
  65 }
  66
  67 /*
  68  * lookup
  69  *
  70  * Description:
  71  *      Searches the hash to find a node.
  72  *
  73  * Return values:
  74  *      0 if not found.
  75  *      pointer to node if found.
  76  */
  77 void *
  78 nsc_lookup(hash_node_t **hash, const char *key)
  79 {
  80         int index;
  81         hash_node_t *node;
  82
  83         index = calc_hash(key);
  84         node = hash[ index ];
  85         while (node) {
  86                 if (strcmp(node->key, key) == 0)
  87                         return (node->data);
  88                 node = node->next;
  89         }
  90         return (0);
  91 }
  92
  93 void *
  94 nsc_remove_node(hash_node_t **hash, char *key)
  95 {
  96         int index;
  97         hash_node_t *node, *prev;
  98         void *retval;
  99
 100         index = calc_hash(key);
 101         if (!hash[ index ]) {
 102                 return (0);
 103         }
 104
 105         if (strcmp(hash[ index ]->key, key) == 0) {
 106                 node = hash[ index ];
 107                 retval = node->data;
 108                 hash[ index ] = hash[ index ]->next;
 109                 free(node->key);
 110                 free(node);
 111                 return (retval);
 112         }
 113         prev = hash[ index ];
 114         node = prev->next;
 115         while (node && (strcmp(node->key, key) != 0)) {
 116                 prev = node;
 117                 node = node->next;
 118         }
 119
 120         /* did we find it? */
 121         if (node) {
 122                 prev->next = node->next;
 123                 retval = node->data;
 124                 free(node->key);
 125                 free(node);
 126                 return (retval);
 127         }
 128         return (0);
 129 }
 130
 131 void
 132 nsc_remove_all(hash_node_t **hash, void (*callback)(void *))
 133 {
 134         int i;
 135         hash_node_t *p, *next;
 136
 137         for (i = 0; i < HASH_PRIME; i++) {
 138                 p = hash[ i ];
 139                 while (p) {
 140                         next = p->next;
 141                         if (callback) {
 142                                 callback(p->data);
 143                         }
 144                         free(p->key);
 145                         free(p);
 146                         p = next;
 147                 }
 148         }
 149         free(hash);
 150 }
 151
 152 /* ---------------------------------------------------------------------- */
 153
 154 /*
 155  * Basic rotating hash, as per Knuth.
 156  */
 157 static int
 158 calc_hash(const char *key)
 159 {
 160         unsigned int hash, i;
 161         int len = strlen(key);
 162         for (hash = len, i = 0; i < len; i++) {
 163                 hash = (hash << 5) ^ (hash >> 27) ^ key[ i ];
 164         }
 165         return (hash % HASH_PRIME);
 166 }