splay.h
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 #ifndef SQUID_SPLAY_H
10 #define SQUID_SPLAY_H
11 
12 #include "fatal.h"
13 #include <stack>
14 
15 // private class of Splay. Do not use directly
16 template <class V>
17 class SplayNode
18 {
19 public:
20  typedef V Value;
21  typedef int SPLAYCMP(Value const &a, Value const &b);
22  typedef void SPLAYFREE(Value &);
23  typedef void SPLAYWALKEE(Value const & nodedata, void *state);
24  static void DefaultFree (Value &aValue) {delete aValue;}
25 
26  SplayNode<V> (Value const &);
28  mutable SplayNode<V> *left;
29  mutable SplayNode<V> *right;
30  void destroy(SPLAYFREE * = DefaultFree);
31  void walk(SPLAYWALKEE *, void *callerState);
32  SplayNode<V> const * start() const;
33  SplayNode<V> const * finish() const;
34 
35  SplayNode<V> * remove(const Value data, SPLAYCMP * compare);
36 
37  SplayNode<V> * insert(Value data, SPLAYCMP * compare);
38 
41  template <class FindValue> SplayNode<V> * splay(const FindValue &data, int( * compare)(FindValue const &a, Value const &b)) const;
42 
44  template <class Visitor> void visit(Visitor &v) const;
45 };
46 
48 
49 template <class V>
51 
52 template <class V>
54 
55 template <class V>
56 class Splay
57 {
58 public:
59  typedef V Value;
60  typedef int SPLAYCMP(Value const &a, Value const &b);
61  typedef void SPLAYFREE(Value &);
64  Splay():head(NULL), elements (0) {}
65 
66  template <class FindValue> Value const *find (FindValue const &, int( * compare)(FindValue const &a, Value const &b)) const;
67 
68  void insert(Value const &, SPLAYCMP *compare);
69 
70  void remove(Value const &, SPLAYCMP *compare);
71 
73 
74  SplayNode<V> const * start() const;
75 
76  SplayNode<V> const * finish() const;
77 
78  size_t size() const;
79 
80  bool empty() const { return size() == 0; }
81 
82  const_iterator begin() const;
83 
84  const_iterator end() const;
85 
87  template <class Visitor> void visit(Visitor &v) const;
88 
89 private:
90  mutable SplayNode<V> * head;
91  size_t elements;
92 };
93 
95 
96 template<class V>
97 SplayNode<V>::SplayNode (Value const &someData) : data(someData), left(NULL), right (NULL) {}
98 
99 template<class V>
100 void
101 SplayNode<V>::walk(SPLAYWALKEE * walkee, void *state)
102 {
103  if (left)
104  left->walk(walkee, state);
105 
106  walkee(data, state);
107 
108  if (right)
109  right->walk(walkee, state);
110 }
111 
112 template<class V>
113 SplayNode<V> const *
115 {
116  if (left)
117  return left->start();
118 
119  return this;
120 }
121 
122 template<class V>
123 SplayNode<V> const *
125 {
126  if (right)
127  return right->finish();
128 
129  return this;
130 }
131 
132 template<class V>
133 void
134 SplayNode<V>::destroy(SPLAYFREE * free_func)
135 {
136  if (left)
137  left->destroy(free_func);
138 
139  if (right)
140  right->destroy(free_func);
141 
142  free_func(data);
143 
144  delete this;
145 }
146 
147 template<class V>
148 SplayNode<V> *
149 SplayNode<V>::remove(Value const dataToRemove, SPLAYCMP * compare)
150 {
151  SplayNode<V> *result = splay(dataToRemove, compare);
152 
153  if (splayLastResult == 0) { /* found it */
154  SplayNode<V> *newTop;
155 
156  if (result->left == NULL) {
157  newTop = result->right;
158  } else {
159  newTop = result->left->splay(dataToRemove, compare);
160  /* temporary */
161  newTop->right = result->right;
162  result->right = NULL;
163  }
164 
165  delete result;
166  return newTop;
167  }
168 
169  return result; /* It wasn't there */
170 }
171 
172 template<class V>
173 SplayNode<V> *
174 SplayNode<V>::insert(Value dataToInsert, SPLAYCMP * compare)
175 {
176  /* create node to insert */
177  SplayNode<V> *newNode = new SplayNode<V>(dataToInsert);
178  SplayNode<V> *newTop = splay(dataToInsert, compare);
179 
180  if (splayLastResult < 0) {
181  newNode->left = newTop->left;
182  newNode->right = newTop;
183  newTop->left = NULL;
184  return newNode;
185  } else if (splayLastResult > 0) {
186  newNode->right = newTop->right;
187  newNode->left = newTop;
188  newTop->right = NULL;
189  return newNode;
190  } else {
191  /* duplicate entry */
192  delete newNode;
193  return newTop;
194  }
195 }
196 
197 template<class V>
198 template<class FindValue>
199 SplayNode<V> *
200 SplayNode<V>::splay(FindValue const &dataToFind, int( * compare)(FindValue const &a, Value const &b)) const
201 {
202  Value temp = Value();
203  SplayNode<V> N(temp);
204  SplayNode<V> *l;
205  SplayNode<V> *r;
206  SplayNode<V> *y;
207  N.left = N.right = NULL;
208  l = r = &N;
209 
210  SplayNode<V> *top = const_cast<SplayNode<V> *>(this);
211 
212  for (;;) {
213  splayLastResult = compare(dataToFind, top->data);
214 
215  if (splayLastResult < 0) {
216  if (top->left == NULL)
217  break;
218 
219  if ((splayLastResult = compare(dataToFind, top->left->data)) < 0) {
220  y = top->left; /* rotate right */
221  top->left = y->right;
222  y->right = top;
223  top = y;
224 
225  if (top->left == NULL)
226  break;
227  }
228 
229  r->left = top; /* link right */
230  r = top;
231  top = top->left;
232  } else if (splayLastResult > 0) {
233  if (top->right == NULL)
234  break;
235 
236  if ((splayLastResult = compare(dataToFind, top->right->data)) > 0) {
237  y = top->right; /* rotate left */
238  top->right = y->left;
239  y->left = top;
240  top = y;
241 
242  if (top->right == NULL)
243  break;
244  }
245 
246  l->right = top; /* link left */
247  l = top;
248  top = top->right;
249  } else {
250  break;
251  }
252  }
253 
254  l->right = top->left; /* assemble */
255  r->left = top->right;
256  top->left = N.right;
257  top->right = N.left;
258  return top;
259 }
260 
261 template <class V>
262 template <class Visitor>
263 void
264 SplayNode<V>::visit(Visitor &visitor) const
265 {
266  if (left)
267  left->visit(visitor);
268  visitor(data);
269  if (right)
270  right->visit(visitor);
271 }
272 
273 template <class V>
274 template <class Visitor>
275 void
276 Splay<V>::visit(Visitor &visitor) const
277 {
278  if (head)
279  head->visit(visitor);
280 }
281 
282 template <class V>
283 template <class FindValue>
284 typename Splay<V>::Value const *
285 Splay<V>::find (FindValue const &value, int( * compare)(FindValue const &a, Value const &b)) const
286 {
287  if (head == NULL)
288  return NULL;
289 
290  head = head->splay(value, compare);
291 
292  if (splayLastResult != 0)
293  return NULL;
294 
295  return &head->data;
296 }
297 
298 template <class V>
299 void
300 Splay<V>::insert(Value const &value, SPLAYCMP *compare)
301 {
302  if (find(value, compare) != NULL) // ignore duplicates
303  return;
304 
305  if (head == NULL)
306  head = new SplayNode<V>(value);
307  else
308  head = head->insert(value, compare);
309  ++elements;
310 }
311 
312 template <class V>
313 void
314 Splay<V>::remove(Value const &value, SPLAYCMP *compare)
315 {
316  // also catches the head==NULL case
317  if (find(value, compare) == NULL)
318  return;
319 
320  head = head->remove(value, compare);
321 
322  --elements;
323 }
324 
325 template <class V>
326 SplayNode<V> const *
328 {
329  if (head)
330  return head->start();
331 
332  return NULL;
333 }
334 
335 template <class V>
336 SplayNode<V> const *
338 {
339  if (head)
340  return head->finish();
341 
342  return NULL;
343 }
344 
345 template <class V>
346 void
347 Splay<V>:: destroy(SPLAYFREE *free_func)
348 {
349  if (head)
350  head->destroy(free_func);
351 
352  head = NULL;
353 
354  elements = 0;
355 }
356 
357 template <class V>
358 size_t
360 {
361  return elements;
362 }
363 
364 template <class V>
367 {
368  return const_iterator(head);
369 }
370 
371 template <class V>
374 {
375  return const_iterator(NULL);
376 }
377 
378 // XXX: This does not seem to iterate the whole thing in some cases.
379 template <class V>
380 class SplayConstIterator
381 {
382 
383 public:
384  typedef const V value_type;
386  bool operator == (SplayConstIterator const &right) const;
389  V const & operator * () const;
390 
391 private:
392  void advance();
393  void addLeftPath(SplayNode<V> *aNode);
394  void init(SplayNode<V> *);
395  std::stack<SplayNode<V> *> toVisit;
396 };
397 
398 template <class V>
400 {
401  init(aNode);
402 }
403 
404 template <class V>
405 bool
407 {
408  if (toVisit.empty() && right.toVisit.empty())
409  return true;
410  if (!toVisit.empty() && !right.toVisit.empty())
411  return toVisit.top() == right.toVisit.top();
412  // only one of the two is empty
413  return false;
414 }
415 
416 template <class V>
419 {
420  advance();
421  return *this;
422 }
423 
424 template <class V>
427 {
428  SplayConstIterator<V> result = *this;
429  advance();
430  return result;
431 }
432 
433 /* advance is simple enough:
434 * if the stack is empty, we're done.
435 * otherwise, pop the last visited node
436 * then, pop the next node to visit
437 * if that has a right child, add it and it's
438 * left-to-end path.
439 * then add the node back.
440 */
441 template <class V>
442 void
444 {
445  if (toVisit.empty())
446  return;
447 
448  toVisit.pop();
449 
450  if (toVisit.empty())
451  return;
452 
453  // not empty
454  SplayNode<V> *currentNode = toVisit.top();
455  toVisit.pop();
456 
457  addLeftPath(currentNode->right);
458 
459  toVisit.push(currentNode);
460 }
461 
462 template <class V>
463 void
465 {
466  if (aNode == NULL)
467  return;
468 
469  do {
470  toVisit.push(aNode);
471  aNode = aNode->left;
472  } while (aNode != NULL);
473 }
474 
475 template <class V>
476 void
478 {
479  addLeftPath(head);
480 }
481 
482 template <class V>
483 V const &
485 {
486  /* can't dereference when past the end */
487 
488  if (toVisit.size() == 0)
489  fatal ("Attempt to dereference SplayConstIterator past-the-end\n");
490 
491  return toVisit.top()->data;
492 }
493 
494 #endif /* SQUID_SPLAY_H */
495 
void insert(Value const &, SPLAYCMP *compare)
Definition: splay.h:300
SQUIDCEXTERN int splayLastResult
Definition: splay.h:94
SplayNode< V > const * start() const
Definition: splay.h:327
SplayNode< V > const * start() const
Definition: splay.h:114
V const & operator*() const
Definition: splay.h:484
SplayNode< V > * head
Definition: splay.h:90
SplayNode< V > * insert(Value data, SPLAYCMP *compare)
Definition: splay.h:174
const_iterator end() const
Definition: splay.h:373
SplayNode(Value const &)
Definition: splay.h:97
void advance()
Definition: splay.h:443
SplayNode< void * > splayNode
Definition: splay.h:47
SplayNode< V > * left
Definition: splay.h:28
#define SQUIDCEXTERN
Definition: squid.h:26
void addLeftPath(SplayNode< V > *aNode)
Definition: splay.h:464
SplayConstIterator & operator++()
Definition: splay.h:418
void walk(SPLAYWALKEE *, void *callerState)
Definition: splay.h:101
SplayNode< V > * remove(const Value data, SPLAYCMP *compare)
Definition: splay.h:149
Definition: splay.h:56
Value const * find(FindValue const &, int(*compare)(FindValue const &a, Value const &b)) const
SplayIterator< V > iterator
Definition: splay.h:62
V Value
Definition: splay.h:20
void SPLAYWALKEE(Value const &nodedata, void *state)
Definition: splay.h:23
SplayNode< V > const * finish() const
Definition: splay.h:337
bool operator==(SplayConstIterator const &right) const
Definition: splay.h:406
Splay()
Definition: splay.h:64
size_t elements
Definition: splay.h:91
void visit(Visitor &v) const
recursively visit left nodes, this node, and then right nodes
Definition: splay.h:264
SplayConstIterator(SplayNode< V > *aNode)
Definition: splay.h:399
Comm::AcceptLimiter dummy
Definition: stub_libcomm.cc:16
void remove(Value const &, SPLAYCMP *compare)
Definition: splay.h:314
const_iterator begin() const
Definition: splay.h:366
void SPLAYFREE(Value &)
Definition: splay.h:61
void fatal(const char *message)
Definition: fatal.cc:39
V Value
Definition: splay.h:59
std::stack< SplayNode< V > * > toVisit
Definition: splay.h:395
void visit(Visitor &v) const
recursively visit all nodes, in left-to-right order
Definition: splay.h:276
bool empty() const
Definition: splay.h:80
Value data
Definition: splay.h:27
SplayNode< V > const * finish() const
Definition: splay.h:124
const SplayConstIterator< V > const_iterator
Definition: splay.h:63
void destroy(SPLAYFREE *=DefaultFree)
Definition: splay.h:134
static void DefaultFree(Value &aValue)
Definition: splay.h:24
void destroy(SPLAYFREE *=SplayNode< V >::DefaultFree)
Definition: splay.h:347
void SPLAYFREE(Value &)
Definition: splay.h:22
SplayNode< V > * right
Definition: splay.h:29
int a
Definition: membanger.c:50
const V value_type
Definition: splay.h:384
SplayNode< V > * splay(const FindValue &data, int(*compare)(FindValue const &a, Value const &b)) const
Definition: splay.h:200
size_t size() const
Definition: splay.h:359
void init(SplayNode< V > *)
Definition: splay.h:477
int SPLAYCMP(Value const &a, Value const &b)
Definition: splay.h:21
int SPLAYCMP(Value const &a, Value const &b)
Definition: splay.h:60
squidaio_request_t * head
Definition: aiops.cc:127
#define NULL
Definition: types.h:166

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors