gprofng: a new GNU profiler

top-level
	* Makefile.def: Add gprofng module.
	* configure.ac: Add --enable-gprofng option.
	* src-release.sh: Add gprofng.
	* Makefile.in: Regenerate.
	* configure: Regenerate.
	* gprofng: New directory.

binutils
	* MAINTAINERS: Add gprofng maintainer.
	* README-how-to-make-a-release: Add gprofng.

include.
	* collectorAPI.h: New file.
	* libcollector.h: New file.
	* libfcollector.h: New file.

1 files changed, 480 insertions, 0 deletions

diff --git a/gprofng/src/PRBTree.cc b/gprofng/src/PRBTree.cc
new file mode 100644
index 0000000..5046a91
--- /dev/null
+++ b/gprofng/src/PRBTree.cc
@@ -0,0 +1,480 @@
+/* Copyright (C) 2021 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;
+}