amanieu / intrusive-rs Goto Github PK

It would be nice to have a way to splice a LinkedList into another LinkedList via mutable reference. The use case is that I have 2 structs, each of which contain a LinkedList, and I would like to transfer all the elements from one LinkedList into the other.

Unfortunately, since both splice_before and splice_after take the other list by value and not by mutable reference, I have to work around it with mem::replace:

struct Foo {
    list: LinkedList<Adapter>,
    other_field: u64,
}

fn transfer(from: &mut Foo, to: &mut Foo) {
    to.list.cursor_mut().splice_before(mem::replace(
        &mut from.list,
        LinkedList::new(Adapter::new()),
    ));
}

This feels a bit hacky and it would be nice if CursorMut provided splice_* methods that took the other list by mutable reference.

In DESIGN.md you write

Elements in a collection can't have a pointer back to the collection itself since these would become invalid if the collection is moved. C++ doesn't suffer from this limitation because it can adjust these pointers in the move constructor. [...]

This basically means that we have to use NULL-terminated linked lists instead of circular linked lists. It's very slightly slower (depending on who you ask), but generally not a big deal. This same restriction also applies to normal collection types in Rust.

This document was written 4 years ago. Was that before std::pin was introduced?
If so (here's my question) would circular lists be possible if the collection were guaranteed to be pinned?
Would that be a meaningful approach to enable circular lists?

Error[E0433]: failed to resolve. Use of undeclared type or module mem
--> intrusive-collections-0.7.7/src/intrusive_pointer.rs:36:9
|
36 | mem::forget(self);
| ^^^ Use of undeclared type or module mem

error: aborting due to previous error

Does this function have any order considerations? That is, does the replaced object need to have the same sort order as the object being replaced? Either way, I think the answer should be in the rustdocs.

(For reasons outside of this question) I need to build an intrusive RB tree where:

• elements automatically remove themselves from the tree in their drop implementation
• iterating over rb tree produces a sequence of Rc<T> elements (i.e. if I got cursor to point to an element -- that element will stay alive until cursor moves on)
• this rb tree is an equivalent of C++ multiset<T> (i.e. multiple elements with the same key are allowed)

Is it possible to do this with intrusive_collections::rbtree::RBTree?

It would be nice to be able to have attributes within intrusive_adapter! macro invocations.

I have #[deny(missing_docs)] on the module in which I use the macro, and I'd like to #[allow(missing_docs)] the stuff the macro produces, or even to have doc comments on the produced code. When I try the first, I run into a recursion limit reached while expanding the macro error.

Minimal code to reproduce:

struct Toy {
    link: RBTreeLink
}

intrusive_adapter!(
    #[allow(missing_docs)]
    pub ToyAdapter = Box<Toy> : Toy { link: RBTreeLink }
);

How easy would it be to modify the macro to preserve attributes?

It would be nice to have the macro able to generate generic adaptors. For example, to make using the following nice:

pub struct Node<T> {
    link: linked_list::Link,
    val: T,
}

intrusive_adaptor!(for <T> List = Object<T> { free_list: linked_list::Link});

(Macro syntax come up with on-the-spot, not sure if that would parse)

When included in a project with this configuration:

intrusive-collections = { version = "0.6", features = ["nightly"] }

Compilation fails with the following errors:

error: type `core::nonzero::NonZero<*mut T>` cannot be dereferenced
  --> intrusive-rs/src/unsafe_ref.rs:47:9
   |
47 |         *ptr.ptr
   |         ^^^^^^^^

error: type `core::nonzero::NonZero<*mut T>` cannot be dereferenced
   --> intrusive-rs/src/unsafe_ref.rs:112:20
    |
112 |         unsafe { &**self.ptr }
    |                    ^^^^^^^^^

error: aborting due to 2 previous errors

I believe this is due to the following change in the rust compiler:

rust-lang/rust#41064

I'm looking into getting more real-world tests for compact_arena, and intrusive collections should be a good fit. However, intrusive-rs uses *const pointers internally.

Would you accept a PR that makes the structures generic over the pointer type and perhaps add a scope type so that we could use compact_arena with this?

Hi,
While using RBTree I faced a problem with a simple scenario: I'm trying to do a kind of search to create a cursor with lower_bound_mut using a reference as an argument and then to insert_after using a value I searched by before; the problem is that the value is still borrowed even the cursor is already created and I see no reason to keep this borrow.

I would just insert it but I want to keep items unique so I do search with optional insertion .

UPD: also I noticed that .get operation on CursorMut returns a reference with a lifetime tied to cursor's lt rather than the tree's one, however, for Cursor is seems to be done correctly , but I may have wrong assumptions about lifetimes and soundness for CursorMut, anyway it would be nice to hear back if I'm using it wrong

Is there currently any possibility to append a list (or a CursorMut) to another list, without manually iterating through it? I haven't found a way in the API docs, but it should be as simple as joining the 2 related pointers.

What I'm trying to do is process a list. While doing the list processing, updates to the list as well as to other lists can happen. Therefore I .take() the original list and move it in a temporary other one. Just acting on the original Cursor and doing mutable changes there is a bit tricky, since I use a shared helper function for list updates which is also used by other methods.

Below is a part of the workflow I try to perform

let mut temp_list = self.actual_list.take();

let mut cursor = temp_list.cursor_mut();
while let Some(elem) = cursor.remove() {
    // For each List item I perform an operation
    let result = elem.do_something();
    // Then I obtain a status, which instructs in which list(s) the
    // element will still be member of
    let status = elem.get_status();
    
    // This manipulates the original list as well as some other lists
    // based on the new status of the element
    self.update_lists_based_on_status(&elem, status);

    if result.is_err() {
        // In the error case I want to abort and all elements which
        // were not processed back to the original list.
        // Ideally to the front in the order they are now in `temp_list`.
        // So something like
        // self.actual_list.push_all_front(elem);
        // would be great

        // This is a workaround. Actually it's wrong since it adds the entries
        // after entries that might have been added through
        // ùpdate_lists_based_on_status()`.
        // Using a reverse iterator and pushing at the front would help here
        while let Some(elem) = cursor.remove() {
            self.actual_list.push_back(elem);
        }

        return result;
    }
}

Why does this have to be a usize? Couldn't it be a u8?

The crate currently depends on rand_xorshift 0.2.0. But it seems like XorShiftRng::seed_from_u64 has been removed in 0.3.0. Here is what the build error looks like when I try to uprev rand_xorshift:

   Compiling intrusive-collections v0.9.1 (/ssd/aosp/external/rust/crates/intrusive-collections)
error[E0599]: no function or associated item named `seed_from_u64` found for struct `rand_xorshift::XorShiftRng` in the current scope
    --> src/rbtree.rs:2216:36
     |
2216 |         let mut rng = XorShiftRng::seed_from_u64(0);
     |                                    ^^^^^^^^^^^^^ function or associated item not found in `rand_xorshift::XorShiftRng`
     |
     = help: items from traits can only be used if the trait is in scope
     = note: the following trait is implemented but not in scope; perhaps add a `use` for it:
             `use rand_core::SeedableRng;`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0599`.
error: could not compile `intrusive-collections`.

To learn more, run the command again with --verbose.

It'd be great to migrate away from the deprecated API.

I would find it convenient (for implementing a custom LRU, with some fancy features but no way to remove arbitrary elements) to have a singly-linked list (with pointers going from the oldest LRU element to the newest), that also allows adding to the end of the list.
The APIs for getting CursorMut prevent this by forbidding keeping a mutable cursor to the end while accessing the list. Having a private CursorMut pointing to the end would allow providing a safe push_back API.

Would you be amenable to this idea? Should I send a pull request?

the following code causes a segmentation fault when executed
using git version of intrusive-collections

use intrusive_collections::{intrusive_adapter, LinkedListLink, LinkedList};

struct Value<T> {
    link: LinkedListLink,
    value: T, 
}

intrusive_adapter!(BoxedValueAdapter<T> = Box<Value<T>>: Value<T> { link: LinkedListLink });

fn main() {
    let mut list = LinkedList::new(BoxedValueAdapter::new());
    for x in 0..10 {
        let c = Value {
            link: LinkedListLink::new(),
            value: x, 
        };
        list.push_back(Box::new(c));
    }

    let mut curs = list.back_mut();
    for _ in 0..2 {
        curs.move_next();
    }

    let rest = curs.split_before();
    let mut curs = list.back_mut();
    curs.splice_after(rest);

    for x in &list {
        println!("{}", x.value);
    }
}

this is the output from running cargo miri with the same code

error[E0080]: Miri evaluation error: type validation failed: encountered 0, but expected something greater or equal to 1
   --> /home/user/.cargo/git/checkouts/intrusive-rs-9ecae677e4651113/e8a03c3/src/linked_list.rs:124:9
    |
124 |         (*self.0).next.set(next);
    |         ^^^^^^^^^^^^^^ Miri evaluation error: type validation failed: encountered 0, but expected something greater or equal to 1
    |
    = note: inside call to `intrusive_collections::linked_list::NodePtr::set_next` at /home/user/.cargo/git/checkouts/intrusive-rs-9ecae677e4651113/e8a03c3/src/linked_list.rs:186:9
    = note: inside call to `intrusive_collections::linked_list::NodePtr::splice` at /home/user/.cargo/git/checkouts/intrusive-rs-9ecae677e4651113/e8a03c3/src/linked_list.rs:504:21
note: inside call to `intrusive_collections::linked_list::CursorMut::<BoxedValueAdapter<i32>>::splice_after` at src/main.rs:27:5
   --> src/main.rs:27:5
    |
27  |     curs.splice_after(rest);
    |     ^^^^^^^^^^^^^^^^^^^^^^^

rustc version

rustc 1.35.0 (3c235d560 2019-05-20)
binary: rustc
commit-hash: 3c235d5600393dfe6c36eeed34042efad8d4f26e
commit-date: 2019-05-20
host: x86_64-unknown-linux-gnu
release: 1.35.0
LLVM version: 8.0

intrusive_adapater macro implements both Send and Sync traits for the implementation of Adapter trait that leads to unsound code for !Send containers such as Rc.

When iterating over a list where the storage type is Rc Arc, it is only possible to get an Option<&A::Value>, which of course is subject to the borrow checker rules. It is not possible to get an item as a strong reference, i.e. as an Option<A::Pointer>.

In some cases, if the list nodes are reference counted, it would be handy to just get an extra reference to the value. I could not find any way to do this safely (I am currently retrieving the Arc via IntrusivePointer, which is unsafe, then cloning it and finally forgetting the temporary instance). Would it be hard to add this functionality?

It is possible to make intrusive_adaptor to accept pointy brackets instead of square brackets by incrementally munching token trees (I have done this in this macro and in this monstrosity of a macro that has now been replaced by custom derive based implementation).

I'll give it a try once my work ends :P

I am trying to use a slab instead of arena and use intrusive collections to the elements in the slab. But I can't seem to make this work without polluting the top level type with a lifetime.

Sample code:

struct Item {
  link: RBTreeLink,
  val: u64,
}

intrusive_adapter!(ItemAdapter<'a> = &'a Item: Item { link: RBTreeLink });
impl<'a> KeyAdapter<'a> for ItemAdapter<'a> {
  type Key = u64;
  fn get_key(&self, i: &'a Item) -> u64 { -i.val }
}

struct TopLevel {
  slab: Slab<Item>,  // storage for items
  ids: HashMap<u64, usize>,  // id to item map (through its index in the slab)
  ord: RBTree<ItemAdapter<'a>>,  // ordered items: what lifetime to put here?!
}

If I add lifetime to TopLevel then it will need to be specified whenever TopLevel is a member of another struct.

Is what I am trying to do possible? If so how?

I have an adapter defined with the intrusive_adapter macro as follows:

intrusive_adapter!(pub ProcessAdapter = Rc<Process>: Process { link: LinkedListLink });

However, I am unable to construct a linked list with it for a static variable:

static mut RUNQUEUE: LinkedList<ProcessAdapter> = LinkedList::new(ProcessAdapter::new());

because the ProcessAdapter::new() function is not const:

error[E0015]: calls in constant functions are limited to constant functions, tuple structs and tuple variants

The following patch fixes the problem for me:

diff --git a/src/adapter.rs b/src/adapter.rs
index ccb0349..3b98873 100644
--- a/src/adapter.rs
+++ b/src/adapter.rs
@@ -175,6 +175,11 @@ macro_rules! intrusive_adapter {
         #[allow(dead_code)]
         impl<$($args $(: ?$bound)*),*> $name<$($args),*> $($where_)* {
             pub const NEW: Self = $name($crate::__core::marker::PhantomData);
+            #[cfg(feature = "nightly")]
+            pub const fn new() -> Self {
+                Self::NEW
+            }
+            #[cfg(not(feature = "nightly"))]
             pub fn new() -> Self {
                 Self::NEW
             }

However, it cause the following compilation warning:

warning: outlives requirements can be inferred
    --> src/rbtree.rs:1456:43
     |
1456 | pub enum Entry<'a, A: Adapter<Link = Link> + 'a> {
     |                                           ^^^^^ help: remove this bound
     |
note: lint level defined here
    --> src/lib.rs:275:9
     |
275  | #![warn(rust_2018_idioms)]
     |         ^^^^^^^^^^^^^^^^
     = note: `#[warn(explicit_outlives_requirements)]` implied by `#[warn(rust_2018_idioms)]`

which I am not sure how to fix, which is why I am submitting this as an issue rather than a pull request.

IIUC the SinglyLinkedList provides front(), push_front() and pop_front(), as only those can be accessed in O(1), when the list keeps track of the list head.

If the list would keep track of the list tail, with the tail (or sentinel) connected circularly, wouldn't back() and push_back() be possible in O(1), (with one indirection for the front operations, e.g., front() = back().next())?

IMO that extends the space savings of a singly linked list (vs. doubly linked list) to many more use cases.

There doesn't seem to be a way to modify the contents of an item in the RBTree.

I'm looking for a way to bubble up cache changes in node to its ancestors all the way to the root in RBTree.
I see there's .parent() method in rbtree::AtomicLinkOps but I'm not sure how to access it from Cursor.

it is incredibly difficult to write generics code over the current adapters since if an object is linked on multiple queues I may want to write generics saying "manipulate queue[x] link" and now it's almost impossible to express with generics basically collapsing due to all the lifetime constrains on cursors and elements

it would be much simpler if we have array of the same adapter, e.g. LinkList and then I can pass reference to the adapter by using the index into the array where the function interanlly can index it on the structure rather than trying to write a generic over any of those adapters

I have a use case where I want to iterate through a linked list and remove the "best" item (by whatever metric). So it involves testing each item, maintaining a reference to the best one found so far, then afterward removing the best item from the list.

This is roughly the code I want to use. It works, but results in the warning rust-lang/rust#59159, which will soon turn into a hard error, that list is being mutably borrowed while reference is already immutably borrowing list.

fn pluck_best_item(list: &mut LinkedList<LinkAdapter>, prefix: &str) -> Option<Rc<Thing>> {
    let mut best_so_far = None;
    
    for thing in list.iter() {
        if is_better_candidate_for_removal(thing, &best_so_far) {
            best_so_far = Some(thing);
        }
    }

    if let Some(reference) = best_so_far {
        let mut cursor = unsafe { list.cursor_mut_from_ptr(reference) };
        return cursor.remove();
    }

    None
}

I found that casting the reference to a *const drops the immutable borrow and makes the borrow checker happy, like so:

if let Some(reference) = best_so_far {
    let ptr = reference as *const Thing;
    let mut cursor = unsafe { list.cursor_mut_from_ptr(ptr) };
    return cursor.remove();
}

Is this pattern safe at all? Not just casting the reference to a pointer, but the whole thing: maintaining a reference that was borrowed immutably to create a mutable cursor in order to remove the item. If it's unsafe, is there a better way to do what I'm trying to?

Hello,

I'm trying to have multiple threads access a shared RBTree instance. Here's a small reproduction of the problem:

use std::sync::{Arc, Mutex};
use std::thread;

use intrusive_collections::{KeyAdapter, intrusive_adapter};
use intrusive_collections::rbtree::*;
use rand::random;

struct MyData {
    link: Link,
    key: u64,
    value: u64,
}

impl MyData {
    fn new(key: u64, value: u64) -> Arc<MyData> {
        Arc::new(MyData {
            link: Link::new(),
            key,
            value,
        })
    }
}

intrusive_adapter!(MyAdapter = Arc<MyData>: MyData { link: Link });

impl<'a> KeyAdapter<'a> for MyAdapter {
    type Key = u64;
    fn get_key(&self, data: &'a MyData) -> Self::Key {
        data.key
    }
}


fn main() {
    let tree = Arc::new(Mutex::new(RBTree::new(MyAdapter::new())));
    for _ in 0..30 {
        let key = random();
        let value = random();
        tree.lock().unwrap().entry(&key).or_insert_with(|| MyData::new(key, value));
    }

    const THREADS: usize = 7;
    let mut threads = Vec::with_capacity(THREADS);
    for _ in 0..THREADS {
        let tree = tree.clone();
        threads.push(thread::spawn(move || {
            for _ in 0..10 {
                let k = random();
                if let Some(data) = tree.lock().unwrap().find(&k).clone_pointer() {
                    println!("found key = {}, value = {}", data.key, data.value);
                }
            }
        }));
    }

    for t in threads.into_iter() {
        t.join().unwrap();
    }
}

This fails to compile with:

error[E0277]: `std::cell::Cell<intrusive_collections::rbtree::NodePtr>` cannot be shared between threads safely
   --> src/intrusive.rs:46:22
    |
46  |         threads.push(thread::spawn(move || {
    |                      ^^^^^^^^^^^^^ `std::cell::Cell<intrusive_collections::rbtree::NodePtr>` cannot be shared between threads safely
    |
    = help: within `MyData`, the trait `std::marker::Sync` is not implemented for `std::cell::Cell<intrusive_collections::rbtree::NodePtr>`
    = note: required because it appears within the type `intrusive_collections::rbtree::Link`
    = note: required because it appears within the type `MyData`
    = note: required because of the requirements on the impl of `std::marker::Send` for `std::sync::Arc<MyData>`
    = note: required because of the requirements on the impl of `std::marker::Send` for `intrusive_collections::rbtree::RBTree<MyAdapter>`
    = note: required because of the requirements on the impl of `std::marker::Send` for `std::sync::Mutex<intrusive_collections::rbtree::RBTree<MyAdapter>>`
    = note: required because of the requirements on the impl of `std::marker::Send` for `std::sync::Arc<std::sync::Mutex<intrusive_collections::rbtree::RBTree<MyAdapter>>>`
    = note: required because it appears within the type `[closure@src/intrusive.rs:46:36: 53:10 tree:std::sync::Arc<std::sync::Mutex<intrusive_collections::rbtree::RBTree<MyAdapter>>>]`

error[E0277]: `std::cell::Cell<usize>` cannot be shared between threads safely
   --> src/intrusive.rs:46:22
    |
46  |         threads.push(thread::spawn(move || {
    |                      ^^^^^^^^^^^^^ `std::cell::Cell<usize>` cannot be shared between threads safely
    |
    = help: within `MyData`, the trait `std::marker::Sync` is not implemented for `std::cell::Cell<usize>`
    = note: required because it appears within the type `intrusive_collections::rbtree::Link`
    = note: required because it appears within the type `MyData`
    = note: required because of the requirements on the impl of `std::marker::Send` for `std::sync::Arc<MyData>`
    = note: required because of the requirements on the impl of `std::marker::Send` for `intrusive_collections::rbtree::RBTree<MyAdapter>`
    = note: required because of the requirements on the impl of `std::marker::Send` for `std::sync::Mutex<intrusive_collections::rbtree::RBTree<MyAdapter>>`
    = note: required because of the requirements on the impl of `std::marker::Send` for `std::sync::Arc<std::sync::Mutex<intrusive_collections::rbtree::RBTree<MyAdapter>>>`
    = note: required because it appears within the type `[closure@src/intrusive.rs:46:36: 53:10 tree:std::sync::Arc<std::sync::Mutex<intrusive_collections::rbtree::RBTree<MyAdapter>>>]`

This appears to be because rbtree::Link implements Send but not Sync. I tried to work around this by using Arc<Mutex<MyData>> but then I got stuck on the implementation of MyAdapter: implementing get_link requires you to acquire the lock but there's no way to ensure that the lock is held (and then released) while the link is mutated.

I wonder if it's actually fine to implement Sync for rbtree::Link. As far as I can tell every safe method that modifies a Link requires a mutable reference to the tree first. I think it might require changing the is_linked method to be unsafe though.

Is there something I'm just missing to make this work?

very common to ask how many elements in the tree & smallest/largest element. Implementation would benefit from having

len,
min,
max

@ the top of the tree and according methods.

if you think you'd pull that up I can implement it.

I'm currently trying to use the library to place an element into multiple collections inside the same overall struct.

I would like that struct to have an accessor, which returns me a mutable reference to one of the stored elements. This would be not be able to mutate the collection, since the accessor requires &mut self, therefore everything should be fine from a safety perspective. However I can not get it to run without rustc complaining. Do you have any idea?

This is what I tried:

struct ElementNode {
    tree_link: RBTreeLink,
    inner: RefCell<ElementImpl>,
}

intrusive_adapter!(ElementTreeAdapter = Rc<ElementNode>: ElementNode {
    tree_link: RBTreeLink
});

pub struct ElementManager {
    element_tree: RBTree<ElementTreeAdapter>,
}

impl ElementManager {
    pub fn get_element_mut(&mut self, id: &ElementId) -> Option<&mut ElementImpl> {
        let node = self.element_tree.find_mut(id).get()?;

        Some(&mut (*node.inner.borrow_mut()))
    }
}

And it yields:

80 |         Some(&mut (*node.inner.borrow_mut()))
   |         ^^^^^^^^^^^^-----------------------^^
   |         |           |
   |         |           temporary value created here
   |         returns a value referencing data owned by the current function

It's likely this is more a misunderstanding than a real issue, however the following gives borrow checker failures despite being seemingly legitimate according to the documentation.

This is the sort of thing you might do if you wanted to represent a tree, where a head node had a set of children, each of those has grandchildren and so forth.

use intrusive_collections::{SinglyLinkedListLink, SinglyLinkedList, intrusive_adapter};
use typed_arena::Arena;

pub struct Thing<'a> {
    link: SinglyLinkedListLink,
    list: SinglyLinkedList<Adapter<'a>>,
}
intrusive_adapter!(Adapter<'a> = &'a Thing<'a>: Thing<'a> { link: SinglyLinkedListLink });

pub fn foo<'a>(_: &'a Arena<Thing<'a>>) {
}

#[test]
fn bar() {
    let arena = Arena::new();
    foo(&arena);
}

This gives the following output:

error[E0597]: `arena` does not live long enough
  --> test.rs:17:9
   |
17 |     foo(&arena);
   |         ^^^^^^ borrowed value does not live long enough
18 | }
   | -
   | |
   | `arena` dropped here while still borrowed
   | borrow might be used here, when `arena` is dropped and runs the destructor for type `Arena<Thing<'_>>`

For more information about this error, try `rustc --explain E0597`.

Plausibly this is related to what's going on inside intrusive_adapter.

it only checks next (even in doubly linked case).

this would be more logical has_successor or something like this

there is now no real method to figure out whether a node is really linked onto the list on not on it.

As in the title, but would it be reasonable to make Link and AtomicLink #[repr(C)]? I realise that an external library could put the links into a bad state, but this would mean that a list, for example, could be constructed in Rust and then passed to a consumer in C. My use case is actually to pass between two Rust binaries in the same address space.

Are there any drawbacks with implementing entry method for CursorMut?

Like this: https://github.com/sergeyfedotov/intrusive-rs/blob/2b9d41c5b7fe87edbb1d91ad1eee6a32c0fa3d83/src/rbtree.rs#L795

The offset_of macro contains the following

        // Create an instance of the container and calculate the offset to its
        // field. Although we are creating references to uninitialized data this
        // is fine since we are not dereferencing them.
        #[allow(unused_unsafe)]
        let val: $container = unsafe { $crate::__core::mem::uninitialized() };

Unfortunately, the comment is wrong. It's not just creating a reference to uninitialized data, it is creating a local variable with uninitialized data. For instance, the following code is UB:

let x: bool = mem::uninitialized();

That said, there currently is no correct way to do what you want. This bug can only really be fixed once MaybeUninit gets stabilized.

Also see this discussion on internals.

What do you think about a parallel library to this that requires the use of Slab(s) and uses usize as pointers to other nodes?

This eliminates the lifetime pollution when implementing with a Slab/Arena as backing store and makes the top level container much more ergonomic.

let mut cur = self.events.front_mut();
cur.insert(Box::new(EventNode::new(OneRootPoint::new(0, 0))));
cur.insert(Box::new(EventNode::new(OneRootPoint::new(0, 0))));

error[E0499]: cannot borrow `cur` as mutable more than once at a time
   --> src/sweep_line/mod.rs:109:9
    |
108 |         cur.insert(Box::new(EventNode::new(OneRootPoint::new(0, 0))));
    |         --- first mutable borrow occurs here
109 |         cur.insert(Box::new(EventNode::new(OneRootPoint::new(0, 0))));
    |         ^^^ second mutable borrow occurs here
...
121 |     }
    |     - first borrow ends here

Are there any reasons to specify insert method with the same lifetime as for CursorMut itself?

Just a small thing you might wanna change. ¯_(ツ)_/¯

I need adapter to be pub (crate) but the macros don't allow that match

I imagine this could work in much the same way as the std::collections::HashSet (in that is uses open addressing) and have the "link" store the index of the bucket an item belongs to.

If an enum variant contains the Link field and the user can guarantee the variant, it should be possible to push the Link into the enum variant type so that only that variant can support the collection rather than wrapping the whole enum in another struct containing the links

Example:

enum SomeEnum {
	variant1: {
		link: Link
		...
	}
}

Instead of

struct SomeWrapper {
	link: Link
	enum: SomeEnum
}

I've tried with multiple versions and it seems like test doesn't pass with out 'alloc' feature ? spot checked
4ce4dd3 and 185d613 and it seems like never passed.
CI config suggests this case wasn't covered?
Does anybody use non-alloc since alloc is no longer nightly?

$ rustc --version
rustc 1.63.0

$ rustc --version
rustc 1.48.0

$ cargo test --no-default-features

some snippets:

error[E0277]: the trait bound Arc<dyn Debug>: IntrusivePointer<_> is not satisfied
--> src/intrusive_pointer.rs:224:48
|
224 | let r = IntrusivePointer::into_raw(p);
| -------------------------- ^ expected an implementor of trait IntrusivePointer<_>
| |
| required by a bound introduced by this call
|
help: consider borrowing here
|
224 | let r = IntrusivePointer::into_raw(&p);
| +

error[E0277]: the trait bound Arc<dyn Debug>: IntrusivePointer<dyn Debug> is not satisfied
--> src/intrusive_pointer.rs:227:34
|
227 | let p2: Arc = IntrusivePointer::from_raw(r);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait IntrusivePointer<dyn Debug> is not implemented for Arc<dyn Debug>
|
= help: the following other types implement trait IntrusivePointer<T>:
&'a T
UnsafeRef

error[E0277]: the trait bound Rc<dyn Debug>: IntrusivePointer<_> is not satisfied
--> src/intrusive_pointer.rs:208:48
|
208 | let r = IntrusivePointer::into_raw(p);
| -------------------------- ^ expected an implementor of trait IntrusivePointer<_>
| |
| required by a bound introduced by this call
|
help: consider borrowing here
|
208 | let r = IntrusivePointer::into_raw(&p);
| +

error[E0277]: the trait bound Rc<dyn Debug>: IntrusivePointer<dyn Debug> is not satisfied
--> src/intrusive_pointer.rs:211:33
|
211 | let p2: Rc = IntrusivePointer::from_raw(r);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait IntrusivePointer<dyn Debug> is not implemented for Rc<dyn Debug>
|
= help: the following other types implement trait IntrusivePointer<T>:
&'a T
UnsafeRef

error[E0277]: the trait bound Box<dyn Debug>: IntrusivePointer<_> is not satisfied
--> src/intrusive_pointer.rs:192:48
|
192 | let r = IntrusivePointer::into_raw(p);
| -------------------------- ^ expected an implementor of trait IntrusivePointer<_>
| |
| required by a bound introduced by this call
|
help: consider borrowing here
|
192 | let r = IntrusivePointer::into_raw(&p);
| +

error[E0277]: the trait bound Box<dyn Debug>: IntrusivePointer<dyn Debug> is not satisfied
--> src/intrusive_pointer.rs:195:34
|
195 | let p2: Box = IntrusivePointer::from_raw(r);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait IntrusivePointer<dyn Debug> is not implemented for Box<dyn Debug>
|
= help: the following other types implement trait IntrusivePointer<T>:
&'a T
UnsafeRef

A common reason to use intrusive data-structures is to be able to look up an element via one data-structure, and then perform some operation on the same element in a different data-structure.

AIUI, this cannot be done safely with this crate, as it requires the unsafe cursor_mut_from_ptr method to be called.

I think a safe interface could be made by having this crate own the allocator that produces elements. For example, a basic allocator could store elements in a Vec<T>, and then use Vec indices as the "pointers" used to identify elements. Safety would be ensured by checking indices against the length of the internal Vec.

This would not prevent logic errors (if you mixed elements from different allocators, you'd get garbage results) but it should all be safe.

An arena allocator could work similarly, but using real pointers and range checks instead.

I disabled the tests that require rand, ran cargo miri test and got the following error:

error[E0080]: constant evaluation error: Pointer must be in-bounds and live at offset 40, but is outside bounds of allocation 40420 which has size 24
    --> /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/libcore/ptr.rs:3009:9
     |
3009 |         &*self.as_ptr()
     |         ^^^^^^^^^^^^^^^ Pointer must be in-bounds and live at offset 40, but is outside bounds of allocation 40420 which has size 24
     |
     = note: inside call to `core::ptr::NonNull::<alloc::sync::ArcInner<i32>>::as_ref` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/liballoc/sync.rs:545:18
     = note: inside call to `alloc::sync::Arc::<i32>::inner` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/liballoc/sync.rs:777:10
     = note: inside call to `<alloc::sync::Arc<i32> as core::ops::Deref>::deref` at /Users/jrmuizel/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/src/liballoc/sync.rs:2140:10
note: inside call to `<alloc::sync::Arc<i32> as core::convert::AsRef<i32>>::as_ref` at src/intrusive_pointer.rs:125:30
    --> src/intrusive_pointer.rs:125:30
     |
125  |         let fake_rc_target = fake_rc.as_ref() as *const _;
     |                              ^^^^^^^^^^^^^^^^
note: inside call to `<alloc::sync::Arc<i32> as intrusive_pointer::IntrusivePointer<i32>>::from_raw` at src/intrusive_pointer.rs:186:32
    --> src/intrusive_pointer.rs:186:32
     |
186  |             let p2: Arc<i32> = IntrusivePointer::from_raw(r);
     |                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside call to `intrusive_pointer::tests::test_arc` at src/intrusive_pointer.rs:180:5
    --> src/intrusive_pointer.rs:180:5
     |
180  | /     fn test_arc() {
181  | |         unsafe {
182  | |             let p = Arc::new(1);
183  | |             let a: *const i32 = &*p;
...    |
189  | |         }
190  | |     }
     | |_____^

Hi,

first, thank you for the great crate. I found a small issue: if I use intrusive_adapter! macro for a type that does not implement Default, it will fail. Actually it does not depend on this Default since it's PhantomData. This is a little bit confusing and requires writing of custom Adapter implementation which does exactly the same as the macro one. I believe an implementation should be used instead of derive. Maybe the same for Clone too, and may be it is even Copy.

Crate is great. Very common problem though in this kind of stuff. I insert into rbtree, then use the link list to change keys, tree ends up corrupted since it seems to pull local copies of keys (basically invariants change). Adapters would need to somehow let each other know when the key is being modified or some other kind of API fix to prevent this.

// get bunch elements into tree/lists & then flip keys & see whether sorting on the
// tree holds

	let mut a = LinkedList::new(MyAdapter::new());
	let mut b = SinglyLinkedList::new(MyAdapter2::new());
	let mut c = RBTree::new(MyAdapter3::new());

	for v in &[30, 40, 50, 60, 70, 80, 90, 100] {
		let mut test = Rc::new(Test {
			value: Cell::new(*v),
			..Test::default()
		});
		a.push_front(test.clone());
		b.push_front(test.clone());
		c.insert(test);
	}

	{
// Find the first element which is greater than or equal to min
		let mut cursor = c.lower_bound_mut(Bound::Included(&40));

		let mut cont = true;
		// Iterate over all elements in the range [min, max]
		while !cursor.is_null() {
			let v = cursor.get();
			println!("{:?}", v);

			cursor.move_next();
		}
	}

	let mut v = 0xff; // pseudo rand

	let deft = Test {
		value: Cell::new(99),
		..Test::default()
	};

	// divide by ten
	let mut mc = a.cursor_mut();

	mc.move_next();

	while ! mc.is_null() {
		let iv = &mc.get().unwrap_or(&deft).value;

		if let Some(imc) = mc.get() {
			println!("{} -> {}", iv.get(), iv.get() + v);
			imc.value.set(iv.get() + v);
		}

		v ^= iv.get();
		mc.move_next();
	}

	{
		let mut cursor = c.lower_bound_mut(Bound::Included(&40));

		let mut cont = true;
		// Iterate over all elements in the range [min, max]
		while !cursor.is_null() {
			let v = cursor.get();
			println!("{:?}", v);

			cursor.move_next();
		}
	}

I want to use intrusive_adapter! with dyn_struct's DynStruct :

type SparseComponentPtrs = DynStruct<LinkedListLink, Option<NonNull<u8>>>;
intrusive_adapter!(SparseAdapter = Box<SparseComponentPtrs>: SparseComponentPtrs { header: LinkedListLink });

But have following error:

error[E0599]: the function or associated item `uninit` exists for union `MaybeUninit<DynStruct<LinkedListLink, Option<NonNull<u8>>>>`, but its trait bounds were not satisfied
  --> crates\ecs_rs\src\component_archetype_cache.rs:25:1
   |
25 | intrusive_adapter!(SparseAdapter = Box<DynStruct<LinkedListLink, Option<NonNull<u8>>>>: DynStruct<LinkedListLink, Option<NonNull<u8>>> { header: LinkedListLink ...
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ function or associated item cannot be called on `MaybeUninit<DynStruct<LinkedListLink, Option<NonNull<u8>>>>` due to unsatisfied trait bounds
   |
  ::: C:\Users\Andy\.cargo\registry\src\github.com-1ecc6299db9ec823\dyn_struct-0.2.0\src\lib.rs:96:1
   |
96 | pub struct DynStruct<Header, Tail> {
   | ---------------------------------- doesn't satisfy `_: Sized`
   |
   = note: the following trait bounds were not satisfied:
           `DynStruct<LinkedListLink, Option<NonNull<u8>>>: Sized`
   = note: this error originates in the macro `_memoffset__let_base_ptr` (in Nightly builds, run with -Z macro-backtrace for more info)

Can I do something about this?

Could we cache total count of items in the container, and provide len() with constant complexity.

The answer is yes I think, but the docs don't make it clear if all or only some of traversals are ordered.

Ben Kimock pointed me to a bug in my code cehteh/cachedb#3

This clearly was caused by my misunderstanding. Still I am wondering whats the reason that LinkedListLink has no Drop implementation that checks if an Link is linked and if so removes it from the list? Do I miss some ill side effect or is it only for performance?

Whilst looking through some of the code in NodePtr, I observed a couple of possible minor optimizations; I haven't had the chance to test these and its possible they are optimized out in release mode, in any event.

I found them whilst exploring whether unlikely / likely hints might make a difference for a large tree.

In last_child() and first_child() there is a null guard. The same null guard is made inside next() and previous(); refactoting out the guarded code would allow one less if statement to be executed.

There's a common pattern in last_child() and first_child() which uses a where loop which checks for either left() or right being null before looping; it should be possible to replace this with a loop like

while
			{
				let left = x.left();
				likely!(left.is_not_null())
			}
			{
				x = left
			}

to avoid a second look up from memory. Given the recently accessed value is already going to be a register or cache, it's possibly moot. Similar code that checks parent() does the same in next() / prev().