/[dynamips]/trunk/hash.c
This is repository of my old source code which isn't updated any more. Go to git.rot13.org for current projects!
ViewVC logotype

Contents of /trunk/hash.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 12 - (show annotations)
Sat Oct 6 16:45:40 2007 UTC (16 years, 5 months ago) by dpavlin
File MIME type: text/plain
File size: 4683 byte(s)
make working copy

1 /*
2 * Cisco router 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 }

  ViewVC Help
Powered by ViewVC 1.1.26