tests/lib/test_skiplist.c

   1 /*
   2  * Copyright (c) 2021, LabN Consulting, L.L.C
   3  *
   4  * This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License as published by the Free
   6  * Software Foundation; either version 2 of the License, or (at your option)
   7  * any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  12  * more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; see the file COPYING; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  17  */
  18
  19 #include <zebra.h>
  20 #include <skiplist.h>
  21
  22 static void sl_debug(struct skiplist *l)
  23 {
  24         int i;
  25
  26         if (!l)
  27                 return;
  28
  29         printf("Skiplist %p has max level %d\n", l, l->level);
  30         for (i = l->level; i >= 0; --i)
  31                 printf("  @%d: %d\n", i, l->level_stats[i]);
  32 }
  33
  34 static void *scramble(int i)
  35 {
  36         uintptr_t result;
  37
  38         result = (uintptr_t)(i & 0xff) << 24;
  39         result |= (uintptr_t)i >> 8;
  40
  41         return (void *)result;
  42 }
  43 #define sampleSize 65536
  44 static int sl_test(void)
  45 {
  46         struct skiplist *l;
  47         register int i, k;
  48         void *keys[sampleSize];
  49         void *v = NULL;
  50         int errors = 0;
  51
  52         l = skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL);
  53
  54         printf("%s: skiplist_new returned %p\n", __func__, l);
  55
  56         for (i = 0; i < 4; i++) {
  57
  58                 for (k = 0; k < sampleSize; k++) {
  59                         if (!(k % 10000))
  60                                 printf("%s: (%d:%d)\n", __func__, i, k);
  61                         /* keys[k] = (void *)random(); */
  62                         keys[k] = scramble(k);
  63                         if (skiplist_insert(l, keys[k], keys[k])) {
  64                                 ++errors;
  65                                 printf("error in insert #%d,#%d\n", i, k);
  66                         }
  67                 }
  68
  69                 printf("%s: inserts done\n", __func__);
  70                 sl_debug(l);
  71
  72                 for (k = 0; k < sampleSize; k++) {
  73
  74                         if (!(k % 10000))
  75                                 printf("[%d:%d]\n", i, k);
  76                         /* keys[k] = (void *)random(); */
  77                         if (skiplist_search(l, keys[k], &v)) {
  78                                 ++errors;
  79                                 printf("error in search #%d,#%d\n", i, k);
  80                         }
  81
  82                         if (v != keys[k]) {
  83                                 ++errors;
  84                                 printf("search returned wrong value\n");
  85                         }
  86                 }
  87                 printf("%s: searches done\n", __func__);
  88
  89
  90                 for (k = 0; k < sampleSize; k++) {
  91
  92                         if (!(k % 10000))
  93                                 printf("<%d:%d>\n", i, k);
  94                         /* keys[k] = (void *)random(); */
  95                         if (skiplist_delete(l, keys[k], keys[k])) {
  96                                 ++errors;
  97                                 printf("error in delete\n");
  98                         }
  99                         keys[k] = scramble(k ^ 0xf0f0f0f0);
 100                         if (skiplist_insert(l, keys[k], keys[k])) {
 101                                 ++errors;
 102                                 printf("error in insert #%d,#%d\n", i, k);
 103                         }
 104                 }
 105
 106                 printf("%s: del+inserts done\n", __func__);
 107                 sl_debug(l);
 108
 109                 for (k = 0; k < sampleSize; k++) {
 110
 111                         if (!(k % 10000))
 112                                 printf("{%d:%d}\n", i, k);
 113                         /* keys[k] = (void *)random(); */
 114                         if (skiplist_delete_first(l)) {
 115                                 ++errors;
 116                                 printf("error in delete_first\n");
 117                         }
 118                 }
 119         }
 120
 121         sl_debug(l);
 122
 123         skiplist_free(l);
 124
 125         return errors;
 126 }
 127
 128 int main(int argc, char **argv)
 129 {
 130         int errors = sl_test();
 131
 132         if (errors)
 133                 return 1;
 134         return 0;
 135 }