1 /* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
2 
3 #include "hashtable.h"
4 #include "hashtable_itr.h"
5 #include <stdlib.h>
6 #include <stdio.h>
7 #include <string.h> /* for memcmp */
8 
9 static const int ITEM_COUNT = 4000;
10 
11 typedef unsigned int uint32_t;
12 typedef unsigned short uint16_t;
13 
14 /*****************************************************************************/
15 struct key
16 {
17     uint32_t one_ip; uint32_t two_ip; uint16_t one_port; uint16_t two_port;
18 };
19 
20 struct value
21 {
22     char *id;
23 };
24 
25 DEFINE_HASHTABLE_INSERT(insert_some, struct key, struct value);
26 DEFINE_HASHTABLE_SEARCH(search_some, struct key, struct value);
27 DEFINE_HASHTABLE_REMOVE(remove_some, struct key, struct value);
28 DEFINE_HASHTABLE_ITERATOR_SEARCH(search_itr_some, struct key);
29 
30 
31 /*****************************************************************************/
32 static unsigned int
hashfromkey(void * ky)33 hashfromkey(void *ky)
34 {
35     struct key *k = (struct key *)ky;
36     return (((k->one_ip << 17) | (k->one_ip >> 15)) ^ k->two_ip) +
37             (k->one_port * 17) + (k->two_port * 13 * 29);
38 }
39 
40 static int
equalkeys(void * k1,void * k2)41 equalkeys(void *k1, void *k2)
42 {
43     return (0 == memcmp(k1,k2,sizeof(struct key)));
44 }
45 
46 /*****************************************************************************/
47 int
main(int argc,char ** argv)48 main(int argc, char **argv)
49 {
50     struct key *k, *kk;
51     struct value *v, *found;
52     struct hashtable *h;
53     struct hashtable_itr *itr;
54     int i;
55 
56     h = create_hashtable(16, hashfromkey, equalkeys);
57     if (NULL == h) exit(-1); /*oom*/
58 
59 
60 /*****************************************************************************/
61 /* Insertion */
62     for (i = 0; i < ITEM_COUNT; i++)
63     {
64         k = (struct key *)malloc(sizeof(struct key));
65         if (NULL == k) {
66             printf("ran out of memory allocating a key\n");
67             return 1;
68         }
69         k->one_ip = 0xcfccee40 + i;
70         k->two_ip = 0xcf0cee67 - (5 * i);
71         k->one_port = 22 + (7 * i);
72         k->two_port = 5522 - (3 * i);
73 
74         v = (struct value *)malloc(sizeof(struct value));
75         v->id = "a value";
76 
77         if (!insert_some(h,k,v)) exit(-1); /*oom*/
78     }
79     printf("After insertion, hashtable contains %u items.\n",
80             hashtable_count(h));
81 
82 /*****************************************************************************/
83 /* Hashtable search */
84     k = (struct key *)malloc(sizeof(struct key));
85     if (NULL == k) {
86         printf("ran out of memory allocating a key\n");
87         return 1;
88     }
89 
90     for (i = 0; i < ITEM_COUNT; i++)
91     {
92         k->one_ip = 0xcfccee40 + i;
93         k->two_ip = 0xcf0cee67 - (5 * i);
94         k->one_port = 22 + (7 * i);
95         k->two_port = 5522 - (3 * i);
96 
97         if (NULL == (found = search_some(h,k))) {
98             printf("BUG: key not found\n");
99         }
100     }
101 
102 /*****************************************************************************/
103 /* Hashtable iteration */
104     /* Iterator constructor only returns a valid iterator if
105      * the hashtable is not empty */
106     itr = hashtable_iterator(h);
107     i = 0;
108     if (hashtable_count(h) > 0)
109     {
110         do {
111             kk = hashtable_iterator_key(itr);
112             v = hashtable_iterator_value(itr);
113             /* here (kk,v) are a valid (key, value) pair */
114             /* We could call 'hashtable_remove(h,kk)' - and this operation
115              * 'free's kk. However, the iterator is then broken.
116              * This is why hashtable_iterator_remove exists - see below.
117              */
118             i++;
119 
120         } while (hashtable_iterator_advance(itr));
121     }
122     printf("Iterated through %u entries.\n", i);
123 
124 /*****************************************************************************/
125 /* Hashtable iterator search */
126 
127     /* Try the search some method */
128     for (i = 0; i < ITEM_COUNT; i++)
129     {
130         k->one_ip = 0xcfccee40 + i;
131         k->two_ip = 0xcf0cee67 - (5 * i);
132         k->one_port = 22 + (7 * i);
133         k->two_port = 5522 - (3 * i);
134 
135         if (0 == search_itr_some(itr,h,k)) {
136             printf("BUG: key not found searching with iterator");
137         }
138     }
139 
140 /*****************************************************************************/
141 /* Hashtable removal */
142 
143     for (i = 0; i < ITEM_COUNT; i++)
144     {
145         k->one_ip = 0xcfccee40 + i;
146         k->two_ip = 0xcf0cee67 - (5 * i);
147         k->one_port = 22 + (7 * i);
148         k->two_port = 5522 - (3 * i);
149 
150         if (NULL == (found = remove_some(h,k))) {
151             printf("BUG: key not found for removal\n");
152         }
153     }
154     printf("After removal, hashtable contains %u items.\n",
155             hashtable_count(h));
156 
157 /*****************************************************************************/
158 /* Hashtable destroy and create */
159 
160     hashtable_destroy(h, 1);
161     h = NULL;
162     free(k);
163 
164     h = create_hashtable(160, hashfromkey, equalkeys);
165     if (NULL == h) {
166         printf("out of memory allocating second hashtable\n");
167         return 1;
168     }
169 
170 /*****************************************************************************/
171 /* Hashtable insertion */
172 
173     for (i = 0; i < ITEM_COUNT; i++)
174     {
175         k = (struct key *)malloc(sizeof(struct key));
176         k->one_ip = 0xcfccee40 + i;
177         k->two_ip = 0xcf0cee67 - (5 * i);
178         k->one_port = 22 + (7 * i);
179         k->two_port = 5522 - (3 * i);
180 
181         v = (struct value *)malloc(sizeof(struct value));
182         v->id = "a value";
183 
184         if (!insert_some(h,k,v))
185         {
186             printf("out of memory inserting into second hashtable\n");
187             return 1;
188         }
189     }
190     printf("After insertion, hashtable contains %u items.\n",
191             hashtable_count(h));
192 
193 /*****************************************************************************/
194 /* Hashtable iterator search and iterator remove */
195 
196     k = (struct key *)malloc(sizeof(struct key));
197     if (NULL == k) {
198         printf("ran out of memory allocating a key\n");
199         return 1;
200     }
201 
202     for (i = ITEM_COUNT - 1; i >= 0; i = i - 7)
203     {
204         k->one_ip = 0xcfccee40 + i;
205         k->two_ip = 0xcf0cee67 - (5 * i);
206         k->one_port = 22 + (7 * i);
207         k->two_port = 5522 - (3 * i);
208 
209         if (0 == search_itr_some(itr, h, k)) {
210             printf("BUG: key %u not found for search preremoval using iterator\n", i);
211             return 1;
212         }
213         if (0 == hashtable_iterator_remove(itr)) {
214             printf("BUG: key not found for removal using iterator\n");
215             return 1;
216         }
217     }
218     free(itr);
219 
220 /*****************************************************************************/
221 /* Hashtable iterator remove and advance */
222 
223     for (itr = hashtable_iterator(h);
224          hashtable_iterator_remove(itr) != 0; ) {
225         ;
226     }
227     free(itr);
228     printf("After removal, hashtable contains %u items.\n",
229             hashtable_count(h));
230 
231 /*****************************************************************************/
232 /* Hashtable destroy */
233 
234     hashtable_destroy(h, 1);
235     free(k);
236     return 0;
237 }
238 
239 /*
240  * Copyright (c) 2002, 2004, Christopher Clark
241  * All rights reserved.
242  *
243  * Redistribution and use in source and binary forms, with or without
244  * modification, are permitted provided that the following conditions
245  * are met:
246  *
247  * * Redistributions of source code must retain the above copyright
248  * notice, this list of conditions and the following disclaimer.
249  *
250  * * Redistributions in binary form must reproduce the above copyright
251  * notice, this list of conditions and the following disclaimer in the
252  * documentation and/or other materials provided with the distribution.
253  *
254  * * Neither the name of the original author; nor the names of any contributors
255  * may be used to endorse or promote products derived from this software
256  * without specific prior written permission.
257  *
258  *
259  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
260  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
261  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
262  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
263  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
264  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
265  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
266  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
267  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
268  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
269  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
270 */
271