gprofng/src/PRBTree.cc

/* Copyright (C) 2021-2024 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
//
// Implementation is based on an algorithm described in
// Sarnak, N., Tarjan, R., "Planar point location using
// persistent search trees", in Communications of the ACM,
// 1986, Vol.29, Number 7.
//

#include "config.h"
#include <memory.h>
#include <string.h>

#include "vec.h"
#include "PRBTree.h"

#define ASSERT(x)

#define IS_BLACK(x)     ((x)==NULL || (x)->color == Black)
#define IS_RED(x)       ((x)!=NULL && (x)->color == Red)
#define SET_BLACK(x)    if(x) x->color = Black
#define SET_RED(x)      (x)->color = Red

#define D_OPPOSITE(x) (((x)==Left) ? Right : Left )

PRBTree::LMap::LMap (Key_t _key, void *_item)
{
  key = _key;
  item = _item;
  color = Red;
  parent = NULL;
  for (int i = 0; i < NPTRS; i++)
    {
      dir[i] = None;
      chld[i] = NULL;
      time[i] = 0;
    }
};

PRBTree::LMap::LMap (const LMap& lm)
{
  key = lm.key;
  item = lm.item;
  color = lm.color;
  parent = lm.parent;
  for (int i = 0; i < NPTRS; i++)
    {
      dir[i] = None;
      chld[i] = NULL;
      time[i] = 0;
    }
};

PRBTree::PRBTree ()
{
  roots = new Vector<LMap*>;
  root = NULL;
  times = new Vector<Time_t>;
  rtts = (Time_t) 0;
  curts = (Time_t) 0;
  mlist = NULL;
  vals = NULL;
}

PRBTree::~PRBTree ()
{
  while (mlist)
    {
      LMap *lm = mlist;
      mlist = mlist->next;
      delete lm;
    }
  delete times;
  delete roots;
  delete vals;
}

Vector<void *> *
PRBTree::values ()
{
  if (vals == NULL)
    {
      vals = new Vector<void*>;
      for (LMap *lm = mlist; lm; lm = lm->next)
	vals->append (lm->item);
    }
  return vals;
}

PRBTree::LMap *
PRBTree::rb_new_node (Key_t key, void *item)
{
  LMap *lm = new LMap (key, item);
  lm->next = mlist;
  mlist = lm;
  return lm;
}

PRBTree::LMap *
PRBTree::rb_new_node (LMap *lm)
{
  LMap *lmnew = new LMap (*lm);
  lmnew->next = mlist;
  mlist = lmnew;
  return lmnew;
}

PRBTree::LMap *
PRBTree::rb_child (LMap *lm, Direction d, Time_t ts)
{
  if (lm == NULL)
    return NULL;
  for (int i = 0; i < NPTRS; i++)
    {
      if (lm->time[i] > ts)
	continue;
      if (lm->dir[i] == d)
	return lm->chld[i];
      else if (lm->dir[i] == None)
	break;
    }
  return NULL;
}

PRBTree::Direction
PRBTree::rb_which_chld (LMap *lm)
{
  LMap *prnt = lm->parent;
  if (prnt == NULL)
    return None;
  for (int i = 0; i < NPTRS; i++)
    {
      if (prnt->dir[i] == None)
	break;
      if (prnt->chld[i] == lm)
	return (Direction) prnt->dir[i];
    }
  return None;
}

PRBTree::LMap *
PRBTree::rb_neighbor (LMap *lm, Time_t ts)
{
  ASSERT (lm->dir[0] != None);
  Direction d = D_OPPOSITE (lm->dir[0]);
  LMap *y = NULL;
  LMap *next = lm->chld[0];
  while (next)
    {
      y = next;
      next = rb_child (y, d, ts);
    }
  return y;
}

PRBTree::LMap *
PRBTree::rb_copy_node (LMap *lm, Direction d)
{
  LMap *nlm = rb_new_node (lm);
  rb_fix_chld (lm->parent, nlm, rb_which_chld (lm));
  if (d == None)
    {
      d = Left;
      rb_fix_chld (nlm, rb_child (lm, d, curts), d);
    }

  // copy the other child
  Direction dd = D_OPPOSITE (d);
  rb_fix_chld (nlm, rb_child (lm, dd, curts), dd);
  return nlm;
}

PRBTree::LMap *
PRBTree::rb_fix_chld (LMap *prnt, LMap *lm, Direction d)
{

  if (prnt == NULL)
    {
      // fixing root
      ASSERT (d == None);
      if (rtts == curts)
	root = lm;
      else
	{
	  roots->append (root);
	  times->append (rtts);
	  root = lm;
	  rtts = curts;
	}
      if (lm != NULL)
	lm->parent = prnt;
      return prnt;
    }

  // If we already have a d-pointer at time curts, reuse it
  for (int i = 0; prnt->time[i] == curts; i++)
    {
      if (prnt->dir[i] == d)
	{
	  prnt->chld[i] = lm;
	  if (lm != NULL)
	    lm->parent = prnt;
	  return prnt;
	}
    }

  if (prnt->dir[NPTRS - 1] != None)
    prnt = rb_copy_node (prnt, d);
  ASSERT (prnt->dir[NPTRS - 1] == None);

  for (int i = NPTRS - 1; i > 0; i--)
    {
      prnt->dir[i] = prnt->dir[i - 1];
      prnt->chld[i] = prnt->chld[i - 1];
      prnt->time[i] = prnt->time[i - 1];
    }
  prnt->dir[0] = d;
  prnt->chld[0] = lm;
  prnt->time[0] = curts;
  if (lm != NULL)
    lm->parent = prnt;
  return prnt;
}

PRBTree::LMap *
PRBTree::rb_rotate (LMap *x, Direction d)
{
  Direction dd = D_OPPOSITE (d);
  LMap *y = rb_child (x, dd, curts);
  x = rb_fix_chld (x, rb_child (y, d, curts), dd);
  rb_fix_chld (x->parent, y, rb_which_chld (x));
  rb_fix_chld (y, x, d);
  return x;
}

void
PRBTree::rb_remove_fixup (LMap *x, LMap *prnt, Direction d0)
{

  while (IS_BLACK (x) && (x != root))
    {
      Direction d = (x == NULL) ? d0 : rb_which_chld (x);
      Direction dd = D_OPPOSITE (d);
      LMap *y = rb_child (prnt, dd, curts);
      if (IS_RED (y))
	{
	  SET_BLACK (y);
	  SET_RED (prnt);
	  prnt = rb_rotate (prnt, d);
	  y = rb_child (prnt, dd, curts);
	}
      LMap *y_d = rb_child (y, d, curts);
      LMap *y_dd = rb_child (y, dd, curts);
      if (IS_BLACK (y_d) && IS_BLACK (y_dd))
	{
	  SET_RED (y);
	  x = prnt;
	  prnt = x->parent;
	}
      else
	{
	  if (IS_BLACK (y_dd))
	    {
	      SET_BLACK (y_d);
	      SET_RED (y);
	      y = rb_rotate (y, dd);
	      prnt = y->parent->parent;
	      y = rb_child (prnt, dd, curts);
	      y_dd = rb_child (y, dd, curts);
	    }
	  y->color = prnt->color;
	  SET_BLACK (prnt);
	  SET_BLACK (y_dd);
	  prnt = rb_rotate (prnt, d);
	  break;
	}
    }
  SET_BLACK (x);
}

PRBTree::LMap *
PRBTree::rb_locate (Key_t key, Time_t ts, bool low)
{
  LMap *lm;
  Direction d;
  int i, lt, rt;
  int tsz = times->size ();

  if (ts >= rtts)
    lm = root;
  else
    {
      // exponential search
      for (i = 1; i <= tsz; i = i * 2)
	if (times->fetch (tsz - i) <= ts)
	  break;

      if (i <= tsz)
	{
	  lt = tsz - i;
	  rt = tsz - i / 2 - 1;
	}
      else
	{
	  lt = 0;
	  rt = tsz - 1;
	}
      while (lt <= rt)
	{
	  int md = (lt + rt) / 2;
	  if (times->fetch (md) <= ts)
	    lt = md + 1;
	  else
	    rt = md - 1;
	}
      if (rt < 0)
	return NULL;
      lm = roots->fetch (rt);
    }

  LMap *last_lo = NULL;
  LMap *last_hi = NULL;
  while (lm != NULL)
    {
      if (key >= lm->key)
	{
	  last_lo = lm;
	  d = Right;
	}
      else
	{
	  last_hi = lm;
	  d = Left;
	}
      lm = rb_child (lm, d, ts);
    }
  return low ? last_lo : last_hi;
}

//==================================================== Public interface

bool
PRBTree::insert (Key_t key, Time_t ts, void *item)
{
  LMap *lm, *y;
  Direction d, dd;
  if (ts > curts)
    curts = ts;
  else if (ts < curts)
    return false; // can only update the current tree

  // Insert in the tree in the usual way
  y = NULL;
  d = None;
  for (LMap *next = root; next;)
    {
      y = next;
      if (key == y->key)
	{
	  // copy the node with both children
	  lm = rb_copy_node (y, None);
	  // but use the new item
	  lm->item = item;
	  return true;
	}
      d = (key < y->key) ? Left : Right;
      next = rb_child (y, d, curts);
    }
  lm = rb_new_node (key, item);
  rb_fix_chld (y, lm, d);

  // Rebalance the tree
  while (IS_RED (lm->parent))
    {
      d = rb_which_chld (lm->parent);
      dd = D_OPPOSITE (d);

      y = rb_child (lm->parent->parent, dd, curts);
      if (IS_RED (y))
	{
	  SET_BLACK (lm->parent);
	  SET_BLACK (y);
	  SET_RED (lm->parent->parent);
	  lm = lm->parent->parent;
	}
      else
	{
	  if (rb_which_chld (lm) == dd)
	    {
	      lm = lm->parent;
	      lm = rb_rotate (lm, d);
	    }
	  SET_BLACK (lm->parent);
	  SET_RED (lm->parent->parent);
	  rb_rotate (lm->parent->parent, dd);
	}
    }

  // Color the root Black
  SET_BLACK (root);
  return true;
}

bool
PRBTree::remove (Key_t key, Time_t ts)
{
  LMap *lm, *x, *y, *prnt;
  if (ts > curts)
    curts = ts;
  else if (ts < curts)
    return false; // can only update the current tree

  lm = rb_locate (key, curts, true);
  if (lm == NULL || lm->key != key)
    return false;

  if (rb_child (lm, Left, curts) && rb_child (lm, Right, curts))
    y = rb_neighbor (lm, curts);
  else
    y = lm;

  x = rb_child (y, Left, curts);
  if (x == NULL)
    x = rb_child (y, Right, curts);

  if (y != lm)
    {
      lm = rb_copy_node (lm, None); // copied with children
      lm->key = y->key;
      lm->item = y->item;
    }

  Direction d = rb_which_chld (y);
  prnt = rb_fix_chld (y->parent, x, d);
  if (IS_BLACK (y))
    rb_remove_fixup (x, prnt, d);
  return true;
}

void *
PRBTree::locate (Key_t key, Time_t ts)
{
  LMap *lm = rb_locate (key, ts, true);
  return lm ? lm->item : NULL;
}

void *
PRBTree::locate_up (Key_t key, Time_t ts)
{
  LMap *lm = rb_locate (key, ts, false);
  return lm ? lm->item : NULL;
}

void *
PRBTree::locate_exact_match (Key_t key, Time_t ts)
{
  LMap *lm = rb_locate (key, ts, true);
  if (lm && key == lm->key)
    return lm->item;
  return NULL;
}