Improve your memory management skills with Linked Lists 🔗

In Embedded C, memory management was one of the hardest things about software development for me to master. I was constantly struggling trying to figure out buffer sizes and access to shared memory.

Until I learned about "Embedded Linked Lists"! They were a real game changer!

Linked Lists

Before we start here's a little refresher from Wikipedia (with a few changes to make it sound more "C like")

A linked list [is a struct with] two fields: a value and a [pointer] to the next node. The last node is linked to [NULL] used to signify the end of the list.

Linked Lists have the big advantage that they do not need a pre-allocated big block of memory. Instead, Linked Lists can be

• spread across memory locations
• dynamically allocated

But even with static memory as often used in Embedded C, Linked Lists are very useful.

A simple HTTP client

Let's look at an HTTP client for example, which can only do one request at a time and should therefore queue pending requests.

But: How long should the queue be? 🤔
Enter: Linked Lists! 💡

// http_client.h

/**
 * Do a HTTP GET on the given request
 *
 * Params:
 * - new_request: A struct with the Request data
 *   (URL, custom header fields, etc)
 *
 * Returns:
 * - 0 if the request was accepted and started immediately 
 * - 1 if the request was queued
 * - < 0 on error
 */
int http_get(struct http_request *new_request);

Embedding Linked Lists into struct http_request

The trick to using linked lists in Embedded C is putting the pointer to the next node inside your struct. That way the applications must take care of the memory management and no more guessing on the side of the HTTP client 🙌

// http_client.h

/** 
 * A struct that contains all the data 
 * for the HTTP request such as the URL 
 */
struct http_request {
    /** A pointer to the next HTTP request to perform */
    struct http_request *next_request;

    /** The URL to GET */
    char *url;
    // ...
    // Other field omitted for brevity
};

Handling the request list in http_get

Inside the HTTP client you keep a reference to the start of the list and simply add every new request to the end of the list

// http_client.c

/** 
 * A pointer to the current HTTP request or NULL if 
 * no request is pending
 */
static struct http_request *current_request = NULL;

int http_get(struct http_request *new_request) {
    // Check if we have an ongoing HTTP request
    if(NULL != current_request) {
        // We have a request ongoing and will add the
        // new request to the end of the list
        struct http_request *req = current_request;
        while(NULL != req->next_request) {
            req = req->next_request;
        }
        req->next_request = new_request
    } else {
        // No ongoing HTTP request, can start with current_request
    }
}

When the current request has finished, simply take the next item from the list until all requests are complete.

// http_client.c

int http_get(struct http_request *new_request) {
    // ...

    // Finished current HTTP request,
    // check if there is another one queued
    current_request = current_request->next_request;
    if(NULL != current_request) {
        // Have an HTTP request queued, start with it now
    }
}

Conclusion

And that's it. This simple but effective method allows you to write a powerfull queueing mechanism without any memory overhead.
If you are interested in seeing real world use of Linked Lists in Embedded Operating systems you can find them for Example in Contiki OS and Contiki-NG (and I'm pretty sure if I knew the Zephyr code base better I would find it there as well Winking face)

Thanks for making it this far! If you learned something from this, consider following me for more IoT, and Embedded Software development content here and an Twitter! 👋

Cover Image by Ioan Sameli