Lists

Types and helpers for doubly-linked lists.

Types

oc_list_links

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

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_links* first;
    oc_list_links* last;
    u64 count;
} 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.

oc_list_links

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

An element of a typed intrusive doubly-linked list.

Fields

prev Points to the previous element in the list.
next Points to the next 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_links 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_links 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_links 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_links element in a list.

Return

A pointer to the previous element in the list.

oc_list_elt

#define oc_list_elt(elt, type, member)

Get the entry for a given list element.

Parameters

elt A pointer to an oc_list_links element.
type The type of the entry to retrieve.
member The name of the oc_list_links 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_elt

#define oc_list_next_elt(elt, type, member)

Get the next entry in a list.

Parameters

elt A pointer to an oc_list_links element in that list.
type The type of the entry to retrieve.
member The name of the oc_list_links 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_elt

#define oc_list_prev_elt(elt, type, member)

Get the previous entry in a list.

Parameters

elt A pointer to an oc_list_links element in that list.
type The type of the entry to retrieve.
member The name of the oc_list_links 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_elt

#define oc_list_checked_elt(elt, type, member)

Same as oc_list_elt, but elt might be null.

Parameters

elt A pointer to an oc_list_links element.
type The type of the entry to retrieve.
member The name of the oc_list_links 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_elt

#define oc_list_first_elt(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_links 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_elt

#define oc_list_last_elt(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_links 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_links 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_links 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_links in type by which the list entries are linked.

oc_list_pop_front_elt

#define oc_list_pop_front_elt(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_links 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_elt

#define oc_list_pop_back_elt(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_links 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_typed_list

#define oc_typed_list(type, linksField)

Create a type specification for a typed doubly-linked list. You should use this as typedef oc_typed_list(myType) myTypeList;

Parameters

type The type of item stored in the list.
linksField The name of the oc_list_links field in type by which the items are linked in the list.

oc_typed_list_empty

#define oc_typed_list_empty(list)

Check if a list is empty.

Parameters

list An oc_typed_list linked list.

Return

true if the list is empty, false otherwise.

oc_typed_list_first

#define oc_typed_list_first(l)

Get the first element of a list.

Parameters

l An oc_typed_list list.

Return

A pointer to the first item of the list.

oc_typed_list_last

#define oc_typed_list_last(l)

Returns the last element of a list.

Parameters

l An oc_typed_list list.

Return

A pointer to the last item of the list.

oc_typed_list_next

#define oc_typed_list_next(list, elt)

Get the next element in a list.

Parameters

list An oc_typed_list list.
elt A pointer to an item in a list.

Return

A pointer to the next item in the list.

oc_typed_list_prev

#define oc_typed_list_prev(list, elt)

Get the previous element in a list.

Parameters

list An oc_typed_list list.
elt A pointer to an item in a list.

Return

A pointer to the previous item in the list.

oc_typed_list_push_front

#define oc_typed_list_push_front(list, item)

Add an element at the end of a list.

Parameters

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

oc_typed_list_push_back

#define oc_typed_list_push_back(list, item)

Add an element at the end of a list.

Parameters

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

oc_typed_list_pop_front

#define oc_typed_list_pop_front(list)

Remove the first entry from a list and return it.

Parameters

list An oc_typed_list object.

Return

A pointer to the item that was removed from the list.

oc_typed_list_pop_back

#define oc_typed_list_pop_back(list)

Remove the last entry from a list and return it.

Parameters

list An oc_typed_list object.

Return

A pointer to the item that was removed from the list.

oc_linked_list_insert_after

#define oc_linked_list_insert_after(list, after, item)

Insert an element in a list after a given element.

Parameters

list An oc_typed_list list.
after The item after which to insert.
item The item to insert in the list.

oc_linked_list_insert_before

#define oc_linked_list_insert_before(list, before, item)

Insert an element in a list before a given element.

Parameters

list An oc_typed_list list.
before The item before which to insert.
item The item to insert in the list.

oc_typed_list_remove

#define oc_typed_list_remove(list, item)

Remove an element from a typed list.

Parameters

list The list to remove from.
item The item to remove from the list.

oc_typed_list_for

#define oc_typed_list_for(list, elt)

Loop through a typed linked list.

This macro creates a loop with an iterator named after the elt macro parameter. The iterator is of 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_typed_list object.
elt The name of the loop iterator.

Note

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

oc_typed_list_for_reverse

#define oc_typed_list_for_reverse(list, elt)

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

Parameters

list An oc_typed_list object.
elt The name of the loop iterator.

oc_typed_list_for_safe

#define oc_typed_list_for_safe(list, elt)

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

Parameters

list An oc_typed_list object.
elt The name of the loop iterator.

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_insert

void oc_list_insert(oc_list* list, oc_list_links* afterElt, oc_list_links* 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_links* beforeElt, oc_list_links* 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_links* 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_links* 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_links* 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_links* 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_links* 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.