Header-only Linked List in C

This is a header-only linked list library written in C.

Table of Contents

1. About the Project
2. Project Status
3. Getting Started
   1. Requirements
      1. git-lfs
      2. Meson Build System
   2. Getting the Source
   3. Building
4. Configuration Options
5. Documentation
6. Need Help?
7. Contributing
8. Further Reading
9. Authors
10. License
11. Acknowledgments

About the Project

This is a header-only linked list library implemented in C. This code has been carried with me and improved over the years. With some research it seems that the implementation that passed into my hands was based on the Linux Kernel's implementation.

You can copy this header to your own projects, or you can consume this repository as a Meson subproject. With Meson, the header can be added to the relevant build components with the c_linked_list_dep variable.

To use this library, embed an ll_t element in a structure:

typedef struct
{
    ll_t node;
    size_t size;
    char* block;
} alloc_node_t;

You then need to declare a linked list variable using the LIST_INIT macro:

LIST_INIT(free_list);

Operations on the list primarily operate through your ll_t struct element.

To add a new element to the list, you can use list_add (or list_add_tail, or list_insert) to add the ll_t element to the desired list variable.

// Note the pointer to the node element!
list_add(&new_memory_block->node, &free_list);

Removing an element only requires the node variable:

list_del(&found_block->node);

Functions for iterating over the list are also provided:

// Declare a variable to hold a pointer to the current element 
// in the processing loop
alloc_node_t* current_block = NULL;

// Iterate over each element in the list
// First param is a variable in your struct type
// Second param is the list to iterate over
// Third param is the ll_t element in your struct type.
list_for_each_entry(current_block, &free_list, node)
{
    // perform an operation on current_block
}

Full documentation and a complete list of available functions can be found in the ll.h file.

For a full example of this library in action, see embeddedartistry/libmemory and the "freelist" implementation.

Back to top

Project Status

This header implementation has been constant for years.

Since the header is now in a standalone repository, I would like to add test cases.

Back to top

Getting Started

Requirements

This project uses Embedded Artistry's standard Meson build system, and dependencies are described in detail on our website.

At a minimum you will need:

• git-lfs, which is used to store binary files in this repository
• Meson is the build system
• Some kind of compiler for your target system.
  • This repository has been tested with:
    • gcc-7, gcc-8, gcc-9
    • arm-none-eabi-gcc
    • Apple clang
    • Mainline clang

git-lfs

This project stores some files using git-lfs.

To install git-lfs on Linux:

sudo apt install git-lfs

To install git-lfs on OS X:

brew install git-lfs

Additional installation instructions can be found on the git-lfs website.

Meson Build System

The Meson build system depends on python3 and ninja-build.

To install on Linux:

sudo apt-get install python3 python3-pip ninja-build

To install on OSX:

brew install python3 ninja

Meson can be installed through pip3:

pip3 install meson

If you want to install Meson globally on Linux, use:

sudo -H pip3 install meson

Back to top

Getting the Source

This project uses git-lfs, so please install it before cloning. If you cloned prior to installing git-lfs, simply run git lfs pull after installation.

This project is hosted on GitHub. You can clone the project directly using this command:

git clone --recursive https://github.com/embeddedartistry/c-linked-list

If you don't clone recursively, be sure to run the following command in the repository or your build will fail:

git submodule update --init

Back to top

Building

If Make is installed, the library can be built by issuing the following command:

make

This will build all targets for your current architecture.

You can clean builds using:

make clean

You can eliminate the generated buildresults folder using:

make distclean

You can also use meson directly for compiling.

Create a build output folder:

meson buildresults

And build all targets by running

ninja -C buildresults

Full instructions for working with the build system, including topics like using alternate toolchains and running supporting tooling, are documented in Embedded Artistry's Standardized Meson Build System on our website.

Back to top

Configuration Options

The following meson project options can be set for this library when creating the build results directory with meson, or by using meson configure:

• disable-builtins will tell the compiler not to generate built-in function
• disable-stack-protection will tell the compiler not to insert stack protection calls
• enable-pedantic: Turn on pedantic warnings
• enable-pedantic-error: Turn on pedantic warnings and errors

Options can be specified using -D and the option name:

meson buildresults -Ddisable-builtins=false

The same style works with meson configure:

cd buildresults
meson configure -Ddisable-builtins=false

Back to top

Documentation

Documentation can be built locally by running the following command:

make docs

Documentation can be found in buildresults/docs, and the root page is index.html.

Back to top

Need help?

If you need further assistance or have any questions, please file a GitHub issue or send us an email using the Embedded Artistry Contact Form.

You can also reach out on Twitter: mbeddedartistry.

Contributing

If you are interested in contributing to this project, please read our contributing guidelines.

Authors

• Phillip Johnston

License

Copyright © 2022 Embedded Artistry LLC

See the LICENSE file for licensing details.

Back to top