test-suite/splay.cc

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