L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
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 */
30namespace cxx {
34namespace Bits {
35
40{
43 {
44 L = 0,
45 R = 1,
46 N = 2
47 };
48 unsigned char d;
49
51 Direction() = default;
52
55
57 explicit Direction(bool b) : d(Direction_e(b)) /*d(b ? R : L)*/ {}
58
63 Direction operator ! () const { return Direction(!d); }
64
66
68 bool operator == (Direction_e o) const { return d == o; }
70 bool operator != (Direction_e o) const { return d != o; }
72 bool operator == (Direction o) const { return d == o.d; }
74 bool operator != (Direction o) const { return d != o.d; }
76};
77
82{
83 // all BSTs are friends
84 template< typename Node, typename Get_key, typename Compare >
85 friend class Bst;
86
87protected:
98 static Bst_node *next(Bst_node const *p, Direction d)
99 { return p->_c[d.d]; }
100
102 static void next(Bst_node *p, Direction d, Bst_node *n)
103 { p->_c[d.d] = n; }
104
107 { return &p->_c[d.d]; }
108
110 template< typename Node > static
111 Node *next(Bst_node const *p, Direction d)
112 { return static_cast<Node *>(p->_c[d.d]); }
113
115 static void rotate(Bst_node **t, Direction idir);
118private:
119 Bst_node *_c[2];
120
121protected:
124
126 explicit Bst_node(bool) { _c[0] = _c[1] = 0; }
127};
128
129inline
130void
132{
133 Bst_node *tmp = *t;
134 *t = next(tmp, idir);
135 next(tmp, idir, next(*t, !idir));
136 next(*t, !idir, tmp);
137}
138
139}}
Basic type of a node in a binary search tree (BST).
Definition bst_base.h:82
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:102
static Bst_node ** next_p(Bst_node *p, Direction d)
Get pointer to link in direction d.
Definition bst_base.h:106
static Node * next(Bst_node const *p, Direction d)
Get next node in direction d as type Node.
Definition bst_base.h:111
Bst_node(bool)
Create initialized node.
Definition bst_base.h:126
static void rotate(Bst_node **t, Direction idir)
Rotate subtree t in the opposite direction of idir.
Definition bst_base.h:131
Bst_node()
Create uninitialized node.
Definition bst_base.h:123
static Bst_node * next(Bst_node const *p, Direction d)
Get next node in direction d.
Definition bst_base.h:98
Basic binary search tree (BST).
Definition bst.h:43
Our C++ library.
Definition arith:22
The direction to go in a binary search tree.
Definition bst_base.h:40
Direction(Direction_e d)
Convert a literal direction (L, R, N) to an object.
Definition bst_base.h:54
Direction(bool b)
Convert a boolean to a direction (false == L, true == R)
Definition bst_base.h:57
bool operator!=(Direction_e o) const
Compare for inequality.
Definition bst_base.h:70
bool operator==(Direction_e o) const
Compare for equality.
Definition bst_base.h:68
Direction()=default
Uninitialized direction.
Direction operator!() const
Negate the direction.
Definition bst_base.h:63
Direction_e
The literal direction values.
Definition bst_base.h:43
@ L
Go to the left child.
Definition bst_base.h:44
@ R
Go to the right child.
Definition bst_base.h:45