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