splay.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2017 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 #if HAVE_UNISTD_H
20 #include <unistd.h>
21 #endif
22 #include <random>
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 
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
67 {
68  LastValue = 0;
69 }
70 
71 void
72 SplayCheck::WalkVoid(void *const &node, void *)
73 {
74  intnode *A = (intnode *)node;
75  CheckNode(*A);
76 }
77 
78 void
80 {
81  if (LastValue > A.i) {
82  /* failure */
83 
84  if (!ExpectedFail)
85  exit(EXIT_FAILURE);
86  } else
87  /* success */
88  if (ExpectedFail)
89  exit(EXIT_FAILURE);
90 
91  LastValue = A.i;
92 }
93 
94 void
95 SplayCheck::WalkNode (intnode *const &a, void *)
96 {
97  CheckNode (*a);
98 }
99 
100 void
102 {
103  CheckNode (a);
104 }
105 
106 void
108 {
109  intnode *i = (intnode *)data;
110  xfree (i);
111 }
112 
113 void
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
127 {}
128 
129 int
130 main(int, char *[])
131 {
132  std::mt19937 generator;
133  xuniform_int_distribution<int> distribution;
134  auto nextRandom = std::bind (distribution, generator);
135 
136  {
137  /* test void * splay containers */
138  splayNode *top = NULL;
139 
140  for (int i = 0; i < 100; ++i) {
141  intnode *I = (intnode *)xcalloc(sizeof(intnode), 1);
142  I->i = nextRandom();
143  if (top)
144  top = top->insert(I, compareintvoid);
145  else
146  top = new splayNode(static_cast<void*>(new intnode(101)));
147  }
148 
151 
154  top->destroy(destintvoid);
155  }
156 
157  /* test typesafe splay containers */
158  {
159  /* intnode* */
160  SplayNode<intnode *> *safeTop = new SplayNode<intnode *>(new intnode(101));
161 
162  for ( int i = 0; i < 100; ++i) {
163  intnode *I;
164  I = new intnode;
165  I->i = nextRandom();
166  safeTop = safeTop->insert(I, compareint);
167  }
168 
170  safeTop->walk(SplayCheck::WalkNode, NULL);
171 
172  safeTop->destroy(destint);
173  }
174  {
175  /* intnode */
176  SplayNode<intnode> *safeTop = new SplayNode<intnode>(101);
177 
178  for (int i = 0; i < 100; ++i) {
179  intnode I;
180  I.i = nextRandom();
181  safeTop = safeTop->insert(I, compareintref);
182  }
183 
185  safeTop->walk(SplayCheck::WalkNodeRef, NULL);
186 
187  safeTop->destroy(destintref);
188  }
189 
190  /* check the check routine */
191  {
193  intnode I;
194  I.i = 1;
195  /* check we don't segfault on NULL splay calls */
197  I.i = 0;
200  }
201 
202  {
203  /* check for begin() */
204  Splay<intnode> *safeTop = new Splay<intnode>();
205 
206  if (safeTop->start() != NULL)
207  exit(EXIT_FAILURE);
208 
209  if (safeTop->finish() != NULL)
210  exit(EXIT_FAILURE);
211 
212  for (int i = 0; i < 100; ++i) {
213  intnode I;
214  I.i = nextRandom();
215 
216  if (I.i > 50 && I.i < 10000000)
217  safeTop->insert(I, compareintref);
218  }
219 
220  {
221  intnode I;
222  I.i = 50;
223  safeTop->insert (I, compareintref);
224  I.i = 10000000;
225  safeTop->insert (I, compareintref);
226  }
227 
228  if (!safeTop->start())
229  exit(EXIT_FAILURE);
230 
231  if (safeTop->start()->data.i != 50)
232  exit(EXIT_FAILURE);
233 
234  if (!safeTop->finish())
235  exit(EXIT_FAILURE);
236 
237  if (safeTop->finish()->data.i != 10000000)
238  exit(EXIT_FAILURE);
239 
240  safeTop->destroy(destintref);
241  }
242 
243  {
244  Splay<intnode *> aSplay;
245 
246  if (aSplay.start() != NULL)
247  exit(EXIT_FAILURE);
248 
249  if (aSplay.size() != 0)
250  exit(EXIT_FAILURE);
251 
252  aSplay.insert (new intnode(5), compareint);
253 
254  if (aSplay.start() == NULL)
255  exit(EXIT_FAILURE);
256 
257  if (aSplay.size() != 1)
258  exit(EXIT_FAILURE);
259 
260  aSplay.destroy(destint);
261 
262  if (aSplay.start() != NULL)
263  exit(EXIT_FAILURE);
264 
265  if (aSplay.size() != 0)
266  exit(EXIT_FAILURE);
267  }
268 
269  /* TODO: also test the other Splay API */
270 
271  return EXIT_SUCCESS;
272 }
273 
void insert(Value const &, SPLAYCMP *compare)
Definition: splay.h:300
int compareint(intnode *const &a, intnode *const &b)
Definition: splay.cc:44
SplayNode< V > const * start() const
Definition: splay.h:327
int compareintref(intnode const &a, intnode const &b)
Definition: splay.cc:120
SplayNode< V > * insert(Value data, SPLAYCMP *compare)
Definition: splay.h:174
SplayNode< void * > splayNode
Definition: splay.h:47
static uint32 B
Definition: md4.c:43
intnode()
Definition: splay.cc:28
#define xcalloc
Definition: membanger.c:57
int i
Definition: membanger.c:49
void walk(SPLAYWALKEE *, void *callerState)
Definition: splay.h:101
void destintref(intnode &)
Definition: splay.cc:126
Definition: splay.h:56
Definition: splay.cc:24
void destintvoid(void *&data)
Definition: splay.cc:107
static void CheckNode(intnode const &)
Definition: splay.cc:79
static void WalkNode(intnode *const &, void *)
Definition: splay.cc:95
SplayNode< V > const * finish() const
Definition: splay.h:337
static void WalkVoid(void *const &, void *)
Definition: splay.cc:72
void const char HLPCB void * data
Definition: stub_helper.cc:16
Definition: parse.c:104
static void WalkNodeRef(intnode const &, void *)
Definition: splay.cc:101
static int LastValue
Definition: splay.cc:54
int i
Definition: splay.cc:32
static void BeginWalk()
Definition: splay.cc:66
static uint32 A
Definition: md4.c:43
void destroy(SPLAYFREE *=DefaultFree)
Definition: splay.h:134
int compareintvoid(void *const &a, void *const &n)
Definition: splay.cc:36
int main(int, char *[])
Definition: splay.cc:130
intnode(int anInt)
Definition: splay.cc:30
void destint(intnode *&data)
Definition: splay.cc:114
void destroy(SPLAYFREE *=SplayNode< V >::DefaultFree)
Definition: splay.h:347
int a
Definition: membanger.c:50
size_t size() const
Definition: splay.h:359
#define xfree
static bool ExpectedFail
Definition: splay.cc:55
#define NULL
Definition: types.h:166

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors