test-suite/splay.cc

   1 /*
   2  * Copyright (C) 1996-2021 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 /*
  10  * based on ftp://ftp.cs.cmu.edu/user/sleator/splaying/top-down-splay.c
  11  * http://bobo.link.cs.cmu.edu/cgi-bin/splay/splay-cgi.pl
  12  */
  13
  14 #include "squid.h"
  15 #include "splay.h"
  16 #include "util.h"
  17
  18 #include <cstdlib>
  19 #include <functional>
  20 #if HAVE_UNISTD_H
  21 #include <unistd.h>
  22 #endif
  23 #include <random>
  24
  25 class intnode
  26 {
  27
  28 public:
  29     intnode() : i(0) {}
  30
  31     intnode (int anInt) : i (anInt) {}
  32
  33     int i;
  34 };
  35
  36 static int
  37 compareintvoid(void *const &a, void *const &n)
  38 {
  39     intnode *A = (intnode *)a;
  40     intnode *B = (intnode *)n;
  41     return A->i - B->i;
  42 }
  43
  44 static int
  45 compareint(intnode *const &a, intnode *const &b)
  46 {
  47     return a->i - b->i;
  48 }
  49
  50 class SplayCheck
  51 {
  52
  53 public:
  54     static void BeginWalk();
  55     static int LastValue;
  56     static bool ExpectedFail;
  57     static void WalkVoid(void *const &, void *);
  58     static void WalkNode(intnode *const &, void *);
  59     static void WalkNodeRef(intnode const &, void *);
  60     static void CheckNode(intnode const &);
  61 };
  62
  63 int SplayCheck::LastValue (0);
  64 bool SplayCheck::ExpectedFail (false);
  65
  66 void
  67 SplayCheck::BeginWalk()
  68 {
  69     LastValue = 0;
  70 }
  71
  72 void
  73 SplayCheck::WalkVoid(void *const &node, void *)
  74 {
  75     intnode *A = (intnode *)node;
  76     CheckNode(*A);
  77 }
  78
  79 void
  80 SplayCheck::CheckNode(intnode const &A)
  81 {
  82     if (LastValue > A.i) {
  83         /* failure */
  84
  85         if (!ExpectedFail)
  86             exit(EXIT_FAILURE);
  87     } else
  88         /* success */
  89         if (ExpectedFail)
  90             exit(EXIT_FAILURE);
  91
  92     LastValue = A.i;
  93 }
  94
  95 void
  96 SplayCheck::WalkNode (intnode *const &a, void *)
  97 {
  98     CheckNode (*a);
  99 }
 100
 101 void
 102 SplayCheck::WalkNodeRef (intnode const &a, void *)
 103 {
 104     CheckNode (a);
 105 }
 106
 107 static void
 108 destintvoid(void *&data)
 109 {
 110     intnode *i = (intnode *)data;
 111     xfree (i);
 112 }
 113
 114 static void
 115 destint(intnode *&data)
 116 {
 117     delete data;
 118 }
 119
 120 static int
 121 compareintref(intnode const &a, intnode const &b)
 122 {
 123     return a.i - b.i;
 124 }
 125
 126 static void
 127 destintref(intnode &)
 128 {}
 129
 130 int
 131 main(int, char *[])
 132 {
 133     std::mt19937 generator;
 134     xuniform_int_distribution<int> distribution;
 135     auto nextRandom = std::bind (distribution, generator);
 136
 137     {
 138         /* test void * splay containers */
 139         splayNode *top = NULL;
 140
 141         for (int i = 0; i < 100; ++i) {
 142             intnode *I = (intnode *)xcalloc(sizeof(intnode), 1);
 143             I->i = nextRandom();
 144             if (top)
 145                 top = top->insert(I, compareintvoid);
 146             else
 147                 top = new splayNode(static_cast<void*>(new intnode(101)));
 148         }
 149
 150         SplayCheck::BeginWalk();
 151         top->walk(SplayCheck::WalkVoid, NULL);
 152
 153         SplayCheck::BeginWalk();
 154         top->walk(SplayCheck::WalkVoid, NULL);
 155         top->destroy(destintvoid);
 156     }
 157
 158     /* test typesafe splay containers */
 159     {
 160         /* intnode* */
 161         SplayNode<intnode *> *safeTop = new SplayNode<intnode *>(new intnode(101));
 162
 163         for ( int i = 0; i < 100; ++i) {
 164             intnode *I;
 165             I = new intnode;
 166             I->i = nextRandom();
 167             safeTop = safeTop->insert(I, compareint);
 168         }
 169
 170         SplayCheck::BeginWalk();
 171         safeTop->walk(SplayCheck::WalkNode, NULL);
 172
 173         safeTop->destroy(destint);
 174     }
 175     {
 176         /* intnode */
 177         SplayNode<intnode> *safeTop = new SplayNode<intnode>(101);
 178
 179         for (int i = 0; i < 100; ++i) {
 180             intnode I;
 181             I.i = nextRandom();
 182             safeTop = safeTop->insert(I, compareintref);
 183         }
 184
 185         SplayCheck::BeginWalk();
 186         safeTop->walk(SplayCheck::WalkNodeRef, NULL);
 187
 188         safeTop->destroy(destintref);
 189     }
 190
 191     /* check the check routine */
 192     {
 193         SplayCheck::BeginWalk();
 194         intnode I;
 195         I.i = 1;
 196         /* check we don't segfault on NULL splay calls */
 197         SplayCheck::WalkNodeRef(I, NULL);
 198         I.i = 0;
 199         SplayCheck::ExpectedFail = true;
 200         SplayCheck::WalkNodeRef(I, NULL);
 201     }
 202
 203     {
 204         /* check for begin() */
 205         Splay<intnode> *safeTop = new Splay<intnode>();
 206
 207         if (safeTop->start() != NULL)
 208             exit(EXIT_FAILURE);
 209
 210         if (safeTop->finish() != NULL)
 211             exit(EXIT_FAILURE);
 212
 213         for (int i = 0; i < 100; ++i) {
 214             intnode I;
 215             I.i = nextRandom();
 216
 217             if (I.i > 50 && I.i < 10000000)
 218                 safeTop->insert(I, compareintref);
 219         }
 220
 221         {
 222             intnode I;
 223             I.i = 50;
 224             safeTop->insert (I, compareintref);
 225             I.i = 10000000;
 226             safeTop->insert (I, compareintref);
 227         }
 228
 229         if (!safeTop->start())
 230             exit(EXIT_FAILURE);
 231
 232         if (safeTop->start()->data.i != 50)
 233             exit(EXIT_FAILURE);
 234
 235         if (!safeTop->finish())
 236             exit(EXIT_FAILURE);
 237
 238         if (safeTop->finish()->data.i != 10000000)
 239             exit(EXIT_FAILURE);
 240
 241         safeTop->destroy(destintref);
 242     }
 243
 244     {
 245         Splay<intnode *> aSplay;
 246
 247         if (aSplay.start() != NULL)
 248             exit(EXIT_FAILURE);
 249
 250         if (aSplay.size() != 0)
 251             exit(EXIT_FAILURE);
 252
 253         aSplay.insert (new intnode(5), compareint);
 254
 255         if (aSplay.start() == NULL)
 256             exit(EXIT_FAILURE);
 257
 258         if (aSplay.size() != 1)
 259             exit(EXIT_FAILURE);
 260
 261         aSplay.destroy(destint);
 262
 263         if (aSplay.start() != NULL)
 264             exit(EXIT_FAILURE);
 265
 266         if (aSplay.size() != 0)
 267             exit(EXIT_FAILURE);
 268     }
 269
 270     /* TODO: also test the other Splay API */
 271
 272     return EXIT_SUCCESS;
 273 }
 274