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