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" 29 template <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 36 class PRBTree 37 { 38 public: 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 53 private: 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