Libwebsockets lws_dll2

Overview

• CMake options: part of core lws
• Public header: (included by libwebsockets.h) include/libwebsockets/lws-dll2.h
• Implementation: lib/core/lws-dll2.c

lws_dll2 is a smart doubly-linked list that simplifies lists while remaining without implementation restrictions or bloat.

lws_dll2 is used throughout lws and is a public export for a few versions now. It’s mature, flexible, robust and leads to restriction-free, readable and maintainable code. And it’s more featureful than generic linked-list abstractions.

Basic approach

There are two objects involved, a singular lws_dll2_owner_t and in every object that will join the list, a lws_dll2_t. This provides some useful characteristics:

• you compose lws_dll2_owner_t and lws_dll2_t objects into your objects that own and participate in lists. The lws_dll2 apis take care of maintaining all the relationships between objects.

• all lws_dll2... objects themselves point to lws_dll2... objects, not your objects you composed them into. You can recover your object pointer using lws_container_of() explained below

• your objects can exist on multiple lists with different owners, you need one lws_dll2_t in your object per list it will participate on

• lws_dll2_ objects can go anywhere in your struct, they don’t have to go at the start or anything like that

• you must remove your object from any lists it is on before destroying it

• you can remove an lws_dll2_t from its owner without having to track or know who the owner is. Objects that may belong to different owners (eg, pending and done lists) are simple to implement.

• if your object is on an list owner in another object, you can always recover a pointer to the owning object for free

lws_dll2 common Apis

api	description
lws_dll2_add_head(lws_dll2_t d, lws_dll2_owner_t owner)	insert at start of owner list
lws_dll2_add_tail(lws_dll2_t d, lws_dll2_owner_t owner)	insert at end of owner list
lws_dll2_remove(lws_dll2_t *d)	remove from owner list
lws_dll2_get_head(lws_dll2_t *d)	get pointer to first object’s lws_dll2_t on list
lws_dll2_get_tail(lws_dll2_t *d)	get pointer to last object’s lws_dll2_t on list
lws_dll2_foreach_safe(lws_dll2_owner_t owner, void user, int (cb)(struct lws_dll2 d, void *user))	Callback for each entry on owner’s list
lws_dll2_add_sorted(lws_dll2_t d, lws_dll2_owner_t own, int (compare)(const lws_dll2_t d, const lws_dll2_t *i))	Use compare to figure out where to insert object into owner’s list

Example

Say you have your own struct already that you want to “own” a list, you just need to embed an lws_dll2_owner_t member in it.

    struct mystruct {
        ...
        lws_dll2_owner_t mylistowner;
        ...
    };

you can have n of those and there’s no requirements about where they go in the struct.

Then in the struct type that will appear on an lws_dll2 list

    struct myitems {
        ...
        lws_dll2_t list;
        ...
    }

Again you can have n of these, ie, an object can appear on multiple lws_dll2_ lists, so long as there is a different lws_dll2_t per list it’s on, and no ordering requirement.

No init is required to use the list objects except the should be zeroed-down from the start… you can explicitly ensure this by using lws_dll2_clear() and lws_dll2_owner_clear() if necessary.

To add to the list

    struct mystruct *mystruct;
    struct myitems *myitem;

    myitem = zalloc(sizeof(*myitem));
    if (!myitem)
        return 1;

    lws_dll2_add_tail(&myitem->list, &mystruct->mylistowner);

To walk the items on the list (using a callback)

static int
my_cb(lws_dll2_t *p, void *user)
{
    struct myitems *myitem = lws_container_of(o, struct myitems, list);

    ...

    return 0;
}

...
    lws_dll2_foreach_safe(mystruct->mylistowner, somepointer, mycb);

This calls back mycb with a pointer to every struct myitem on the list… somepointer is passed to the callback’s user parameter, it can be NULL or something of interest to the callback.

Notice that inside the callback, the pointer to .list used by lws_dll2 is converted back into a pointer to the struct myitems that contains the list, where it can be used as normal.

The _safe in lws_dll2_foreach_safe() refers to it being safe to remove the object from the owner during the callback (and, if desired, destroy it), without disturbing the list walk action.

In the case you want to walk the list inline, there’s a slighly more complex way using a helper, it looks like

    lws_start_foreach_dll_safe(struct lws_dll2 *, p, p1, mystruct->listowner.head)
        struct myitems *myitem = lws_container_of(p, struct myitems, list);

        ...
    lws_end_foreach_dll_safe(p, p1)

the functionality is the same as lws_dll2_foreach_safe() but you may find it more convenient to access local vars that are in scope without passing them into a callback. p and p1 are arbitrary temp symbols that should not conflict with anything already in scope and do not need additional init or declaration.

Sorted insertion

Although it’s done linearly, under some conditions the lws_dll2_add_sorted() may save you a lot of difficulty, it scans the existing list from the head forward calling a provided callback to determine if the new item should be inserted there… how it assesses the sorting order is arbitrary and is up to the callback you provide… it could compare strings in the objects, or numbers or some more complex function.

What did we learn this time?

• linked-lists are highly desirable abstractions because they don’t waste unused space and suffer from limits of preallocated arrays.

• lws_dll2 offers bidi lists and a single object can appear on multiple lists.

• Objects know which list their lws_dll2 is on and how many items are on a list cheaply

• Walking lists and recovering object pointers is cheap

• Sorted link-list insertion with user-defined comparison callback is supported.