tests/test-qht.c

   1 /*
   2  * Copyright (C) 2016, Emilio G. Cota <cota@braap.org>
   3  *
   4  * License: GNU GPL, version 2 or later.
   5  *   See the COPYING file in the top-level directory.
   6  */
   7 #include "qemu/osdep.h"
   8 #include "qemu/qht.h"
   9
  10 #define N 5000
  11
  12 static struct qht ht;
  13 static int32_t arr[N * 2];
  14
  15 static bool is_equal(const void *obj, const void *userp)
  16 {
  17     const int32_t *a = obj;
  18     const int32_t *b = userp;
  19
  20     return *a == *b;
  21 }
  22
  23 static void insert(int a, int b)
  24 {
  25     int i;
  26
  27     for (i = a; i < b; i++) {
  28         uint32_t hash;
  29
  30         arr[i] = i;
  31         hash = i;
  32
  33         qht_insert(&ht, &arr[i], hash);
  34     }
  35 }
  36
  37 static void rm(int init, int end)
  38 {
  39     int i;
  40
  41     for (i = init; i < end; i++) {
  42         uint32_t hash;
  43
  44         hash = arr[i];
  45         g_assert_true(qht_remove(&ht, &arr[i], hash));
  46     }
  47 }
  48
  49 static void check(int a, int b, bool expected)
  50 {
  51     struct qht_stats stats;
  52     int i;
  53
  54     for (i = a; i < b; i++) {
  55         void *p;
  56         uint32_t hash;
  57         int32_t val;
  58
  59         val = i;
  60         hash = i;
  61         p = qht_lookup(&ht, is_equal, &val, hash);
  62         g_assert_true(!!p == expected);
  63     }
  64     qht_statistics_init(&ht, &stats);
  65     if (stats.used_head_buckets) {
  66         g_assert_cmpfloat(qdist_avg(&stats.chain), >=, 1.0);
  67     }
  68     g_assert_cmpuint(stats.head_buckets, >, 0);
  69     qht_statistics_destroy(&stats);
  70 }
  71
  72 static void count_func(struct qht *ht, void *p, uint32_t hash, void *userp)
  73 {
  74     unsigned int *curr = userp;
  75
  76     (*curr)++;
  77 }
  78
  79 static void check_n(size_t expected)
  80 {
  81     struct qht_stats stats;
  82
  83     qht_statistics_init(&ht, &stats);
  84     g_assert_cmpuint(stats.entries, ==, expected);
  85     qht_statistics_destroy(&stats);
  86 }
  87
  88 static void iter_check(unsigned int count)
  89 {
  90     unsigned int curr = 0;
  91
  92     qht_iter(&ht, count_func, &curr);
  93     g_assert_cmpuint(curr, ==, count);
  94 }
  95
  96 static void qht_do_test(unsigned int mode, size_t init_entries)
  97 {
  98     qht_init(&ht, 0, mode);
  99
 100     insert(0, N);
 101     check(0, N, true);
 102     check_n(N);
 103     check(-N, -1, false);
 104     iter_check(N);
 105
 106     rm(101, 102);
 107     check_n(N - 1);
 108     insert(N, N * 2);
 109     check_n(N + N - 1);
 110     rm(N, N * 2);
 111     check_n(N - 1);
 112     insert(101, 102);
 113     check_n(N);
 114
 115     rm(10, 200);
 116     check_n(N - 190);
 117     insert(150, 200);
 118     check_n(N - 190 + 50);
 119     insert(10, 150);
 120     check_n(N);
 121
 122     rm(1, 2);
 123     check_n(N - 1);
 124     qht_reset_size(&ht, 0);
 125     check_n(0);
 126     check(0, N, false);
 127
 128     qht_destroy(&ht);
 129 }
 130
 131 static void qht_test(unsigned int mode)
 132 {
 133     qht_do_test(mode, 0);
 134     qht_do_test(mode, 1);
 135     qht_do_test(mode, 2);
 136     qht_do_test(mode, 8);
 137     qht_do_test(mode, 16);
 138     qht_do_test(mode, 8192);
 139     qht_do_test(mode, 16384);
 140 }
 141
 142 static void test_default(void)
 143 {
 144     qht_test(0);
 145 }
 146
 147 static void test_resize(void)
 148 {
 149     qht_test(QHT_MODE_AUTO_RESIZE);
 150 }
 151
 152 int main(int argc, char *argv[])
 153 {
 154     g_test_init(&argc, &argv, NULL);
 155     g_test_add_func("/qht/mode/default", test_default);
 156     g_test_add_func("/qht/mode/resize", test_resize);
 157     return g_test_run();
 158 }