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 } 167