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