gprofng/src/PRBTree.cc

   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 //    The Persistent Red-Black Tree
  22 //
  23 // Implementation is based on an algorithm described in
  24 // Sarnak, N., Tarjan, R., "Planar point location using
  25 // persistent search trees", in Communications of the ACM,
  26 // 1986, Vol.29, Number 7.
  27 //
  28
  29 #include "config.h"
  30 #include <memory.h>
  31 #include <string.h>
  32
  33 #include "vec.h"
  34 #include "PRBTree.h"
  35
  36 #define ASSERT(x)
  37
  38 #define IS_BLACK(x)     ((x)==NULL || (x)->color == Black)
  39 #define IS_RED(x)       ((x)!=NULL && (x)->color == Red)
  40 #define SET_BLACK(x)    if(x) x->color = Black
  41 #define SET_RED(x)      (x)->color = Red
  42
  43 #define D_OPPOSITE(x) (((x)==Left) ? Right : Left )
  44
  45 PRBTree::LMap::LMap (Key_t _key, void *_item)
  46 {
  47   key = _key;
  48   item = _item;
  49   color = Red;
  50   parent = NULL;
  51   for (int i = 0; i < NPTRS; i++)
  52     {
  53       dir[i] = None;
  54       chld[i] = NULL;
  55       time[i] = 0;
  56     }
  57 };
  58
  59 PRBTree::LMap::LMap (const LMap& lm)
  60 {
  61   key = lm.key;
  62   item = lm.item;
  63   color = lm.color;
  64   parent = lm.parent;
  65   for (int i = 0; i < NPTRS; i++)
  66     {
  67       dir[i] = None;
  68       chld[i] = NULL;
  69       time[i] = 0;
  70     }
  71 };
  72
  73 PRBTree::PRBTree ()
  74 {
  75   roots = new Vector<LMap*>;
  76   root = NULL;
  77   times = new Vector<Time_t>;
  78   rtts = (Time_t) 0;
  79   curts = (Time_t) 0;
  80   mlist = NULL;
  81   vals = NULL;
  82 }
  83
  84 PRBTree::~PRBTree ()
  85 {
  86   while (mlist)
  87     {
  88       LMap *lm = mlist;
  89       mlist = mlist->next;
  90       delete lm;
  91     }
  92   delete times;
  93   delete roots;
  94   delete vals;
  95 }
  96
  97 Vector<void *> *
  98 PRBTree::values ()
  99 {
 100   if (vals == NULL)
 101     {
 102       vals = new Vector<void*>;
 103       for (LMap *lm = mlist; lm; lm = lm->next)
 104         vals->append (lm->item);
 105     }
 106   return vals;
 107 }
 108
 109 PRBTree::LMap *
 110 PRBTree::rb_new_node (Key_t key, void *item)
 111 {
 112   LMap *lm = new LMap (key, item);
 113   lm->next = mlist;
 114   mlist = lm;
 115   return lm;
 116 }
 117
 118 PRBTree::LMap *
 119 PRBTree::rb_new_node (LMap *lm)
 120 {
 121   LMap *lmnew = new LMap (*lm);
 122   lmnew->next = mlist;
 123   mlist = lmnew;
 124   return lmnew;
 125 }
 126
 127 PRBTree::LMap *
 128 PRBTree::rb_child (LMap *lm, Direction d, Time_t ts)
 129 {
 130   if (lm == NULL)
 131     return NULL;
 132   for (int i = 0; i < NPTRS; i++)
 133     {
 134       if (lm->time[i] > ts)
 135         continue;
 136       if (lm->dir[i] == d)
 137         return lm->chld[i];
 138       else if (lm->dir[i] == None)
 139         break;
 140     }
 141   return NULL;
 142 }
 143
 144 PRBTree::Direction
 145 PRBTree::rb_which_chld (LMap *lm)
 146 {
 147   LMap *prnt = lm->parent;
 148   if (prnt == NULL)
 149     return None;
 150   for (int i = 0; i < NPTRS; i++)
 151     {
 152       if (prnt->dir[i] == None)
 153         break;
 154       if (prnt->chld[i] == lm)
 155         return (Direction) prnt->dir[i];
 156     }
 157   return None;
 158 }
 159
 160 PRBTree::LMap *
 161 PRBTree::rb_neighbor (LMap *lm, Time_t ts)
 162 {
 163   ASSERT (lm->dir[0] != None);
 164   Direction d = D_OPPOSITE (lm->dir[0]);
 165   LMap *y = NULL;
 166   LMap *next = lm->chld[0];
 167   while (next)
 168     {
 169       y = next;
 170       next = rb_child (y, d, ts);
 171     }
 172   return y;
 173 }
 174
 175 PRBTree::LMap *
 176 PRBTree::rb_copy_node (LMap *lm, Direction d)
 177 {
 178   LMap *nlm = rb_new_node (lm);
 179   rb_fix_chld (lm->parent, nlm, rb_which_chld (lm));
 180   if (d == None)
 181     {
 182       d = Left;
 183       rb_fix_chld (nlm, rb_child (lm, d, curts), d);
 184     }
 185
 186   // copy the other child
 187   Direction dd = D_OPPOSITE (d);
 188   rb_fix_chld (nlm, rb_child (lm, dd, curts), dd);
 189   return nlm;
 190 }
 191
 192 PRBTree::LMap *
 193 PRBTree::rb_fix_chld (LMap *prnt, LMap *lm, Direction d)
 194 {
 195
 196   if (prnt == NULL)
 197     {
 198       // fixing root
 199       ASSERT (d == None);
 200       if (rtts == curts)
 201         root = lm;
 202       else
 203         {
 204           roots->append (root);
 205           times->append (rtts);
 206           root = lm;
 207           rtts = curts;
 208         }
 209       if (lm != NULL)
 210         lm->parent = prnt;
 211       return prnt;
 212     }
 213
 214   // If we already have a d-pointer at time curts, reuse it
 215   for (int i = 0; prnt->time[i] == curts; i++)
 216     {
 217       if (prnt->dir[i] == d)
 218         {
 219           prnt->chld[i] = lm;
 220           if (lm != NULL)
 221             lm->parent = prnt;
 222           return prnt;
 223         }
 224     }
 225
 226   if (prnt->dir[NPTRS - 1] != None)
 227     prnt = rb_copy_node (prnt, d);
 228   ASSERT (prnt->dir[NPTRS - 1] == None);
 229
 230   for (int i = NPTRS - 1; i > 0; i--)
 231     {
 232       prnt->dir[i] = prnt->dir[i - 1];
 233       prnt->chld[i] = prnt->chld[i - 1];
 234       prnt->time[i] = prnt->time[i - 1];
 235     }
 236   prnt->dir[0] = d;
 237   prnt->chld[0] = lm;
 238   prnt->time[0] = curts;
 239   if (lm != NULL)
 240     lm->parent = prnt;
 241   return prnt;
 242 }
 243
 244 PRBTree::LMap *
 245 PRBTree::rb_rotate (LMap *x, Direction d)
 246 {
 247   Direction dd = D_OPPOSITE (d);
 248   LMap *y = rb_child (x, dd, curts);
 249   x = rb_fix_chld (x, rb_child (y, d, curts), dd);
 250   rb_fix_chld (x->parent, y, rb_which_chld (x));
 251   rb_fix_chld (y, x, d);
 252   return x;
 253 }
 254
 255 void
 256 PRBTree::rb_remove_fixup (LMap *x, LMap *prnt, Direction d0)
 257 {
 258
 259   while (IS_BLACK (x) && (x != root))
 260     {
 261       Direction d = (x == NULL) ? d0 : rb_which_chld (x);
 262       Direction dd = D_OPPOSITE (d);
 263       LMap *y = rb_child (prnt, dd, curts);
 264       if (IS_RED (y))
 265         {
 266           SET_BLACK (y);
 267           SET_RED (prnt);
 268           prnt = rb_rotate (prnt, d);
 269           y = rb_child (prnt, dd, curts);
 270         }
 271       LMap *y_d = rb_child (y, d, curts);
 272       LMap *y_dd = rb_child (y, dd, curts);
 273       if (IS_BLACK (y_d) && IS_BLACK (y_dd))
 274         {
 275           SET_RED (y);
 276           x = prnt;
 277           prnt = x->parent;
 278         }
 279       else
 280         {
 281           if (IS_BLACK (y_dd))
 282             {
 283               SET_BLACK (y_d);
 284               SET_RED (y);
 285               y = rb_rotate (y, dd);
 286               prnt = y->parent->parent;
 287               y = rb_child (prnt, dd, curts);
 288               y_dd = rb_child (y, dd, curts);
 289             }
 290           y->color = prnt->color;
 291           SET_BLACK (prnt);
 292           SET_BLACK (y_dd);
 293           prnt = rb_rotate (prnt, d);
 294           break;
 295         }
 296     }
 297   SET_BLACK (x);
 298 }
 299
 300 PRBTree::LMap *
 301 PRBTree::rb_locate (Key_t key, Time_t ts, bool low)
 302 {
 303   LMap *lm;
 304   Direction d;
 305   int i, lt, rt;
 306   int tsz = times->size ();
 307
 308   if (ts >= rtts)
 309     lm = root;
 310   else
 311     {
 312       // exponential search
 313       for (i = 1; i <= tsz; i = i * 2)
 314         if (times->fetch (tsz - i) <= ts)
 315           break;
 316
 317       if (i <= tsz)
 318         {
 319           lt = tsz - i;
 320           rt = tsz - i / 2 - 1;
 321         }
 322       else
 323         {
 324           lt = 0;
 325           rt = tsz - 1;
 326         }
 327       while (lt <= rt)
 328         {
 329           int md = (lt + rt) / 2;
 330           if (times->fetch (md) <= ts)
 331             lt = md + 1;
 332           else
 333             rt = md - 1;
 334         }
 335       if (rt < 0)
 336         return NULL;
 337       lm = roots->fetch (rt);
 338     }
 339
 340   LMap *last_lo = NULL;
 341   LMap *last_hi = NULL;
 342   while (lm != NULL)
 343     {
 344       if (key >= lm->key)
 345         {
 346           last_lo = lm;
 347           d = Right;
 348         }
 349       else
 350         {
 351           last_hi = lm;
 352           d = Left;
 353         }
 354       lm = rb_child (lm, d, ts);
 355     }
 356   return low ? last_lo : last_hi;
 357 }
 358
 359 //==================================================== Public interface
 360
 361 bool
 362 PRBTree::insert (Key_t key, Time_t ts, void *item)
 363 {
 364   LMap *lm, *y;
 365   Direction d, dd;
 366   if (ts > curts)
 367     curts = ts;
 368   else if (ts < curts)
 369     return false; // can only update the current tree
 370
 371   // Insert in the tree in the usual way
 372   y = NULL;
 373   d = None;
 374   for (LMap *next = root; next;)
 375     {
 376       y = next;
 377       if (key == y->key)
 378         {
 379           // copy the node with both children
 380           lm = rb_copy_node (y, None);
 381           // but use the new item
 382           lm->item = item;
 383           return true;
 384         }
 385       d = (key < y->key) ? Left : Right;
 386       next = rb_child (y, d, curts);
 387     }
 388   lm = rb_new_node (key, item);
 389   rb_fix_chld (y, lm, d);
 390
 391   // Rebalance the tree
 392   while (IS_RED (lm->parent))
 393     {
 394       d = rb_which_chld (lm->parent);
 395       dd = D_OPPOSITE (d);
 396
 397       y = rb_child (lm->parent->parent, dd, curts);
 398       if (IS_RED (y))
 399         {
 400           SET_BLACK (lm->parent);
 401           SET_BLACK (y);
 402           SET_RED (lm->parent->parent);
 403           lm = lm->parent->parent;
 404         }
 405       else
 406         {
 407           if (rb_which_chld (lm) == dd)
 408             {
 409               lm = lm->parent;
 410               lm = rb_rotate (lm, d);
 411             }
 412           SET_BLACK (lm->parent);
 413           SET_RED (lm->parent->parent);
 414           rb_rotate (lm->parent->parent, dd);
 415         }
 416     }
 417
 418   // Color the root Black
 419   SET_BLACK (root);
 420   return true;
 421 }
 422
 423 bool
 424 PRBTree::remove (Key_t key, Time_t ts)
 425 {
 426   LMap *lm, *x, *y, *prnt;
 427   if (ts > curts)
 428     curts = ts;
 429   else if (ts < curts)
 430     return false; // can only update the current tree
 431
 432   lm = rb_locate (key, curts, true);
 433   if (lm == NULL || lm->key != key)
 434     return false;
 435
 436   if (rb_child (lm, Left, curts) && rb_child (lm, Right, curts))
 437     y = rb_neighbor (lm, curts);
 438   else
 439     y = lm;
 440
 441   x = rb_child (y, Left, curts);
 442   if (x == NULL)
 443     x = rb_child (y, Right, curts);
 444
 445   if (y != lm)
 446     {
 447       lm = rb_copy_node (lm, None); // copied with children
 448       lm->key = y->key;
 449       lm->item = y->item;
 450     }
 451
 452   Direction d = rb_which_chld (y);
 453   prnt = rb_fix_chld (y->parent, x, d);
 454   if (IS_BLACK (y))
 455     rb_remove_fixup (x, prnt, d);
 456   return true;
 457 }
 458
 459 void *
 460 PRBTree::locate (Key_t key, Time_t ts)
 461 {
 462   LMap *lm = rb_locate (key, ts, true);
 463   return lm ? lm->item : NULL;
 464 }
 465
 466 void *
 467 PRBTree::locate_up (Key_t key, Time_t ts)
 468 {
 469   LMap *lm = rb_locate (key, ts, false);
 470   return lm ? lm->item : NULL;
 471 }
 472
 473 void *
 474 PRBTree::locate_exact_match (Key_t key, Time_t ts)
 475 {
 476   LMap *lm = rb_locate (key, ts, true);
 477   if (lm && key == lm->key)
 478     return lm->item;
 479   return NULL;
 480 }