test-suite/splay.cc

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