Annotation of embedaddon/bird2/lib/hash_test.c, revision 1.1
1.1 ! misho 1: /*
! 2: * BIRD Library -- Hash Tests
! 3: *
! 4: * (c) 2015 CZ.NIC z.s.p.o.
! 5: *
! 6: * Can be freely distributed and used under the terms of the GNU GPL.
! 7: */
! 8:
! 9: #undef LOCAL_DEBUG
! 10:
! 11: #include "test/birdtest.h"
! 12:
! 13: #include "lib/hash.h"
! 14:
! 15: struct test_node {
! 16: struct test_node *next; /* Hash chain */
! 17: u32 key;
! 18: };
! 19:
! 20: #define TEST_KEY(n) n->key
! 21: #define TEST_NEXT(n) n->next
! 22: #define TEST_EQ(n1,n2) n1 == n2
! 23: #define TEST_FN(n) (n) ^ u32_hash((n))
! 24: #define TEST_ORDER 13
! 25: #define TEST_PARAMS /TEST_ORDER, *2, 2, 2, TEST_ORDER, 20
! 26: #define TEST_REHASH test_rehash
! 27:
! 28: HASH_DEFINE_REHASH_FN(TEST, struct test_node);
! 29:
! 30: HASH(struct test_node) hash;
! 31: struct pool *my_pool;
! 32:
! 33: #define MAX_NUM (1 << TEST_ORDER)
! 34:
! 35: struct test_node nodes[MAX_NUM];
! 36:
! 37: static void
! 38: print_rate_of_fulfilment(void)
! 39: {
! 40: int i;
! 41: int num_stacked_items = 0;
! 42:
! 43: for (i = 0; i < MAX_NUM; i++)
! 44: if (!hash.data[i])
! 45: num_stacked_items++;
! 46:
! 47: double percent_stacked_items = ((double)num_stacked_items/(double)MAX_NUM)*100.;
! 48: bt_debug("%d (%.2f %%) chained of %d hashes \n", num_stacked_items, percent_stacked_items, MAX_NUM);
! 49: }
! 50:
! 51: #ifdef LOCAL_DEBUG
! 52: static void
! 53: dump_nodes(void)
! 54: {
! 55: int i;
! 56: for (i = 0; i < MAX_NUM; i++)
! 57: bt_debug("nodes[%3d] is at address %14p has .key %3d, .next %14p \n", i, &nodes[i], nodes[i].key, nodes[i].next);
! 58: }
! 59: #endif
! 60:
! 61: static void
! 62: init_hash_(uint order)
! 63: {
! 64: resource_init();
! 65: my_pool = rp_new(&root_pool, "Test pool");
! 66:
! 67: HASH_INIT(hash, my_pool, order);
! 68:
! 69: int i;
! 70: for (i = 0; i < MAX_NUM; i++)
! 71: {
! 72: nodes[i].key = i;
! 73: nodes[i].next = NULL;
! 74: }
! 75:
! 76: bt_debug("MAX_NUM %d \n", MAX_NUM);
! 77: }
! 78:
! 79: static void
! 80: init_hash(void)
! 81: {
! 82: init_hash_(TEST_ORDER);
! 83: }
! 84:
! 85: static void
! 86: validate_filled_hash(void)
! 87: {
! 88: int i;
! 89: struct test_node *node;
! 90: for (i = 0; i < MAX_NUM; i++)
! 91: {
! 92: node = HASH_FIND(hash, TEST, nodes[i].key);
! 93: bt_assert_msg(node->key == nodes[i].key, "Hash should be filled, to find (%p) the node[%d] (%p) with .key = %u, .next %p", node, i, &nodes[i], nodes[i].key, nodes[i].next);
! 94: }
! 95:
! 96: print_rate_of_fulfilment();
! 97: }
! 98:
! 99: static void
! 100: validate_empty_hash(void)
! 101: {
! 102: int i;
! 103: struct test_node *node;
! 104: for (i = 0; i < MAX_NUM; i++)
! 105: {
! 106: node = HASH_FIND(hash, TEST, nodes[i].key);
! 107: bt_assert_msg(node == NULL, "Hash should be empty, to find (%p) the node[%d] (%p) with .key %u, .next %p", node, i, &nodes[i], nodes[i].key, nodes[i].next);
! 108: }
! 109: }
! 110:
! 111: static void
! 112: fill_hash(void)
! 113: {
! 114: int i;
! 115: struct test_node *node;
! 116:
! 117: for (i = 0; i < MAX_NUM; i++)
! 118: {
! 119: nodes[i].key = i;
! 120: node = &nodes[i];
! 121: HASH_INSERT(hash, TEST, node);
! 122: }
! 123: }
! 124:
! 125: static int
! 126: t_insert_find(void)
! 127: {
! 128: init_hash();
! 129: fill_hash();
! 130: validate_filled_hash();
! 131:
! 132: return 1;
! 133: }
! 134:
! 135: static int
! 136: t_insert_find_random(void)
! 137: {
! 138: init_hash();
! 139:
! 140: int i;
! 141: struct test_node *node;
! 142: for (i = 0; i < MAX_NUM; i++)
! 143: {
! 144: nodes[i].key = bt_random();
! 145: node = &nodes[i];
! 146: HASH_INSERT(hash, TEST, node);
! 147: }
! 148:
! 149: validate_filled_hash();
! 150:
! 151: return 1;
! 152: }
! 153:
! 154: static int
! 155: t_insert2_find(void)
! 156: {
! 157: init_hash_(1);
! 158:
! 159: int i;
! 160: struct test_node *node;
! 161: for (i = 0; i < MAX_NUM; i++)
! 162: {
! 163: nodes[i].key = i;
! 164: node = &nodes[i];
! 165: HASH_INSERT2(hash, TEST, my_pool, node);
! 166: }
! 167: bt_assert_msg(hash.order != 1, "The hash should auto-resize from order 2^1. The order of the hash is 2^%u.", hash.order);
! 168:
! 169: validate_filled_hash();
! 170:
! 171: return 1;
! 172: }
! 173:
! 174: static int
! 175: t_walk(void)
! 176: {
! 177: init_hash();
! 178: fill_hash();
! 179:
! 180: uint i;
! 181: uint check[MAX_NUM];
! 182: for (i = 0; i < MAX_NUM; i++)
! 183: check[i] = 0;
! 184:
! 185: HASH_WALK(hash, next, n)
! 186: {
! 187: check[n->key]++;
! 188: }
! 189: HASH_WALK_END;
! 190:
! 191: for (i = 0; i < MAX_NUM; i++)
! 192: bt_assert(check[i] == 1);
! 193:
! 194: return 1;
! 195: }
! 196:
! 197: static int
! 198: t_walk_delsafe_delete(void)
! 199: {
! 200: init_hash();
! 201: fill_hash();
! 202:
! 203: HASH_WALK_DELSAFE(hash, next, n)
! 204: {
! 205: HASH_DELETE(hash, TEST, n->key);
! 206: }
! 207: HASH_WALK_DELSAFE_END;
! 208:
! 209: validate_empty_hash();
! 210:
! 211: return 1;
! 212: }
! 213:
! 214: static int
! 215: t_walk_delsafe_remove(void)
! 216: {
! 217: init_hash();
! 218: fill_hash();
! 219:
! 220: HASH_WALK_DELSAFE(hash, next, n)
! 221: {
! 222: HASH_REMOVE(hash, TEST, n);
! 223: }
! 224: HASH_WALK_DELSAFE_END;
! 225:
! 226: validate_empty_hash();
! 227:
! 228: return 1;
! 229: }
! 230:
! 231: static int
! 232: t_walk_delsafe_delete2(void)
! 233: {
! 234: init_hash();
! 235: fill_hash();
! 236:
! 237: HASH_WALK_DELSAFE(hash, next, n)
! 238: {
! 239: HASH_DELETE2(hash, TEST, my_pool, n->key);
! 240: }
! 241: HASH_WALK_DELSAFE_END;
! 242:
! 243: validate_empty_hash();
! 244:
! 245: return 1;
! 246: }
! 247:
! 248: static int
! 249: t_walk_delsafe_remove2(void)
! 250: {
! 251: init_hash();
! 252: fill_hash();
! 253:
! 254: HASH_WALK_DELSAFE(hash, next, n)
! 255: {
! 256: HASH_REMOVE2(hash, TEST, my_pool, n);
! 257: }
! 258: HASH_WALK_DELSAFE_END;
! 259:
! 260: validate_empty_hash();
! 261:
! 262: return 1;
! 263: }
! 264:
! 265: static int
! 266: t_walk_filter(void)
! 267: {
! 268: init_hash();
! 269: fill_hash();
! 270:
! 271: uint i;
! 272: uint check[MAX_NUM];
! 273: for (i = 0; i < MAX_NUM; i++)
! 274: check[i] = 0;
! 275:
! 276: HASH_WALK_FILTER(hash, next, n, m)
! 277: {
! 278: bt_assert(n == *m);
! 279: check[n->key]++;
! 280: }
! 281: HASH_WALK_FILTER_END;
! 282:
! 283: for (i = 0; i < MAX_NUM; i++)
! 284: bt_assert(check[i] == 1);
! 285:
! 286: return 1;
! 287: }
! 288:
! 289: int
! 290: main(int argc, char *argv[])
! 291: {
! 292: bt_init(argc, argv);
! 293:
! 294: bt_test_suite(t_insert_find, "HASH_INSERT and HASH_FIND");
! 295: bt_test_suite(t_insert_find_random, "HASH_INSERT pseudo-random keys and HASH_FIND");
! 296: bt_test_suite(t_insert2_find, "HASH_INSERT2 and HASH_FIND. HASH_INSERT2 is HASH_INSERT and a smart auto-resize function");
! 297: bt_test_suite(t_walk, "HASH_WALK");
! 298: bt_test_suite(t_walk_delsafe_delete, "HASH_WALK_DELSAFE and HASH_DELETE");
! 299: bt_test_suite(t_walk_delsafe_delete2, "HASH_WALK_DELSAFE and HASH_DELETE2. HASH_DELETE2 is HASH_DELETE and smart auto-resize function");
! 300: bt_test_suite(t_walk_delsafe_remove, "HASH_WALK_DELSAFE and HASH_REMOVE");
! 301: bt_test_suite(t_walk_delsafe_remove2, "HASH_WALK_DELSAFE and HASH_REMOVE2. HASH_REMOVE2 is HASH_REMOVE and smart auto-resize function");
! 302: bt_test_suite(t_walk_filter, "HASH_WALK_FILTER");
! 303:
! 304: return bt_exit_value();
! 305: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hash_test.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib