xref: /titanic_41/usr/src/lib/libnsctl/common/hash.c (revision fcf3ce441efd61da9bb2884968af01cb7c1452cc)
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