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
45PRBTree::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
59PRBTree::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
73PRBTree::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
84PRBTree::~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
97Vector<void *> *
98PRBTree::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
109PRBTree::LMap *
110PRBTree::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
118PRBTree::LMap *
119PRBTree::rb_new_node (LMap *lm)
120{
121  LMap *lmnew = new LMap (*lm);
122  lmnew->next = mlist;
123  mlist = lmnew;
124  return lmnew;
125}
126
127PRBTree::LMap *
128PRBTree::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
144PRBTree::Direction
145PRBTree::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
160PRBTree::LMap *
161PRBTree::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
175PRBTree::LMap *
176PRBTree::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
192PRBTree::LMap *
193PRBTree::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
244PRBTree::LMap *
245PRBTree::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
255void
256PRBTree::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
300PRBTree::LMap *
301PRBTree::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
361bool
362PRBTree::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
423bool
424PRBTree::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
459void *
460PRBTree::locate (Key_t key, Time_t ts)
461{
462  LMap *lm = rb_locate (key, ts, true);
463  return lm ? lm->item : NULL;
464}
465
466void *
467PRBTree::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
473void *
474PRBTree::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}
481