Graphviz: lib/util/list.h File Reference

Searching...

No Matches

type-generic dynamically expanding list More...

#include <assert.h>
#include <stdint.h>
#include <string.h>
#include <util/list-private.h>

Include dependency graph for list.h:

This graph shows which files directly or indirectly include this file:

Macros
#define	LIST(type)

#define	LIST_DTOR_FREE ((void *)1)

#define	LIST_SIZE(list) gv_list_size_((list)->impl)

#define	LIST_IS_EMPTY(list) (LIST_SIZE(list) == 0)

#define	LIST_TRY_APPEND(list, item)

#define	LIST_APPEND(list, item)

#define	LIST_PREPEND(list, item)

#define	LIST_GET(list, index) ((list)->base[gv_list_get_((list)->impl, (index))])

#define	LIST_AT(list, index) (&(list)->base[gv_list_get_((list)->impl, (index))])

#define	LIST_FRONT(list) LIST_AT((list), 0)

#define	LIST_BACK(list) LIST_AT((list), LIST_SIZE(list) - 1)

#define	LIST_SET(list, index, item)

#define	LIST_REMOVE(list, item)

#define	LIST_CLEAR(list)

#define	LIST_RESERVE(list, capacity) gv_list_reserve_(&(list)->impl, capacity, sizeof((list)->base[0]))

#define	LIST_CONTAINS(list, needle)

#define	LIST_COPY(dst, src)

#define	LIST_IS_CONTIGUOUS(list) gv_list_is_contiguous_((list)->impl);

#define	LIST_SYNC(list) gv_list_sync_(&(list)->impl, sizeof((list)->base[0]))

#define	LIST_SORT(list, cmp) gv_list_sort_(&(list)->impl, (cmp), sizeof((list)->base[0]))

#define	LIST_REVERSE(list) gv_list_reverse_(&(list)->impl, sizeof((list)->base[0]))

#define	LIST_SHRINK_TO_FIT(list) gv_list_shrink_to_fit_(&(list)->impl, sizeof((list)->base[0]))

#define	LIST_FREE(list)

#define	LIST_PUSH_BACK(list, item) LIST_APPEND((list), (item))

#define	LIST_POP_FRONT(list)

#define	LIST_POP_BACK(list)

#define	LIST_DETACH(list, datap, sizep)

Detailed Description

The code in this header is structured as a public API made up of macros that do as little as possible before handing off to internal functions.

If you are familiar with the concept of a dynamically expanding array like C++’s std::vector, the only things that will likely throw you off are:

The genericity of LIST is implemented through a union that overlaps the base member of a list_t_ (a generic list core) with a typed pointer. This design involves the public macros dealing in the LIST(foo) type while the private functions deal in list_t_s.
The start of the list is not always index 0, in order to more efficiently implement a queue. See the diagram and discussion in try_reserve to better understand this.

Some general terminology you may see in function/macro names: base – the start of the underlying heap allocation backing a list dtor – destructor head – slot index of the start of a list item – a list element slot – an item-sized space in the list, offset recorded from base

Some unorthodox idioms you may see used in this file: • (void)(foo == bar) as a way to force the compiler to type-check that foo and bar have compatible types. This is the best we can do for pointer compatibility checks without typeof. • (void)(sizeof(foo) == sizeof(bar) ? (void)0 : (void)(…,abort()) as an even weaker version of the above, for when we need to delay a check to runtime instead of compile-time. This is a very unreliable check for foo and bar being the same type, so should be avoided wherever possible.

Definition in file list.h.

Macro Definition Documentation

◆ LIST

#define LIST ( type )

Value:

  struct {                                                                     \
    union {                                                                    \
      type *base;                                                              \
      list_t_ impl;                                                            \
    };                                                  \
    void (*dtor)(type);                             \
    type scratch;            \
  }

list data structure

Typical usage:

LIST(int) my_int_list = {0};

Definition at line 55 of file list.h.

◆ LIST_APPEND

#define LIST_APPEND	(	list,
		item
	)

Value:

  do {                                                                         \
    const size_t slot_ =                                                       \
        gv_list_append_slot_(&(list)->impl, sizeof((list)->base[0]));          \
    (list)->base[slot_] = (item);                                              \
  } while (0)

add an item to the end of a list

You can think of this macro as having the C type:

void LIST_APPEND(LIST(<type>) *list, <type> item);

This macro succeeds or exits on out-of-memory; it never return failure.

Note, in contrast to LIST_TRY_APPEND, gv_list_append_slot_ and the write to (list)->base[…] are in separate statements because the gv_list_append_slot_ call here can alter (list)->base.

Parameters

list	List to operate on
item	Element to append

Definition at line 132 of file list.h.

◆ LIST_AT

#define LIST_AT	(	list,
		index
	)	(&(list)->base[gv_list_get_((list)->impl, (index))])

retrieve a pointer to an item from a list

You can think of this macro as having one of the C types:

<type> *LIST_AT(LIST(<type>) *list, size_t index); const <type> *LIST_AT(const LIST(<type>) *list, size_t index);

Parameters

list	List to operate on
index	Item index to get

Returns: Pointer to item at the given index

Definition at line 178 of file list.h.

◆ LIST_BACK

#define LIST_BACK ( list ) LIST_AT((list), LIST_SIZE(list) - 1)

retrieve a pointer to the last item in a list

You can think of this macro as having one of the C types:

<type> *LIST_BACK(LIST(<type>) *list); const <type> *LIST_BACK(const LIST(<type>) *list);

Parameters

list	List to operate on

Returns: Pointer to the last item in the list

Definition at line 201 of file list.h.

◆ LIST_CLEAR

#define LIST_CLEAR ( list )

Value:

  do {                                                                         \
    for (size_t i_ = 0; i_ < LIST_SIZE(list); ++i_) {                          \
      const size_t slot_ = gv_list_get_((list)->impl, i_);                     \
      LIST_DTOR_((list), slot_);                                               \
    }                                                                          \
    gv_list_clear_(&(list)->impl, sizeof((list)->base[0]));                    \
  } while (0)

remove all items from a list

You can think of this macro as having the C type:

void LIST_CLEAR(LIST(<type>) *list);

Parameters

list	List to clear

Definition at line 249 of file list.h.

◆ LIST_CONTAINS

#define LIST_CONTAINS	(	list,
		needle
	)

Value:

  gv_list_contains_((list)->impl,                                              \
                    ((void)((list)->base == &(needle)), &(needle)),            \
                    sizeof((list)->base[0]))

does a list contain a given item?

You can think of this macro as having the C type:

bool LIST_CONTAINS(const LIST(<type>) *list, <type> needle);

The needle parameter must be an expression that can have its address taken. E.g. LIST_CONTAINS(my_ints, 2) is not valid. This can be worked around with C99 compound literals, LIST_CONTAINS(my_ints, (int){2}).

Parameters

list	List to search
needle	Item to search for

Returns: True if the item was found

Definition at line 282 of file list.h.

◆ LIST_COPY

#define LIST_COPY	(	dst,
		src
	)

Value:

  do {                                                                         \
    (void)((dst)->base == (src)->base);                                        \
    memset((dst), 0, sizeof(*(dst)));                                          \
    (dst)->impl = gv_list_copy_((src)->impl, sizeof((src)->base[0]));          \
    (dst)->dtor = (src)->dtor;                                                 \
  } while (0)

copy a list

You can think of this macro as having the C type:

void LIST_COPY(LIST(<type>) *dst, const LIST(<type>) *src);

Parameters

[out]	dst	Copy of the source list on completion
	src	List to copy

Definition at line 295 of file list.h.

◆ LIST_DETACH

#define LIST_DETACH	(	list,
		datap,
		sizep
	)

Value:

  do {                                                                         \
    *(datap) = (list)->base;                                                   \
    *(sizep) = (list)->impl.size;                                              \
                                                                               \
    (list)->impl = (list_t_){0};                                               \
  } while (0)

transform a managed list into a bare array

You can think of this macro as having the C type:

void LIST_DETACH(LIST(<type>) *list, <type> **data, size_t *size);

This can be useful when needing to pass data to a callee who does not use this API. The managed list is emptied and left in a state where it can be reused for other purposes.

Parameters

	list	List to operate on
[out]	data	The list data on completion
[out]	size	The list size on completion

Definition at line 434 of file list.h.

◆ LIST_DTOR_FREE

#define LIST_DTOR_FREE ((void *)1)

sentinel value to indicate you want free to be used as a list destructor

Sample usage:

LIST(char *) my_strings = {.dtor = LIST_DTOR_FREE};

Definition at line 70 of file list.h.

◆ LIST_FREE

#define LIST_FREE ( list )

Value:

  do {                                                                         \
    LIST_CLEAR(list);                                                          \
    gv_list_free_(&(list)->impl);                                              \
  } while (0)

free resources associated with a list

You can think of this macro as having the C type:

void LIST_FREE(LIST(<type>) *list);

After a call to this function, the list is empty and may be reused.

Parameters

list	List to free

Definition at line 379 of file list.h.

◆ LIST_FRONT

#define LIST_FRONT ( list ) LIST_AT((list), 0)

retrieve a pointer to the first item in a list

You can think of this macro as having one of the C types:

<type> *LIST_FRONT(LIST(<type>) *list); const <type> *LIST_FRONT(const LIST(<type>) *list);

Parameters

list	List to operate on

Returns: Pointer to the first item in the list

Definition at line 190 of file list.h.

◆ LIST_GET

#define LIST_GET	(	list,
		index
	)	((list)->base[gv_list_get_((list)->impl, (index))])

retrieve an item from a list

You can think of this macro as having the C type:

<type> LIST_GET(const LIST(<type>) *list, size_t index);

Parameters

list	List to operate on
index	Item index to get

Returns: Item at the given index

Definition at line 165 of file list.h.

◆ LIST_IS_CONTIGUOUS

#define LIST_IS_CONTIGUOUS ( list ) gv_list_is_contiguous_((list)->impl);

does the list not wrap past its end?

This checks whether the list is discontiguous in how its elements appear in memory:

                    ┌───┬───┬───┬───┬───┬───┬───┬───┐

a contiguous list: │ │ │ w │ x │ y │ z │ │ │ └───┴───┴───┴───┴───┴───┴───┴───┘ 0 1 2 3

┌───┬───┬───┬───┬───┬───┬───┬───┐ a discontiguous list: │ y │ z │ │ │ │ │ x │ y │ └───┴───┴───┴───┴───┴───┴───┴───┘ 2 3 0 1

You can think of this macro as having the C type:

bool LIST_IS_CONTIGUOUS(const LIST(<type>>) *list);

Parameters

list	List to inspect

Returns: True if the list is contiguous

Definition at line 324 of file list.h.

◆ LIST_IS_EMPTY

#define LIST_IS_EMPTY ( list ) (LIST_SIZE(list) == 0)

does this list contain no elements?

You can think of this macro as having the C type:

bool LIST_IS_EMPTY(const LIST(<type>) *list);

Parameters

list	List to inspect

Returns: True if the list is empty

Definition at line 90 of file list.h.

◆ LIST_POP_BACK

#define LIST_POP_BACK ( list )

Value:

  (gv_list_pop_back_(&(list)->impl, &(list)->scratch,                          \
                     sizeof((list)->base[0])),                                 \
   (list)->scratch)

remove and return the last item of a list

You can think of this macro as having the C type:

<type> LIST_POP_BACK(LIST(<type>) *list);

Parameters

list	List to operate on

Returns: Popped item

Definition at line 416 of file list.h.

◆ LIST_POP_FRONT

#define LIST_POP_FRONT ( list )

Value:

  (gv_list_pop_front_(&(list)->impl, &(list)->scratch,                         \
                      sizeof((list)->base[0])),                                \
   (list)->scratch)

remove and return the first item of a list

You can think of this macro as having the C type:

<type> LIST_POP_FRONT(LIST(<type>) *list);

Parameters

list	List to operate on

Returns: Popped item

Definition at line 403 of file list.h.

◆ LIST_PREPEND

#define LIST_PREPEND	(	list,
		item
	)

Value:

  do {                                                                         \
    const size_t slot_ =                                                       \
        gv_list_prepend_slot_(&(list)->impl, sizeof((list)->base[0]));         \
    (list)->base[slot_] = (item);                                              \
  } while (0)

add an item to the beginning of a list

You can think of this macro as having the C type:

void LIST_PREPEND(LIST(<type>) *list, <type> item);

This macro succeeds or exits on out-of-memory; it never return failure.

Parameters

list	List to operate on
item	Element to prepend

Definition at line 149 of file list.h.

◆ LIST_PUSH_BACK

#define LIST_PUSH_BACK	(	list,
		item
	)	LIST_APPEND((list), (item))

alias for append

You can think of this macro as having the C type:

void LIST_PUSH_BACK(LIST(<type>) *list, <type> item);

Parameters

list	List to operate on
item	Item to append

Definition at line 393 of file list.h.

◆ LIST_REMOVE

#define LIST_REMOVE	(	list,
		item
	)

Value:

  do {                                                                         \
    /* get something we can take the address of */                             \
    (list)->scratch = (item);                                                  \
                                                                               \
    const size_t found_ = gv_list_find_((list)->impl, &(list)->scratch,        \
                                        sizeof((list)->base[0]));              \
    if (found_ == SIZE_MAX) { /* not found */                                  \
      break;                                                                   \
    }                                                                          \
                                                                               \
    LIST_DTOR_((list), found_);                                                \
    gv_list_remove_(&(list)->impl, found_, sizeof((list)->base[0]));           \
  } while (0)

remove an item from a list

You can think of this macro as having the C type:

void LIST_REMOVE(LIST(<type>) *list, <type> item);

Parameters

list	List to operate on
item	Item to remove

Definition at line 227 of file list.h.

◆ LIST_RESERVE

#define LIST_RESERVE	(	list,
		capacity
	)	gv_list_reserve_(&(list)->impl, capacity, sizeof((list)->base[0]))

reserve space for new items in a list

You can think of this macro as having the C type:

void LIST_RESERVE(LIST(<type>) *list, size_t capacity);

Parameters

list	List to operate on
capacity	Total number of item slots to make available

Definition at line 266 of file list.h.

◆ LIST_REVERSE

#define LIST_REVERSE ( list ) gv_list_reverse_(&(list)->impl, sizeof((list)->base[0]))

reverse the item order of a list

You can think of this macro as having the C type:

void LIST_REVERSE(LIST(<type>) *list);

Parameters

list	List to operate on

Definition at line 357 of file list.h.

◆ LIST_SET

#define LIST_SET	(	list,
		index,
		item
	)

Value:

  do {                                                                         \
    const size_t slot_ = gv_list_get_((list)->impl, (index));                  \
    LIST_DTOR_((list), slot_);                                                 \
    (list)->base[slot_] = (item);                                              \
  } while (0)

update the value of an item in a list

You can think of this macro as having the C type:

void LIST_SET(LIST(<type>) *list, size_t index, <type> item);

Parameters

list	List to operate on
index	Index of item to update
item	New value to set

Definition at line 212 of file list.h.

◆ LIST_SHRINK_TO_FIT

#define LIST_SHRINK_TO_FIT ( list ) gv_list_shrink_to_fit_(&(list)->impl, sizeof((list)->base[0]))

decrease the allocated capacity of a list to minimum

You can think of this macro as having the C type:

void LIST_SHRINK_TO_FIT(LIST(<type>) *list);

Parameters

list	List to operate on

Definition at line 367 of file list.h.

◆ LIST_SIZE

#define LIST_SIZE ( list ) gv_list_size_((list)->impl)

get the number of elements in a list

You can think of this macro as having the C type:

size_t LIST_SIZE(const LIST(<type>) *list);

Parameters

list	List to inspect

Returns: Size of the list

Definition at line 80 of file list.h.

◆ LIST_SORT

#define LIST_SORT	(	list,
		cmp
	)	gv_list_sort_(&(list)->impl, (cmp), sizeof((list)->base[0]))

sort a list

You can think of this macro as having the C type:

void LIST_SORT(LIST(<type>) *list, int (*comparator)(const void *a, const void *b));

Parameters

list	List to operate on
comparator	How to compare two list items

Definition at line 347 of file list.h.

◆ LIST_SYNC

#define LIST_SYNC ( list ) gv_list_sync_(&(list)->impl, sizeof((list)->base[0]))

shuffle the populated contents to reset head to 0

You can think of this macro as having the C type:

void LIST_SYNC(LIST(<type>) *list);

See the LIST_IS_CONTIGUOUS leading comment for a better understanding of what it means for head to be non-zero.

Parameters

list	List to operate on

Definition at line 336 of file list.h.

◆ LIST_TRY_APPEND

#define LIST_TRY_APPEND	(	list,
		item
	)

Value:

  (((list)->impl.size < (list)->impl.capacity ||                               \
    gv_list_try_reserve_(                                                      \
        &(list)->impl,                                                         \
        (list)->impl.capacity == 0 ? 1 : ((list)->impl.capacity * 2),          \
        sizeof((list)->base[0])) ||                                            \
    gv_list_try_reserve_(&(list)->impl, (list)->impl.capacity + 1,             \
                         sizeof((list)->base[0]))) &&                          \
   (((list)->base[gv_list_append_slot_(&(list)->impl,                          \
                                       sizeof((list)->base[0]))] = (item)),    \
    1))

try to append a new item to a list

You can think of this macro as having the C type:

bool LIST_TRY_APPEND(LIST(<type>) *list, <type> item);

Note that referencing (list)->base and calling gv_list_append_slot_ within a single expression without an intervening sequence point is OK because, after the preceding reservation probes, we know gv_list_append_slot_ will not alter (list)->base.

Parameters

list	List to operate on
item	Item to append

Returns: True if the append succeeded

Definition at line 106 of file list.h.

Macros

Detailed Description

Macro Definition Documentation

◆ LIST

◆ LIST_APPEND

◆ LIST_AT

◆ LIST_BACK

◆ LIST_CLEAR

◆ LIST_CONTAINS

◆ LIST_COPY

◆ LIST_DETACH

◆ LIST_DTOR_FREE

◆ LIST_FREE

◆ LIST_FRONT

◆ LIST_GET

◆ LIST_IS_CONTIGUOUS

◆ LIST_IS_EMPTY

◆ LIST_POP_BACK

◆ LIST_POP_FRONT

◆ LIST_PREPEND

◆ LIST_PUSH_BACK

◆ LIST_REMOVE

◆ LIST_RESERVE

◆ LIST_REVERSE

◆ LIST_SET

◆ LIST_SHRINK_TO_FIT

◆ LIST_SIZE

◆ LIST_SORT

◆ LIST_SYNC

◆ LIST_TRY_APPEND