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
9static const int ITEM_COUNT = 4000;
10
11typedef unsigned int uint32_t;
12typedef unsigned short uint16_t;
13
14/*****************************************************************************/
15struct key
16{
17    uint32_t one_ip; uint32_t two_ip; uint16_t one_port; uint16_t two_port;
18};
19
20struct value
21{
22    char *id;
23};
24
25DEFINE_HASHTABLE_INSERT(insert_some, struct key, struct value);
26DEFINE_HASHTABLE_SEARCH(search_some, struct key, struct value);
27DEFINE_HASHTABLE_REMOVE(remove_some, struct key, struct value);
28DEFINE_HASHTABLE_ITERATOR_SEARCH(search_itr_some, struct key);
29
30
31/*****************************************************************************/
32static unsigned int
33hashfromkey(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
40static int
41equalkeys(void *k1, void *k2)
42{
43    return (0 == memcmp(k1,k2,sizeof(struct key)));
44}
45
46/*****************************************************************************/
47int
48main(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