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 } 481