Generic circular doubly linked list

Question

Edit:

New version improved with the answers and comments received here:

Generic circular doubly-linked list v2

---

I have written a linked list library that I can use whenever I need a linked list, so I tried to have all the functionality that one could expect from a linked list.

From the different types of linked lists, I decided that the best one is the circular doubly linked list, which has many advantages, and the only disadvantage that I know is using a little extra space.

---

How it works:

Initializing the list:

struct Alx_LinkedList *list; if (alx_llist_init(&list)) goto err; 

Adding members (and data at the same time):

char x[4] = "Hi!"; if (alx_llist_append(list, (const void *)x, sizeof(x)) < 0) goto err; 

Removing an element:

alx_llist_remove_tail(list); 

Moving through the list (the pointer called current):

alx_llist_move_to(list, 7); 

(of course, the user can move as always by using the next and prev (or head and tail) pointers, and assigning them to current):

list->current = list->current->next; 

Editing the data in a node:

double y[5] = {0, 1.1, 1,1,1,}; if (alx_llist_edit_current(list, (const void *)y, sizeof(y))) goto err; 

Finding a node:

ptrdiff_t pos; pos = alx_llist_find(list, node); 

Get size of the list (nmemb):

ptrdiff_t nmemb; nmemb = list->nmemb; 

Remove all nodes:

alx_llist_remove_all(list); 

Deinitialize list:

alx_llist_deinit(list); 

---

The functions to add a first element or remove the last element need not be used by the user, as the other functions check if those need to be called and do so internally, but they can still be used if the user wants to.

All functions report errors with negative return values, and non-error but abnormal things may return positive values.

---

Features:

The data can have any type and any size. The list creates a (malloced) copy of the data, and frees it automatically so that the user only needs to pass a (const void *) to the data and the size of the data.

The size is always available to the user and updated automatically by the functions (if the user modifies this value, the behavior is undefined!).

---

Is there any functionallity that you would add, or any improvement to this linked list?

---

Code:

linked-list.h:

 /****************************************************************************** ******* include guard ******************************************************** ******************************************************************************/ #pragma once /* libalx/extra/alx/linked-list.h */ /****************************************************************************** ******* headers ************************************************************** ******************************************************************************/ #include <stddef.h> /****************************************************************************** ******* macros *************************************************************** ******************************************************************************/ /****************************************************************************** ******* enum ***************************************************************** ******************************************************************************/ /****************************************************************************** ******* struct / union ******************************************************* ******************************************************************************/ struct Alx_LLNode { void *data; struct Alx_LLNode *prev; struct Alx_LLNode *next; }; struct Alx_LinkedList { struct Alx_LLNode *head; struct Alx_LLNode *tail; struct Alx_LLNode *current; ptrdiff_t nmemb; }; /****************************************************************************** ******* prototypes *********************************************************** ******************************************************************************/ __attribute__((nonnull)) int alx_llist_init (struct Alx_LinkedList **list); __attribute__((nonnull)) int alx_llist_deinit (struct Alx_LinkedList *list); __attribute__((nonnull)) int alx_llist_first_element (struct Alx_LinkedList *list, const void *data, size_t size); __attribute__((nonnull)) int alx_llist_remove_last (struct Alx_LinkedList *list); __attribute__((nonnull)) int alx_llist_prepend (struct Alx_LinkedList *list, const void *data, size_t size); __attribute__((nonnull)) int alx_llist_append (struct Alx_LinkedList *list, const void *data, size_t size); __attribute__((nonnull)) int alx_llist_insert_before (struct Alx_LinkedList *list, const void *data, size_t size); __attribute__((nonnull)) int alx_llist_insert_after (struct Alx_LinkedList *list, const void *data, size_t size); __attribute__((nonnull)) int alx_llist_remove_head (struct Alx_LinkedList *list); __attribute__((nonnull)) int alx_llist_remove_tail (struct Alx_LinkedList *list); __attribute__((nonnull)) int alx_llist_remove_current(struct Alx_LinkedList *list); __attribute__((nonnull)) int alx_llist_remove_all (struct Alx_LinkedList *list); __attribute__((nonnull, pure)) ptrdiff_t alx_llist_find (struct Alx_LinkedList *list, struct Alx_LLNode *node); __attribute__((nonnull)) int alx_llist_move_fwd (struct Alx_LinkedList *list, ptrdiff_t n); __attribute__((nonnull)) int alx_llist_move_bwd (struct Alx_LinkedList *list, ptrdiff_t n); __attribute__((nonnull)) int alx_llist_move_to (struct Alx_LinkedList *list, ptrdiff_t pos); __attribute__((nonnull)) int alx_llist_edit_current (struct Alx_LinkedList *list, const void *data, size_t size); /****************************************************************************** ******* inline *************************************************************** ******************************************************************************/ /****************************************************************************** ******* end of file ********************************************************** ******************************************************************************/ 

linked-list.c:

 /****************************************************************************** ******* headers ************************************************************** ******************************************************************************/ #include "libalx/extra/alx/linked-list.h" #include <stdlib.h> #include <string.h> #include "libalx/base/stdlib/alloc/mallocarrays.h" #include "libalx/base/stdlib/alloc/mallocs.h" #include "libalx/base/stdlib/alloc/reallocs.h" /****************************************************************************** ******* macros *************************************************************** ******************************************************************************/ /****************************************************************************** ******* enum / struct / union ************************************************ ******************************************************************************/ /****************************************************************************** ******* static prototypes **************************************************** ******************************************************************************/ /****************************************************************************** ******* global functions ***************************************************** ******************************************************************************/ int alx_llist_init (struct Alx_LinkedList **list) { if (alx_mallocarrays(list, 1)) return -1; (*list)->head = NULL; (*list)->tail = NULL; (*list)->current = NULL; (*list)->nmemb = 0; return 0; } int alx_llist_deinit (struct Alx_LinkedList *list) { int status; status = alx_llist_remove_all(list); free(list); return status; } int alx_llist_first_element (struct Alx_LinkedList *list, const void *data, size_t size) { struct Alx_LLNode *node; if (list->nmemb) return -3; if (alx_mallocarrays(&node, 1)) return -1; if (alx_mallocs(&node->data, size)) goto err; memcpy(node->data, data, size); node->prev = node; node->next = node; list->head = node; list->tail = node; list->current = node; list->nmemb = 1; return 0; err: free(node); return -2; } int alx_llist_remove_last (struct Alx_LinkedList *list) { struct Alx_LLNode *node; if (list->nmemb != 1) return -1; node = list->head; free(node->data); list->head = NULL; list->tail = NULL; list->current = NULL; free(node); list->nmemb = 0; return 0; } int alx_llist_prepend (struct Alx_LinkedList *list, const void *data, size_t size) { struct Alx_LLNode *node; if (!list->nmemb) { alx_llist_first_element(list, data, size); return 1; } if (alx_mallocarrays(&node, 1)) return -1; if (alx_mallocs(&node->data, size)) goto err; memcpy(node->data, data, size); node->prev = list->tail; node->next = list->head; list->head->prev = node; list->tail->next = node; list->head = node; (list->nmemb)++; return 0; err: free(node); return -2; } int alx_llist_append (struct Alx_LinkedList *list, const void *data, size_t size) { struct Alx_LLNode *node; if (!list->nmemb) { alx_llist_first_element(list, data, size); return 1; } if (alx_mallocarrays(&node, 1)) return -1; if (alx_mallocs(&node->data, size)) goto err; memcpy(node->data, data, size); node->prev = list->tail; node->next = list->head; list->head->prev = node; list->tail->next = node; list->tail = node; (list->nmemb)++; return 0; err: free(node); return -2; } int alx_llist_insert_before (struct Alx_LinkedList *list, const void *data, size_t size) { struct Alx_LLNode *node; if (!list->nmemb) { alx_llist_first_element(list, data, size); return 1; } if (alx_mallocarrays(&node, 1)) return -1; if (alx_mallocs(&node->data, size)) goto err; memcpy(node->data, data, size); node->prev = list->current->prev; node->next = list->current; list->current->prev->next = node; list->current->prev = node; list->current = node; (list->nmemb)++; return 0; err: free(node); return -2; } int alx_llist_insert_after (struct Alx_LinkedList *list, const void *data, size_t size) { struct Alx_LLNode *node; if (!list->nmemb) { alx_llist_first_element(list, data, size); return 1; } if (alx_mallocarrays(&node, 1)) return -1; if (alx_mallocs(&node->data, size)) goto err; memcpy(node->data, data, size); node->prev = list->current; node->next = list->current->next; list->current->next->prev = node; list->current->next = node; list->current = node; (list->nmemb)++; return 0; err: free(node); return -2; } int alx_llist_remove_head (struct Alx_LinkedList *list) { struct Alx_LLNode *node; switch (list->nmemb) { case 0: return 1; case 1: return alx_llist_remove_last(list); } node = list->head; free(node->data); list->head->prev->next = node->next; list->head->next->prev = node->prev; if (list->current == list->head) list->current = node->next; list->head = node->next; free(node); (list->nmemb)--; return 0; } int alx_llist_remove_tail (struct Alx_LinkedList *list) { struct Alx_LLNode *node; switch (list->nmemb) { case 0: return 1; case 1: return alx_llist_remove_last(list); } node = list->tail; free(node->data); list->tail->prev->next = node->next; list->tail->next->prev = node->prev; if (list->current == list->tail) list->current = node->prev; list->tail = node->prev; free(node); (list->nmemb)--; return 0; } int alx_llist_remove_current(struct Alx_LinkedList *list) { struct Alx_LLNode *node; switch (list->nmemb) { case 0: return 1; case 1: return alx_llist_remove_last(list); } node = list->current; free(node->data); list->current->prev->next = node->next; list->current->next->prev = node->prev; if (list->tail == list->current) { list->tail = node->prev; list->current = node->prev; } else if (list->head == list->current) { list->head = node->next; list->current = node->next; } else { list->current = node->prev; } free(node); (list->nmemb)--; return 0; } int alx_llist_remove_all (struct Alx_LinkedList *list) { ptrdiff_t n; n = list->nmemb; if (!n) return 1; for (ptrdiff_t i = 0; i < n; i++) alx_llist_remove_tail(list); return 0; } ptrdiff_t alx_llist_find (struct Alx_LinkedList *list, struct Alx_LLNode *node) { struct Alx_LLNode *tmp; tmp = list->head; for (ptrdiff_t i = 0; i < list->nmemb; i++) { if (tmp == node) return i; tmp = tmp->next; } return -1; } int alx_llist_move_fwd (struct Alx_LinkedList *list, ptrdiff_t n) { int status; if (n < 0) return alx_llist_move_bwd(list, -n); status = 0; for (ptrdiff_t i = 0; i < n; i++) { list->current = list->current->next; if (list->current == list->head) status++; } return 0; } int alx_llist_move_bwd (struct Alx_LinkedList *list, ptrdiff_t n) { int status; if (n < 0) return alx_llist_move_fwd(list, -n); status = 0; for (ptrdiff_t i = 0; i < n; i++) { list->current = list->current->prev; if (list->current == list->tail) status--; } return 0; } int alx_llist_move_to (struct Alx_LinkedList *list, ptrdiff_t pos) { list->current = list->head; if (pos < 0) return alx_llist_move_bwd(list, -pos); return alx_llist_move_fwd(list, pos); } int alx_llist_edit_current (struct Alx_LinkedList *list, const void *data, size_t size) { struct Alx_LLNode *node; if (!list->nmemb) return -1; node = list->current; if (alx_reallocs(&node->data, size)) return -2; memmove(node->data, data, size); return 0; } /****************************************************************************** ******* static function definitions ****************************************** ******************************************************************************/ /****************************************************************************** ******* end of file ********************************************************** ******************************************************************************/ 

---

Functions and macros used in linked-list.h:

 /* * [[gnu::nonnull]] * int alx_mallocarrays(type **restrict ptr, ptrdiff_t nmemb); */ #define alx_mallocarrays(ptr, nmemb) ( \ { \ __auto_type ptr_ = (ptr); \ \ *ptr_ = alx_mallocarray(nmemb, sizeof(**ptr_)); \ \ !(*ptr_); \ } \ ) inline void *alx_mallocarray (ptrdiff_t nmemb, size_t size) { if (nmemb < 0) goto ovf; if ((size_t)nmemb > (SIZE_MAX / size)) goto ovf; return malloc(size * (size_t)nmemb); ovf: errno = ENOMEM; return NULL; } /* * [[gnu::nonnull]] * int alx_mallocs(void **restrict ptr, size_t size); */ #define alx_mallocs(ptr, size) ( \ { \ __auto_type ptr_ = (ptr); \ \ *ptr_ = malloc(size); \ \ !(*ptr_); \ } \ ) /* * [[gnu::nonnull]] * int alx_reallocs(void **restrict ptr, size_t size); */ #define alx_reallocs(ptr, size) ( \ { \ __auto_type ptr_ = (ptr); \ \ *ptr_ = realloc(*ptr_, size); \ \ !(*ptr_); \ } \ ) 

---

Finally, I'm sorry about the tabs. It is aligned to 8 characters. I will add a double tab when I can, so that it looks good.

Answer 1

Prefer writing functions over macros

In many cases, macros can be replaced by perfectly ordinary functions which do the same thing, but are usually safer to use. Consider alx_mallocs() for example, it can be simply written as:

static inline bool alx_mallocs(void **ptr, size_t size) { return (*ptr = malloc(size)); } 

There's no need for tricks to prevent the arguments from being evaluated more than once. You can then even add __attribute__((nonnull)) in front of it if your compiler supports it.

Move current out of the list

By making the current point part of Alx_LinkedList, you prevent multiple parts of the code from accessing the same list simultaneously. This is an issue even in single-threaded code. For example, consider a loop going through the elements of the list, and if some condition is true, it has to call another function which also wants to iterate through the list. This nested list access is not possible with your functions.

It is better to create a new struct that represents a cursor into an existing list.

Remove redundant functions

You have these two functions:

int alx_llist_move_fwd (struct Alx_LinkedList *list, ptrdiff_t n); int alx_llist_move_bwd (struct Alx_LinkedList *list, ptrdiff_t n); 

They do the same thing; they move the current pointer, but they take a signed offset and both handle that fine. Just keep a single function:

int alx_llist_move (struct Alx_LinkedList *list, ptrdiff_t n); 

If someone wants to move backwards, they can just pass in a negative number. Internally you could split it into multiple functions for handling forward and backwards movement differently, but at least keep your API simple.

Use proper names

alx_llist_edit_current() is probably better rewritten as alx_llist_set_current().

If I see alx_llist_first_element(), I don't know what it does. Does it get the first element? Does it set the first element? Does it move current to the first element? Only by reading the code do I know what it does. It apparently sets the first element, but only if there was no first element to begin with. If it's just an internal helper function, it should not be part of the API, so remove it from linked-list.h, but still give it a better name in linked-list.c.

Add a function to get data out of a node

You have functions to insert data into the list, but I don't see any function that gets the data back out. Apparently you have to just follow the data pointer of an Alx_LLnode. It's cleaner and more symmetrical to add a function to retrieve the data pointer from a node. And that immediately brings to light another problem:

Store the size of the data in a node

You allow setting the contents of a node by providing both a pointer to a blob of data, and its size. So it is natural to expect that given a node, I can get back the pointer to that blob, and its size.

Make it clear that this is a circular linked list

To distinguish it from a regular linked list, make sure the names of structs and functions make it clear that it is a circular linked list. It's also best if the filenames themselves reflect this.

Answer 2

Here are some things that may help you improve your code.

Don't rely on non-standard extensions

Some of your code, such as the alx_mallocarrays macro is relying on a braced-group within an expression which is not valid C, even if your compiler supports it. See this question for details. The code also requires __auto_type and __attribute__ which are also gcc extensions. All of these make your code non-portable; at the very least this limitation should be expressly acknowledged in the header and/or documentation.

Use include guards

There should be an include guard in each .h file. That is, start the file with:

#ifndef LINKED_LIST_H #define LINKED_LIST_H // file contents go here #endif // LINKED_LIST_H 

The use of #pragma once is a common extension, but it's not in the standard and thus represents at least a potential portability problem. See SF.8

Avoid relative paths in #includes

Generally it's better to omit relative path names from #include files and instead point the compiler to the appropriate location.

#include "libalx/extra/alx/linked-list.h" #include <stdlib.h> #include <string.h> #include "libalx/base/stdlib/alloc/mallocarrays.h" #include "libalx/base/stdlib/alloc/mallocs.h" #include "libalx/base/stdlib/alloc/reallocs.h" 

For gcc, you'd use -I. This makes the code less dependent on the actual file structure, and leaving such details in a single location: a Makefile or compiler configuration file. The order of these also suggests the next item.

Put your own #includes first

If you put your own #includes first, you will catch errors in which the #include is incomplete. For example, I suspect that the three last .h files above need one or more things from <stdlib.h> or <string.h>. If that's the case, then the files that need them should #include them. Otherwise the code is dependent on the order of the #includes in the code which is a recipe for disaster and frustration.

Avoid goto

The use of goto is error prone and is better avoided. In the cases in which it's used, it's easily avoided. For example instead of this:

 if (alx_mallocs(&node->data, size)) goto err; memcpy(node->data, data, size); node->prev = list->current->prev; node->next = list->current; list->current->prev->next = node; list->current->prev = node; list->current = node; (list->nmemb)++; return 0; err: free(node); return -2; 

Write this:

if (!alx_mallocs(&node->data, size)) { memcpy(node->data, data, size); node->prev = list->current->prev; node->next = list->current; list->current->prev->next = node; list->current->prev = node; list->current = node; (list->nmemb)++; return 0; } free(node); return -2; 

Eliminate "magic numbers"

There are a few numbers in the code, such as -1 and -2 that have a specific meaning in their particular context. By using named constants such as err_mallocarrays and err_mallocs, the program becomes easier to read and maintain.

Use const where practical

Some of the functions, such as alx_llist_find do not alter the passed parameters. Those parameters should be declared const.

Consider documenting the header file

The header is where I'd look to figure out how to use this class. Because the nameing of functions is generally good, I wouldn't need a lot, but some functions such as alx_llist_find and alx_llist_remove_last are a bit strange. I'd normally expect to be able to find by value rather than address and the alx_llist_remove_last seems too specialized for a general interface. Use it internally only if it's useful, but don't clutter the public interface with unneeded functions. An ideal interface is minimal but sufficient.

Answer 3

Small review

inline void *alx_mallocarray (ptrdiff_t nmemb, size_t size) { if (nmemb < 0) goto ovf; if ((size_t)nmemb > (SIZE_MAX / size)) goto ovf; return malloc(size * (size_t)nmemb); ovf: errno = ENOMEM; return NULL; } 

(SIZE_MAX / size) overflows on pathological size==0 - code lacks protection.

Code does not certainly set errno when malloc(non_zero) returns NULL. Suggest doing so if other code uses errno = ENOMEM;

ENOMEM is not part of standard C.

Pedantic: (size_t)nmemb potentially truncates. Could use (uintmax_t)nmemb instead to quiet mixed type warnings.

malloc(0) returning a non-NULL or NULL is often an annoying issue. I avoid with explicit code:

if (size == 0) size = 1; //allocate 1 // or depending on upper code use. if (size == 0) return NULL. 

Answer 4

Instead of having a data pointer in the node, you might consider making the node and the data part of the same allocation.

The data can be either after the structure or using the "struct hack". You could also make the node pointer be the data pointer, and reference the node fields as ((struct Alx_LLNode*)data)[-1].next, and the like. This takes some extra care at allocation and access time, but could be worth it.

Given the quality of inlined functions, you could make two accessor functions (get and set) for each field and they would inline perfectly.

If you do this, I would pay attention to alignment requirements vs structure size. I.e. for performance, make sure your header size is a multiple of the worst alignment requirement or preference for data on your hardware. (For example, on x386 and above, 32 bit ints have NO alignment requirement, but are faster if aligned on 4 byte boundaries.)