lunaix-os/tests/units/btrie/test-alloc.c

   1 #include <lunaix/ds/btrie.h>
   2 #include <testing/basic.h>
   3 #include <lunaix/spike.h>
   4 #include <lunaix/compiler.h>
   5
   6 #define WIDTH   8
   7
   8 static void no_inline
   9 __alloc_simple()
  10 {
  11     struct btrie tree;
  12     struct btrie_node *root;
  13     btrie_init(&tree, ilog2(WIDTH));
  14
  15     expect_long(btrie_map(&tree, 0, 100, (void*)1), 0);
  16     expect_long(btrie_map(&tree, 0, 100, (void*)2), 1);
  17     expect_long(btrie_map(&tree, 0, 100, (void*)3), 2);
  18     expect_long(btrie_map(&tree, 0, 100, (void*)4), 3);
  19
  20     root = tree.btrie_root;
  21     expect_notnull(root->children);
  22     expect_int(root->children_cnt, 4);
  23
  24     for (int i = 0; i < 4; i++)
  25     {
  26         expect_notnull(root->children[i]);
  27         expect_int(root->children[i]->index, i);
  28         expect_ulong((ptr_t)root->children[i]->data, i + 1);
  29     }
  30
  31     for (int i = 4; i < WIDTH; i++)
  32     {
  33         expect_null(root->children[i]);
  34     }
  35
  36     btrie_release(&tree);
  37 }
  38
  39 static void no_inline
  40 __alloc_edge()
  41 {
  42     struct btrie tree;
  43     struct btrie_node *root;
  44     btrie_init(&tree, ilog2(WIDTH));
  45
  46     expect_long(btrie_map(&tree, 7, 100, (void*)1), 7);
  47     expect_long(btrie_map(&tree, 7, 100, (void*)2), 8);
  48     expect_long(btrie_map(&tree, 7, 100, (void*)3), 9);
  49     expect_long(btrie_map(&tree, 7, 100, (void*)4), 10);
  50
  51     root = tree.btrie_root;
  52     expect_notnull(root->children);
  53     expect_int(root->children_cnt, 2);
  54
  55     expect_notnull(root->children[7]);
  56     expect_int(root->children[7]->index, 7);
  57     expect_ulong((ptr_t)root->children[7]->data, 1);
  58
  59     expect_notnull(root->children[1]);
  60     root = root->children[1];
  61
  62     for (int i = 0; i < 3; i++)
  63     {
  64         expect_notnull(root->children[i]);
  65         expect_int(root->children[i]->index, i);
  66         expect_ulong((ptr_t)root->children[i]->data, i + 2);
  67     }
  68
  69     btrie_release(&tree);
  70 }
  71
  72 static void no_inline
  73 __alloc_narrow()
  74 {
  75     struct btrie tree;
  76     struct btrie_node *root;
  77     btrie_init(&tree, ilog2(WIDTH));
  78
  79     expect_long(btrie_map(&tree, 4, 7, (void*)1), 4);
  80     expect_long(btrie_map(&tree, 4, 7, (void*)2), 5);
  81     expect_long(btrie_map(&tree, 4, 7, (void*)3), 6);
  82     expect_long(btrie_map(&tree, 4, 7, (void*)4), -1);
  83
  84     root = tree.btrie_root;
  85     expect_notnull(root->children);
  86     expect_int(root->children_cnt, 3);
  87
  88     for (int i = 0; i < 4; ++i)
  89     {
  90         expect_null(root->children[i]);
  91     }
  92
  93     for (int i = 4, j = 1; i < WIDTH - 1; ++i, ++j)
  94     {
  95         expect_notnull(root->children[i]);
  96         expect_int(root->children[i]->index, i);
  97         expect_ulong((ptr_t)root->children[i]->data, j);
  98     }
  99
 100     btrie_release(&tree);
 101 }
 102
 103 static void no_inline
 104 __alloc_narrow_partial()
 105 {
 106     struct btrie tree;
 107     struct btrie_node *root;
 108     btrie_init(&tree, ilog2(WIDTH));
 109
 110     expect_long(btrie_map(&tree, 15, 17, (void*)1), 15);
 111     expect_long(btrie_map(&tree, 15, 17, (void*)2), 16);
 112     expect_long(btrie_map(&tree, 15, 17, (void*)3), -1);
 113
 114     root = tree.btrie_root;
 115     expect_notnull(root->children);
 116     expect_int(root->children_cnt, 2);
 117
 118     // check left subtree
 119
 120     root = root->children[1];
 121     expect_notnull(root);
 122     expect_int(root->children_cnt, 1);
 123
 124     int i = 0;
 125     for (; i < WIDTH - 1; ++i)
 126     {
 127         expect_null(root->children[i]);
 128     }
 129
 130     // i = WIDTH - 1
 131     expect_notnull(root->children[i]);
 132     expect_int(root->children[i]->index, i);
 133     expect_ulong((ptr_t)root->children[i]->data, 1);
 134
 135     // check right subtree
 136
 137     root = tree.btrie_root;
 138     root = root->children[2];
 139     expect_notnull(root);
 140     expect_int(root->children_cnt, 1);
 141
 142     i = 0;
 143     expect_notnull(root->children[i]);
 144     expect_int(root->children[i]->index, i);
 145     expect_ulong((ptr_t)root->children[i]->data, 2);
 146
 147     for (i++; i < WIDTH; ++i)
 148     {
 149         expect_null(root->children[i]);
 150     }
 151
 152     btrie_release(&tree);
 153 }
 154
 155 static void no_inline
 156 __alloc_dense()
 157 {
 158     int mis_alloc = 0;
 159     struct btrie tree;
 160     btrie_init(&tree, ilog2(WIDTH));
 161
 162     for (size_t i = 0; i < 1000; i++)
 163     {
 164         if (btrie_map(&tree, 0, 1001, (void*)i+1) == -1UL)
 165         {
 166             mis_alloc++;
 167         }
 168     }
 169
 170     expect_int(mis_alloc, 0);
 171     btrie_release(&tree);
 172 }
 173
 174 static void no_inline
 175 __alloc_retrive()
 176 {
 177     struct btrie tree;
 178     struct btrie_node *root;
 179     btrie_init(&tree, ilog2(WIDTH));
 180
 181     expect_long(btrie_map(&tree, 4, 7, (void*)1), 4);
 182     expect_long(btrie_map(&tree, 4, 7, (void*)2), 5);
 183     expect_long(btrie_map(&tree, 4, 7, (void*)3), 6);
 184
 185     expect_ulong(__ptr(btrie_get(&tree, 6)), 3);
 186     expect_ulong(__ptr(btrie_get(&tree, 5)), 2);
 187     expect_ulong(__ptr(btrie_get(&tree, 4)), 1);
 188
 189     btrie_release(&tree);
 190 }
 191
 192 void
 193 run_test(int argc, const char* argv[])
 194 {
 195     testcase("simple_alloc", __alloc_simple());
 196     testcase("simple_edge",  __alloc_edge());
 197     testcase("simple_narrow",  __alloc_narrow());
 198     testcase("narrow_partial",  __alloc_narrow_partial());
 199     testcase("alloc_dense",  __alloc_dense());
 200     testcase("alloc_get",  __alloc_retrive());
 201 }