Lists

Types and helpers for doubly-linked lists.

Types

oc_list_elt

typedef struct oc_list_elt
{
    oc_list_elt* prev;
    oc_list_elt* next;
} oc_list_elt;

An element of an intrusive doubly-linked list.

Fields

prev Points to the previous element in the list.
next Points to the next element in the list.

oc_list

typedef struct oc_list
{
    oc_list_elt* first;
    oc_list_elt* last;
} oc_list;

A doubly-linked list.

Fields

first Points to the first element in the list.
last Points to the last element in the list.

Macros

oc_list_begin

#define oc_list_begin(l)

Get the first element of a list.

Parameters

l An oc_list list.

Return

A pointer to the first oc_list_elt of the list.

oc_list_last

#define oc_list_last(l)

Returns the last element of a list.

Parameters

l An oc_list list.

Return

A pointer to the last oc_list_elt of the list.

oc_list_next

#define oc_list_next(elt)

Get the next element in a list.

Parameters

elt A pointer to an oc_list_elt element in a list.

Return

A pointer to the next element in the list.

oc_list_prev

#define oc_list_prev(elt)

Get the previous element in a list.

Parameters

elt A pointer to an oc_list_elt element in a list.

Return

A pointer to the previous element in the list.

oc_list_entry

#define oc_list_entry(elt, type, member)

Get the entry for a given list element.

Parameters

elt A pointer to an oc_list_elt element.
type The type of the entry to retrieve.
member The name of the oc_list_elt field in type by which the entry is linked into the list.

Return

A pointer to the entry of type type which is linked into the list by element elt.

oc_list_next_entry

#define oc_list_next_entry(list, elt, type, member)

Get the next entry in a list.

Parameters

list An oc_list object.
elt A pointer to an oc_list_elt element in that list.
type The type of the entry to retrieve.
member The name of the oc_list_elt field in type by which the entry is linked into the list.

Return

A pointer to the entry of type type which is linked into the list after element elt.

oc_list_prev_entry

#define oc_list_prev_entry(list, elt, type, member)

Get the previous entry in a list.

Parameters

list An oc_list object.
elt A pointer to an oc_list_elt element in that list.
type The type of the entry to retrieve.
member The name of the oc_list_elt field in type by which the entry is linked into the list.

Return

A pointer to the entry of type type which is linked into the list before element elt.

oc_list_checked_entry

#define oc_list_checked_entry(elt, type, member)

Same as oc_list_entry, but elt might be null.

Parameters

elt A pointer to an oc_list_elt element.
type The type of the entry to retrieve.
member The name of the oc_list_elt field in type by which the entry is linked into the list.

Return

If elt is null, the macro returns a null pointer. Otherwise it returns a pointer to the entry of type type which is linked into the list by element elt.

oc_list_first_entry

#define oc_list_first_entry(list, type, member)

Get the first entry of a list.

Parameters

list An oc_list object.
type The type of the entry to retrieve.
member The name of the oc_list_elt field in type by which the entry is linked into the list.

Return

A pointer to the entry of type type which is the first entry in the list.

oc_list_last_entry

#define oc_list_last_entry(list, type, member)

Get the last entry of a list.

Parameters

list An oc_list object.
type The type of the entry to retrieve.
member The name of the oc_list_elt field in type by which the entry is linked into the list.

Return

A pointer to the entry of type type which is the last entry in the list.

oc_list_for

#define oc_list_for(list, elt, type, member)

Loop through a linked list.

This macro creates a loop with an iterator named after the elt macro parameter. The iterator is of the type specified by the type macro parameter, which must be the type of the entries linked in the list.

You should follow this macro with the loop body, where you can use the iterator.

Parameters

list An oc_list object.
elt The name of the loop iterator.
type The type of the loop iterator. This must be the type of the entries linked in list.
member The name of the field of type oc_list_elt in type by which the list entries are linked.

Note

You should not add or remove elements from the list inside the loop body. If you need to do so, use oc_list_for_safe instead.

oc_list_for_reverse

#define oc_list_for_reverse(list, elt, type, member)

Loop through a linked list from last to first. See oc_list_for for details.

Parameters

list An oc_list object.
elt The name of the loop iterator.
type The type of the loop iterator. This must be the type of the entries linked in list.
member The name of the field of type oc_list_elt in type by which the list entries are linked.

oc_list_for_safe

#define oc_list_for_safe(list, elt, type, member)

Loop through a linked list in a way that allows adding or removing elements from it in the loop body. See oc_list_for for more details.

Parameters

list An oc_list object.
elt The name of the loop iterator.
type The type of the loop iterator. This must be the type of the entries linked in list.
member The name of the field of type oc_list_elt in type by which the list entries are linked.

oc_list_pop_front_entry

#define oc_list_pop_front_entry(list, type, member)

Remove the first entry from a list and return it.

Parameters

list An oc_list object.
type The type of the entry to retrieve.
member The name of the field of type oc_list_elt in type by which the list entries are linked.

Return

A pointer of type type to the entry that was removed from the list.

oc_list_pop_back_entry

#define oc_list_pop_back_entry(list, type, member)

Remove the last entry from a list and return it.

Parameters

list An oc_list object.
type The type of the entry to retrieve.
member The name of the field of type oc_list_elt in type by which the list entries are linked.

Return

A pointer of type type to the entry that was removed from the list.

Functions

oc_list_empty

bool oc_list_empty(oc_list list);

Check if a list is empty.

Parameters

list A linked list.

Return

true if the list is empty, false otherwise.

oc_list_init

void oc_list_init(oc_list* list);

Zero-initializes a linked list.

Parameters

list A pointer to the list to initialize.

Note

In C the same result can be achieved with *list = (oc_list){0}.

oc_list_insert

void oc_list_insert(oc_list* list, oc_list_elt* afterElt, oc_list_elt* elt);

Insert an element in a list after a given element.

Parameters

elt The element to insert in the list.

oc_list_insert_before

void oc_list_insert_before(oc_list* list, oc_list_elt* beforeElt, oc_list_elt* elt);

Insert an element in a list before a given element.

Parameters

list The list to insert in.
beforeElt The element before which to insert.
elt The element to insert in the list.

oc_list_remove

void oc_list_remove(oc_list* list, oc_list_elt* elt);

Remove an element from a list.

Parameters

list The list to remove from.
elt The element to remove from the list.

oc_list_push_back

void oc_list_push_back(oc_list* list, oc_list_elt* elt);

Add an element at the end of a list.

Parameters

list The list to add an element to.
elt The element to add to the list.

oc_list_pop_back

oc_list_elt* oc_list_pop_back(oc_list* list);

Remove the last element from a list.

Parameters

list The list to remove an element from.

Return

The element that was removed, or a null pointer if the list was empty.

oc_list_push_front

void oc_list_push_front(oc_list* list, oc_list_elt* elt);

Add an element at the beginning of a list.

Parameters

list The list to add an element to.
elt The element to add to the list.

oc_list_pop_front

oc_list_elt* oc_list_pop_front(oc_list* list);

Remove the first element from a list.

Parameters

list The list to remove an element from.

Return

The element that was removed, or a null pointer if the list was empty.