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