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 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 41 equalkeys(void *k1, void *k2) 42 { 43 return (0 == memcmp(k1,k2,sizeof(struct key))); 44 } 45 46 /*****************************************************************************/ 47 int 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 */