test-suite/splay.cc

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