1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
/* Copyright (C) 2021-2023 Free Software Foundation, Inc.
Contributed by Oracle.
This file is part of GNU Binutils.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, 51 Franklin Street - Fifth Floor, Boston,
MA 02110-1301, USA. */
//
// The Persistent Red-Black Tree
//
#ifndef _PRBTREE_H
#define _PRBTREE_H
#include "dbe_types.h"
template <class ITEM> class Vector;
// The number of pointers in a node must be set greater than 2.
// The higher the number the faster the search seems to be and
// the more memory the tree takes.
#define NPTRS 5
class PRBTree
{
public:
typedef Vaddr Key_t;
typedef hrtime_t Time_t;
PRBTree ();
~PRBTree ();
bool insert (Key_t key, Time_t ts, void *item);
bool remove (Key_t key, Time_t ts);
void *locate (Key_t key, Time_t ts);
void *locate_exact_match (Key_t key, Time_t ts);
void *locate_up (Key_t key, Time_t ts);
Vector<void *> *values ();
private:
enum Color
{
Red,
Black
};
enum Direction
{
None,
Left,
Right
};
struct LMap
{
Key_t key;
void *item;
LMap *parent;
LMap *chld[NPTRS];
Time_t time[NPTRS];
char dir[NPTRS];
char color;
LMap *next;
LMap (Key_t _key, void *_item);
LMap (const LMap& lm);
};
friend struct LMap;
LMap *mlist; // The master list of all nodes
Vector<LMap*> *roots;
Vector<Time_t> *times;
Vector<void *> *vals;
LMap *root;
Time_t rtts; // root timestamp
Time_t curts; // last update timestamp
LMap *rb_locate (Key_t key, Time_t ts, bool low);
LMap *rb_new_node (Key_t key, void *item);
LMap *rb_new_node (LMap *lm);
LMap *rb_copy_node (LMap *lm, Direction d);
LMap *rb_fix_chld (LMap *prnt, LMap *lm, Direction d);
LMap *rb_rotate (LMap *x, Direction d);
void rb_remove_fixup (LMap *x, LMap *prnt, Direction d0);
static LMap *rb_child (LMap *lm, Direction d, Time_t ts);
static Direction rb_which_chld (LMap *lm);
static LMap *rb_neighbor (LMap *lm, Time_t ts);
};
#endif /* _PRBTREE_H */
|
