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 **
nsc_create_hash()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
nsc_insert_node(hash_node_t ** hash,void * data,const char * key)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 *
nsc_lookup(hash_node_t ** hash,const char * key)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 *
nsc_remove_node(hash_node_t ** hash,char * key)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
nsc_remove_all(hash_node_t ** hash,void (* callback)(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
calc_hash(const char * key)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