1 // Copyright 2016 Amanieu d'Antras
2 // Copyright 2020 Amari Robinson
3 //
4 // Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
5 // http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
6 // http://opensource.org/licenses/MIT>, at your option. This file may not be
7 // copied, modified, or distributed except according to those terms.
8
9 //! Intrusive red-black tree.
10
11 use core::borrow::Borrow;
12 use core::cell::Cell;
13 use core::cmp::Ordering;
14 use core::fmt;
15 use core::mem;
16 use core::ptr::NonNull;
17
18 use crate::Bound::{self, Excluded, Included, Unbounded};
19
20 use crate::link_ops::{self, DefaultLinkOps};
21 use crate::linked_list::LinkedListOps;
22 use crate::pointer_ops::PointerOps;
23 use crate::singly_linked_list::SinglyLinkedListOps;
24 use crate::unchecked_option::UncheckedOptionExt;
25 use crate::xor_linked_list::XorLinkedListOps;
26 use crate::Adapter;
27 use crate::KeyAdapter;
28
29 // =============================================================================
30 // RBTreeOps
31 // =============================================================================
32
33 /// The color of a red-black tree node.
34 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
35 #[allow(missing_docs)]
36 pub enum Color {
37 Red,
38 Black,
39 }
40
41 /// Link operations for `RBTree`.
42 pub unsafe trait RBTreeOps: link_ops::LinkOps {
43 /// Returns the left child of `ptr`.
44 ///
45 /// # Safety
46 /// An implementation of `left` must not panic.
left(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>47 unsafe fn left(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>;
48
49 /// Returns the right child of `ptr`.
50 ///
51 /// # Safety
52 /// An implementation of `right` must not panic.
right(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>53 unsafe fn right(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>;
54
55 /// Returns the parent of `ptr`.
56 ///
57 /// # Safety
58 /// An implementation of `parent` must not panic.
parent(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>59 unsafe fn parent(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>;
60
61 /// Returns the color of `ptr`.
62 ///
63 /// # Safety
64 /// An implementation of `color` must not panic.
color(&self, ptr: Self::LinkPtr) -> Color65 unsafe fn color(&self, ptr: Self::LinkPtr) -> Color;
66
67 /// Sets the left child of `ptr`.
68 ///
69 /// # Safety
70 /// An implementation of `set_left` must not panic.
set_left(&mut self, ptr: Self::LinkPtr, left: Option<Self::LinkPtr>)71 unsafe fn set_left(&mut self, ptr: Self::LinkPtr, left: Option<Self::LinkPtr>);
72
73 /// Sets the right child of `ptr`.
74 ///
75 /// # Safety
76 /// An implementation of `set_right` must not panic.
set_right(&mut self, ptr: Self::LinkPtr, right: Option<Self::LinkPtr>)77 unsafe fn set_right(&mut self, ptr: Self::LinkPtr, right: Option<Self::LinkPtr>);
78
79 /// Sets the parent of `ptr`.
80 ///
81 /// # Safety
82 /// An implementation of `set_parent` must not panic.
set_parent(&mut self, ptr: Self::LinkPtr, parent: Option<Self::LinkPtr>)83 unsafe fn set_parent(&mut self, ptr: Self::LinkPtr, parent: Option<Self::LinkPtr>);
84
85 /// Sets the color of `ptr`.
86 ///
87 /// # Safety
88 /// An implementation of `set_color` must not panic.
set_color(&mut self, ptr: Self::LinkPtr, color: Color)89 unsafe fn set_color(&mut self, ptr: Self::LinkPtr, color: Color);
90 }
91
92 // =============================================================================
93 // Link
94 // =============================================================================
95
96 /// Intrusive link that allows an object to be inserted into a
97 /// `RBTree`.
98 #[repr(align(2))]
99 pub struct Link {
100 left: Cell<Option<NonNull<Link>>>,
101 right: Cell<Option<NonNull<Link>>>,
102 parent_color: Cell<usize>,
103 }
104
105 // Use a special value to indicate an unlinked node. This value represents a
106 // red root node, which is impossible in a valid red-black tree.
107 const UNLINKED_MARKER: usize = 0;
108
109 impl Link {
110 /// Creates a new `Link`.
111 #[inline]
new() -> Link112 pub const fn new() -> Link {
113 Link {
114 left: Cell::new(None),
115 right: Cell::new(None),
116 parent_color: Cell::new(UNLINKED_MARKER),
117 }
118 }
119
120 /// Checks whether the `Link` is linked into a `RBTree`.
121 #[inline]
is_linked(&self) -> bool122 pub fn is_linked(&self) -> bool {
123 self.parent_color.get() != UNLINKED_MARKER
124 }
125
126 /// Forcibly unlinks an object from a `RBTree`.
127 ///
128 /// # Safety
129 ///
130 /// It is undefined behavior to call this function while still linked into a
131 /// `RBTree`. The only situation where this function is useful is
132 /// after calling `fast_clear` on a `RBTree`, since this clears
133 /// the collection without marking the nodes as unlinked.
134 #[inline]
force_unlink(&self)135 pub unsafe fn force_unlink(&self) {
136 self.parent_color.set(UNLINKED_MARKER);
137 }
138 }
139
140 impl DefaultLinkOps for Link {
141 type Ops = LinkOps;
142
143 const NEW: Self::Ops = LinkOps;
144 }
145
146 // An object containing a link can be sent to another thread if it is unlinked.
147 unsafe impl Send for Link {}
148
149 // Provide an implementation of Clone which simply initializes the new link as
150 // unlinked. This allows structs containing a link to derive Clone.
151 impl Clone for Link {
152 #[inline]
clone(&self) -> Link153 fn clone(&self) -> Link {
154 Link::new()
155 }
156 }
157
158 // Same as above
159 impl Default for Link {
160 #[inline]
default() -> Link161 fn default() -> Link {
162 Link::new()
163 }
164 }
165
166 // Provide an implementation of Debug so that structs containing a link can
167 // still derive Debug.
168 impl fmt::Debug for Link {
169 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result170 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
171 // There isn't anything sensible to print here except whether the link
172 // is currently in a tree.
173 if self.is_linked() {
174 write!(f, "linked")
175 } else {
176 write!(f, "unlinked")
177 }
178 }
179 }
180
181 // =============================================================================
182 // LinkOps
183 // =============================================================================
184
185 /// Default `LinkOps` implementation for `RBTree`.
186 #[derive(Clone, Copy, Default)]
187 pub struct LinkOps;
188
189 impl LinkOps {
190 #[inline]
set_parent_color( self, ptr: <Self as link_ops::LinkOps>::LinkPtr, parent: Option<<Self as link_ops::LinkOps>::LinkPtr>, color: Color, )191 unsafe fn set_parent_color(
192 self,
193 ptr: <Self as link_ops::LinkOps>::LinkPtr,
194 parent: Option<<Self as link_ops::LinkOps>::LinkPtr>,
195 color: Color,
196 ) {
197 assert!(mem::align_of::<Link>() >= 2);
198 let bit = match color {
199 Color::Red => 0,
200 Color::Black => 1,
201 };
202 let parent_usize = parent.map(|x| x.as_ptr() as usize).unwrap_or(0);
203 ptr.as_ref().parent_color.set((parent_usize & !1) | bit);
204 }
205 }
206
207 unsafe impl link_ops::LinkOps for LinkOps {
208 type LinkPtr = NonNull<Link>;
209
210 #[inline]
acquire_link(&mut self, ptr: Self::LinkPtr) -> bool211 unsafe fn acquire_link(&mut self, ptr: Self::LinkPtr) -> bool {
212 if ptr.as_ref().is_linked() {
213 false
214 } else {
215 self.set_parent_color(ptr, None, Color::Black);
216 true
217 }
218 }
219
220 #[inline]
release_link(&mut self, ptr: Self::LinkPtr)221 unsafe fn release_link(&mut self, ptr: Self::LinkPtr) {
222 ptr.as_ref().parent_color.set(UNLINKED_MARKER);
223 }
224 }
225
226 unsafe impl RBTreeOps for LinkOps {
227 #[inline]
left(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>228 unsafe fn left(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
229 ptr.as_ref().left.get()
230 }
231
232 #[inline]
right(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>233 unsafe fn right(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
234 ptr.as_ref().right.get()
235 }
236
237 #[inline]
parent(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>238 unsafe fn parent(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
239 let parent_usize = ptr.as_ref().parent_color.get() & !1;
240 NonNull::new(parent_usize as *mut Link)
241 }
242
243 #[inline]
color(&self, ptr: Self::LinkPtr) -> Color244 unsafe fn color(&self, ptr: Self::LinkPtr) -> Color {
245 if ptr.as_ref().parent_color.get() & 1 == 1 {
246 Color::Black
247 } else {
248 Color::Red
249 }
250 }
251
252 #[inline]
set_left(&mut self, ptr: Self::LinkPtr, left: Option<Self::LinkPtr>)253 unsafe fn set_left(&mut self, ptr: Self::LinkPtr, left: Option<Self::LinkPtr>) {
254 ptr.as_ref().left.set(left);
255 }
256
257 #[inline]
set_right(&mut self, ptr: Self::LinkPtr, right: Option<Self::LinkPtr>)258 unsafe fn set_right(&mut self, ptr: Self::LinkPtr, right: Option<Self::LinkPtr>) {
259 ptr.as_ref().right.set(right);
260 }
261
262 #[inline]
set_parent(&mut self, ptr: Self::LinkPtr, parent: Option<Self::LinkPtr>)263 unsafe fn set_parent(&mut self, ptr: Self::LinkPtr, parent: Option<Self::LinkPtr>) {
264 self.set_parent_color(ptr, parent, self.color(ptr));
265 }
266
267 #[inline]
set_color(&mut self, ptr: Self::LinkPtr, color: Color)268 unsafe fn set_color(&mut self, ptr: Self::LinkPtr, color: Color) {
269 self.set_parent_color(ptr, self.parent(ptr), color);
270 }
271 }
272
273 unsafe impl SinglyLinkedListOps for LinkOps {
274 #[inline]
next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>275 unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
276 self.right(ptr)
277 }
278
279 #[inline]
set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>)280 unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
281 self.set_right(ptr, next);
282 }
283 }
284
285 unsafe impl LinkedListOps for LinkOps {
286 #[inline]
next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>287 unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
288 self.right(ptr)
289 }
290
291 #[inline]
prev(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>292 unsafe fn prev(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
293 self.left(ptr)
294 }
295
296 #[inline]
set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>)297 unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
298 self.set_right(ptr, next);
299 }
300
301 #[inline]
set_prev(&mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>)302 unsafe fn set_prev(&mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>) {
303 self.set_left(ptr, prev);
304 }
305 }
306
307 unsafe impl XorLinkedListOps for LinkOps {
308 #[inline]
next( &self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>, ) -> Option<Self::LinkPtr>309 unsafe fn next(
310 &self,
311 ptr: Self::LinkPtr,
312 prev: Option<Self::LinkPtr>,
313 ) -> Option<Self::LinkPtr> {
314 let packed = self.right(ptr).map(|x| x.as_ptr() as usize).unwrap_or(0);
315 let raw = packed ^ prev.map(|x| x.as_ptr() as usize).unwrap_or(0);
316 NonNull::new(raw as *mut _)
317 }
318
319 #[inline]
prev( &self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>, ) -> Option<Self::LinkPtr>320 unsafe fn prev(
321 &self,
322 ptr: Self::LinkPtr,
323 next: Option<Self::LinkPtr>,
324 ) -> Option<Self::LinkPtr> {
325 let packed = self.right(ptr).map(|x| x.as_ptr() as usize).unwrap_or(0);
326 let raw = packed ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
327 NonNull::new(raw as *mut _)
328 }
329
330 #[inline]
set( &mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>, next: Option<Self::LinkPtr>, )331 unsafe fn set(
332 &mut self,
333 ptr: Self::LinkPtr,
334 prev: Option<Self::LinkPtr>,
335 next: Option<Self::LinkPtr>,
336 ) {
337 let new_packed = prev.map(|x| x.as_ptr() as usize).unwrap_or(0)
338 ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
339
340 let new_next = NonNull::new(new_packed as *mut _);
341 self.set_right(ptr, new_next);
342 }
343
344 #[inline]
replace_next_or_prev( &mut self, ptr: Self::LinkPtr, old: Option<Self::LinkPtr>, new: Option<Self::LinkPtr>, )345 unsafe fn replace_next_or_prev(
346 &mut self,
347 ptr: Self::LinkPtr,
348 old: Option<Self::LinkPtr>,
349 new: Option<Self::LinkPtr>,
350 ) {
351 let packed = self.right(ptr).map(|x| x.as_ptr() as usize).unwrap_or(0);
352 let new_packed = packed
353 ^ old.map(|x| x.as_ptr() as usize).unwrap_or(0)
354 ^ new.map(|x| x.as_ptr() as usize).unwrap_or(0);
355
356 let new_next = NonNull::new(new_packed as *mut _);
357 self.set_right(ptr, new_next);
358 }
359 }
360
361 #[inline]
is_left_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr, parent: T::LinkPtr) -> bool362 unsafe fn is_left_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr, parent: T::LinkPtr) -> bool {
363 link_ops.left(parent) == Some(ptr)
364 }
365
366 #[inline]
first_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> T::LinkPtr367 unsafe fn first_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> T::LinkPtr {
368 let mut x = ptr;
369 while let Some(y) = link_ops.left(x) {
370 x = y;
371 }
372 x
373 }
374
375 #[inline]
last_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> T::LinkPtr376 unsafe fn last_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> T::LinkPtr {
377 let mut x = ptr;
378 while let Some(y) = link_ops.right(x) {
379 x = y;
380 }
381 x
382 }
383
384 #[inline]
next<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> Option<T::LinkPtr>385 unsafe fn next<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> Option<T::LinkPtr> {
386 if let Some(right) = link_ops.right(ptr) {
387 Some(first_child(link_ops, right))
388 } else {
389 let mut x = ptr;
390 loop {
391 if let Some(parent) = link_ops.parent(x) {
392 if is_left_child(link_ops, x, parent) {
393 return Some(parent);
394 }
395
396 x = parent;
397 } else {
398 return None;
399 }
400 }
401 }
402 }
403
404 #[inline]
prev<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> Option<T::LinkPtr>405 unsafe fn prev<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> Option<T::LinkPtr> {
406 if let Some(left) = link_ops.left(ptr) {
407 Some(last_child(link_ops, left))
408 } else {
409 let mut x = ptr;
410 loop {
411 if let Some(parent) = link_ops.parent(x) {
412 if !is_left_child(link_ops, x, parent) {
413 return Some(parent);
414 }
415
416 x = parent;
417 } else {
418 return None;
419 }
420 }
421 }
422 }
423
424 #[inline]
replace_with<T: RBTreeOps>( link_ops: &mut T, ptr: T::LinkPtr, new: T::LinkPtr, root: &mut Option<T::LinkPtr>, )425 unsafe fn replace_with<T: RBTreeOps>(
426 link_ops: &mut T,
427 ptr: T::LinkPtr,
428 new: T::LinkPtr,
429 root: &mut Option<T::LinkPtr>,
430 ) {
431 if let Some(parent) = link_ops.parent(ptr) {
432 if is_left_child(link_ops, ptr, parent) {
433 link_ops.set_left(parent, Some(new));
434 } else {
435 link_ops.set_right(parent, Some(new));
436 }
437 } else {
438 *root = Some(new);
439 }
440 if let Some(left) = link_ops.left(ptr) {
441 link_ops.set_parent(left, Some(new));
442 }
443 if let Some(right) = link_ops.right(ptr) {
444 link_ops.set_parent(right, Some(new));
445 }
446 link_ops.set_left(new, link_ops.left(ptr));
447 link_ops.set_right(new, link_ops.right(ptr));
448 link_ops.set_parent(new, link_ops.parent(ptr));
449 link_ops.set_color(new, link_ops.color(ptr));
450 link_ops.release_link(ptr);
451 }
452
453 #[inline]
insert_left<T: RBTreeOps>( link_ops: &mut T, ptr: T::LinkPtr, new: T::LinkPtr, root: &mut Option<T::LinkPtr>, )454 unsafe fn insert_left<T: RBTreeOps>(
455 link_ops: &mut T,
456 ptr: T::LinkPtr,
457 new: T::LinkPtr,
458 root: &mut Option<T::LinkPtr>,
459 ) {
460 link_ops.set_parent(new, Some(ptr));
461 link_ops.set_color(new, Color::Red);
462 link_ops.set_left(new, None);
463 link_ops.set_right(new, None);
464 link_ops.set_left(ptr, Some(new));
465 post_insert(link_ops, new, root);
466 }
467
468 #[inline]
insert_right<T: RBTreeOps>( link_ops: &mut T, ptr: T::LinkPtr, new: T::LinkPtr, root: &mut Option<T::LinkPtr>, )469 unsafe fn insert_right<T: RBTreeOps>(
470 link_ops: &mut T,
471 ptr: T::LinkPtr,
472 new: T::LinkPtr,
473 root: &mut Option<T::LinkPtr>,
474 ) {
475 link_ops.set_parent(new, Some(ptr));
476 link_ops.set_color(new, Color::Red);
477 link_ops.set_left(new, None);
478 link_ops.set_right(new, None);
479 link_ops.set_right(ptr, Some(new));
480 post_insert(link_ops, new, root);
481 }
482
rotate_left<T: RBTreeOps>( link_ops: &mut T, ptr: T::LinkPtr, root: &mut Option<T::LinkPtr>, )483 unsafe fn rotate_left<T: RBTreeOps>(
484 link_ops: &mut T,
485 ptr: T::LinkPtr,
486 root: &mut Option<T::LinkPtr>,
487 ) {
488 let y = link_ops.right(ptr).unwrap_unchecked();
489 link_ops.set_right(ptr, link_ops.left(y));
490 if let Some(right) = link_ops.right(ptr) {
491 link_ops.set_parent(right, Some(ptr));
492 }
493 link_ops.set_parent(y, link_ops.parent(ptr));
494 if let Some(parent) = link_ops.parent(ptr) {
495 if is_left_child(link_ops, ptr, parent) {
496 link_ops.set_left(parent, Some(y));
497 } else {
498 link_ops.set_right(parent, Some(y));
499 }
500 } else {
501 *root = Some(y);
502 }
503 link_ops.set_left(y, Some(ptr));
504 link_ops.set_parent(ptr, Some(y));
505 }
506
rotate_right<T: RBTreeOps>( link_ops: &mut T, ptr: T::LinkPtr, root: &mut Option<T::LinkPtr>, )507 unsafe fn rotate_right<T: RBTreeOps>(
508 link_ops: &mut T,
509 ptr: T::LinkPtr,
510 root: &mut Option<T::LinkPtr>,
511 ) {
512 let y = link_ops.left(ptr).unwrap_unchecked();
513 link_ops.set_left(ptr, link_ops.right(y));
514 if let Some(left) = link_ops.left(ptr) {
515 link_ops.set_parent(left, Some(ptr));
516 }
517 link_ops.set_parent(y, link_ops.parent(ptr));
518 if let Some(parent) = link_ops.parent(ptr) {
519 if is_left_child(link_ops, ptr, parent) {
520 link_ops.set_left(parent, Some(y));
521 } else {
522 link_ops.set_right(parent, Some(y));
523 }
524 } else {
525 *root = Some(y);
526 }
527 link_ops.set_right(y, Some(ptr));
528 link_ops.set_parent(ptr, Some(y));
529 }
530
531 // This code is based on the red-black tree implementation in libc++
post_insert<T: RBTreeOps>( link_ops: &mut T, ptr: T::LinkPtr, root: &mut Option<T::LinkPtr>, )532 unsafe fn post_insert<T: RBTreeOps>(
533 link_ops: &mut T,
534 ptr: T::LinkPtr,
535 root: &mut Option<T::LinkPtr>,
536 ) {
537 let mut x = ptr;
538 while let Some(parent) = link_ops.parent(x) {
539 if link_ops.color(parent) != Color::Red {
540 break;
541 }
542 // SAFETY: The root of the tree must be black, and `parent` cannot be the root if it is red.
543 let grandparent = link_ops.parent(parent).unwrap_unchecked();
544
545 if is_left_child(link_ops, parent, grandparent) {
546 let y = link_ops.right(grandparent);
547 if let Some(y) = y {
548 if link_ops.color(y) == Color::Red {
549 x = parent;
550 link_ops.set_color(x, Color::Black);
551 x = grandparent;
552
553 if link_ops.parent(x).is_none() {
554 link_ops.set_color(x, Color::Black);
555 } else {
556 link_ops.set_color(x, Color::Red);
557 }
558 link_ops.set_color(y, Color::Black);
559 continue;
560 }
561 }
562 if !is_left_child(link_ops, x, parent) {
563 x = parent;
564 rotate_left(link_ops, x, root);
565 }
566 x = link_ops.parent(x).unwrap_unchecked();
567 link_ops.set_color(x, Color::Black);
568 x = link_ops.parent(x).unwrap_unchecked();
569 link_ops.set_color(x, Color::Red);
570 rotate_right(link_ops, x, root);
571 break;
572 } else {
573 let y = link_ops.left(grandparent);
574 if let Some(y) = y {
575 if link_ops.color(y) == Color::Red {
576 x = parent;
577 link_ops.set_color(x, Color::Black);
578 x = grandparent;
579 if link_ops.parent(x).is_none() {
580 link_ops.set_color(x, Color::Black);
581 } else {
582 link_ops.set_color(x, Color::Red);
583 }
584 link_ops.set_color(y, Color::Black);
585 continue;
586 }
587 }
588 if is_left_child(link_ops, x, parent) {
589 x = parent;
590 rotate_right(link_ops, x, root);
591 }
592 x = link_ops.parent(x).unwrap_unchecked();
593 link_ops.set_color(x, Color::Black);
594 x = link_ops.parent(x).unwrap_unchecked();
595 link_ops.set_color(x, Color::Red);
596 rotate_left(link_ops, x, root);
597 break;
598 }
599 }
600 }
601
602 // This code is based on the red-black tree implementation in libc++
remove<T: RBTreeOps>(link_ops: &mut T, ptr: T::LinkPtr, root: &mut Option<T::LinkPtr>)603 unsafe fn remove<T: RBTreeOps>(link_ops: &mut T, ptr: T::LinkPtr, root: &mut Option<T::LinkPtr>) {
604 let y = if link_ops.left(ptr).is_none() || link_ops.right(ptr).is_none() {
605 ptr
606 } else {
607 next(link_ops, ptr).unwrap_unchecked()
608 };
609 let x = if link_ops.left(y).is_some() {
610 link_ops.left(y)
611 } else {
612 link_ops.right(y)
613 };
614 let mut w = None;
615 if let Some(x) = x {
616 link_ops.set_parent(x, link_ops.parent(y));
617 }
618 if let Some(y_parent) = link_ops.parent(y) {
619 if is_left_child(link_ops, y, y_parent) {
620 link_ops.set_left(y_parent, x);
621 w = link_ops.right(y_parent);
622 } else {
623 link_ops.set_right(y_parent, x);
624 w = link_ops.left(y_parent);
625 }
626 } else {
627 *root = x;
628 }
629 let removed_black = link_ops.color(y) == Color::Black;
630 if y != ptr {
631 if let Some(parent) = link_ops.parent(ptr) {
632 link_ops.set_parent(y, Some(parent));
633 if is_left_child(link_ops, ptr, parent) {
634 link_ops.set_left(parent, Some(y));
635 } else {
636 link_ops.set_right(parent, Some(y));
637 }
638 } else {
639 link_ops.set_parent(y, None);
640 *root = Some(y);
641 }
642 link_ops.set_left(y, link_ops.left(ptr));
643 link_ops.set_parent(link_ops.left(y).unwrap_unchecked(), Some(y));
644 link_ops.set_right(y, link_ops.right(ptr));
645 if let Some(y_right) = link_ops.right(y) {
646 link_ops.set_parent(y_right, Some(y));
647 }
648 link_ops.set_color(y, link_ops.color(ptr));
649 }
650 if removed_black && !root.is_none() {
651 if let Some(x) = x {
652 link_ops.set_color(x, Color::Black);
653 } else {
654 let mut w = w.unwrap_unchecked();
655 loop {
656 let mut w_parent = link_ops.parent(w).unwrap_unchecked();
657 if !is_left_child(link_ops, w, w_parent) {
658 if link_ops.color(w) == Color::Red {
659 link_ops.set_color(w, Color::Black);
660 link_ops.set_color(w_parent, Color::Red);
661 rotate_left(link_ops, w_parent, root);
662 w = link_ops
663 .right(link_ops.left(w).unwrap_unchecked())
664 .unwrap_unchecked();
665 w_parent = link_ops.parent(w).unwrap_unchecked();
666 }
667
668 let left_color = link_ops.left(w).map(|x| link_ops.color(x));
669 let right_color = link_ops.right(w).map(|x| link_ops.color(x));
670 if (left_color != Some(Color::Red)) && (right_color != Some(Color::Red)) {
671 link_ops.set_color(w, Color::Red);
672 if link_ops.parent(w_parent).is_none()
673 || link_ops.color(w_parent) == Color::Red
674 {
675 link_ops.set_color(w_parent, Color::Black);
676 break;
677 }
678 let w_grandparent = link_ops.parent(w_parent).unwrap_unchecked();
679 w = if is_left_child(link_ops, w_parent, w_grandparent) {
680 link_ops.right(w_grandparent).unwrap_unchecked()
681 } else {
682 link_ops.left(w_grandparent).unwrap_unchecked()
683 };
684 } else {
685 if link_ops.right(w).map(|x| link_ops.color(x)) != Some(Color::Red) {
686 link_ops.set_color(link_ops.left(w).unwrap_unchecked(), Color::Black);
687 link_ops.set_color(w, Color::Red);
688 rotate_right(link_ops, w, root);
689 w = link_ops.parent(w).unwrap_unchecked();
690 w_parent = link_ops.parent(w).unwrap_unchecked();
691 }
692 link_ops.set_color(w, link_ops.color(w_parent));
693 link_ops.set_color(w_parent, Color::Black);
694 link_ops.set_color(link_ops.right(w).unwrap_unchecked(), Color::Black);
695 rotate_left(link_ops, w_parent, root);
696 break;
697 }
698 } else {
699 if link_ops.color(w) == Color::Red {
700 link_ops.set_color(w, Color::Black);
701 link_ops.set_color(w_parent, Color::Red);
702 rotate_right(link_ops, w_parent, root);
703 w = link_ops
704 .left(link_ops.right(w).unwrap_unchecked())
705 .unwrap_unchecked();
706 w_parent = link_ops.parent(w).unwrap_unchecked();
707 }
708 let left_color = link_ops.left(w).map(|x| link_ops.color(x));
709 let right_color = link_ops.right(w).map(|x| link_ops.color(x));
710 if (left_color != Some(Color::Red)) && (right_color != Some(Color::Red)) {
711 link_ops.set_color(w, Color::Red);
712 if link_ops.parent(w_parent).is_none()
713 || link_ops.color(w_parent) == Color::Red
714 {
715 link_ops.set_color(w_parent, Color::Black);
716 break;
717 }
718 w = if is_left_child(
719 link_ops,
720 w_parent,
721 link_ops.parent(w_parent).unwrap_unchecked(),
722 ) {
723 link_ops
724 .right(link_ops.parent(w_parent).unwrap_unchecked())
725 .unwrap_unchecked()
726 } else {
727 link_ops
728 .left(link_ops.parent(w_parent).unwrap_unchecked())
729 .unwrap_unchecked()
730 };
731 } else {
732 if link_ops.left(w).map(|x| link_ops.color(x)) != Some(Color::Red) {
733 link_ops.set_color(link_ops.right(w).unwrap_unchecked(), Color::Black);
734 link_ops.set_color(w, Color::Red);
735 rotate_left(link_ops, w, root);
736 w = link_ops.parent(w).unwrap_unchecked();
737 w_parent = link_ops.parent(w).unwrap_unchecked();
738 }
739 link_ops.set_color(w, link_ops.color(w_parent));
740 link_ops.set_color(w_parent, Color::Black);
741 link_ops.set_color(link_ops.left(w).unwrap_unchecked(), Color::Black);
742 rotate_right(link_ops, w_parent, root);
743 break;
744 }
745 }
746 }
747 }
748 }
749 link_ops.release_link(ptr);
750 }
751
752 // =============================================================================
753 // Cursor, CursorMut
754 // =============================================================================
755
756 /// A cursor which provides read-only access to a `RBTree`.
757 pub struct Cursor<'a, A: Adapter>
758 where
759 A::LinkOps: RBTreeOps,
760 {
761 current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
762 tree: &'a RBTree<A>,
763 }
764
765 impl<'a, A: Adapter> Clone for Cursor<'a, A>
766 where
767 A::LinkOps: RBTreeOps,
768 {
769 #[inline]
770 fn clone(&self) -> Cursor<'a, A> {
771 Cursor {
772 current: self.current,
773 tree: self.tree,
774 }
775 }
776 }
777
778 impl<'a, A: Adapter> Cursor<'a, A>
779 where
780 A::LinkOps: RBTreeOps,
781 {
782 /// Checks if the cursor is currently pointing to the null object.
783 #[inline]
784 pub fn is_null(&self) -> bool {
785 self.current.is_none()
786 }
787
788 /// Returns a reference to the object that the cursor is currently
789 /// pointing to.
790 ///
791 /// This returns `None` if the cursor is currently pointing to the null
792 /// object.
793 #[inline]
794 pub fn get(&self) -> Option<&'a <A::PointerOps as PointerOps>::Value> {
795 Some(unsafe { &*self.tree.adapter.get_value(self.current?) })
796 }
797
798 /// Clones and returns the pointer that points to the element that the
799 /// cursor is referencing.
800 ///
801 /// This returns `None` if the cursor is currently pointing to the null
802 /// object.
803 #[inline]
804 pub fn clone_pointer(&self) -> Option<<A::PointerOps as PointerOps>::Pointer>
805 where
806 <A::PointerOps as PointerOps>::Pointer: Clone,
807 {
808 let raw_pointer = self.get()? as *const <A::PointerOps as PointerOps>::Value;
809 Some(unsafe {
810 crate::pointer_ops::clone_pointer_from_raw(self.tree.adapter.pointer_ops(), raw_pointer)
811 })
812 }
813
814 /// Moves the cursor to the next element of the `RBTree`.
815 ///
816 /// If the cursor is pointer to the null object then this will move it to
817 /// the first element of the `RBTree`. If it is pointing to the last
818 /// element of the `RBTree` then this will move it to the null object.
819 #[inline]
820 pub fn move_next(&mut self) {
821 if let Some(current) = self.current {
822 self.current = unsafe { next(self.tree.adapter.link_ops(), current) };
823 } else if let Some(root) = self.tree.root {
824 self.current = Some(unsafe { first_child(self.tree.adapter.link_ops(), root) });
825 } else {
826 self.current = None;
827 }
828 }
829
830 /// Moves the cursor to the previous element of the `RBTree`.
831 ///
832 /// If the cursor is pointer to the null object then this will move it to
833 /// the last element of the `RBTree`. If it is pointing to the first
834 /// element of the `RBTree` then this will move it to the null object.
835 #[inline]
836 pub fn move_prev(&mut self) {
837 if let Some(current) = self.current {
838 self.current = unsafe { prev(self.tree.adapter.link_ops(), current) };
839 } else if let Some(root) = self.tree.root {
840 self.current = Some(unsafe { last_child(self.tree.adapter.link_ops(), root) });
841 } else {
842 self.current = None;
843 }
844 }
845
846 /// Returns a cursor pointing to the next element of the `RBTree`.
847 ///
848 /// If the cursor is pointer to the null object then this will return the
849 /// first element of the `RBTree`. If it is pointing to the last
850 /// element of the `RBTree` then this will return a null cursor.
851 #[inline]
852 pub fn peek_next(&self) -> Cursor<'_, A> {
853 let mut next = self.clone();
854 next.move_next();
855 next
856 }
857
858 /// Returns a cursor pointing to the previous element of the `RBTree`.
859 ///
860 /// If the cursor is pointer to the null object then this will return the
861 /// last element of the `RBTree`. If it is pointing to the first
862 /// element of the `RBTree` then this will return a null cursor.
863 #[inline]
864 pub fn peek_prev(&self) -> Cursor<'_, A> {
865 let mut prev = self.clone();
866 prev.move_prev();
867 prev
868 }
869 }
870
871 /// A cursor which provides mutable access to a `RBTree`.
872 pub struct CursorMut<'a, A: Adapter>
873 where
874 A::LinkOps: RBTreeOps,
875 {
876 current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
877 tree: &'a mut RBTree<A>,
878 }
879
880 impl<'a, A: Adapter> CursorMut<'a, A>
881 where
882 A::LinkOps: RBTreeOps,
883 {
884 /// Checks if the cursor is currently pointing to the null object.
885 #[inline]
886 pub fn is_null(&self) -> bool {
887 self.current.is_none()
888 }
889
890 /// Returns a reference to the object that the cursor is currently
891 /// pointing to.
892 ///
893 /// This returns None if the cursor is currently pointing to the null
894 /// object.
895 #[inline]
896 pub fn get(&self) -> Option<&<A::PointerOps as PointerOps>::Value> {
897 Some(unsafe { &*self.tree.adapter.get_value(self.current?) })
898 }
899
900 /// Returns a read-only cursor pointing to the current element.
901 ///
902 /// The lifetime of the returned `Cursor` is bound to that of the
903 /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
904 /// `CursorMut` is frozen for the lifetime of the `Cursor`.
905 #[inline]
906 pub fn as_cursor(&self) -> Cursor<'_, A> {
907 Cursor {
908 current: self.current,
909 tree: self.tree,
910 }
911 }
912
913 /// Moves the cursor to the next element of the `RBTree`.
914 ///
915 /// If the cursor is pointer to the null object then this will move it to
916 /// the first element of the `RBTree`. If it is pointing to the last
917 /// element of the `RBTree` then this will move it to the null object.
918 #[inline]
919 pub fn move_next(&mut self) {
920 if let Some(current) = self.current {
921 self.current = unsafe { next(self.tree.adapter.link_ops(), current) };
922 } else if let Some(root) = self.tree.root {
923 self.current = Some(unsafe { first_child(self.tree.adapter.link_ops(), root) });
924 } else {
925 self.current = None;
926 }
927 }
928
929 /// Moves the cursor to the previous element of the `RBTree`.
930 ///
931 /// If the cursor is pointer to the null object then this will move it to
932 /// the last element of the `RBTree`. If it is pointing to the first
933 /// element of the `RBTree` then this will move it to the null object.
934 #[inline]
935 pub fn move_prev(&mut self) {
936 if let Some(current) = self.current {
937 self.current = unsafe { prev(self.tree.adapter.link_ops(), current) };
938 } else if let Some(root) = self.tree.root {
939 self.current = Some(unsafe { last_child(self.tree.adapter.link_ops(), root) });
940 } else {
941 self.current = None;
942 }
943 }
944
945 /// Returns a cursor pointing to the next element of the `RBTree`.
946 ///
947 /// If the cursor is pointer to the null object then this will return the
948 /// first element of the `RBTree`. If it is pointing to the last
949 /// element of the `RBTree` then this will return a null cursor.
950 #[inline]
951 pub fn peek_next(&self) -> Cursor<'_, A> {
952 let mut next = self.as_cursor();
953 next.move_next();
954 next
955 }
956
957 /// Returns a cursor pointing to the previous element of the `RBTree`.
958 ///
959 /// If the cursor is pointer to the null object then this will return the
960 /// last element of the `RBTree`. If it is pointing to the first
961 /// element of the `RBTree` then this will return a null cursor.
962 #[inline]
963 pub fn peek_prev(&self) -> Cursor<'_, A> {
964 let mut prev = self.as_cursor();
965 prev.move_prev();
966 prev
967 }
968
969 /// Removes the current element from the `RBTree`.
970 ///
971 /// A pointer to the element that was removed is returned, and the cursor is
972 /// moved to point to the next element in the `RBTree`.
973 ///
974 /// If the cursor is currently pointing to the null object then no element
975 /// is removed and `None` is returned.
976 #[inline]
977 pub fn remove(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer> {
978 unsafe {
979 if let Some(current) = self.current {
980 let next = next(self.tree.adapter.link_ops(), current);
981 let result = current;
982 remove(
983 self.tree.adapter.link_ops_mut(),
984 current,
985 &mut self.tree.root,
986 );
987 self.current = next;
988 Some(
989 self.tree
990 .adapter
991 .pointer_ops()
992 .from_raw(self.tree.adapter.get_value(result)),
993 )
994 } else {
995 None
996 }
997 }
998 }
999
1000 /// Removes the current element from the `RBTree` and inserts another
1001 /// object in its place.
1002 ///
1003 /// A pointer to the element that was removed is returned, and the cursor is
1004 /// modified to point to the newly added element.
1005 ///
1006 /// When using this function you must ensure that the elements in the
1007 /// collection are maintained in increasing order. Failure to do this may
1008 /// lead to `find`, `upper_bound`, `lower_bound` and `range` returning
1009 /// incorrect results.
1010 ///
1011 /// If the cursor is currently pointing to the null object then an error is
1012 /// returned containing the given `val` parameter.
1013 ///
1014 /// # Panics
1015 ///
1016 /// Panics if the new element is already linked to a different intrusive
1017 /// collection.
1018 #[inline]
1019 pub fn replace_with(
1020 &mut self,
1021 val: <A::PointerOps as PointerOps>::Pointer,
1022 ) -> Result<<A::PointerOps as PointerOps>::Pointer, <A::PointerOps as PointerOps>::Pointer>
1023 {
1024 unsafe {
1025 if let Some(current) = self.current {
1026 let new = self.tree.node_from_value(val);
1027 let result = current;
1028 replace_with(
1029 self.tree.adapter.link_ops_mut(),
1030 current,
1031 new,
1032 &mut self.tree.root,
1033 );
1034 self.current = Some(new);
1035 Ok(self
1036 .tree
1037 .adapter
1038 .pointer_ops()
1039 .from_raw(self.tree.adapter.get_value(result)))
1040 } else {
1041 Err(val)
1042 }
1043 }
1044 }
1045
1046 /// Inserts a new element into the `RBTree` after the current one.
1047 ///
1048 /// When using this function you must ensure that the elements in the
1049 /// collection are maintained in increasing order. Failure to do this may
1050 /// lead to `find`, `upper_bound`, `lower_bound` and `range` returning
1051 /// incorrect results.
1052 ///
1053 /// If the cursor is pointing at the null object then the new element is
1054 /// inserted at the start of the `RBTree`.
1055 ///
1056 /// # Panics
1057 ///
1058 /// Panics if the new element is already linked to a different intrusive
1059 /// collection.
1060 #[inline]
1061 pub fn insert_after(&mut self, val: <A::PointerOps as PointerOps>::Pointer) {
1062 unsafe {
1063 let new = self.tree.node_from_value(val);
1064 let link_ops = self.tree.adapter.link_ops_mut();
1065
1066 if let Some(root) = self.tree.root {
1067 if let Some(current) = self.current {
1068 if link_ops.right(current).is_some() {
1069 let next = next(link_ops, current).unwrap_unchecked();
1070 insert_left(link_ops, next, new, &mut self.tree.root);
1071 } else {
1072 insert_right(link_ops, current, new, &mut self.tree.root);
1073 }
1074 } else {
1075 insert_left(
1076 link_ops,
1077 first_child(link_ops, root),
1078 new,
1079 &mut self.tree.root,
1080 );
1081 }
1082 } else {
1083 self.tree.insert_root(new);
1084 }
1085 }
1086 }
1087
1088 /// Inserts a new element into the `RBTree` before the current one.
1089 ///
1090 /// When using this function you must ensure that the elements in the
1091 /// collection are maintained in increasing order. Failure to do this may
1092 /// lead to `find`, `upper_bound`, `lower_bound` and `range` returning
1093 /// incorrect results.
1094 ///
1095 /// If the cursor is pointing at the null object then the new element is
1096 /// inserted at the end of the `RBTree`.
1097 ///
1098 /// # Panics
1099 ///
1100 /// Panics if the new element is already linked to a different intrusive
1101 /// collection.
1102 #[inline]
1103 pub fn insert_before(&mut self, val: <A::PointerOps as PointerOps>::Pointer) {
1104 unsafe {
1105 let new = self.tree.node_from_value(val);
1106 let link_ops = self.tree.adapter.link_ops_mut();
1107
1108 if let Some(root) = self.tree.root {
1109 if let Some(current) = self.current {
1110 if link_ops.left(current).is_some() {
1111 let prev = prev(link_ops, current).unwrap_unchecked();
1112 insert_right(link_ops, prev, new, &mut self.tree.root);
1113 } else {
1114 insert_left(link_ops, current, new, &mut self.tree.root);
1115 }
1116 } else {
1117 insert_right(
1118 link_ops,
1119 last_child(link_ops, root),
1120 new,
1121 &mut self.tree.root,
1122 );
1123 }
1124 } else {
1125 self.tree.insert_root(new);
1126 }
1127 }
1128 }
1129 }
1130
1131 impl<'a, A: for<'b> KeyAdapter<'b>> CursorMut<'a, A>
1132 where
1133 <A as Adapter>::LinkOps: RBTreeOps,
1134 {
1135 /// Inserts a new element into the `RBTree`.
1136 ///
1137 /// The new element will be inserted at the correct position in the tree
1138 /// based on its key, regardless of the current cursor position.
1139 ///
1140 /// # Panics
1141 ///
1142 /// Panics if the new element is already linked to a different intrusive
1143 /// collection.
1144 #[inline]
1145 pub fn insert<'c>(&'c mut self, val: <A::PointerOps as PointerOps>::Pointer)
1146 where
1147 <A as KeyAdapter<'c>>::Key: Ord,
1148 {
1149 // We explicitly drop the returned CursorMut here, otherwise we would
1150 // end up with multiple CursorMut in the same collection.
1151 self.tree.insert(val);
1152 }
1153 }
1154
1155 // =============================================================================
1156 // RBTree
1157 // =============================================================================
1158
1159 /// An intrusive red-black tree.
1160 ///
1161 /// When this collection is dropped, all elements linked into it will be
1162 /// converted back to owned pointers and dropped.
1163 ///
1164 /// Note that you are responsible for ensuring that the elements in a `RBTree`
1165 /// remain in ascending key order. This property can be violated, either because
1166 /// the key of an element was modified, or because the
1167 /// `insert_before`/`insert_after` methods of `CursorMut` were incorrectly used.
1168 /// If this situation occurs, memory safety will not be violated but the `find`,
1169 /// `upper_bound`, `lower_bound` and `range` may return incorrect results.
1170 pub struct RBTree<A: Adapter>
1171 where
1172 A::LinkOps: RBTreeOps,
1173 {
1174 root: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1175 adapter: A,
1176 }
1177
1178 impl<A: Adapter> RBTree<A>
1179 where
1180 A::LinkOps: RBTreeOps,
1181 {
1182 #[inline]
1183 fn node_from_value(
1184 &mut self,
1185 val: <A::PointerOps as PointerOps>::Pointer,
1186 ) -> <A::LinkOps as link_ops::LinkOps>::LinkPtr {
1187 use link_ops::LinkOps;
1188
1189 unsafe {
1190 let raw = self.adapter.pointer_ops().into_raw(val);
1191 let link = self.adapter.get_link(raw);
1192
1193 if !self.adapter.link_ops_mut().acquire_link(link) {
1194 // convert the node back into a pointer
1195 self.adapter.pointer_ops().from_raw(raw);
1196
1197 panic!("attempted to insert an object that is already linked");
1198 }
1199
1200 link
1201 }
1202 }
1203
1204 /// Creates an empty `RBTree`.
1205 #[cfg(not(feature = "nightly"))]
1206 #[inline]
1207 pub fn new(adapter: A) -> RBTree<A> {
1208 RBTree {
1209 root: None,
1210 adapter,
1211 }
1212 }
1213
1214 /// Creates an empty `RBTree`.
1215 #[cfg(feature = "nightly")]
1216 #[inline]
1217 pub const fn new(adapter: A) -> RBTree<A> {
1218 RBTree {
1219 root: None,
1220 adapter,
1221 }
1222 }
1223
1224 /// Returns `true` if the `RBTree` is empty.
1225 #[inline]
1226 pub fn is_empty(&self) -> bool {
1227 self.root.is_none()
1228 }
1229
1230 /// Returns a null `Cursor` for this tree.
1231 #[inline]
1232 pub fn cursor(&self) -> Cursor<'_, A> {
1233 Cursor {
1234 current: None,
1235 tree: self,
1236 }
1237 }
1238
1239 /// Returns a null `CursorMut` for this tree.
1240 #[inline]
1241 pub fn cursor_mut(&mut self) -> CursorMut<'_, A> {
1242 CursorMut {
1243 current: None,
1244 tree: self,
1245 }
1246 }
1247
1248 /// Creates a `Cursor` from a pointer to an element.
1249 ///
1250 /// # Safety
1251 ///
1252 /// `ptr` must be a pointer to an object that is part of this tree.
1253 #[inline]
1254 pub unsafe fn cursor_from_ptr(
1255 &self,
1256 ptr: *const <A::PointerOps as PointerOps>::Value,
1257 ) -> Cursor<'_, A> {
1258 Cursor {
1259 current: Some(self.adapter.get_link(ptr)),
1260 tree: self,
1261 }
1262 }
1263
1264 /// Creates a `CursorMut` from a pointer to an element.
1265 ///
1266 /// # Safety
1267 ///
1268 /// `ptr` must be a pointer to an object that is part of this tree.
1269 #[inline]
1270 pub unsafe fn cursor_mut_from_ptr(
1271 &mut self,
1272 ptr: *const <A::PointerOps as PointerOps>::Value,
1273 ) -> CursorMut<'_, A> {
1274 CursorMut {
1275 current: Some(self.adapter.get_link(ptr)),
1276 tree: self,
1277 }
1278 }
1279
1280 /// Returns a `Cursor` pointing to the first element of the tree. If the
1281 /// tree is empty then a null cursor is returned.
1282 #[inline]
1283 pub fn front(&self) -> Cursor<'_, A> {
1284 let mut cursor = self.cursor();
1285 cursor.move_next();
1286 cursor
1287 }
1288
1289 /// Returns a `CursorMut` pointing to the first element of the tree. If the
1290 /// the tree is empty then a null cursor is returned.
1291 #[inline]
1292 pub fn front_mut(&mut self) -> CursorMut<'_, A> {
1293 let mut cursor = self.cursor_mut();
1294 cursor.move_next();
1295 cursor
1296 }
1297
1298 /// Returns a `Cursor` pointing to the last element of the tree. If the tree
1299 /// is empty then a null cursor is returned.
1300 #[inline]
1301 pub fn back(&self) -> Cursor<'_, A> {
1302 let mut cursor = self.cursor();
1303 cursor.move_prev();
1304 cursor
1305 }
1306
1307 /// Returns a `CursorMut` pointing to the last element of the tree. If the
1308 /// tree is empty then a null cursor is returned.
1309 #[inline]
1310 pub fn back_mut(&mut self) -> CursorMut<'_, A> {
1311 let mut cursor = self.cursor_mut();
1312 cursor.move_prev();
1313 cursor
1314 }
1315
1316 #[inline]
1317 unsafe fn insert_root(&mut self, node: <A::LinkOps as link_ops::LinkOps>::LinkPtr) {
1318 self.adapter.link_ops_mut().set_parent(node, None);
1319 self.adapter.link_ops_mut().set_color(node, Color::Black);
1320 self.adapter.link_ops_mut().set_left(node, None);
1321 self.adapter.link_ops_mut().set_right(node, None);
1322 self.root = Some(node);
1323 }
1324
1325 /// Gets an iterator over the objects in the `RBTree`.
1326 #[inline]
1327 pub fn iter(&self) -> Iter<'_, A> {
1328 let link_ops = self.adapter.link_ops();
1329
1330 if let Some(root) = self.root {
1331 Iter {
1332 head: Some(unsafe { first_child(link_ops, root) }),
1333 tail: Some(unsafe { last_child(link_ops, root) }),
1334 tree: self,
1335 }
1336 } else {
1337 Iter {
1338 head: None,
1339 tail: None,
1340 tree: self,
1341 }
1342 }
1343 }
1344
1345 #[inline]
1346 fn clear_recurse(&mut self, current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>) {
1347 use link_ops::LinkOps;
1348 // If adapter.get_value or Pointer::from_raw panic here, it will leak
1349 // the nodes and keep them linked. However this is harmless since there
1350 // is nothing you can do with just a Link.
1351 if let Some(current) = current {
1352 unsafe {
1353 let left = self.adapter.link_ops_mut().left(current);
1354 let right = self.adapter.link_ops_mut().right(current);
1355 self.clear_recurse(left);
1356 self.clear_recurse(right);
1357 self.adapter.link_ops_mut().release_link(current);
1358 self.adapter
1359 .pointer_ops()
1360 .from_raw(self.adapter.get_value(current));
1361 }
1362 }
1363 }
1364
1365 /// Removes all elements from the `RBTree`.
1366 ///
1367 /// This will unlink all object currently in the tree, which requires
1368 /// iterating through all elements in the `RBTree`. Each element is
1369 /// converted back to an owned pointer and then dropped.
1370 #[inline]
1371 pub fn clear(&mut self) {
1372 let root = self.root.take();
1373 self.clear_recurse(root);
1374 }
1375
1376 /// Empties the `RBTree` without unlinking or freeing objects in it.
1377 ///
1378 /// Since this does not unlink any objects, any attempts to link these
1379 /// objects into another `RBTree` will fail but will not cause any
1380 /// memory unsafety. To unlink those objects manually, you must call the
1381 /// `force_unlink` function on them.
1382 #[inline]
1383 pub fn fast_clear(&mut self) {
1384 self.root = None;
1385 }
1386
1387 /// Takes all the elements out of the `RBTree`, leaving it empty. The
1388 /// taken elements are returned as a new `RBTree`.
1389 #[inline]
1390 pub fn take(&mut self) -> RBTree<A>
1391 where
1392 A: Clone,
1393 {
1394 let tree = RBTree {
1395 root: self.root,
1396 adapter: self.adapter.clone(),
1397 };
1398 self.root = None;
1399 tree
1400 }
1401 }
1402
1403 impl<A: for<'a> KeyAdapter<'a>> RBTree<A>
1404 where
1405 <A as Adapter>::LinkOps: RBTreeOps,
1406 {
1407 #[inline]
1408 fn find_internal<'a, Q: ?Sized + Ord>(
1409 &self,
1410 key: &Q,
1411 ) -> Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>
1412 where
1413 <A as KeyAdapter<'a>>::Key: Borrow<Q>,
1414 <A::PointerOps as PointerOps>::Value: 'a,
1415 {
1416 let link_ops = self.adapter.link_ops();
1417
1418 let mut tree = self.root;
1419 while let Some(x) = tree {
1420 let current = unsafe { &*self.adapter.get_value(x) };
1421 match key.cmp(self.adapter.get_key(current).borrow()) {
1422 Ordering::Less => tree = unsafe { link_ops.left(x) },
1423 Ordering::Equal => return tree,
1424 Ordering::Greater => tree = unsafe { link_ops.right(x) },
1425 }
1426 }
1427 None
1428 }
1429
1430 /// Returns a `Cursor` pointing to an element with the given key. If no such
1431 /// element is found then a null cursor is returned.
1432 ///
1433 /// If multiple elements with an identical key are found then an arbitrary
1434 /// one is returned.
1435 #[inline]
1436 pub fn find<'a, Q: ?Sized + Ord>(&'a self, key: &Q) -> Cursor<'a, A>
1437 where
1438 <A as KeyAdapter<'a>>::Key: Borrow<Q>,
1439 {
1440 Cursor {
1441 current: self.find_internal(key),
1442 tree: self,
1443 }
1444 }
1445
1446 /// Returns a `CursorMut` pointing to an element with the given key. If no
1447 /// such element is found then a null cursor is returned.
1448 ///
1449 /// If multiple elements with an identical key are found then an arbitrary
1450 /// one is returned.
1451 #[inline]
1452 pub fn find_mut<'a, Q: ?Sized + Ord>(&'a mut self, key: &Q) -> CursorMut<'a, A>
1453 where
1454 <A as KeyAdapter<'a>>::Key: Borrow<Q>,
1455 {
1456 CursorMut {
1457 current: self.find_internal(key),
1458 tree: self,
1459 }
1460 }
1461
1462 #[inline]
1463 fn lower_bound_internal<'a, Q: ?Sized + Ord>(
1464 &self,
1465 bound: Bound<&Q>,
1466 ) -> Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>
1467 where
1468 <A as KeyAdapter<'a>>::Key: Borrow<Q>,
1469 <A::PointerOps as PointerOps>::Value: 'a,
1470 {
1471 let link_ops = self.adapter.link_ops();
1472
1473 let mut tree = self.root;
1474 let mut result = None;
1475 while let Some(x) = tree {
1476 let current = unsafe { &*self.adapter.get_value(x) };
1477 let cond = match bound {
1478 Unbounded => true,
1479 Included(key) => key <= self.adapter.get_key(current).borrow(),
1480 Excluded(key) => key < self.adapter.get_key(current).borrow(),
1481 };
1482 if cond {
1483 result = tree;
1484 tree = unsafe { link_ops.left(x) };
1485 } else {
1486 tree = unsafe { link_ops.right(x) };
1487 }
1488 }
1489 result
1490 }
1491
1492 /// Returns a `Cursor` pointing to the lowest element whose key is above
1493 /// the given bound. If no such element is found then a null cursor is
1494 /// returned.
1495 #[inline]
1496 pub fn lower_bound<'a, Q: ?Sized + Ord>(&'a self, bound: Bound<&Q>) -> Cursor<'a, A>
1497 where
1498 <A as KeyAdapter<'a>>::Key: Borrow<Q>,
1499 {
1500 Cursor {
1501 current: self.lower_bound_internal(bound),
1502 tree: self,
1503 }
1504 }
1505
1506 /// Returns a `CursorMut` pointing to the first element whose key is
1507 /// above the given bound. If no such element is found then a null
1508 /// cursor is returned.
1509 #[inline]
1510 pub fn lower_bound_mut<'a, Q: ?Sized + Ord>(&'a mut self, bound: Bound<&Q>) -> CursorMut<'a, A>
1511 where
1512 <A as KeyAdapter<'a>>::Key: Borrow<Q>,
1513 {
1514 CursorMut {
1515 current: self.lower_bound_internal(bound),
1516 tree: self,
1517 }
1518 }
1519
1520 #[inline]
1521 fn upper_bound_internal<'a, Q: ?Sized + Ord>(
1522 &self,
1523 bound: Bound<&Q>,
1524 ) -> Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>
1525 where
1526 <A as KeyAdapter<'a>>::Key: Borrow<Q>,
1527 <A::PointerOps as PointerOps>::Value: 'a,
1528 {
1529 let link_ops = self.adapter.link_ops();
1530
1531 let mut tree = self.root;
1532 let mut result = None;
1533 while let Some(x) = tree {
1534 let current = unsafe { &*self.adapter.get_value(x) };
1535 let cond = match bound {
1536 Unbounded => false,
1537 Included(key) => key < self.adapter.get_key(current).borrow(),
1538 Excluded(key) => key <= self.adapter.get_key(current).borrow(),
1539 };
1540 if cond {
1541 tree = unsafe { link_ops.left(x) };
1542 } else {
1543 result = tree;
1544 tree = unsafe { link_ops.right(x) };
1545 }
1546 }
1547 result
1548 }
1549
1550 /// Returns a `Cursor` pointing to the last element whose key is below
1551 /// the given bound. If no such element is found then a null cursor is
1552 /// returned.
1553 #[inline]
1554 pub fn upper_bound<'a, Q: ?Sized + Ord>(&'a self, bound: Bound<&Q>) -> Cursor<'a, A>
1555 where
1556 <A as KeyAdapter<'a>>::Key: Borrow<Q>,
1557 {
1558 Cursor {
1559 current: self.upper_bound_internal(bound),
1560 tree: self,
1561 }
1562 }
1563
1564 /// Returns a `CursorMut` pointing to the last element whose key is
1565 /// below the given bound. If no such element is found then a null
1566 /// cursor is returned.
1567 #[inline]
1568 pub fn upper_bound_mut<'a, Q: ?Sized + Ord>(&'a mut self, bound: Bound<&Q>) -> CursorMut<'a, A>
1569 where
1570 <A as KeyAdapter<'a>>::Key: Borrow<Q>,
1571 {
1572 CursorMut {
1573 current: self.upper_bound_internal(bound),
1574 tree: self,
1575 }
1576 }
1577
1578 /// Inserts a new element into the `RBTree`.
1579 ///
1580 /// The new element will be inserted at the correct position in the tree
1581 /// based on its key.
1582 ///
1583 /// Returns a mutable cursor pointing to the newly added element.
1584 ///
1585 /// # Panics
1586 ///
1587 /// Panics if the new element is already linked to a different intrusive
1588 /// collection.
1589 #[inline]
1590 pub fn insert<'a>(&'a mut self, val: <A::PointerOps as PointerOps>::Pointer) -> CursorMut<'_, A>
1591 where
1592 <A as KeyAdapter<'a>>::Key: Ord,
1593 {
1594 unsafe {
1595 let new = self.node_from_value(val);
1596 let raw = self.adapter.get_value(new);
1597 if let Some(root) = self.root {
1598 let key = self.adapter.get_key(&*raw);
1599 let mut tree = root;
1600 loop {
1601 let current = &*self.adapter.get_value(tree);
1602 if key < self.adapter.get_key(current) {
1603 if let Some(left) = self.adapter.link_ops().left(tree) {
1604 tree = left;
1605 } else {
1606 insert_left(self.adapter.link_ops_mut(), tree, new, &mut self.root);
1607 break;
1608 }
1609 } else {
1610 if let Some(right) = self.adapter.link_ops().right(tree) {
1611 tree = right;
1612 } else {
1613 insert_right(self.adapter.link_ops_mut(), tree, new, &mut self.root);
1614 break;
1615 }
1616 }
1617 }
1618 } else {
1619 self.insert_root(new);
1620 }
1621 CursorMut {
1622 current: Some(new),
1623 tree: self,
1624 }
1625 }
1626 }
1627
1628 /// Returns an `Entry` for the given key which contains a `CursorMut` to an
1629 /// element with the given key or an `InsertCursor` which points to a place
1630 /// in which to insert a new element with the given key.
1631 ///
1632 /// This is more efficient than calling `find` followed by `insert` since
1633 /// the tree does not have to be searched a second time to find a place to
1634 /// insert the new element.
1635 ///
1636 /// If multiple elements with an identical key are found then an arbitrary
1637 /// one is returned.
1638 #[inline]
1639 pub fn entry<'a, Q: ?Sized + Ord>(&'a mut self, key: &Q) -> Entry<'a, A>
1640 where
1641 <A as KeyAdapter<'a>>::Key: Borrow<Q>,
1642 {
1643 unsafe {
1644 if let Some(root) = self.root {
1645 let mut tree = root;
1646 loop {
1647 let current = &*self.adapter.get_value(tree);
1648 match key.cmp(self.adapter.get_key(current).borrow()) {
1649 Ordering::Less => {
1650 if let Some(left) = self.adapter.link_ops().left(tree) {
1651 tree = left;
1652 } else {
1653 return Entry::Vacant(InsertCursor {
1654 parent: Some(tree),
1655 insert_left: true,
1656 tree: self,
1657 });
1658 }
1659 }
1660 Ordering::Equal => {
1661 return Entry::Occupied(CursorMut {
1662 current: Some(tree),
1663 tree: self,
1664 });
1665 }
1666 Ordering::Greater => {
1667 if let Some(right) = self.adapter.link_ops().right(tree) {
1668 tree = right;
1669 } else {
1670 return Entry::Vacant(InsertCursor {
1671 parent: Some(tree),
1672 insert_left: false,
1673 tree: self,
1674 });
1675 }
1676 }
1677 }
1678 }
1679 } else {
1680 Entry::Vacant(InsertCursor {
1681 parent: None,
1682 insert_left: false,
1683 tree: self,
1684 })
1685 }
1686 }
1687 }
1688
1689 /// Constructs a double-ended iterator over a sub-range of elements in the
1690 /// tree, starting at min, and ending at max. If min is `Unbounded`, then it
1691 /// will be treated as "negative infinity", and if max is `Unbounded`, then
1692 /// it will be treated as "positive infinity". Thus
1693 /// `range(Unbounded, Unbounded)` will yield the whole collection.
1694 #[inline]
1695 pub fn range<'a, Min: ?Sized + Ord, Max: ?Sized + Ord>(
1696 &'a self,
1697 min: Bound<&Min>,
1698 max: Bound<&Max>,
1699 ) -> Iter<'a, A>
1700 where
1701 <A as KeyAdapter<'a>>::Key: Borrow<Min> + Borrow<Max>,
1702 <A as KeyAdapter<'a>>::Key: Ord,
1703 {
1704 let lower = self.lower_bound_internal(min);
1705 let upper = self.upper_bound_internal(max);
1706
1707 if let (Some(lower), Some(upper)) = (lower, upper) {
1708 let lower_key = unsafe { self.adapter.get_key(&*self.adapter.get_value(lower)) };
1709 let upper_key = unsafe { self.adapter.get_key(&*self.adapter.get_value(upper)) };
1710 if upper_key >= lower_key {
1711 return Iter {
1712 head: Some(lower),
1713 tail: Some(upper),
1714 tree: self,
1715 };
1716 }
1717 }
1718 Iter {
1719 head: None,
1720 tail: None,
1721 tree: self,
1722 }
1723 }
1724 }
1725
1726 // Allow read-only access to values from multiple threads
1727 unsafe impl<A: Adapter + Sync> Sync for RBTree<A>
1728 where
1729 <A::PointerOps as PointerOps>::Value: Sync,
1730 A::LinkOps: RBTreeOps,
1731 {
1732 }
1733
1734 // Allow sending to another thread if the ownership (represented by the <A::PointerOps as PointerOps>::Pointer owned
1735 // pointer type) can be transferred to another thread.
1736 unsafe impl<A: Adapter + Send> Send for RBTree<A>
1737 where
1738 <A::PointerOps as PointerOps>::Pointer: Send,
1739 A::LinkOps: RBTreeOps,
1740 {
1741 }
1742
1743 // Drop all owned pointers if the collection is dropped
1744 impl<A: Adapter> Drop for RBTree<A>
1745 where
1746 A::LinkOps: RBTreeOps,
1747 {
1748 #[inline]
drop(&mut self)1749 fn drop(&mut self) {
1750 self.clear();
1751 }
1752 }
1753
1754 impl<A: Adapter> IntoIterator for RBTree<A>
1755 where
1756 A::LinkOps: RBTreeOps,
1757 {
1758 type Item = <A::PointerOps as PointerOps>::Pointer;
1759 type IntoIter = IntoIter<A>;
1760
1761 #[inline]
into_iter(self) -> IntoIter<A>1762 fn into_iter(self) -> IntoIter<A> {
1763 let link_ops = self.adapter.link_ops();
1764
1765 if let Some(root) = self.root {
1766 IntoIter {
1767 head: Some(unsafe { first_child(link_ops, root) }),
1768 tail: Some(unsafe { last_child(link_ops, root) }),
1769 tree: self,
1770 }
1771 } else {
1772 IntoIter {
1773 head: None,
1774 tail: None,
1775 tree: self,
1776 }
1777 }
1778 }
1779 }
1780
1781 impl<'a, A: Adapter + 'a> IntoIterator for &'a RBTree<A>
1782 where
1783 A::LinkOps: RBTreeOps,
1784 {
1785 type Item = &'a <A::PointerOps as PointerOps>::Value;
1786 type IntoIter = Iter<'a, A>;
1787
1788 #[inline]
into_iter(self) -> Iter<'a, A>1789 fn into_iter(self) -> Iter<'a, A> {
1790 self.iter()
1791 }
1792 }
1793
1794 impl<A: Adapter + Default> Default for RBTree<A>
1795 where
1796 A::LinkOps: RBTreeOps,
1797 {
default() -> RBTree<A>1798 fn default() -> RBTree<A> {
1799 RBTree::new(A::default())
1800 }
1801 }
1802
1803 impl<A: Adapter> fmt::Debug for RBTree<A>
1804 where
1805 A::LinkOps: RBTreeOps,
1806 <A::PointerOps as PointerOps>::Value: fmt::Debug,
1807 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1808 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1809 f.debug_set().entries(self.iter()).finish()
1810 }
1811 }
1812
1813 // =============================================================================
1814 // InsertCursor, Entry
1815 // =============================================================================
1816
1817 /// A cursor pointing to a slot in which an element can be inserted into a
1818 /// `RBTree`.
1819 pub struct InsertCursor<'a, A: Adapter>
1820 where
1821 A::LinkOps: RBTreeOps,
1822 {
1823 parent: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1824 insert_left: bool,
1825 tree: &'a mut RBTree<A>,
1826 }
1827
1828 impl<'a, A: Adapter + 'a> InsertCursor<'a, A>
1829 where
1830 A::LinkOps: RBTreeOps,
1831 {
1832 /// Inserts a new element into the `RBTree` at the location indicated by
1833 /// this `InsertCursor`.
1834 ///
1835 /// # Panics
1836 ///
1837 /// Panics if the new element is already linked to a different intrusive
1838 /// collection.
1839 pub fn insert(self, val: <A::PointerOps as PointerOps>::Pointer) -> CursorMut<'a, A> {
1840 unsafe {
1841 let new = self.tree.node_from_value(val);
1842 let link_ops = self.tree.adapter.link_ops_mut();
1843 if let Some(parent) = self.parent {
1844 if self.insert_left {
1845 insert_left(link_ops, parent, new, &mut self.tree.root);
1846 } else {
1847 insert_right(link_ops, parent, new, &mut self.tree.root);
1848 }
1849 } else {
1850 self.tree.insert_root(new);
1851 }
1852 CursorMut {
1853 current: Some(new),
1854 tree: self.tree,
1855 }
1856 }
1857 }
1858 }
1859
1860 /// An entry in a `RBTree`.
1861 ///
1862 /// See the documentation for `RBTree::entry`.
1863 pub enum Entry<'a, A: Adapter>
1864 where
1865 A::LinkOps: RBTreeOps,
1866 {
1867 /// An occupied entry.
1868 Occupied(CursorMut<'a, A>),
1869
1870 /// A vacant entry.
1871 Vacant(InsertCursor<'a, A>),
1872 }
1873
1874 impl<'a, A: Adapter + 'a> Entry<'a, A>
1875 where
1876 A::LinkOps: RBTreeOps,
1877 {
1878 /// Inserts an element into the `RBTree` if the entry is vacant, returning
1879 /// a `CursorMut` to the resulting value. If the entry is occupied then a
1880 /// `CursorMut` pointing to the element is returned.
1881 ///
1882 /// # Panics
1883 ///
1884 /// Panics if the `Entry` is vacant and the new element is already linked to
1885 /// a different intrusive collection.
1886 pub fn or_insert(self, val: <A::PointerOps as PointerOps>::Pointer) -> CursorMut<'a, A> {
1887 match self {
1888 Entry::Occupied(entry) => entry,
1889 Entry::Vacant(entry) => entry.insert(val),
1890 }
1891 }
1892
1893 /// Calls the given function and inserts the result into the `RBTree` if the
1894 /// entry is vacant, returning a `CursorMut` to the resulting value. If the
1895 /// entry is occupied then a `CursorMut` pointing to the element is
1896 /// returned and the function is not executed.
1897 ///
1898 /// # Panics
1899 ///
1900 /// Panics if the `Entry` is vacant and the new element is already linked to
1901 /// a different intrusive collection.
1902 pub fn or_insert_with<F>(self, default: F) -> CursorMut<'a, A>
1903 where
1904 F: FnOnce() -> <A::PointerOps as PointerOps>::Pointer,
1905 {
1906 match self {
1907 Entry::Occupied(entry) => entry,
1908 Entry::Vacant(entry) => entry.insert(default()),
1909 }
1910 }
1911 }
1912
1913 // =============================================================================
1914 // Iter
1915 // =============================================================================
1916
1917 /// An iterator over references to the items of a `RBTree`.
1918 pub struct Iter<'a, A: Adapter>
1919 where
1920 A::LinkOps: RBTreeOps,
1921 {
1922 head: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1923 tail: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1924 tree: &'a RBTree<A>,
1925 }
1926 impl<'a, A: Adapter + 'a> Iterator for Iter<'a, A>
1927 where
1928 A::LinkOps: RBTreeOps,
1929 {
1930 type Item = &'a <A::PointerOps as PointerOps>::Value;
1931
1932 #[inline]
1933 fn next(&mut self) -> Option<&'a <A::PointerOps as PointerOps>::Value> {
1934 let head = self.head?;
1935
1936 if Some(head) == self.tail {
1937 self.head = None;
1938 self.tail = None;
1939 } else {
1940 self.head = unsafe { next(self.tree.adapter.link_ops(), head) };
1941 }
1942 Some(unsafe { &*self.tree.adapter.get_value(head) })
1943 }
1944 }
1945 impl<'a, A: Adapter + 'a> DoubleEndedIterator for Iter<'a, A>
1946 where
1947 A::LinkOps: RBTreeOps,
1948 {
1949 #[inline]
1950 fn next_back(&mut self) -> Option<&'a <A::PointerOps as PointerOps>::Value> {
1951 let tail = self.tail?;
1952
1953 if Some(tail) == self.head {
1954 self.head = None;
1955 self.tail = None;
1956 } else {
1957 self.tail = unsafe { prev(self.tree.adapter.link_ops(), tail) };
1958 }
1959 Some(unsafe { &*self.tree.adapter.get_value(tail) })
1960 }
1961 }
1962 impl<'a, A: Adapter + 'a> Clone for Iter<'a, A>
1963 where
1964 A::LinkOps: RBTreeOps,
1965 {
1966 #[inline]
1967 fn clone(&self) -> Iter<'a, A> {
1968 Iter {
1969 head: self.head,
1970 tail: self.tail,
1971 tree: self.tree,
1972 }
1973 }
1974 }
1975
1976 // =============================================================================
1977 // IntoIter
1978 // =============================================================================
1979
1980 /// An iterator which consumes a `RBTree`.
1981 pub struct IntoIter<A: Adapter>
1982 where
1983 A::LinkOps: RBTreeOps,
1984 {
1985 head: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1986 tail: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1987 tree: RBTree<A>,
1988 }
1989 impl<A: Adapter> Iterator for IntoIter<A>
1990 where
1991 A::LinkOps: RBTreeOps,
1992 {
1993 type Item = <A::PointerOps as PointerOps>::Pointer;
1994
1995 #[inline]
1996 fn next(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer> {
1997 use link_ops::LinkOps;
1998
1999 let head = self.head?;
2000 let link_ops = self.tree.adapter.link_ops_mut();
2001 unsafe {
2002 // Remove the node from the tree. Since head is always the
2003 // left-most node, we can infer the following:
2004 // - head.left is null.
2005 // - head is a left child of its parent (or the root node).
2006 if let Some(parent) = link_ops.parent(head) {
2007 link_ops.set_left(parent, link_ops.right(head));
2008 } else {
2009 self.tree.root = link_ops.right(head);
2010 if link_ops.right(head).is_none() {
2011 self.tail = None;
2012 }
2013 }
2014 if let Some(right) = link_ops.right(head) {
2015 link_ops.set_parent(right, link_ops.parent(head));
2016 self.head = Some(first_child(link_ops, right));
2017 } else {
2018 self.head = link_ops.parent(head);
2019 }
2020 link_ops.release_link(head);
2021 Some(
2022 self.tree
2023 .adapter
2024 .pointer_ops()
2025 .from_raw(self.tree.adapter.get_value(head)),
2026 )
2027 }
2028 }
2029 }
2030 impl<A: Adapter> DoubleEndedIterator for IntoIter<A>
2031 where
2032 A::LinkOps: RBTreeOps,
2033 {
2034 #[inline]
2035 fn next_back(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer> {
2036 use link_ops::LinkOps;
2037
2038 let tail = self.tail?;
2039 let link_ops = self.tree.adapter.link_ops_mut();
2040 unsafe {
2041 // Remove the node from the tree. Since tail is always the
2042 // right-most node, we can infer the following:
2043 // - tail.right is null.
2044 // - tail is a right child of its parent (or the root node).
2045 if let Some(parent) = link_ops.parent(tail) {
2046 link_ops.set_right(parent, link_ops.left(tail));
2047 } else {
2048 self.tree.root = link_ops.left(tail);
2049 if link_ops.left(tail).is_none() {
2050 self.tail = None;
2051 }
2052 }
2053 if let Some(left) = link_ops.left(tail) {
2054 link_ops.set_parent(left, link_ops.parent(tail));
2055 self.tail = Some(last_child(link_ops, left));
2056 } else {
2057 self.tail = link_ops.parent(tail);
2058 }
2059 link_ops.release_link(tail);
2060 Some(
2061 self.tree
2062 .adapter
2063 .pointer_ops()
2064 .from_raw(self.tree.adapter.get_value(tail)),
2065 )
2066 }
2067 }
2068 }
2069
2070 // =============================================================================
2071 // Tests
2072 // =============================================================================
2073
2074 #[cfg(test)]
2075 mod tests {
2076 use super::{Entry, KeyAdapter, Link, PointerOps, RBTree};
2077 use crate::Bound::*;
2078 use rand::prelude::*;
2079 use rand_xorshift::XorShiftRng;
2080 use std::fmt;
2081 use std::rc::Rc;
2082 use std::vec::Vec;
2083 use std::{format, vec};
2084
2085 #[derive(Clone)]
2086 struct Obj {
2087 link: Link,
2088 value: i32,
2089 }
2090 impl fmt::Debug for Obj {
2091 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2092 write!(f, "{}", self.value)
2093 }
2094 }
2095 intrusive_adapter!(ObjAdapter = Rc<Obj>: Obj { link: Link });
2096 impl<'a> KeyAdapter<'a> for ObjAdapter {
2097 type Key = i32;
2098 fn get_key(&self, value: &'a <Self::PointerOps as PointerOps>::Value) -> i32 {
2099 value.value
2100 }
2101 }
2102 fn make_obj(value: i32) -> Rc<Obj> {
2103 Rc::new(Obj {
2104 link: Link::new(),
2105 value,
2106 })
2107 }
2108
2109 #[test]
2110 fn test_link() {
2111 let a = make_obj(1);
2112 assert!(!a.link.is_linked());
2113 assert_eq!(format!("{:?}", a.link), "unlinked");
2114
2115 let mut b = RBTree::<ObjAdapter>::default();
2116 assert!(b.is_empty());
2117
2118 assert_eq!(b.insert(a.clone()).get().unwrap().value, 1);
2119 assert!(!b.is_empty());
2120 assert!(a.link.is_linked());
2121 assert_eq!(format!("{:?}", a.link), "linked");
2122
2123 let c = a.as_ref().clone();
2124 assert!(!c.link.is_linked());
2125
2126 unsafe {
2127 assert_eq!(b.cursor_from_ptr(a.as_ref()).get().unwrap().value, 1);
2128 assert_eq!(b.cursor_mut_from_ptr(a.as_ref()).get().unwrap().value, 1);
2129 }
2130
2131 assert_eq!(
2132 b.front_mut().remove().unwrap().as_ref() as *const _,
2133 a.as_ref() as *const _
2134 );
2135 assert!(b.is_empty());
2136 assert!(!a.link.is_linked());
2137 }
2138
2139 #[test]
2140 fn test_cursor() {
2141 let a = make_obj(1);
2142 let b = make_obj(2);
2143 let c = make_obj(3);
2144 let mut t = RBTree::new(ObjAdapter::new());
2145 let mut cur = t.cursor_mut();
2146 assert!(cur.is_null());
2147 assert!(cur.get().is_none());
2148 assert!(cur.remove().is_none());
2149
2150 cur.insert_before(a.clone());
2151 cur.insert_before(c.clone());
2152 cur.move_prev();
2153 cur.insert(b.clone());
2154 assert!(cur.peek_next().is_null());
2155 cur.move_next();
2156 assert!(cur.is_null());
2157
2158 cur.move_next();
2159 assert!(cur.peek_prev().is_null());
2160 assert!(!cur.is_null());
2161 assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
2162
2163 {
2164 let mut cur2 = cur.as_cursor();
2165 assert_eq!(cur2.get().unwrap() as *const _, a.as_ref() as *const _);
2166 assert_eq!(cur2.peek_next().get().unwrap().value, 2);
2167 cur2.move_next();
2168 assert_eq!(cur2.get().unwrap().value, 2);
2169 cur2.move_next();
2170 assert_eq!(cur2.peek_prev().get().unwrap().value, 2);
2171 assert_eq!(cur2.get().unwrap() as *const _, c.as_ref() as *const _);
2172 cur2.move_prev();
2173 assert_eq!(cur2.get().unwrap() as *const _, b.as_ref() as *const _);
2174 cur2.move_next();
2175 assert_eq!(cur2.get().unwrap() as *const _, c.as_ref() as *const _);
2176 cur2.move_next();
2177 assert!(cur2.is_null());
2178 assert!(cur2.clone().get().is_none());
2179 }
2180 assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
2181
2182 let a2 = make_obj(1);
2183 let b2 = make_obj(2);
2184 let c2 = make_obj(3);
2185 assert_eq!(
2186 cur.replace_with(a2.clone()).unwrap().as_ref() as *const _,
2187 a.as_ref() as *const _
2188 );
2189 assert!(!a.link.is_linked());
2190 cur.move_next();
2191 assert_eq!(
2192 cur.replace_with(b2.clone()).unwrap().as_ref() as *const _,
2193 b.as_ref() as *const _
2194 );
2195 assert!(!b.link.is_linked());
2196 cur.move_next();
2197 assert_eq!(
2198 cur.replace_with(c2.clone()).unwrap().as_ref() as *const _,
2199 c.as_ref() as *const _
2200 );
2201 assert!(!c.link.is_linked());
2202 cur.move_next();
2203 assert_eq!(
2204 cur.replace_with(c.clone()).unwrap_err().as_ref() as *const _,
2205 c.as_ref() as *const _
2206 );
2207 }
2208
2209 #[cfg(not(miri))]
2210 #[test]
2211 fn test_insert_remove() {
2212 let v = (0..100).map(make_obj).collect::<Vec<_>>();
2213 assert!(v.iter().all(|x| !x.link.is_linked()));
2214 let mut t = RBTree::new(ObjAdapter::new());
2215 assert!(t.is_empty());
2216 let mut rng = XorShiftRng::seed_from_u64(0);
2217
2218 {
2219 let mut expected = Vec::new();
2220 for x in v.iter() {
2221 t.insert(x.clone());
2222 expected.push(x.value);
2223 assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
2224 }
2225
2226 while let Some(x) = t.front_mut().remove() {
2227 assert_eq!(x.value, expected.remove(0));
2228 assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
2229 }
2230 assert!(expected.is_empty());
2231 assert!(t.is_empty());
2232 }
2233
2234 {
2235 let mut expected = Vec::new();
2236 for x in v.iter().rev() {
2237 t.insert(x.clone());
2238 expected.insert(0, x.value);
2239 assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
2240 }
2241
2242 while let Some(x) = t.back_mut().remove() {
2243 assert_eq!(x.value, expected.pop().unwrap());
2244 assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
2245 }
2246 assert!(expected.is_empty());
2247 assert!(t.is_empty());
2248 }
2249
2250 {
2251 let mut indices = (0..v.len()).collect::<Vec<_>>();
2252 indices.shuffle(&mut rng);
2253 let mut expected = Vec::new();
2254 for i in indices {
2255 t.insert(v[i].clone());
2256 expected.push(v[i].value);
2257 expected[..].sort();
2258 assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
2259 }
2260
2261 while !expected.is_empty() {
2262 {
2263 let index = rng.gen_range(0, expected.len());
2264 let mut c = t.cursor_mut();
2265 for _ in 0..(index + 1) {
2266 c.move_next();
2267 }
2268 assert_eq!(c.remove().unwrap().value, expected.remove(index));
2269 }
2270 assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
2271 }
2272 assert!(t.is_empty());
2273 }
2274
2275 {
2276 let mut indices = (0..v.len()).collect::<Vec<_>>();
2277 indices.shuffle(&mut rng);
2278 let mut expected = Vec::new();
2279 for i in indices {
2280 {
2281 let mut c = t.front_mut();
2282 loop {
2283 if let Some(x) = c.get() {
2284 if x.value > v[i].value {
2285 break;
2286 }
2287 } else {
2288 break;
2289 }
2290 c.move_next();
2291 }
2292 c.insert_before(v[i].clone());
2293 }
2294 expected.push(v[i].value);
2295 expected[..].sort();
2296 assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
2297 }
2298
2299 t.clear();
2300 assert!(t.is_empty());
2301 }
2302
2303 {
2304 let mut indices = (0..v.len()).collect::<Vec<_>>();
2305 indices.shuffle(&mut rng);
2306 let mut expected = Vec::new();
2307 for i in indices {
2308 {
2309 let mut c = t.back_mut();
2310 loop {
2311 if let Some(x) = c.get() {
2312 if x.value < v[i].value {
2313 break;
2314 }
2315 } else {
2316 break;
2317 }
2318 c.move_prev();
2319 }
2320 c.insert_after(v[i].clone());
2321 }
2322 expected.push(v[i].value);
2323 expected[..].sort();
2324 assert_eq!(t.iter().map(|x| x.value).collect::<Vec<_>>(), expected);
2325 }
2326 }
2327 }
2328
2329 #[cfg(not(miri))]
2330 #[test]
2331 fn test_iter() {
2332 let v = (0..10).map(|x| make_obj(x * 10)).collect::<Vec<_>>();
2333 let mut t = RBTree::new(ObjAdapter::new());
2334 for x in v.iter() {
2335 t.insert(x.clone());
2336 }
2337
2338 assert_eq!(
2339 format!("{:?}", t),
2340 "{0, 10, 20, 30, 40, 50, 60, 70, 80, 90}"
2341 );
2342
2343 assert_eq!(
2344 t.iter().clone().map(|x| x.value).collect::<Vec<_>>(),
2345 vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
2346 );
2347 assert_eq!(
2348 (&t).into_iter().rev().map(|x| x.value).collect::<Vec<_>>(),
2349 vec![90, 80, 70, 60, 50, 40, 30, 20, 10, 0]
2350 );
2351 assert_eq!(
2352 t.range(Unbounded, Unbounded)
2353 .map(|x| x.value)
2354 .collect::<Vec<_>>(),
2355 vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
2356 );
2357
2358 assert_eq!(
2359 t.range(Included(&0), Unbounded)
2360 .map(|x| x.value)
2361 .collect::<Vec<_>>(),
2362 vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
2363 );
2364 assert_eq!(
2365 t.range(Excluded(&0), Unbounded)
2366 .map(|x| x.value)
2367 .collect::<Vec<_>>(),
2368 vec![10, 20, 30, 40, 50, 60, 70, 80, 90]
2369 );
2370 assert_eq!(
2371 t.range(Included(&25), Unbounded)
2372 .map(|x| x.value)
2373 .collect::<Vec<_>>(),
2374 vec![30, 40, 50, 60, 70, 80, 90]
2375 );
2376 assert_eq!(
2377 t.range(Excluded(&25), Unbounded)
2378 .map(|x| x.value)
2379 .collect::<Vec<_>>(),
2380 vec![30, 40, 50, 60, 70, 80, 90]
2381 );
2382 assert_eq!(
2383 t.range(Included(&70), Unbounded)
2384 .map(|x| x.value)
2385 .collect::<Vec<_>>(),
2386 vec![70, 80, 90]
2387 );
2388 assert_eq!(
2389 t.range(Excluded(&70), Unbounded)
2390 .map(|x| x.value)
2391 .collect::<Vec<_>>(),
2392 vec![80, 90]
2393 );
2394 assert_eq!(
2395 t.range(Included(&100), Unbounded)
2396 .map(|x| x.value)
2397 .collect::<Vec<_>>(),
2398 vec![]
2399 );
2400 assert_eq!(
2401 t.range(Excluded(&100), Unbounded)
2402 .map(|x| x.value)
2403 .collect::<Vec<_>>(),
2404 vec![]
2405 );
2406
2407 assert_eq!(
2408 t.range(Unbounded, Included(&90))
2409 .map(|x| x.value)
2410 .collect::<Vec<_>>(),
2411 vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
2412 );
2413 assert_eq!(
2414 t.range(Unbounded, Excluded(&90))
2415 .map(|x| x.value)
2416 .collect::<Vec<_>>(),
2417 vec![0, 10, 20, 30, 40, 50, 60, 70, 80]
2418 );
2419 assert_eq!(
2420 t.range(Unbounded, Included(&25))
2421 .map(|x| x.value)
2422 .collect::<Vec<_>>(),
2423 vec![0, 10, 20]
2424 );
2425 assert_eq!(
2426 t.range(Unbounded, Excluded(&25))
2427 .map(|x| x.value)
2428 .collect::<Vec<_>>(),
2429 vec![0, 10, 20]
2430 );
2431 assert_eq!(
2432 t.range(Unbounded, Included(&70))
2433 .map(|x| x.value)
2434 .collect::<Vec<_>>(),
2435 vec![0, 10, 20, 30, 40, 50, 60, 70]
2436 );
2437 assert_eq!(
2438 t.range(Unbounded, Excluded(&70))
2439 .map(|x| x.value)
2440 .collect::<Vec<_>>(),
2441 vec![0, 10, 20, 30, 40, 50, 60]
2442 );
2443 assert_eq!(
2444 t.range(Unbounded, Included(&-1))
2445 .map(|x| x.value)
2446 .collect::<Vec<_>>(),
2447 vec![]
2448 );
2449 assert_eq!(
2450 t.range(Unbounded, Excluded(&-1))
2451 .map(|x| x.value)
2452 .collect::<Vec<_>>(),
2453 vec![]
2454 );
2455
2456 assert_eq!(
2457 t.range(Included(&25), Included(&80))
2458 .map(|x| x.value)
2459 .collect::<Vec<_>>(),
2460 vec![30, 40, 50, 60, 70, 80]
2461 );
2462 assert_eq!(
2463 t.range(Included(&25), Excluded(&80))
2464 .map(|x| x.value)
2465 .collect::<Vec<_>>(),
2466 vec![30, 40, 50, 60, 70]
2467 );
2468 assert_eq!(
2469 t.range(Excluded(&25), Included(&80))
2470 .map(|x| x.value)
2471 .collect::<Vec<_>>(),
2472 vec![30, 40, 50, 60, 70, 80]
2473 );
2474 assert_eq!(
2475 t.range(Excluded(&25), Excluded(&80))
2476 .map(|x| x.value)
2477 .collect::<Vec<_>>(),
2478 vec![30, 40, 50, 60, 70]
2479 );
2480
2481 assert_eq!(
2482 t.range(Included(&25), Included(&25))
2483 .map(|x| x.value)
2484 .collect::<Vec<_>>(),
2485 vec![]
2486 );
2487 assert_eq!(
2488 t.range(Included(&25), Excluded(&25))
2489 .map(|x| x.value)
2490 .collect::<Vec<_>>(),
2491 vec![]
2492 );
2493 assert_eq!(
2494 t.range(Excluded(&25), Included(&25))
2495 .map(|x| x.value)
2496 .collect::<Vec<_>>(),
2497 vec![]
2498 );
2499 assert_eq!(
2500 t.range(Excluded(&25), Excluded(&25))
2501 .map(|x| x.value)
2502 .collect::<Vec<_>>(),
2503 vec![]
2504 );
2505
2506 assert_eq!(
2507 t.range(Included(&50), Included(&50))
2508 .map(|x| x.value)
2509 .collect::<Vec<_>>(),
2510 vec![50]
2511 );
2512 assert_eq!(
2513 t.range(Included(&50), Excluded(&50))
2514 .map(|x| x.value)
2515 .collect::<Vec<_>>(),
2516 vec![]
2517 );
2518 assert_eq!(
2519 t.range(Excluded(&50), Included(&50))
2520 .map(|x| x.value)
2521 .collect::<Vec<_>>(),
2522 vec![]
2523 );
2524 assert_eq!(
2525 t.range(Excluded(&50), Excluded(&50))
2526 .map(|x| x.value)
2527 .collect::<Vec<_>>(),
2528 vec![]
2529 );
2530
2531 assert_eq!(
2532 t.range(Included(&100), Included(&-2))
2533 .map(|x| x.value)
2534 .collect::<Vec<_>>(),
2535 vec![]
2536 );
2537 assert_eq!(
2538 t.range(Included(&100), Excluded(&-2))
2539 .map(|x| x.value)
2540 .collect::<Vec<_>>(),
2541 vec![]
2542 );
2543 assert_eq!(
2544 t.range(Excluded(&100), Included(&-2))
2545 .map(|x| x.value)
2546 .collect::<Vec<_>>(),
2547 vec![]
2548 );
2549 assert_eq!(
2550 t.range(Excluded(&100), Excluded(&-2))
2551 .map(|x| x.value)
2552 .collect::<Vec<_>>(),
2553 vec![]
2554 );
2555
2556 let mut v2 = Vec::new();
2557 for x in t.take() {
2558 v2.push(x.value);
2559 }
2560 assert_eq!(v2, vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90]);
2561 assert!(t.is_empty());
2562 for _ in t.take() {
2563 unreachable!();
2564 }
2565
2566 for x in v.iter() {
2567 t.insert(x.clone());
2568 }
2569 v2.clear();
2570 for x in t.into_iter().rev() {
2571 v2.push(x.value);
2572 }
2573 assert_eq!(v2, vec![90, 80, 70, 60, 50, 40, 30, 20, 10, 0]);
2574 }
2575
2576 #[test]
2577 fn test_find() {
2578 let v = (0..10).map(|x| make_obj(x * 10)).collect::<Vec<_>>();
2579 let mut t = RBTree::new(ObjAdapter::new());
2580 for x in v.iter() {
2581 t.insert(x.clone());
2582 }
2583
2584 for i in -9..100 {
2585 fn mod10(x: i32) -> i32 {
2586 if x < 0 {
2587 10 + x % 10
2588 } else {
2589 x % 10
2590 }
2591 }
2592 {
2593 let c = t.find(&i);
2594 assert_eq!(
2595 c.get().map(|x| x.value),
2596 if i % 10 == 0 { Some(i) } else { None }
2597 );
2598 }
2599 {
2600 let c = t.find_mut(&i);
2601 assert_eq!(
2602 c.get().map(|x| x.value),
2603 if i % 10 == 0 { Some(i) } else { None }
2604 );
2605 }
2606 {
2607 let c = t.upper_bound(Unbounded);
2608 assert_eq!(c.get().map(|x| x.value), Some(90));
2609 }
2610 {
2611 let c = t.upper_bound_mut(Unbounded);
2612 assert_eq!(c.get().map(|x| x.value), Some(90));
2613 }
2614 {
2615 let c = t.upper_bound(Included(&i));
2616 assert_eq!(
2617 c.get().map(|x| x.value),
2618 if i >= 0 { Some(i - mod10(i)) } else { None }
2619 );
2620 }
2621 {
2622 let c = t.upper_bound_mut(Included(&i));
2623 assert_eq!(
2624 c.get().map(|x| x.value),
2625 if i >= 0 { Some(i - mod10(i)) } else { None }
2626 );
2627 }
2628 {
2629 let c = t.upper_bound(Excluded(&i));
2630 assert_eq!(
2631 c.get().map(|x| x.value),
2632 if i > 0 {
2633 Some(i - 1 - mod10(i - 1))
2634 } else {
2635 None
2636 }
2637 );
2638 }
2639 {
2640 let c = t.upper_bound_mut(Excluded(&i));
2641 assert_eq!(
2642 c.get().map(|x| x.value),
2643 if i > 0 {
2644 Some(i - 1 - mod10(i - 1))
2645 } else {
2646 None
2647 }
2648 );
2649 }
2650 {
2651 let c = t.lower_bound(Unbounded);
2652 assert_eq!(c.get().map(|x| x.value), Some(0));
2653 }
2654 {
2655 let c = t.lower_bound_mut(Unbounded);
2656 assert_eq!(c.get().map(|x| x.value), Some(0));
2657 }
2658 {
2659 let c = t.lower_bound(Included(&i));
2660 assert_eq!(
2661 c.get().map(|x| x.value),
2662 if i <= 90 {
2663 Some((i + 9) - mod10(i + 9))
2664 } else {
2665 None
2666 }
2667 );
2668 }
2669 {
2670 let c = t.lower_bound_mut(Included(&i));
2671 assert_eq!(
2672 c.get().map(|x| x.value),
2673 if i <= 90 {
2674 Some((i + 9) - mod10(i + 9))
2675 } else {
2676 None
2677 }
2678 );
2679 }
2680 {
2681 let c = t.lower_bound(Excluded(&i));
2682 assert_eq!(
2683 c.get().map(|x| x.value),
2684 if i < 90 {
2685 Some((i + 10) - mod10(i + 10))
2686 } else {
2687 None
2688 }
2689 );
2690 }
2691 {
2692 let c = t.lower_bound_mut(Excluded(&i));
2693 assert_eq!(
2694 c.get().map(|x| x.value),
2695 if i < 90 {
2696 Some((i + 10) - mod10(i + 10))
2697 } else {
2698 None
2699 }
2700 );
2701 }
2702 }
2703 }
2704
2705 #[test]
2706 fn test_fast_clear() {
2707 let mut t = RBTree::new(ObjAdapter::new());
2708 let a = make_obj(1);
2709 let b = make_obj(2);
2710 let c = make_obj(3);
2711 t.insert(a.clone());
2712 t.insert(b.clone());
2713 t.insert(c.clone());
2714
2715 t.fast_clear();
2716 assert!(t.is_empty());
2717 assert!(a.link.is_linked());
2718 assert!(b.link.is_linked());
2719 assert!(c.link.is_linked());
2720 unsafe {
2721 a.link.force_unlink();
2722 b.link.force_unlink();
2723 c.link.force_unlink();
2724 }
2725 assert!(t.is_empty());
2726 assert!(!a.link.is_linked());
2727 assert!(!b.link.is_linked());
2728 assert!(!c.link.is_linked());
2729 }
2730
2731 #[test]
2732 fn test_entry() {
2733 let mut t = RBTree::new(ObjAdapter::new());
2734 let a = make_obj(1);
2735 let b = make_obj(2);
2736 let c = make_obj(3);
2737 let d = make_obj(4);
2738 let e = make_obj(5);
2739 let f = make_obj(6);
2740 t.entry(&3).or_insert(c.clone());
2741 t.entry(&2).or_insert(b.clone());
2742 t.entry(&1).or_insert(a.clone());
2743
2744 match t.entry(&2) {
2745 Entry::Vacant(_) => unreachable!(),
2746 Entry::Occupied(c) => assert_eq!(c.get().unwrap().value, 2),
2747 }
2748 assert_eq!(t.entry(&2).or_insert(b.clone()).get().unwrap().value, 2);
2749 assert_eq!(
2750 t.entry(&2)
2751 .or_insert_with(|| b.clone())
2752 .get()
2753 .unwrap()
2754 .value,
2755 2
2756 );
2757
2758 match t.entry(&5) {
2759 Entry::Vacant(c) => assert_eq!(c.insert(e.clone()).get().unwrap().value, 5),
2760 Entry::Occupied(_) => unreachable!(),
2761 }
2762 assert!(e.link.is_linked());
2763 assert_eq!(t.entry(&4).or_insert(d.clone()).get().unwrap().value, 4);
2764 assert!(d.link.is_linked());
2765 assert_eq!(
2766 t.entry(&6)
2767 .or_insert_with(|| f.clone())
2768 .get()
2769 .unwrap()
2770 .value,
2771 6
2772 );
2773 assert!(f.link.is_linked());
2774 }
2775
2776 #[test]
2777 fn test_non_static() {
2778 #[derive(Clone)]
2779 struct Obj<'a, T> {
2780 link: Link,
2781 value: &'a T,
2782 }
2783 intrusive_adapter!(ObjAdapter<'a, T> = &'a Obj<'a, T>: Obj<'a, T> {link: Link} where T: 'a);
2784 impl<'a, 'b, T: 'a + 'b> KeyAdapter<'a> for ObjAdapter<'b, T> {
2785 type Key = &'a T;
2786 fn get_key(&self, value: &'a Obj<'b, T>) -> &'a T {
2787 value.value
2788 }
2789 }
2790
2791 let v = 5;
2792 let a = Obj {
2793 link: Link::default(),
2794 value: &v,
2795 };
2796 let b = a.clone();
2797 let mut l = RBTree::new(ObjAdapter::new());
2798 l.insert(&a);
2799 l.insert(&b);
2800 assert_eq!(*l.front().get().unwrap().value, 5);
2801 assert_eq!(*l.back().get().unwrap().value, 5);
2802 }
2803
2804 macro_rules! test_clone_pointer {
2805 ($ptr: ident, $ptr_import: path) => {
2806 use $ptr_import;
2807
2808 #[derive(Clone)]
2809 struct Obj {
2810 link: Link,
2811 value: usize,
2812 }
2813 intrusive_adapter!(ObjAdapter = $ptr<Obj>: Obj { link: Link });
2814 impl<'a> KeyAdapter<'a> for ObjAdapter {
2815 type Key = usize;
2816 fn get_key(&self, value: &'a Obj) -> usize {
2817 value.value
2818 }
2819 }
2820
2821 let a = $ptr::new(Obj {
2822 link: Link::new(),
2823 value: 5,
2824 });
2825 let mut l = RBTree::new(ObjAdapter::new());
2826 l.insert(a.clone());
2827 assert_eq!(2, $ptr::strong_count(&a));
2828
2829 let pointer = l.front().clone_pointer().unwrap();
2830 assert_eq!(pointer.value, 5);
2831 assert_eq!(3, $ptr::strong_count(&a));
2832
2833 l.front_mut().remove();
2834 assert!(l.front().clone_pointer().is_none());
2835 };
2836 }
2837
2838 #[test]
2839 fn test_clone_pointer_rc() {
2840 test_clone_pointer!(Rc, std::rc::Rc);
2841 }
2842
2843 #[test]
2844 fn test_clone_pointer_arc() {
2845 test_clone_pointer!(Arc, std::sync::Arc);
2846 }
2847 }
2848