UIT is a Unified Intrusive Linked List library. This library brings together 4 different linked lists based on a unified abstraction, the core trick is mock_head. In addition, some balanced trees have been implemented, what makes it different is that they're simplified with mock_sentinel, which is similar to the mock_head.

• Simple and easy-to-understand code
• Fewer branches and better performance, e.g. there's no branch in the uit::idslist::push_back method
• Pointers to pointers are no longer required, even the hlist (uit::isdlist) is no exception
• For uit::dlist and uit::sdlist, nodes can be directly removed without holding the original linked list
• Truly zero overhead
• No macros

• There are some undefined behaviors in the implementation of the mock_head. Regardless of the approach taken, the mock_head is not a complete object that actually exists, which violates lifetime rules, exceeds object boundaries, and may violate strict aliasing, among other violations not listed here.
• Among these, isdlist, idslist, and idlist are self-referential types, with isdlist and idlist being move-only.

This project is used for experimental exploration, I will not bear any consequences caused by the practical application of this project.

The main branch contains the prototype implementation, which is straightforward to understand. It must be said that the v2 branch is a better implementation under the current C++ standard definition, which utilizes class inheritance, it can currently (not guaranteed in the future) work on Clang and MSVC with high-level optimizations (such as O3), but for GCC, you must add an extra option -fno-strict-aliasing.

I have a private repository named uit_ng that still uses mock_head, it utilizes composition instead of class inheritance, yet maintains zero-overhead abstraction. Despite this, it works correctly across Big Three (GCC, Clang and MSVC) at the highest optimization levels, and passes all test cases without requiring additional compiler flags or special attributes in the source code. So far, I haven’t been able to create a test case that it fails. If enough people express interest, I would consider making this repository public.

struct nested_node {
    int m_sn;
    struct inner {
        nested_node *right; // The pointer used for linking is a member of the subobject.
    };
    uint64_t m_weight;
};

Not currently, but I've attempted this before, and it can even support more complex situations than nested member pointers. It's not complicated and only requires a few template tricks to implement. If someone has a genuine need for this feature with solid justification, I'll implement it. However, it should be noted that this would make the code less elegant, and impose higher requirements on the compiler version.

No, the UB introduced by the mock_sentinel does not affect the correctness, so there is no immediate plan to change it to a user-passed sentinel approach, as such an interface would not be concise enough for users.

No, it depends on the implementation, and the slowness is due to parrot code. Red-Black Tree does not have any advantages over SBT or WBT in terms of functionality, performance, or complexity. However, I have no plans to make these optimized implementations public, including the non-recursive implementation with parent pointers.

For simplicity, I will use a singly linked list as an example in C language. Firstly, we define a singly linked list node type struct node, and implement the push_front, the code is as follows:

#include <stddef.h>

struct node {
    int sn;
    struct node *next;
};

static struct node *head = NULL;

void push_front(struct node *n) {
    n->next = head;
    head = n;
}

Traditionally, when we want to remove a node from a singly linked list, we need the help of a pointer to pointer.

struct node *remove_with_pointer_to_pointer(struct node *n) {
    struct node **prev = &head;
    for (struct node *cur = *prev; cur != NULL;) {
        if (cur == n) {
            *prev = cur->next;
            return cur;
        }
        prev = &cur->next;
        cur = *prev;
    }
    return NULL;
}

Why do we need a pointer to pointer? The core reason is that the type of the head node and data node are different, and the pointer to pointer unifies them. If we define the head as static struct node head = {0, NULL};, the pointer to pointer will no longer be needed, but there is a problem of memory waste, the member int sn; is redundant in the example, we only need the member struct node *next;.

The solution is to use head node to simulate data node through the container_of, the code is as follows:

#define container_of(_field_, _type_, _member_)                                                    \
    ((_type_ *) ((size_t) (_field_) -offsetof(_type_, _member_)))

#define MOCK_HEAD(_field_, _type_, _member_) container_of(_field_, _type_, _member_)

struct node *remove_with_mock_head(struct node *n) {
    struct node *prev = MOCK_HEAD(&head, struct node, next);
    for (struct node *cur = prev->next; cur != NULL;) {
        if (cur == n) {
            prev->next = cur->next;
            return cur;
        }
        prev = cur;
        cur = prev->next;
    }
    return NULL;
}

As you can see, mock_head is just a alias of the contianer_of, it unifies head node and data node, just like pointer to pointer. It should be noted that when accessing head node members, all members except for struct node *next; are undefined in the example.

Of course, this is just an example. The implementation of container_of is slightly different in C++, please see the header in this library.

For an empty slist: head.right = nullptr;.

For an empty sdlist: head.right = nullptr;.

#include <iostream>
#include <uit/islist.hpp>

class apple {
   public:
    apple(uint64_t weight, int sn) noexcept
        : weight(weight)
        , sn(sn) {
    }

    uint64_t weight;
    apple *right;
    int sn;
};

int main(int argc, char *argv[]) {
    uit::islist<&apple::right> list{};

    apple a0{500, 0};
    apple a1{501, 1};
    apple a2{502, 2};
    apple a3{503, 3};

    list.push_front(&a3);
    list.push_front(&a2);
    list.push_front(&a1);
    list.push_front(&a0);

    for (const auto &i: list) {
        std::cout << "sn: " << i.sn << ", weight: " << i.weight << std::endl;
    }
    return 0;
}

#include <iostream>
#include <uit/islist.hpp>

class apple : public uit::isnode<apple, "0"> {
   public:
    apple(uint64_t weight, int sn) noexcept
        : weight(weight)
        , sn(sn) {
    }

    uint64_t weight;
    int sn;
};

int main(int argc, char *argv[]) {
    uit::islist<apple, "0"> list{};

    apple a0{500, 0};
    apple a1{501, 1};
    apple a2{502, 2};
    apple a3{503, 3};

    list.push_front(&a3);
    list.push_front(&a2);
    list.push_front(&a1);
    list.push_front(&a0);

    for (const auto &i: list) {
        std::cout << "sn: " << i.sn << ", weight: " << i.weight << std::endl;
    }
    return 0;
}

Please refer to the examples and tests folder.

• Move the implementation with mock_head into the uit::exp namespace and implement a practical linear linked list without UB.

ykiko helped me answer the key questions I encountered in this project, and thank you all for your attention to this project.