L4Re - L4 Runtime Environment
bst_base.h
Go to the documentation of this file.
1 // vi:ft=cpp
6 /*
7  * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
8  * Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
9  * economic rights: Technische Universit├Ąt Dresden (Germany)
10  *
11  * This file is part of TUD:OS and distributed under the terms of the
12  * GNU General Public License 2.
13  * Please see the COPYING-GPL-2 file for details.
14  *
15  * As a special exception, you may use this file as part of a free software
16  * library without restriction. Specifically, if other files instantiate
17  * templates or use macros or inline functions from this file, or you compile
18  * this file and link it with other files to produce an executable, this
19  * file does not by itself cause the resulting executable to be covered by
20  * the GNU General Public License. This exception does not however
21  * invalidate any other reasons why the executable file might be covered by
22  * the GNU General Public License.
23  */
24 
25 #pragma once
26 
27 /*
28  * This file contains very basic bits for implementing binary serach trees
29  */
30 namespace cxx {
34 namespace Bits {
35 
39 struct Direction
40 {
43  {
44  L = 0,
45  R = 1,
46  N = 2
47  };
48  unsigned char d;
49 
51  Direction() {}
52 
54  Direction(Direction_e d) : d(d) {}
55 
57  explicit Direction(bool b) : d(Direction_e(b)) /*d(b ? R : L)*/ {}
58 
63  Direction operator ! () const { return Direction(!d); }
64 
66 
67  bool operator == (Direction_e o) const { return d == o; }
68  bool operator != (Direction_e o) const { return d != o; }
69  bool operator == (Direction o) const { return d == o.d; }
70  bool operator != (Direction o) const { return d != o.d; }
72 };
73 
77 class Bst_node
78 {
79  // all BSTs are friends
80  template< typename Node, typename Get_key, typename Compare >
81  friend class Bst;
82 
83 protected:
92 
94  static Bst_node *next(Bst_node const *p, Direction d)
95  { return p->_c[d.d]; }
96 
98  static void next(Bst_node *p, Direction d, Bst_node *n)
99  { p->_c[d.d] = n; }
100 
103  { return &p->_c[d.d]; }
104 
106  template< typename Node > static
107  Node *next(Bst_node const *p, Direction d)
108  { return static_cast<Node *>(p->_c[d.d]); }
109 
111  static void rotate(Bst_node **t, Direction idir);
114 private:
115  Bst_node *_c[2];
116 
117 protected:
119  Bst_node() {}
120 
122  explicit Bst_node(bool) { _c[0] = _c[1] = 0; }
123 };
124 
125 inline
126 void
128 {
129  Bst_node *tmp = *t;
130  *t = next(tmp, idir);
131  next(tmp, idir, next(*t, !idir));
132  next(*t, !idir, tmp);
133 }
134 
135 }}
Our C++ library.
Definition: arith:22
Bst_node()
Create uninitialized node.
Definition: bst_base.h:119
Go to the left child.
Definition: bst_base.h:44
Direction()
Uninitialized direction.
Definition: bst_base.h:51
The direction to go in a binary search tree.
Definition: bst_base.h:39
Direction operator!() const
Negate the direction.
Definition: bst_base.h:63
static Bst_node * next(Bst_node const *p, Direction d)
Get next node in direction d.
Definition: bst_base.h:94
static void rotate(Bst_node **t, Direction idir)
Rotate subtree t in the opposite direction of idir.
Definition: bst_base.h:127
Bst_node(bool)
Create initialized node.
Definition: bst_base.h:122
static Node * next(Bst_node const *p, Direction d)
Get next node in direction d as type Node.
Definition: bst_base.h:107
Direction_e
The literal direction values.
Definition: bst_base.h:42
Basic binary search tree (BST).
Definition: bst.h:40
Basic type of a node in a binary search tree (BST).
Definition: bst_base.h:77
static Bst_node ** next_p(Bst_node *p, Direction d)
Get pointer to link in direction d.
Definition: bst_base.h:102
Direction(bool b)
Convert a boolean to a direction (false == L, true == R)
Definition: bst_base.h:57
Go to the right child.
Definition: bst_base.h:45
Direction(Direction_e d)
Convert a literal direction (L, R, N) to an object.
Definition: bst_base.h:54
static void next(Bst_node *p, Direction d, Bst_node *n)
Set next node of p in direction d to n.
Definition: bst_base.h:98