tests/lib/test_skiplist.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Copyright (c) 2021, LabN Consulting, L.L.C
   4  */
   5
   6 #include <zebra.h>
   7 #include <skiplist.h>
   8
   9 static void sl_debug(struct skiplist *l)
  10 {
  11         int i;
  12
  13         if (!l)
  14                 return;
  15
  16         printf("Skiplist %p has max level %d\n", l, l->level);
  17         for (i = l->level; i >= 0; --i)
  18                 printf("  @%d: %d\n", i, l->level_stats[i]);
  19 }
  20
  21 static void *scramble(int i)
  22 {
  23         uintptr_t result;
  24
  25         result = (uintptr_t)(i & 0xff) << 24;
  26         result |= (uintptr_t)i >> 8;
  27
  28         return (void *)result;
  29 }
  30 #define sampleSize 65536
  31 static int sl_test(void)
  32 {
  33         struct skiplist *l;
  34         register int i, k;
  35         void *keys[sampleSize];
  36         void *v = NULL;
  37         int errors = 0;
  38
  39         l = skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL);
  40
  41         printf("%s: skiplist_new returned %p\n", __func__, l);
  42
  43         for (i = 0; i < 4; i++) {
  44
  45                 for (k = 0; k < sampleSize; k++) {
  46                         if (!(k % 10000))
  47                                 printf("%s: (%d:%d)\n", __func__, i, k);
  48                         /* keys[k] = (void *)random(); */
  49                         keys[k] = scramble(k);
  50                         if (skiplist_insert(l, keys[k], keys[k])) {
  51                                 ++errors;
  52                                 printf("error in insert #%d,#%d\n", i, k);
  53                         }
  54                 }
  55
  56                 printf("%s: inserts done\n", __func__);
  57                 sl_debug(l);
  58
  59                 for (k = 0; k < sampleSize; k++) {
  60
  61                         if (!(k % 10000))
  62                                 printf("[%d:%d]\n", i, k);
  63                         /* keys[k] = (void *)random(); */
  64                         if (skiplist_search(l, keys[k], &v)) {
  65                                 ++errors;
  66                                 printf("error in search #%d,#%d\n", i, k);
  67                         }
  68
  69                         if (v != keys[k]) {
  70                                 ++errors;
  71                                 printf("search returned wrong value\n");
  72                         }
  73                 }
  74                 printf("%s: searches done\n", __func__);
  75
  76
  77                 for (k = 0; k < sampleSize; k++) {
  78
  79                         if (!(k % 10000))
  80                                 printf("<%d:%d>\n", i, k);
  81                         /* keys[k] = (void *)random(); */
  82                         if (skiplist_delete(l, keys[k], keys[k])) {
  83                                 ++errors;
  84                                 printf("error in delete\n");
  85                         }
  86                         keys[k] = scramble(k ^ 0xf0f0f0f0);
  87                         if (skiplist_insert(l, keys[k], keys[k])) {
  88                                 ++errors;
  89                                 printf("error in insert #%d,#%d\n", i, k);
  90                         }
  91                 }
  92
  93                 printf("%s: del+inserts done\n", __func__);
  94                 sl_debug(l);
  95
  96                 for (k = 0; k < sampleSize; k++) {
  97
  98                         if (!(k % 10000))
  99                                 printf("{%d:%d}\n", i, k);
 100                         /* keys[k] = (void *)random(); */
 101                         if (skiplist_delete_first(l)) {
 102                                 ++errors;
 103                                 printf("error in delete_first\n");
 104                         }
 105                 }
 106         }
 107
 108         sl_debug(l);
 109
 110         skiplist_free(l);
 111
 112         return errors;
 113 }
 114
 115 int main(int argc, char **argv)
 116 {
 117         int errors = sl_test();
 118
 119         if (errors)
 120                 return 1;
 121         return 0;
 122 }