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_DROP_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 452 of file list.h.

◆ LIST_DROP_BACK

#define LIST_DROP_BACK ( list )

Value:

  do {                                                                         \
    const size_t slot_ = gv_list_get_((list)->impl, LIST_SIZE(list) - 1);      \
    LIST_DTOR_((list), slot_);                                                 \
    gv_list_pop_back_(&(list)->impl, &(list)->scratch,                         \
                      sizeof((list)->base[0]));                                \
  } while (0)

remove the last item of a list

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

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

This can be used to pop the last element when the caller does not need the popped item.

Parameters

list	List to operate on

Definition at line 431 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_DROP_BACK

◆ 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