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
LMap(Key_t _key,void * _item)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
LMap(const LMap & lm)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
PRBTree()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
~PRBTree()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 *> *
values()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 *
rb_new_node(Key_t key,void * item)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 *
rb_new_node(LMap * lm)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 *
rb_child(LMap * lm,Direction d,Time_t ts)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
rb_which_chld(LMap * lm)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 *
rb_neighbor(LMap * lm,Time_t ts)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 *
rb_copy_node(LMap * lm,Direction d)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 *
rb_fix_chld(LMap * prnt,LMap * lm,Direction d)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 *
rb_rotate(LMap * x,Direction d)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
rb_remove_fixup(LMap * x,LMap * prnt,Direction d0)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 *
rb_locate(Key_t key,Time_t ts,bool low)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
insert(Key_t key,Time_t ts,void * item)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
remove(Key_t key,Time_t ts)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 *
locate(Key_t key,Time_t ts)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 *
locate_up(Key_t key,Time_t ts)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 *
locate_exact_match(Key_t key,Time_t ts)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