1  /* Copyright (C) 2021-2023 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 */