test-suite/splay.cc

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