L4Re Operating System Framework
Interface and Usage Documentation
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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 * License: see LICENSE.spdx (in this directory or the directories above)
12 */
13
14#pragma once
15
16/*
17 * This file contains very basic bits for implementing binary search trees
18 */
19namespace cxx {
23namespace Bits {
24
29{
32 {
33 L = 0,
34 R = 1,
35 N = 2
36 };
37 unsigned char d;
38
40 Direction() = default;
41
44
46 explicit Direction(bool b) : d(Direction_e(b)) /*d(b ? R : L)*/ {}
47
52 Direction operator ! () const { return Direction(!d); }
53
55
57 bool operator == (Direction_e o) const { return d == o; }
59 bool operator != (Direction_e o) const { return d != o; }
61 bool operator == (Direction o) const { return d == o.d; }
63 bool operator != (Direction o) const { return d != o.d; }
65};
66
71{
72 // all BSTs are friends
73 template< typename Node, typename Get_key, typename Compare >
74 friend class Bst;
75
76protected:
87 static Bst_node *next(Bst_node const *p, Direction d)
88 { return p->_c[d.d]; }
89
91 static void next(Bst_node *p, Direction d, Bst_node *n)
92 { p->_c[d.d] = n; }
93
96 { return &p->_c[d.d]; }
97
99 template< typename Node > static
100 Node *next(Bst_node const *p, Direction d)
101 { return static_cast<Node *>(p->_c[d.d]); }
102
104 static void rotate(Bst_node **t, Direction idir);
107private:
108 Bst_node *_c[2];
109
110protected:
113
115 explicit Bst_node(bool) { _c[0] = _c[1] = 0; }
116};
117
118inline
119void
121{
122 Bst_node *tmp = *t;
123 *t = next(tmp, idir);
124 next(tmp, idir, next(*t, !idir));
125 next(*t, !idir, tmp);
126}
127
128}}
Basic type of a node in a binary search tree (BST).
Definition bst_base.h:71
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:91
static Bst_node ** next_p(Bst_node *p, Direction d)
Get pointer to link in direction d.
Definition bst_base.h:95
static Node * next(Bst_node const *p, Direction d)
Get next node in direction d as type Node.
Definition bst_base.h:100
Bst_node(bool)
Create initialized node.
Definition bst_base.h:115
static void rotate(Bst_node **t, Direction idir)
Rotate subtree t in the opposite direction of idir.
Definition bst_base.h:120
Bst_node()
Create uninitialized node.
Definition bst_base.h:112
static Bst_node * next(Bst_node const *p, Direction d)
Get next node in direction d.
Definition bst_base.h:87
Basic binary search tree (BST).
Definition bst.h:32
Our C++ library.
Definition arith:11
The direction to go in a binary search tree.
Definition bst_base.h:29
Direction(Direction_e d)
Convert a literal direction (L, R, N) to an object.
Definition bst_base.h:43
Direction(bool b)
Convert a boolean to a direction (false == L, true == R)
Definition bst_base.h:46
bool operator!=(Direction_e o) const
Compare for inequality.
Definition bst_base.h:59
bool operator==(Direction_e o) const
Compare for equality.
Definition bst_base.h:57
Direction()=default
Uninitialized direction.
Direction operator!() const
Negate the direction.
Definition bst_base.h:52
Direction_e
The literal direction values.
Definition bst_base.h:32
@ L
Go to the left child.
Definition bst_base.h:33
@ R
Go to the right child.
Definition bst_base.h:34