mirror of
https://github.com/autc04/Retro68.git
synced 2024-06-08 04:29:46 +00:00
481 lines
9.3 KiB
C++
481 lines
9.3 KiB
C++
/* 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;
|
|
}
|