Open Source C Library Melon: Doubly Linked List

#algorithms #c #opensource

This article introduces the use of the double-linked list of the open source C library Melon.

Readers who are interested in the open source C library can visit its Github repo.

Introduction to Linked List

First briefly introduce what is a doubly linked list. You can refer to the following figure:

Simply put, a linked list is to connect nodes one by one through pointers. In the doubly linked list, each node not only records the pointer to the next node, but also records the pointer to the previous node.

Advantages of the doubly linked list:

The time complexity of node insertion and deletion operations is O(1), so it is very suitable for frequent insertion and deletion scenarios.

Use of doubly linked list

Let’s define a type first:

typedef struct test_s {
 int val;
} test_t;

In the subsequent introduction, what we have to do is to use Melon’s linked list component to transform this structure and build it into a doubly linked list.

In Melon, there are two implementations of doubly linked lists. Both implementations have their own advantages, so readers can choose to use them according to the needs.

The first implementation

#include <stdio.h>
#include <stdlib.h>
#include "mln_defs.h"

typedef struct test_s {
    int val;
    struct test_s *prev;
    struct test_s *next;
} test_t;

MLN_CHAIN_FUNC_DECLARE(test, test_t, static inline void, );
MLN_CHAIN_FUNC_DEFINE(test, test_t, static inline void, prev, next);

int main(void)
{
  int i;
  test_t *head = NULL, *tail = NULL, *t;

  for (i = 0; i < 10; ++i) {
    t = (test_t *)malloc(sizeof(test_t));
    if (t == NULL) {
        fprintf(stderr, "malloc failed.\n");
        return -1;
    }
    t->val = i;
    t->prev = t->next = NULL;
    test_chain_add(&head, &tail, t);
  }

  for (t = head; t != NULL; t = t->next) {
    printf("%d\n", t->val);
  }
  return 0;
}

In this code, the main is very simple. It uses a for loop to malloc 10 test_t structures, and then fill their val with the integer i. Then use the test_chain_add to link these nodes into a list. Finally, uses a for loop to traverse the nodes and print the value of val.

Here comes the question, where did test_chain_add come from?

We see that there are two MLN_CHAIN_FUNC_xxx macros before main, these two macros are defined in the header file mln_defs.h in Melon, and are used to define and declare the insertion and deletion functions of the linked list.

MLN_CHAIN_FUNC_DECLARE

The first parameter: function name prefix
The second parameter: custom structure type
The third parameter: function return value and function type
The fourth parameter: function parameter restriction attribute (not used in this example)

MLN_CHAIN_FUNC_DEFINE

The first parameter: function name prefix
The second parameter: custom structure type
The third parameter: function return value and function type
The fourth parameter: the name of the pointer member used to access the previous node in the custom structure
The fifth parameter: the name of the pointer member used to access the next node in the custom structure

These two macros will define and declare two functions named: test_chain_add and test_chain_del. The prototypes of these two functions are similar to the following:

void (*chain_op)(type **head, type **tail, type *node);

The first parameter is the address of the first pointer of the doubly linked list, the second parameter is the address of the last pointer of the doubly linked list, and the third parameter is the node pointer to be operated.

Features

The advantage of this implementation is that the insertion and deletion functions can be defined as inline, and the names of the forward and backward pointers can be changed at will. And when traversing the linked list, you only need to access these two pointers of the custom node.

The disadvantage is that users need to know the member names of the forward and backward pointers in the custom structure. And if many doubly linked lists are defined, many insertion and deletion functions need to be defined either, which will increase the size of the executable program.

The second implementation

#include "mln_list.h"
#include "mln_defs.h"
#include <stdlib.h>

typedef struct {
    int        val;
    mln_list_t node;
} test_t;

int main(void)
{
    int i;
    test_t *t;
    mln_list_t sentinel = mln_list_null();

    for (i = 0; i < 3; ++i) {
        t = (test_t *)calloc(1, sizeof(*t));
        if (t == NULL)
            return -1;
        mln_list_add(&sentinel, &t->node);
        t->val = i;
    }
    for (t = mln_container_of(mln_list_head(&sentinel), test_t, node); \
         t != NULL; \
         t = mln_container_of(mln_list_next(&t->node), test_t, node))
    {
        printf("%d\n", t->val);
    }
    return 0;
}

The behavior of the main function is exactly the same as the code of the first implementation. The difference lies in the following aspects:

Include mln_list.h
Instead of adding the forward and backward pointers to test_t, a member (node) of a fixed type (mln_list_t) is added.
The head and tail pointers of the doubly linked list are changed to a mln_list_t type variable named sentinel.
The linked list insertion function is no longer a custom prefix function, but a function with a fixed name called mln_list_add.
To access the first node of the linked list use the macro mln_list_head
To obtain the pointer to the host structure where the linked list node is located (ie test_t in this example), you need to use the macro mln_container_of defined in mln_defs.h.

Features

Advantages: Users do not need to care about the implementation details of the linked list, they only need to add mln_list_t type members into the custom type. And the insertion and deletion operations of the function are fixed names, respectively: mln_list_add and mln_list_remove.

Disadvantage: Access to the host node (test_t) to which the linked list node belongs requires the help of the macro mln_container_of, which does not seem as intuitive as the first implementation. And the linked list operation functions are all non-inline, so the overhead of frequent calls will be higher than the first implementation.

In fact, readers may notice that the second implementation (mln_list.c) is implemented by the first doubly linked list implementation.