Graphviz: lib/util/list.c File Reference

Searching...

No Matches

#include <assert.h>
#include <errno.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <util/alloc.h>
#include <util/asan.h>
#include <util/exit.h>
#include <util/gv_math.h>
#include <util/list-private.h>
#include <util/prisize_t.h>

Include dependency graph for list.c:

Go to the source code of this file.

Macros
#define	INDEX_TO(origin, index, stride)

Functions
static const void *	slot_from_const_list (const list_t_ *list, size_t index, size_t stride)

static void *	slot_from_list (list_t_ *list, size_t index, size_t stride)

static const void *	slot_from_const_base (const void *base, size_t index, size_t stride)

static void *	slot_from_base (void *base, size_t index, size_t stride)

size_t	gv_list_append_slot_ (list_t_ *list, size_t item_size)

size_t	gv_list_prepend_slot_ (list_t_ *list, size_t item_size)

static int	try_reserve (list_t_ *list, size_t capacity, size_t item_size)

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

size_t	gv_list_get_ (const list_t_ list, size_t index)

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

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

void	gv_list_clear_ (list_t_ *list, size_t item_size)

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

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

list_t_	gv_list_copy_ (const list_t_ list, size_t item_size)

bool	gv_list_is_contiguous_ (const list_t_ list)

void	gv_list_sync_ (list_t_ *list, size_t item_size)

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

static void	exchange (void a, void b, size_t size)

void	gv_list_reverse_ (list_t_ *list, size_t item_size)

void	gv_list_shrink_to_fit_ (list_t_ *list, size_t item_size)

void	gv_list_free_ (list_t_ *list)

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

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

Macro Definition Documentation

◆ INDEX_TO

#define INDEX_TO	(	origin,
		index,
		stride
	)

Value:

  (_Generic((origin),                                                          \
       const list_t_ *: slot_from_const_list,                                  \
       list_t_ *: slot_from_list,                                              \
       const void *: slot_from_const_base,                                     \
       void *: slot_from_base)((origin), (index), (stride)))

Definition at line 47 of file list.c.

Function Documentation

◆ exchange()

static void exchange	(	void *	a,
		void *	b,
		size_t	size
	)

static

Definition at line 297 of file list.c.

References NULL, and SWAP.

◆ gv_list_append_slot_()

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_()

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_()

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_()

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_()

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_()

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_()

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_()

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_()

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_()

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_()

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_()

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_()

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_()

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_()

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_sort_()

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_()

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_()

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:

◆ slot_from_base()

static void * slot_from_base	(	void *	base,
		size_t	index,
		size_t	stride
	)

static

Definition at line 40 of file list.c.

References NULL.

◆ slot_from_const_base()

static const void * slot_from_const_base	(	const void *	base,
		size_t	index,
		size_t	stride
	)

static

Definition at line 32 of file list.c.

References NULL.

◆ slot_from_const_list()

static const void * slot_from_const_list	(	const list_t_ *	list,
		size_t	index,
		size_t	stride
	)

static

Definition at line 15 of file list.c.

References list_t_::base, and NULL.

◆ slot_from_list()

static void * slot_from_list	(	list_t_ *	list,
		size_t	index,
		size_t	stride
	)

static

Definition at line 24 of file list.c.

References list_t_::base, and NULL.

◆ try_reserve()

static int try_reserve	(	list_t_ *	list,
		size_t	capacity,
		size_t	item_size
	)

static

Definition at line 96 of file list.c.

References ASAN_POISON, ASAN_UNPOISON, list_t_::base, list_t_::capacity, list_t_::head, INDEX_TO, NULL, prefix, list_t_::size, and SIZE_MAX.

Referenced by gv_list_reserve_(), and gv_list_try_reserve_().

Here is the caller graph for this function:

Macros

Functions

Macro Definition Documentation

◆ INDEX_TO

Function Documentation

◆ exchange()

◆ gv_list_append_slot_()

◆ gv_list_clear_()

◆ gv_list_contains_()

◆ gv_list_copy_()

◆ gv_list_find_()

◆ gv_list_free_()

◆ gv_list_get_()

◆ gv_list_is_contiguous_()

◆ gv_list_pop_back_()

◆ gv_list_pop_front_()

◆ gv_list_prepend_slot_()

◆ gv_list_remove_()

◆ gv_list_reserve_()

◆ gv_list_reverse_()

◆ gv_list_shrink_to_fit_()

◆ gv_list_sort_()

◆ gv_list_sync_()

◆ gv_list_try_reserve_()

◆ slot_from_base()

◆ slot_from_const_base()

◆ slot_from_const_list()

◆ slot_from_list()

◆ try_reserve()