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.

• pacmaninbw: Please do not change the question, especially the code after it has been answered. See codereview.stackexchange.com/help/someone-answers

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.

• alx - recommends codidact: "alx_llist_move_to(list, pos) makes it sound like you go to an absolute position, but it just moves the current pointer relatively.": No it doesn't. Look carefully at it ;)
• alx - recommends codidact: "Move current out of the list": Very good point!
• alx - recommends codidact: "Prefer writing functions over macros": So true. That function was different internally previously, and I needed the macro, but yesterday I did some modifications, and didn't notice that it can be a static inline now!
• G. Sliepen: Ah! Indeed alx_llist_move_to() resets the current pointer. I was confused by the fact that it seemed to handle negative pos, which doesn't make any sense if it's supposed to go to an absolute position...
• G. Sliepen: Oh, it's a circular list! I completely missed that (despite it actually being in the title of your post), since it's not clear at all from the names of the functions. In fact, nowhere in linked-list.h nor linked-list.c does it mention the word "circular". Please make this explicit, by clearly having circular in the names of the structs and functions, or at least something to distinguish it from a regular linked list.

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.

• alx - recommends codidact: Thank you very much! For the two first points, I should have noticed that I require GCC extensions for my library to work. About the relative paths, I think it's safer, because I can have different files with the same name in different paths, and I don't have to care about conflicts, and the structure of my library is more or less constant; another good thing I find with this scheme is that I know that all those files come from libalx library, but that's a personal thing.
• alx - recommends codidact: About putting my includes first: That's the only point I really disagree: I follow Google's C++ style guide. I've used different include orders, and I think this is the best one I've used; it helps a lot in finding bugs. Try it!
• Edward: Either way the point is this: "You should include all the headers that define the symbols you rely upon" which is from that same style guide.
• alx - recommends codidact: Yes, I forgot to say it: All my headers include all they need; they don't depend on the caller.
• chux: "Put your own #includes first" --> Within linked-list.c, code does put linked-list.h first. The other own.h files should be first in their respective .c files. OP's include layout is good here.

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.

• alx - recommends codidact: Good catch! That bug has been in my code for a long time. I'll just add if (!size) return NULL;
• alx - recommends codidact: I set errno to ENOMEM when the input size is too large (nmemb so high that it overflows to a negative value, or a multiplication that would overflow), but if the return value of malloc is NULL because the size is 0, then I don't want errno to be ENOMEM
• chux: @CacahueteFrito Note that when malloc(non_zero) returns NULL, C does not specify errno is set to anything. So the whole reason to set errno in this surrounding code is of questionable value. I'd expect that if errno = ENOMEM is set in this function's code, for consistency, it would set errno = ENOMEM on malloc failure - instead of relying on malloc(non_zero) --> NULL maybe setting it.
• alx - recommends codidact: C doesn't, but POSIX does. I use POSIX, so I thought it would be appropriate. Given that I already rely on GCC (and also LIBBSD) extensions on my code, I don't think I should care about setting errno as if POSIX on non-POSIX systems. In fact, my Makefile defines -D _POSIX_C_SOURCE=200809L.
• chux: @CacahueteFrito The reliance on POSIX may be part of what you are doing, but it is not part of the posted question. If a C review depends on non-standard C, best to include that info in the question and tag it appropriately. Had post been a POSIX one, this answer would reflect that.

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.)

• alx - recommends codidact: Wouldn't that impose limits on the data, such as a maximum size? I'm not sure I understand it completely; especially the [-1] thing. Could you show some example, please?
• David G.: @CacahueteFrito: Yes, it would reduce the maximum size of an object by the size of the header. But this is only a significant issue if the maximum size of a memory allocation is less that the size of memory. This is the case in x86 MEDIUM or LARGE model. Otherwise, it should actually increase the allocatable memory by the size of the malloc header.
• David G.: @CacahueteFrito: The [-1] trick is something I picked up from g++'s implementation of CString. Any example I might write is otherwise contrived. The point is that if the pointer points to the start of data after the structure, then when the pointer is cast to the structure type, the structure is one before before. One could also write (((struct Alx_LLNode*)data)-1)->next Initial allocation would then be: data=rawptr+sizeof(struct Alx_LLNode) or data=(void*)(1+(struct Alx_LLNode*)rawptr)
• alx - recommends codidact: Now I understand it! A bit ugly, though xD
• David G.: @CacahueteFrito: Ugly, yes. Elegant, perhaps. Effective, yes. Isolatable to two inline-able function if desired. (initial allocation function, convert data pointer to struct ptr) Whether to expose it in a header is based on how much you want to inline in client code.