splay.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2022 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 
51 {
52 
53 public:
54  static void BeginWalk();
55  static int LastValue;
56  static bool ExpectedFail;
57  static void WalkVoid(void *const &, void *);
58  static void WalkNode(intnode *const &, void *);
59  static void WalkNodeRef(intnode const &, void *);
60  static void CheckNode(intnode const &);
61 };
62 
63 int SplayCheck::LastValue (0);
64 bool SplayCheck::ExpectedFail (false);
65 
66 void
68 {
69  LastValue = 0;
70 }
71 
72 void
73 SplayCheck::WalkVoid(void *const &node, void *)
74 {
75  intnode *A = (intnode *)node;
76  CheckNode(*A);
77 }
78 
79 void
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::WalkNode (intnode *const &a, void *)
97 {
98  CheckNode (*a);
99 }
100 
101 void
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
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
128 {}
129 
130 int
131 main(int, char *[])
132 {
133  std::mt19937 generator;
134  xuniform_int_distribution<int> distribution;
135  auto nextRandom = std::bind (distribution, generator);
136 
137  {
138  /* test void * splay containers */
139  splayNode *top = NULL;
140 
141  for (int i = 0; i < 100; ++i) {
142  intnode *I = (intnode *)xcalloc(sizeof(intnode), 1);
143  I->i = nextRandom();
144  if (top)
145  top = top->insert(I, compareintvoid);
146  else
147  top = new splayNode(static_cast<void*>(new intnode(101)));
148  }
149 
152 
155  top->destroy(destintvoid);
156  }
157 
158  /* test typesafe splay containers */
159  {
160  /* intnode* */
161  SplayNode<intnode *> *safeTop = new SplayNode<intnode *>(new intnode(101));
162 
163  for ( int i = 0; i < 100; ++i) {
164  intnode *I;
165  I = new intnode;
166  I->i = nextRandom();
167  safeTop = safeTop->insert(I, compareint);
168  }
169 
171  safeTop->walk(SplayCheck::WalkNode, NULL);
172 
173  safeTop->destroy(destint);
174  }
175  {
176  /* intnode */
177  SplayNode<intnode> *safeTop = new SplayNode<intnode>(101);
178 
179  for (int i = 0; i < 100; ++i) {
180  intnode I;
181  I.i = nextRandom();
182  safeTop = safeTop->insert(I, compareintref);
183  }
184 
186  safeTop->walk(SplayCheck::WalkNodeRef, NULL);
187 
188  safeTop->destroy(destintref);
189  }
190 
191  /* check the check routine */
192  {
194  intnode I;
195  I.i = 1;
196  /* check we don't segfault on NULL splay calls */
198  I.i = 0;
201  }
202 
203  {
204  /* check for begin() */
205  Splay<intnode> *safeTop = new Splay<intnode>();
206 
207  if (safeTop->start() != NULL)
208  exit(EXIT_FAILURE);
209 
210  if (safeTop->finish() != NULL)
211  exit(EXIT_FAILURE);
212 
213  for (int i = 0; i < 100; ++i) {
214  intnode I;
215  I.i = nextRandom();
216 
217  if (I.i > 50 && I.i < 10000000)
218  safeTop->insert(I, compareintref);
219  }
220 
221  {
222  intnode I;
223  I.i = 50;
224  safeTop->insert (I, compareintref);
225  I.i = 10000000;
226  safeTop->insert (I, compareintref);
227  }
228 
229  if (!safeTop->start())
230  exit(EXIT_FAILURE);
231 
232  if (safeTop->start()->data.i != 50)
233  exit(EXIT_FAILURE);
234 
235  if (!safeTop->finish())
236  exit(EXIT_FAILURE);
237 
238  if (safeTop->finish()->data.i != 10000000)
239  exit(EXIT_FAILURE);
240 
241  safeTop->destroy(destintref);
242  }
243 
244  {
245  Splay<intnode *> aSplay;
246 
247  if (aSplay.start() != NULL)
248  exit(EXIT_FAILURE);
249 
250  if (aSplay.size() != 0)
251  exit(EXIT_FAILURE);
252 
253  aSplay.insert (new intnode(5), compareint);
254 
255  if (aSplay.start() == NULL)
256  exit(EXIT_FAILURE);
257 
258  if (aSplay.size() != 1)
259  exit(EXIT_FAILURE);
260 
261  aSplay.destroy(destint);
262 
263  if (aSplay.start() != NULL)
264  exit(EXIT_FAILURE);
265 
266  if (aSplay.size() != 0)
267  exit(EXIT_FAILURE);
268  }
269 
270  /* TODO: also test the other Splay API */
271 
272  return EXIT_SUCCESS;
273 }
274 
Definition: parse.c:104
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71
static void WalkVoid(void *const &, void *)
Definition: splay.cc:73
SplayNode< V > const * finish() const
Definition: splay.h:337
SplayNode< V > * insert(Value data, SPLAYCMP *compare)
Definition: splay.h:174
static void destint(intnode *&data)
Definition: splay.cc:115
static void WalkNodeRef(intnode const &, void *)
Definition: splay.cc:102
intnode(int anInt)
Definition: splay.cc:31
int main(int, char *[])
Definition: splay.cc:131
size_t size() const
Definition: splay.h:359
void walk(SPLAYWALKEE *, void *callerState)
Definition: splay.h:101
void destroy(SPLAYFREE *=SplayNode< V >::DefaultFree)
Definition: splay.h:347
static int LastValue
Definition: splay.cc:55
Definition: splay.h:57
SplayNode< void * > splayNode
Definition: splay.h:47
#define NULL
Definition: types.h:166
void insert(Value const &, SPLAYCMP *compare)
Definition: splay.h:300
int i
Definition: splay.cc:33
static uint32 A
Definition: md4.c:43
static int compareintvoid(void *const &a, void *const &n)
Definition: splay.cc:37
Definition: splay.cc:26
static void BeginWalk()
Definition: splay.cc:67
#define xfree
SplayNode< V > const * start() const
Definition: splay.h:327
static void CheckNode(intnode const &)
Definition: splay.cc:80
static int compareint(intnode *const &a, intnode *const &b)
Definition: splay.cc:45
static void destintvoid(void *&data)
Definition: splay.cc:108
static void WalkNode(intnode *const &, void *)
Definition: splay.cc:96
static bool ExpectedFail
Definition: splay.cc:56
static uint32 B
Definition: md4.c:43
intnode()
Definition: splay.cc:29
static void destintref(intnode &)
Definition: splay.cc:127
void destroy(SPLAYFREE *=DefaultFree)
Definition: splay.h:134
static int compareintref(intnode const &a, intnode const &b)
Definition: splay.cc:121

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors