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