list-private.h File Reference

internal implementation details of list.h More...

#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <util/api.h>

Include dependency graph for list-private.h:

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

Go to the source code of this file.

Data Structures
struct	list_t_

Macros
#define	LIST_DTOR_(list, slot)

Functions
static size_t	gv_list_size_ (const list_t_ list)
UTIL_API bool	gv_list_try_reserve_ (list_t_ *list, size_t capacity, size_t item_size)
UTIL_API size_t	gv_list_append_slot_ (list_t_ *list, size_t item_size)
UTIL_API size_t	gv_list_prepend_slot_ (list_t_ *list, size_t item_size)
UTIL_API size_t	gv_list_get_ (const list_t_ list, size_t index)
UTIL_API size_t	gv_list_find_ (const list_t_ list, const void *needle, size_t item_size)
UTIL_API void	gv_list_remove_ (list_t_ *list, size_t index, size_t item_size)
UTIL_API void	gv_list_clear_ (list_t_ *list, size_t item_size)
UTIL_API void	gv_list_reserve_ (list_t_ *list, size_t capacity, size_t item_size)
UTIL_API bool	gv_list_contains_ (const list_t_ list, const void *needle, size_t item_size)
UTIL_API list_t_	gv_list_copy_ (const list_t_ list, size_t item_size)
UTIL_API bool	gv_list_is_contiguous_ (const list_t_ list)
UTIL_API void	gv_list_sync_ (list_t_ *list, size_t item_size)
UTIL_API void	gv_list_sort_ (list_t_ *list, int(*cmp)(const void *, const void *), size_t item_size)
UTIL_API void	gv_list_reverse_ (list_t_ *list, size_t item_size)
UTIL_API void	gv_list_shrink_to_fit_ (list_t_ *list, size_t item_size)
UTIL_API void	gv_list_free_ (list_t_ *list)
UTIL_API void	gv_list_pop_front_ (list_t_ *list, void *into, size_t item_size)
UTIL_API void	gv_list_pop_back_ (list_t_ *list, void *into, size_t item_size)

Detailed Description

Everything in this header should be considered “private” in the sense that it should not be called except by macros in list.h.

Definition in file list-private.h.

Macro Definition Documentation

LIST_DTOR_

#define LIST_DTOR_	(		list,
			slot
	)

Value:

  do {                                                                         \
    if ((list)->dtor == LIST_DTOR_FREE) {                                      \
      /* we need to juggle the element into a pointer to avoid compilation */  \
      /* errors from this (untaken) branch when the element type is not a  */  \
      /* pointer */                                                            \
      void *ptr_;                                                              \
      sizeof((list)->base[0]) == sizeof(ptr_)                                  \
          ? (void)0                                                            \
          : (void)(fprintf(stderr, "list element type is not a pointer, but "  \
                                   "`free` used as destructor\n"),             \
                   abort());                                                   \
      memcpy(&ptr_, &(list)->base[slot], sizeof(ptr_));                        \
      free(ptr_);                                                              \
    } else if ((list)->dtor != NULL) {                                         \
      (list)->dtor((list)->base[slot]);                                        \
    }                                                                          \
  } while (0)

run the destructor of a list on a given slot

Though this uses the public type LIST(<type>) defined in list.h, this is an internal API not expected to be called by anything other than the macros in list.h.

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

void LIST_DTOR_(LIST(<type>) *list, size_t slot);

Parameters

list	List to operate on
slot	Slot to destruct

Definition at line 87 of file list-private.h.

Function Documentation

gv_list_append_slot_()

UTIL_API size_t gv_list_append_slot_	(	list_t_ *	list,
		size_t	item_size
	)

add an empty space for an item to the end of a list

This function calls exit on failure.

Parameters

list	List to operate on
item_size	Byte size of each list item

Returns

Index of the new (empty) slot

Definition at line 54 of file list.c.

References ASAN_UNPOISON, list_t_::capacity, gv_list_reserve_(), list_t_::head, INDEX_TO, NULL, and list_t_::size.

Here is the call graph for this function:

gv_list_clear_()

UTIL_API void gv_list_clear_	(	list_t_ *	list,
		size_t	item_size
	)

remove all items from a list

Parameters

list	List to operate on
item_size	Byte size of list items

Definition at line 197 of file list.c.

References ASAN_POISON, gv_list_get_(), list_t_::head, INDEX_TO, NULL, and list_t_::size.

Here is the call graph for this function:

gv_list_contains_()

UTIL_API bool gv_list_contains_	(	const list_t_	list,
		const void *	needle,
		size_t	item_size
	)

does a list contain a given item?

Parameters

list	List to search
needle	Item to search for
item_size	Byte size of each list item

Returns

True if the item was found

Definition at line 223 of file list.c.

References gv_list_find_(), and SIZE_MAX.

Here is the call graph for this function:

gv_list_copy_()

UTIL_API list_t_ gv_list_copy_	(	const list_t_	list,
		size_t	item_size
	)

make a copy of a list

This function calls exit on failure.

Parameters

list	List to copy
item_size	Byte size of each list item

Returns

A copy of the original list

Definition at line 228 of file list.c.

References ASAN_POISON, list_t_::base, list_t_::capacity, gv_calloc(), gv_list_get_(), INDEX_TO, and list_t_::size.

Here is the call graph for this function:

gv_list_find_()

UTIL_API size_t gv_list_find_	(	const list_t_	list,
		const void *	needle,
		size_t	item_size
	)

find the slot containing the given item

Parameters

list	List to search
needle	Item to search for
item_size	Byte size of each list item

Returns

Slot index on success or SIZE_MAX if not found

Definition at line 166 of file list.c.

References gv_list_get_(), INDEX_TO, list_t_::size, and SIZE_MAX.

Referenced by gv_list_contains_().

Here is the call graph for this function:

Here is the caller graph for this function:

gv_list_free_()

UTIL_API void gv_list_free_

(

list_t_ *

list

)

free resources associated with a list

Parameters

list	List to operate on

Definition at line 333 of file list.c.

References list_t_::base, free(), and NULL.

Here is the call graph for this function:

gv_list_get_()

UTIL_API size_t gv_list_get_	(	const list_t_	list,
		size_t	index
	)

get the slot index of a given list item index

Parameters

list	List to operate on
index	Index of item to lookup

Returns

Slot index corresponding to the given index

Definition at line 161 of file list.c.

References list_t_::capacity, list_t_::head, and list_t_::size.

Referenced by gv_list_clear_(), gv_list_copy_(), gv_list_find_(), gv_list_pop_back_(), gv_list_pop_front_(), gv_list_remove_(), and gv_list_reverse_().

Here is the caller graph for this function:

gv_list_is_contiguous_()

UTIL_API bool gv_list_is_contiguous_

(

const list_t_

list

)

does the list 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

Parameters

list	List to inspect

Returns

True if the list is contiguous

Definition at line 250 of file list.c.

References list_t_::capacity, list_t_::head, and list_t_::size.

Referenced by gv_list_sync_().

Here is the caller graph for this function:

gv_list_pop_back_()

UTIL_API void gv_list_pop_back_	(	list_t_ *	list,
		void *	into,
		size_t	item_size
	)

remove and return the last item of a list

Parameters

	list	List to operate on
[out]	into	Destination to pop the item into
	item_size	Byte size of each list item

Definition at line 353 of file list.c.

References ASAN_POISON, gv_list_get_(), INDEX_TO, NULL, and list_t_::size.

Here is the call graph for this function:

gv_list_pop_front_()

UTIL_API void gv_list_pop_front_	(	list_t_ *	list,
		void *	into,
		size_t	item_size
	)

remove and return the first item of a list

Parameters

	list	List to operate on
[out]	into	Destination to pop the item into
	item_size	Byte size of each list item

Definition at line 339 of file list.c.

References ASAN_POISON, list_t_::capacity, gv_list_get_(), list_t_::head, INDEX_TO, NULL, and list_t_::size.

Here is the call graph for this function:

gv_list_prepend_slot_()

UTIL_API size_t gv_list_prepend_slot_	(	list_t_ *	list,
		size_t	item_size
	)

add an empty space for an item to the beginning of a list

This function calls exit on failure.

Parameters

list	List to operate on
item_size	Byte size of each list item

Returns

Index of the new (empty) slot

Definition at line 75 of file list.c.

References ASAN_UNPOISON, list_t_::capacity, gv_list_reserve_(), list_t_::head, INDEX_TO, NULL, and list_t_::size.

Here is the call graph for this function:

gv_list_remove_()

UTIL_API void gv_list_remove_	(	list_t_ *	list,
		size_t	index,
		size_t	item_size
	)

remove a slot from a list

Parameters

list	List to operate on
index	Slot index to remove
item_size	Byte size of each list item

Definition at line 179 of file list.c.

References ASAN_POISON, gv_list_get_(), INDEX_TO, NULL, and list_t_::size.

Here is the call graph for this function:

gv_list_reserve_()

UTIL_API void gv_list_reserve_	(	list_t_ *	list,
		size_t	capacity,
		size_t	item_size
	)

reserve space for new items in a list

This function is a no-op if sufficient space is already available.

Parameters

list	List to operate on
capacity	Total number of slots to make available
item_size	Byte size of list items

Definition at line 212 of file list.c.

References err, graphviz_exit(), PRISIZE_T, and try_reserve().

Referenced by gv_list_append_slot_(), and gv_list_prepend_slot_().

Here is the call graph for this function:

Here is the caller graph for this function:

gv_list_reverse_()

UTIL_API void gv_list_reverse_	(	list_t_ *	list,
		size_t	item_size
	)

reverse the item order of a list

Parameters

list	List to operate on
item_size	Byte size of each list item

Definition at line 309 of file list.c.

References exchange, gv_list_get_(), INDEX_TO, NULL, and list_t_::size.

Here is the call graph for this function:

gv_list_shrink_to_fit_()

UTIL_API void gv_list_shrink_to_fit_	(	list_t_ *	list,
		size_t	item_size
	)

decrease the allocated capacity of a list to minimum

Parameters

list	List to operate on
item_size	Byte size of list items

Definition at line 322 of file list.c.

References list_t_::base, list_t_::capacity, gv_list_sync_(), gv_recalloc(), NULL, and list_t_::size.

Here is the call graph for this function:

gv_list_size_()

static size_t gv_list_size_ ( const list_t_  list )

inlinestatic

get the number of elements in a list

Parameters

list	List to inspect

Returns

Size of the list

Definition at line 39 of file list-private.h.

References list_t_::size.

gv_list_sort_()

UTIL_API void gv_list_sort_	(	list_t_ *	list,
		int(*)(const void *, const void *)	cmp,
		size_t	item_size
	)

sort a list

Parameters

list	List to operate on
cmp	Comparator for ordering list items
item_size	Byte size of each list item

Definition at line 285 of file list.c.

References list_t_::base, cmp(), gv_list_sync_(), NULL, and list_t_::size.

Here is the call graph for this function:

gv_list_sync_()

UTIL_API void gv_list_sync_	(	list_t_ *	list,
		size_t	item_size
	)

shuffle the populated contents to reset head to 0

See the gv_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
item_size	Byte size of each list item

Definition at line 254 of file list.c.

References ASAN_POISON, ASAN_UNPOISON, list_t_::base, list_t_::capacity, gv_list_is_contiguous_(), list_t_::head, INDEX_TO, NULL, and list_t_::size.

Referenced by gv_list_shrink_to_fit_(), and gv_list_sort_().

Here is the call graph for this function:

Here is the caller graph for this function:

gv_list_try_reserve_()

UTIL_API bool gv_list_try_reserve_	(	list_t_ *	list,
		size_t	capacity,
		size_t	item_size
	)

try to reserve the given capacity for usage

Parameters

list	List to operate on
capacity	Requested size to expand to
item_size	Byte size of each list item

Returns

True if reservation succeeded

Definition at line 156 of file list.c.

References NULL, and try_reserve().

Here is the call graph for this function: