1 |
dpavlin |
1 |
/* |
2 |
dpavlin |
7 |
* Cisco router simulation platform. |
3 |
dpavlin |
1 |
* 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 |
|
|
} |