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     /* under KVM we might fetch stats from an uninitialized qht */
  99     check_n(0);
 100
 101     qht_init(&ht, 0, mode);
 102
 103     check_n(0);
 104     insert(0, N);
 105     check(0, N, true);
 106     check_n(N);
 107     check(-N, -1, false);
 108     iter_check(N);
 109
 110     rm(101, 102);
 111     check_n(N - 1);
 112     insert(N, N * 2);
 113     check_n(N + N - 1);
 114     rm(N, N * 2);
 115     check_n(N - 1);
 116     insert(101, 102);
 117     check_n(N);
 118
 119     rm(10, 200);
 120     check_n(N - 190);
 121     insert(150, 200);
 122     check_n(N - 190 + 50);
 123     insert(10, 150);
 124     check_n(N);
 125
 126     rm(1, 2);
 127     check_n(N - 1);
 128     qht_reset_size(&ht, 0);
 129     check_n(0);
 130     check(0, N, false);
 131
 132     qht_destroy(&ht);
 133 }
 134
 135 static void qht_test(unsigned int mode)
 136 {
 137     qht_do_test(mode, 0);
 138     qht_do_test(mode, 1);
 139     qht_do_test(mode, 2);
 140     qht_do_test(mode, 8);
 141     qht_do_test(mode, 16);
 142     qht_do_test(mode, 8192);
 143     qht_do_test(mode, 16384);
 144 }
 145
 146 static void test_default(void)
 147 {
 148     qht_test(0);
 149 }
 150
 151 static void test_resize(void)
 152 {
 153     qht_test(QHT_MODE_AUTO_RESIZE);
 154 }
 155
 156 int main(int argc, char *argv[])
 157 {
 158     g_test_init(&argc, &argv, NULL);
 159     g_test_add_func("/qht/mode/default", test_default);
 160     g_test_add_func("/qht/mode/resize", test_resize);
 161     return g_test_run();
 162 }