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