Support specifying allocator

[ClawSeven]

Hi, Amanieu,

I encountered some issues while developing memory management (MM) using an intrusive linked list. As you may know, the Box pointer uses #global_allocator to allocate and deallocate memory on the heap. However, in the kernel, the memory allocated by #global_allocator needs to be managed. Therefore, I have implemented a customized allocator for Box, called Alloc.

However, the current intrusive implementation does not allow for the specification of allocators, and PointerOps trait is only implemented for Box<T, Global>. In issue #87, I applied generic associated types and provided an implementation, but it is not ideal. I am struggling to come up with a better solution.

The current implementation allows us to specify allocators when using the intrusive_adapter macro, as shown here:

        use intrusive_collections::intrusive_adapter;
        use intrusive_collections::{LinkedList, LinkedListLink};
        use std::cell::Cell;

        // A simple struct containing an instrusive link and a value
        struct Test {
            link: LinkedListLink,
            value: Cell<i32>,
        }

        // The adapter describes how an object can be inserted into an intrusive
        // collection. This is automatically generated using a macro.
        intrusive_adapter!(TestAdapter = Global, Box<Test, Global>: Test { link: LinkedListLink });

        // Create a list and some objects
        let mut list = LinkedList::new(TestAdapter::new());
        let a = Box::new(Test {
            link: LinkedListLink::new(),
            value: Cell::new(1),
        });
        let b = Box::new(Test {
            link: LinkedListLink::new(),
            value: Cell::new(2),
        });
        let c = Box::new(Test {
            link: LinkedListLink::new(),
            value: Cell::new(3),
        });

        // Insert the objects at the front of the list
        list.push_front(a);
        list.push_front(b);
        list.push_front(c);
        assert_eq!(list.iter().map(|x| x.value.get()).collect::<Vec<_>>(), [3, 2, 1]);

I would appreciate your assistance in finding a better solution that supports specifying allocators. I look forward to your reply.

[Amanieu]

The PointerOps trait provides all the flexibility needed to support custom allocators: you need to hold a copy of the allocator in your custom MyPointerOps object and use it to reconstruct a Box<T, A> from a *const T.

However since you are using a custom PointerOps, you cannot use the intrusive_adapter macro and need to make a type that implements the Adapter trait manually.

No changes to this crate are needed, it's just that you can't use the DefaultPointerOps and intrusive_adapter! helpers with custom allocators.

[ClawSeven]

Wow, thank you for the elegant solution! By the way, does the intrusive-rs crate support raw pointers? I understand that I may need to implement a custom PointerOps, but I am wondering if there is any additional work required to support raw pointers.

[ClawSeven]

I have found that there is an UnsafeRef pointer available in the intrusive-rs crate. I can use this pointer instead of raw pointers, and free the memory by myself. Your design is very well thought out.