Return to trie_test.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / filter

Annotation of embedaddon/bird2/filter/trie_test.c, revision 1.1.1.1

1.1       misho       1: /*
                      2:  *     Filters: Utility Functions 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: #include "test/birdtest.h"
                     10: #include "test/bt-utils.h"
                     11: 
                     12: #include "filter/filter.h"
                     13: #include "filter/data.h"
                     14: #include "conf/conf.h"
                     15: 
                     16: #define TESTS_NUM              10
                     17: #define PREFIXES_NUM           10
                     18: #define PREFIX_TESTS_NUM       10000
                     19: 
                     20: #define BIG_BUFFER_SIZE                10000
                     21: 
                     22: /* Wrapping structure for storing f_prefixes structures in list */
                     23: struct f_prefix_node {
                     24:   node n;
                     25:   struct f_prefix prefix;
                     26: };
                     27: 
                     28: static u32
                     29: xrandom(u32 max)
                     30: {
                     31:   return (bt_random() % max);
                     32: }
                     33: 
                     34: static int
                     35: is_prefix_included(list *prefixes, struct f_prefix *needle)
                     36: {
                     37:   struct f_prefix_node *n;
                     38:   WALK_LIST(n, *prefixes)
                     39:   {
                     40:     ip6_addr cmask = ip6_mkmask(MIN(n->prefix.net.pxlen, needle->net.pxlen));
                     41: 
                     42:     ip6_addr ip = net6_prefix(&n->prefix.net);
                     43:     ip6_addr needle_ip = net6_prefix(&needle->net);
                     44: 
                     45:     if ((ipa_compare(ipa_and(ip, cmask), ipa_and(needle_ip, cmask)) == 0) &&
                     46:        (n->prefix.lo <= needle->net.pxlen) && (needle->net.pxlen <= n->prefix.hi))
                     47:     {
                     48:       bt_debug("FOUND\t" PRIip6 "/%d %d-%d\n", ARGip6(net6_prefix(&n->prefix.net)), n->prefix.net.pxlen, n->prefix.lo, n->prefix.hi);
                     49:       return 1; /* OK */
                     50:     }
                     51:   }
                     52:   return 0; /* FAIL */
                     53: }
                     54: 
                     55: static struct f_prefix
                     56: get_random_ip6_prefix(void)
                     57: {
                     58:   struct f_prefix p;
                     59:   u8 pxlen = xrandom(120)+8;
                     60:   ip6_addr ip6 = ip6_build(bt_random(),bt_random(),bt_random(),bt_random());
                     61:   net_addr_ip6 net6 = NET_ADDR_IP6(ip6, pxlen);
                     62: 
                     63:   p.net = *((net_addr*) &net6);
                     64: 
                     65:   if (bt_random() % 2)
                     66:   {
                     67:     p.lo = 0;
                     68:     p.hi = p.net.pxlen;
                     69:   }
                     70:   else
                     71:   {
                     72:     p.lo = p.net.pxlen;
                     73:     p.hi = net_max_prefix_length[p.net.type];
                     74:   }
                     75: 
                     76:   return p;
                     77: }
                     78: 
                     79: static void
                     80: generate_random_ipv6_prefixes(list *prefixes)
                     81: {
                     82:   int i;
                     83:   for (i = 0; i < PREFIXES_NUM; i++)
                     84:   {
                     85:     struct f_prefix f = get_random_ip6_prefix();
                     86: 
                     87:     struct f_prefix_node *px = calloc(1, sizeof(struct f_prefix_node));
                     88:     px->prefix = f;
                     89: 
                     90:     bt_debug("ADD\t" PRIip6 "/%d %d-%d\n", ARGip6(net6_prefix(&px->prefix.net)), px->prefix.net.pxlen, px->prefix.lo, px->prefix.hi);
                     91:     add_tail(prefixes, &px->n);
                     92:   }
                     93: }
                     94: 
                     95: static int
                     96: t_match_net(void)
                     97: {
                     98:   bt_bird_init();
                     99:   bt_config_parse(BT_CONFIG_SIMPLE);
                    100: 
                    101:   uint round;
                    102:   for (round = 0; round < TESTS_NUM; round++)
                    103:   {
                    104:     list prefixes; /* of structs f_extended_prefix */
                    105:     init_list(&prefixes);
                    106:     struct f_trie *trie = f_new_trie(config->mem, sizeof(struct f_trie_node));
                    107: 
                    108:     generate_random_ipv6_prefixes(&prefixes);
                    109:     struct f_prefix_node *n;
                    110:     WALK_LIST(n, prefixes)
                    111:     {
                    112:       trie_add_prefix(trie, &n->prefix.net, n->prefix.lo, n->prefix.hi);
                    113:     }
                    114: 
                    115:     int i;
                    116:     for (i = 0; i < PREFIX_TESTS_NUM; i++)
                    117:     {
                    118:       struct f_prefix f = get_random_ip6_prefix();
                    119:       bt_debug("TEST\t" PRIip6 "/%d\n", ARGip6(net6_prefix(&f.net)), f.net.pxlen);
                    120: 
                    121:       int should_be = is_prefix_included(&prefixes, &f);
                    122:       int is_there  = trie_match_net(trie, &f.net);
                    123:       bt_assert_msg(should_be == is_there, "Prefix " PRIip6 "/%d %s", ARGip6(net6_prefix(&f.net)), f.net.pxlen, (should_be ? "should be found in trie" : "should not be found in trie"));
                    124:     }
                    125: 
                    126:     struct f_prefix_node *nxt;
                    127:     WALK_LIST_DELSAFE(n, nxt, prefixes)
                    128:     {
                    129:       free(n);
                    130:     }
                    131:   }
                    132: 
                    133:   bt_bird_cleanup();
                    134:   return 1;
                    135: }
                    136: 
                    137: static int
                    138: t_trie_same(void)
                    139: {
                    140:   bt_bird_init();
                    141:   bt_config_parse(BT_CONFIG_SIMPLE);
                    142: 
                    143:   int round;
                    144:   for (round = 0; round < TESTS_NUM*4; round++)
                    145:   {
                    146:     struct f_trie * trie1 = f_new_trie(config->mem, sizeof(struct f_trie_node));
                    147:     struct f_trie * trie2 = f_new_trie(config->mem, sizeof(struct f_trie_node));
                    148: 
                    149:     list prefixes; /* a list of f_extended_prefix structures */
                    150:     init_list(&prefixes);
                    151:     int i;
                    152:     for (i = 0; i < 100; i++)
                    153:       generate_random_ipv6_prefixes(&prefixes);
                    154: 
                    155:     struct f_prefix_node *n;
                    156:     WALK_LIST(n, prefixes)
                    157:     {
                    158:       trie_add_prefix(trie1, &n->prefix.net, n->prefix.lo, n->prefix.hi);
                    159:     }
                    160:     WALK_LIST_BACKWARDS(n, prefixes)
                    161:     {
                    162:       trie_add_prefix(trie2, &n->prefix.net, n->prefix.lo, n->prefix.hi);
                    163:     }
                    164: 
                    165:     bt_assert(trie_same(trie1, trie2));
                    166: 
                    167:     struct f_prefix_node *nxt;
                    168:     WALK_LIST_DELSAFE(n, nxt, prefixes)
                    169:     {
                    170:       free(n);
                    171:     }
                    172:   }
                    173: 
                    174:   return 1;
                    175: }
                    176: 
                    177: int
                    178: main(int argc, char *argv[])
                    179: {
                    180:   bt_init(argc, argv);
                    181: 
                    182:   bt_test_suite(t_match_net, "Testing random prefix matching");
                    183:   bt_test_suite(t_trie_same, "A trie filled forward should be same with a trie filled backward.");
                    184: 
                    185:   return bt_exit_value();
                    186: }