test-suite/splay.cc

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