test-suite/splay.cc

   1 /*
   2  * $Id: splay.cc,v 1.8 2006/04/25 10:40:29 serassio Exp $
   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         {
 169             intnode *I;
 170             I = new intnode;
 171             I->i = squid_random();
 172             safeTop = safeTop->insert(I, compareint);
 173         }
 174
 175         SplayCheck::BeginWalk();
 176         safeTop->walk(SplayCheck::WalkNode, NULL);
 177
 178         safeTop->destroy(destint);
 179         /* check we don't segfault on NULL splay calls */
 180         safeTop = NULL;
 181         safeTop->splay((intnode *)NULL, compareint);
 182     }
 183     {
 184         /* intnode */
 185         SplayNode<intnode> *safeTop = NULL;
 186
 187         for (int i = 0; i < 100; i++)
 188         {
 189             intnode I;
 190             I.i = squid_random();
 191             safeTop = safeTop->insert(I, compareintref);
 192         }
 193
 194         SplayCheck::BeginWalk();
 195         safeTop->walk(SplayCheck::WalkNodeRef, NULL);
 196
 197         safeTop->destroy(destintref);
 198         /* check we don't segfault on NULL splay calls */
 199         safeTop = NULL;
 200         safeTop->splay(intnode(), compareintref);
 201         SplayCheck::BeginWalk();
 202         safeTop->walk(SplayCheck::WalkNodeRef, NULL);
 203     }
 204     /* check the check routine */
 205     SplayCheck::BeginWalk();
 206     intnode I;
 207     I.i = 1;
 208     /* check we don't segfault on NULL splay calls */
 209     SplayCheck::WalkNodeRef(I, NULL);
 210     I.i = 0;
 211     SplayCheck::ExpectedFail = true;
 212     SplayCheck::WalkNodeRef(I, NULL);
 213
 214     {
 215         /* check for begin() */
 216         SplayNode<intnode> *safeTop = NULL;
 217
 218         if (safeTop->start() != NULL)
 219             exit (1);
 220
 221         if (safeTop->finish() != NULL)
 222             exit (1);
 223
 224         for (int i = 0; i < 100; i++) {
 225             intnode I;
 226             I.i = squid_random();
 227
 228             if (I.i > 50 && I.i < 10000000)
 229                 safeTop = safeTop->insert(I, compareintref);
 230         }
 231
 232         {
 233             intnode I;
 234             I.i = 50;
 235             safeTop = safeTop->insert (I, compareintref);
 236             I.i = 10000000;
 237             safeTop = safeTop->insert (I, compareintref);
 238         }
 239
 240         if (!safeTop->start())
 241             exit (1);
 242
 243         if (safeTop->start()->data.i != 50)
 244             exit (1);
 245
 246         if (!safeTop->finish())
 247             exit (1);
 248
 249         if (safeTop->finish()->data.i != 10000000)
 250             exit (1);
 251
 252         safeTop->destroy(destintref);
 253     }
 254
 255     {
 256         Splay<intnode *> aSplay;
 257
 258         if (aSplay.start() != NULL)
 259             exit (1);
 260
 261         if (aSplay.size() != 0)
 262             exit (1);
 263
 264         aSplay.insert (new intnode(5), compareint);
 265
 266         if (aSplay.start() == NULL)
 267             exit (1);
 268
 269         if (aSplay.size() != 1)
 270             exit (1);
 271
 272         aSplay.destroy(destint);
 273
 274         if (aSplay.start() != NULL)
 275             exit (1);
 276
 277         if (aSplay.size() != 0)
 278             exit (1);
 279     }
 280
 281     return 0;
 282 }