1 |
/* |
2 |
* Cisco 7200 (Predator) simulation platform. |
3 |
* Copyright (c) 2006 Christophe Fillot (cf@utc.fr) |
4 |
* |
5 |
* Generic Hash Tables. |
6 |
*/ |
7 |
|
8 |
#include <stdio.h> |
9 |
#include <stdlib.h> |
10 |
#include <unistd.h> |
11 |
#include <string.h> |
12 |
#include <sys/types.h> |
13 |
#include <sys/stat.h> |
14 |
#include <sys/mman.h> |
15 |
#include <assert.h> |
16 |
|
17 |
#include "utils.h" |
18 |
#include "hash.h" |
19 |
|
20 |
/* Compare two strings */ |
21 |
int str_equal(void *s1, void *s2) |
22 |
{ |
23 |
return(strcmp((char *)s1, (char *)s2) == 0); |
24 |
} |
25 |
|
26 |
/* Hash function for a string */ |
27 |
u_int str_hash(void *str) |
28 |
{ |
29 |
char *p,*s = (char *)str; |
30 |
u_int h,g; |
31 |
|
32 |
for(h=0,p=s;*p!='\0';p+=1) |
33 |
{ |
34 |
h = (h << 4) + *p; |
35 |
if ((g = h & 0xf0000000)) { |
36 |
h = h ^ (g >> 24); |
37 |
h = h ^ g; |
38 |
} |
39 |
} |
40 |
|
41 |
return(h); |
42 |
} |
43 |
|
44 |
/* Compare two integers (yes, it's stupid) */ |
45 |
int int_equal(void *i1, void *i2) |
46 |
{ |
47 |
return(((int)(long)i1) == (int)(long)i2); |
48 |
} |
49 |
|
50 |
/* Hash function for an integer (see above) */ |
51 |
u_int int_hash(void *i) |
52 |
{ |
53 |
u_int val = (u_int)(long)i; |
54 |
return(val ^ (val >> 16)); |
55 |
} |
56 |
|
57 |
/* Compare two u64 (yes, it's stupid) */ |
58 |
int u64_equal(void *i1, void *i2) |
59 |
{ |
60 |
return((*(m_uint64_t *)i1) == (*(m_uint64_t *)i2)); |
61 |
} |
62 |
|
63 |
/* Hash function for an u64 (see above) */ |
64 |
u_int u64_hash(void *i) |
65 |
{ |
66 |
m_uint64_t val = *(m_uint64_t *)i; |
67 |
return((u_int)(val ^ (val >> 32))); |
68 |
} |
69 |
|
70 |
/* Compare 2 pointers */ |
71 |
int ptr_equal(void *i1,void *i2) |
72 |
{ |
73 |
return((int)(i1 == i2)); |
74 |
} |
75 |
|
76 |
/* Hash function for a pointer (see above) */ |
77 |
u_int ptr_hash(void *i) |
78 |
{ |
79 |
m_uint64_t val = (m_uint64_t)(m_iptr_t)i; |
80 |
return((u_int)((val & 0xFFFF) ^ ((val >> 24) & 0xFFFF) ^ |
81 |
((val >> 48) & 0xFFFF))); |
82 |
} |
83 |
|
84 |
/* Free memory used by a node */ |
85 |
static inline void hash_node_free(hash_node_t *node) |
86 |
{ |
87 |
free(node); |
88 |
} |
89 |
|
90 |
/* Allocate memory for a new node */ |
91 |
static hash_node_t *hash_node_alloc(hash_table_t *ht,void *key,void *value) |
92 |
{ |
93 |
hash_node_t *node; |
94 |
|
95 |
node = malloc(sizeof(*node)); |
96 |
assert(node!=NULL); |
97 |
node->key = key; |
98 |
node->value = value; |
99 |
node->next = NULL; |
100 |
return node; |
101 |
} |
102 |
|
103 |
/* Create a new hash table */ |
104 |
hash_table_t *hash_table_create(hash_fcompute hash_func,hash_fcompare key_cmp, |
105 |
int hash_size) |
106 |
{ |
107 |
hash_table_t *ht; |
108 |
|
109 |
if (!hash_func || (hash_size <= 0)) |
110 |
return NULL; |
111 |
|
112 |
ht = malloc(sizeof(*ht)); |
113 |
assert(ht!=NULL); |
114 |
|
115 |
memset(ht,0,sizeof(*ht)); |
116 |
ht->hash_func = hash_func; |
117 |
ht->key_cmp = key_cmp; |
118 |
ht->size = hash_size; |
119 |
ht->nodes = calloc(ht->size,sizeof(hash_node_t *)); |
120 |
assert(ht->nodes!=NULL); |
121 |
return ht; |
122 |
} |
123 |
|
124 |
/* Delete an existing Hash Table */ |
125 |
void hash_table_delete(hash_table_t *ht) |
126 |
{ |
127 |
if (ht) { |
128 |
/* todo */ |
129 |
free(ht); |
130 |
} |
131 |
} |
132 |
|
133 |
/* Insert a new (key,value). If key already exists in table, replace value */ |
134 |
int hash_table_insert(hash_table_t *ht,void *key,void *value) |
135 |
{ |
136 |
hash_node_t *node; |
137 |
u_int hash_val; |
138 |
|
139 |
assert(ht!=NULL); |
140 |
|
141 |
hash_val = ht->hash_func(key) % ht->size; |
142 |
|
143 |
for(node=ht->nodes[hash_val];node;node=node->next) |
144 |
if (ht->key_cmp(node->key,key)) { |
145 |
node->value = value; |
146 |
return(0); |
147 |
} |
148 |
|
149 |
node = hash_node_alloc(ht,key,value); |
150 |
node->next = ht->nodes[hash_val]; |
151 |
ht->nodes[hash_val] = node; |
152 |
ht->nnodes++; |
153 |
return(0); |
154 |
} |
155 |
|
156 |
/* Remove a pair (key,value) from an hash table */ |
157 |
void *hash_table_remove(hash_table_t *ht,void *key) |
158 |
{ |
159 |
hash_node_t **node,*tmp; |
160 |
u_int hash_val; |
161 |
void *value; |
162 |
|
163 |
assert(ht!=NULL); |
164 |
|
165 |
hash_val = ht->hash_func(key) % ht->size; |
166 |
|
167 |
for(node=&ht->nodes[hash_val];*node;node=&(*node)->next) |
168 |
if (ht->key_cmp((*node)->key,key)) { |
169 |
tmp = *node; |
170 |
value = tmp->value; |
171 |
*node = tmp->next; |
172 |
|
173 |
hash_node_free(tmp); |
174 |
return(value); |
175 |
} |
176 |
|
177 |
return NULL; |
178 |
} |
179 |
|
180 |
/* Hash Table Lookup */ |
181 |
void *hash_table_lookup(hash_table_t *ht,void *key) |
182 |
{ |
183 |
hash_node_t *node; |
184 |
u_int hash_val; |
185 |
|
186 |
assert(ht!=NULL); |
187 |
|
188 |
hash_val = ht->hash_func(key) % ht->size; |
189 |
|
190 |
for(node=ht->nodes[hash_val];node;node=node->next) |
191 |
if (ht->key_cmp(node->key,key)) |
192 |
return node->value; |
193 |
|
194 |
return NULL; |
195 |
} |
196 |
|
197 |
/* Hash Table Lookup - key direct comparison */ |
198 |
void *hash_table_lookup_dcmp(hash_table_t *ht,void *key) |
199 |
{ |
200 |
hash_node_t *node; |
201 |
u_int hash_val; |
202 |
|
203 |
assert(ht!=NULL); |
204 |
|
205 |
hash_val = ht->hash_func(key) % ht->size; |
206 |
|
207 |
for(node=ht->nodes[hash_val];node;node=node->next) |
208 |
if (node->key == key) |
209 |
return node->value; |
210 |
|
211 |
return NULL; |
212 |
} |
213 |
|
214 |
/* Call the specified function for each node found in hash table */ |
215 |
int hash_table_foreach(hash_table_t *ht,hash_fforeach user_fn,void *opt_arg) |
216 |
{ |
217 |
hash_node_t *node; |
218 |
int i; |
219 |
|
220 |
assert(ht!=NULL); |
221 |
|
222 |
for(i=0;i<ht->size;i++) |
223 |
for(node=ht->nodes[i];node;node=node->next) |
224 |
user_fn(node->key,node->value,opt_arg); |
225 |
|
226 |
return(0); |
227 |
} |