We all know the gist: linked lists are cool, but they when they tend to grow performance drops considerably. Lookup speed and allocation overhead can be costly. The migration to trees or other structures may or may not bring the desired results. In contrast, embedding a number of elements into linked list node can help quite a bit with all of these issues.
The idea is simple: a portable macro library header in the style of queue(3) or tree(3) that takes care of all the work. The design, however, brings a few caveats. First of all, element allocation is replaced by node allocation. That means the macros need explicit allocation and free hints. Another problem is taking care that elements are properly sorted and that a full node is split in two equal halves. It’s a bit tricky to get right, but, as usual, the code can be found on GitHub as a work in progress.
The page (I know this clashes with other conventions, but we are in userland and can do almost anything) or node structure is declared with a name, the embedded type (int, struct something, etc.) and the number of elements per page:
struct page_struct {
int reserved;
int value;
};
PAGE_DECLARE(page_head, struct page_struct, 4);
To insert an element we need a couple of tools: a compare function (or macro) and an allocation function (or macro). And later, we also need a free function:
#define PAGE_CMP(x, y) ((x)->value - (y)->value) #define PAGE_MALLOC(x, y) malloc(y) #define PAGE_FREE(x, y) free(y)
The prototype for malloc and free has two elements: the first one is an arbitrary context pointer, the second argument is equal to malloc(3) and free(3). If you don’t need special allocation, the redefinition macros are for you. But if you are working with memory pools and so on, you’ll most likely need the context pointer.
struct page_head *root = NULL;
struct page_struct test = {
.value = 1,
};
PAGE_INSERT(root, &test, PAGE_CMP, PAGE_MALLOC, NULL);
After insert, we can search for the element with the macro PAGE_FIND(). Finding elements is pretty cool as we can do a number of tricks under the hood:
- Look at the first element in the page. If it is greater than what we are looking for, we can abort the search.
- Look at the last element in the page. If it is smaller than what we are looking for, we can go to the next page and return to step one.
- If the range in the page matches, go through the list and find the element. We can even use a binary search approach here given we have a fair number of embedded elements on the page.
Last but not least, the list can be destroyed by calling the following macro with the free function. Currently, there’s no use case for removing elements from the list, so we do it globally unsing PAGE_COLLAPSE().
That’s all for now. In the next part of this series we will focus on the insert strategy and go a bit into details about the motivation to use macros instead of functions.