"Fossies" - the Fresh Open Source Software Archive

Member "libmaxminddb-1.5.2/t/data-pool-t.c" (18 Feb 2021, 11373 Bytes) of package /linux/misc/libmaxminddb-1.5.2.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "data-pool-t.c": 1.5.0_vs_1.5.2.

    1 #include "libtap/tap.h"
    2 #include "maxminddb_test_helper.h"
    3 #include <assert.h>
    4 #include <data-pool.h>
    5 #include <inttypes.h>
    6 #include <math.h>
    7 
    8 static void test_data_pool_new(void);
    9 static void test_data_pool_destroy(void);
   10 static void test_data_pool_alloc(void);
   11 static void test_data_pool_to_list(void);
   12 static bool create_and_check_list(size_t const, size_t const);
   13 static void check_block_count(MMDB_entry_data_list_s const *const,
   14                               size_t const);
   15 
   16 int main(void) {
   17     plan(NO_PLAN);
   18     test_data_pool_new();
   19     test_data_pool_destroy();
   20     test_data_pool_alloc();
   21     test_data_pool_to_list();
   22     done_testing();
   23 }
   24 
   25 static void test_data_pool_new(void) {
   26     {
   27         MMDB_data_pool_s *const pool = data_pool_new(0);
   28         ok(!pool, "size 0 is not valid");
   29     }
   30 
   31     {
   32         MMDB_data_pool_s *const pool = data_pool_new(SIZE_MAX - 10);
   33         ok(!pool, "very large size is not valid");
   34     }
   35 
   36     {
   37         MMDB_data_pool_s *const pool = data_pool_new(512);
   38         ok(pool != NULL, "size 512 is valid");
   39         cmp_ok(pool->size, "==", 512, "size is 512");
   40         cmp_ok(pool->used, "==", 0, "used size is 0");
   41         data_pool_destroy(pool);
   42     }
   43 }
   44 
   45 static void test_data_pool_destroy(void) {
   46     { data_pool_destroy(NULL); }
   47 
   48     {
   49         MMDB_data_pool_s *const pool = data_pool_new(512);
   50         ok(pool != NULL, "created pool");
   51         data_pool_destroy(pool);
   52     }
   53 }
   54 
   55 static void test_data_pool_alloc(void) {
   56     {
   57         MMDB_data_pool_s *const pool = data_pool_new(1);
   58         ok(pool != NULL, "created pool");
   59         cmp_ok(pool->used, "==", 0, "used size starts at 0");
   60 
   61         MMDB_entry_data_list_s *const entry1 = data_pool_alloc(pool);
   62         ok(entry1 != NULL, "allocated first entry");
   63         // Arbitrary so that we can recognize it.
   64         entry1->entry_data.offset = (uint32_t)123;
   65 
   66         cmp_ok(pool->size, "==", 1, "size is still 1");
   67         cmp_ok(pool->used, "==", 1, "used size is 1 after taking one");
   68 
   69         MMDB_entry_data_list_s *const entry2 = data_pool_alloc(pool);
   70         ok(entry2 != NULL, "got another entry");
   71         ok(entry1 != entry2, "second entry is different from first entry");
   72 
   73         cmp_ok(pool->size, "==", 2, "size is 2 (new block)");
   74         cmp_ok(pool->used, "==", 1, "used size is 1 in current block");
   75 
   76         ok(entry1->entry_data.offset == 123,
   77            "accessing the original entry's memory is ok");
   78 
   79         data_pool_destroy(pool);
   80     }
   81 
   82     {
   83         size_t const initial_size = 10;
   84         MMDB_data_pool_s *const pool = data_pool_new(initial_size);
   85         ok(pool != NULL, "created pool");
   86 
   87         MMDB_entry_data_list_s *entry1 = NULL;
   88         for (size_t i = 0; i < initial_size; i++) {
   89             MMDB_entry_data_list_s *const entry = data_pool_alloc(pool);
   90             ok(entry != NULL, "got an entry");
   91             // Give each a unique number so we can check it.
   92             entry->entry_data.offset = (uint32_t)i;
   93             if (i == 0) {
   94                 entry1 = entry;
   95             }
   96         }
   97 
   98         cmp_ok(pool->size, "==", initial_size, "size is the initial size");
   99         cmp_ok(pool->used, "==", initial_size, "used size is as expected");
  100 
  101         MMDB_entry_data_list_s *const entry = data_pool_alloc(pool);
  102         ok(entry != NULL, "got an entry");
  103         entry->entry_data.offset = (uint32_t)initial_size;
  104 
  105         cmp_ok(
  106             pool->size, "==", initial_size * 2, "size is the initial size*2");
  107         cmp_ok(pool->used, "==", 1, "used size is as expected");
  108 
  109         MMDB_entry_data_list_s *const list = data_pool_to_list(pool);
  110 
  111         MMDB_entry_data_list_s *element = list;
  112         for (size_t i = 0; i < initial_size + 1; i++) {
  113             ok(element->entry_data.offset == (uint32_t)i,
  114                "found offset %" PRIu32 ", should have %zu",
  115                element->entry_data.offset,
  116                i);
  117             element = element->next;
  118         }
  119 
  120         ok(entry1->entry_data.offset == (uint32_t)0,
  121            "accessing entry1's original memory is ok after growing the pool");
  122 
  123         data_pool_destroy(pool);
  124     }
  125 }
  126 
  127 static void test_data_pool_to_list(void) {
  128     {
  129         size_t const initial_size = 16;
  130         MMDB_data_pool_s *const pool = data_pool_new(initial_size);
  131         ok(pool != NULL, "created pool");
  132 
  133         MMDB_entry_data_list_s *const entry1 = data_pool_alloc(pool);
  134         ok(entry1 != NULL, "got an entry");
  135 
  136         MMDB_entry_data_list_s *const list_one_element =
  137             data_pool_to_list(pool);
  138         ok(list_one_element != NULL, "got a list");
  139         ok(list_one_element == entry1,
  140            "list's first element is the first we retrieved");
  141         ok(list_one_element->next == NULL, "list is one element in size");
  142 
  143         MMDB_entry_data_list_s *const entry2 = data_pool_alloc(pool);
  144         ok(entry2 != NULL, "got another entry");
  145 
  146         MMDB_entry_data_list_s *const list_two_elements =
  147             data_pool_to_list(pool);
  148         ok(list_two_elements != NULL, "got a list");
  149         ok(list_two_elements == entry1,
  150            "list's first element is the first we retrieved");
  151         ok(list_two_elements->next != NULL, "list has a second element");
  152 
  153         MMDB_entry_data_list_s *const second_element = list_two_elements->next;
  154         ok(second_element == entry2,
  155            "second item in list is second we retrieved");
  156         ok(second_element->next == NULL, "list ends with the second element");
  157 
  158         data_pool_destroy(pool);
  159     }
  160 
  161     {
  162         size_t const initial_size = 1;
  163         MMDB_data_pool_s *const pool = data_pool_new(initial_size);
  164         ok(pool != NULL, "created pool");
  165 
  166         MMDB_entry_data_list_s *const entry1 = data_pool_alloc(pool);
  167         ok(entry1 != NULL, "got an entry");
  168 
  169         MMDB_entry_data_list_s *const list_one_element =
  170             data_pool_to_list(pool);
  171         ok(list_one_element != NULL, "got a list");
  172         ok(list_one_element == entry1,
  173            "list's first element is the first we retrieved");
  174         ok(list_one_element->next == NULL, "list ends with this element");
  175 
  176         data_pool_destroy(pool);
  177     }
  178 
  179     {
  180         size_t const initial_size = 2;
  181         MMDB_data_pool_s *const pool = data_pool_new(initial_size);
  182         ok(pool != NULL, "created pool");
  183 
  184         MMDB_entry_data_list_s *const entry1 = data_pool_alloc(pool);
  185         ok(entry1 != NULL, "got an entry");
  186 
  187         MMDB_entry_data_list_s *const entry2 = data_pool_alloc(pool);
  188         ok(entry2 != NULL, "got an entry");
  189         ok(entry1 != entry2, "second entry is different from the first");
  190 
  191         MMDB_entry_data_list_s *const list_element1 = data_pool_to_list(pool);
  192         ok(list_element1 != NULL, "got a list");
  193         ok(list_element1 == entry1,
  194            "list's first element is the first we retrieved");
  195 
  196         MMDB_entry_data_list_s *const list_element2 = list_element1->next;
  197         ok(list_element2 == entry2,
  198            "second element is the second we retrieved");
  199         ok(list_element2->next == NULL, "list ends with this element");
  200 
  201         data_pool_destroy(pool);
  202     }
  203 
  204     {
  205         diag("starting test: fill one block save for one spot");
  206         ok(create_and_check_list(3, 2), "fill one block save for one spot");
  207     }
  208 
  209     {
  210         diag("starting test: fill one block");
  211         ok(create_and_check_list(3, 3), "fill one block");
  212     }
  213 
  214     {
  215         diag(
  216             "starting test: fill one block and use one spot in the next block");
  217         ok(create_and_check_list(3, 3 + 1),
  218            "fill one block and use one spot in the next block");
  219     }
  220 
  221     {
  222         diag("starting test: fill two blocks save for one spot");
  223         ok(create_and_check_list(3, 3 + 3 * 2 - 1),
  224            "fill two blocks save for one spot");
  225     }
  226 
  227     {
  228         diag("starting test: fill two blocks");
  229         ok(create_and_check_list(3, 3 + 3 * 2), "fill two blocks");
  230     }
  231 
  232     {
  233         diag("starting test: fill two blocks and use one spot in the next");
  234         ok(create_and_check_list(3, 3 + 3 * 2 + 1),
  235            "fill two blocks and use one spot in the next");
  236     }
  237 
  238     {
  239         diag("starting test: fill three blocks save for one spot");
  240         ok(create_and_check_list(3, 3 + 3 * 2 + 3 * 2 * 2 - 1),
  241            "fill three blocks save for one spot");
  242     }
  243 
  244     {
  245         diag("starting test: fill three blocks");
  246         ok(create_and_check_list(3, 3 + 3 * 2 + 3 * 2 * 2),
  247            "fill three blocks");
  248     }
  249 
  250     // It would be nice to have a larger number of these, but it's expensive to
  251     // run many. We currently hardcode what this will be anyway, so varying
  252     // this is not very interesting.
  253     size_t const initial_sizes[] = {1, 2, 32, 64, 128, 256};
  254 
  255     size_t const max_element_count = 4096;
  256 
  257     for (size_t i = 0; i < sizeof(initial_sizes) / sizeof(initial_sizes[0]);
  258          i++) {
  259         size_t const initial_size = initial_sizes[i];
  260 
  261         for (size_t element_count = 0; element_count < max_element_count;
  262              element_count++) {
  263             assert(create_and_check_list(initial_size, element_count));
  264         }
  265     }
  266 }
  267 
  268 // Use assert() rather than libtap as libtap is significantly slower and we run
  269 // this frequently.
  270 static bool create_and_check_list(size_t const initial_size,
  271                                   size_t const element_count) {
  272     MMDB_data_pool_s *const pool = data_pool_new(initial_size);
  273     assert(pool != NULL);
  274 
  275     assert(pool->used == 0);
  276 
  277     // Hold on to the pointers as we initially see them so that we can check
  278     // they are still valid after building the list.
  279     MMDB_entry_data_list_s **const entry_array =
  280         calloc(element_count, sizeof(MMDB_entry_data_list_s *));
  281     assert(entry_array != NULL);
  282 
  283     for (size_t i = 0; i < element_count; i++) {
  284         MMDB_entry_data_list_s *const entry = data_pool_alloc(pool);
  285         assert(entry != NULL);
  286 
  287         entry->entry_data.offset = (uint32_t)i;
  288 
  289         entry_array[i] = entry;
  290     }
  291 
  292     MMDB_entry_data_list_s *const list = data_pool_to_list(pool);
  293 
  294     if (element_count == 0) {
  295         assert(list == NULL);
  296         data_pool_destroy(pool);
  297         free(entry_array);
  298         return true;
  299     }
  300 
  301     assert(list != NULL);
  302 
  303     MMDB_entry_data_list_s *element = list;
  304     for (size_t i = 0; i < element_count; i++) {
  305         assert(element->entry_data.offset == (uint32_t)i);
  306 
  307         assert(element == entry_array[i]);
  308 
  309         element = element->next;
  310     }
  311     assert(element == NULL);
  312 
  313     check_block_count(list, initial_size);
  314 
  315     data_pool_destroy(pool);
  316     free(entry_array);
  317     return true;
  318 }
  319 
  320 // Use assert() rather than libtap as libtap is significantly slower and we run
  321 // this frequently.
  322 static void check_block_count(MMDB_entry_data_list_s const *const list,
  323                               size_t const initial_size) {
  324     size_t got_block_count = 0;
  325     size_t got_element_count = 0;
  326 
  327     MMDB_entry_data_list_s const *element = list;
  328     while (element) {
  329         got_element_count++;
  330 
  331         if (element->pool) {
  332             got_block_count++;
  333         }
  334 
  335         element = element->next;
  336     }
  337 
  338     // Because <number of elements> = <initial size> * 2^(number of blocks)
  339     double const a = ceil((double)got_element_count / (double)initial_size);
  340     double const b = log2(a);
  341     size_t const expected_block_count = ((size_t)b) + 1;
  342 
  343     assert(got_block_count == expected_block_count);
  344 }