/[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

Annotation of /trunk/hash.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 12 - (hide 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 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     }

  ViewVC Help
Powered by ViewVC 1.1.26