gprofng/src/PRBTree.h

   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 */