Detailed Description

Author: hacatu

Version: 0.3.0 Base function table for Crater containers

LICENSE

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

DESCRIPTION

Crater is a collection of generic data structures for C, including vectors, avl trees, heaps (binary, pairing, and minmax), kd trees, linked lists, hash tables, slab allocators, random number generators, and option parsing

Definition in file container.h.

Go to the source code of this file.

Data Structures
struct	cr8r_base_ft
	Base function table for all Crater containers. More...

Macros
#define	CR8R_FLA_CAST(T, p) (((union{__typeof__(p) data; T a;})(p)).a)
	Cast a flexible length array member to a given type using union hackery sorcery.

#define	CR8R_OUTER(ptr, T, memb) ((T)((void)(ptr) - offsetof(T, memb)))
	Convert a pointer to an intrusive data structure to a pointer to the outer structure containing it, based on the type of the outer structure. More...

#define	CR8R_OUTER_S(ptr, ft) (((void*)(ptr) - (ft)->base.size))
	Convert a pointer to an intrusive data structure to a pointer to the outer structure containing it, based on a function table. More...

#define	CR8R_INNER(ptr, T, memb) (((void*)(ptr) + offsetof(T, memb)))
	Convert a pointer to an outer data structure to a pointer to the intrusive data structure within it, based on the type of the outer structure. More...

#define	CR8R_INNER_S(ptr, ft) (((void*)(ptr) + (ft)->base.size))
	Convert a pointer to an outer data structure to a pointer to the intrusive data structure within it, based on a function table. More...

#define	CR8R_ATTR_NO_SAN(...)
	Prevent clang from reporting spurious errors when a length zero array is passed to a length annotated function parameter.

Enumerations
enum	cr8r_walk_decision { CR8R_WALK_CONTINUE = 0 , CR8R_WALK_SKIP_CHILDREN = 1 , CR8R_WALK_STOP = 2 }
	Enum to allow a callee/visitor to control the behavior of a tree traversal.

Functions
uint64_t	cr8r_default_new_size (cr8r_base_ft *, uint64_t cap)
	"Default" ft->new_size implementation (for vectors) More...

uint64_t	cr8r_default_bump_size (cr8r_base_ft *, uint64_t cap)
	"Default" increase-by-one ft->new_size implementation (for vectors) More...

void *	cr8r_default_resize (cr8r_base_ft , void p, uint64_t cap)
	"Default" ft->resize implementation (for vectors) More...

void *	cr8r_default_resize_pass (cr8r_base_ft , void p, uint64_t cap)
	"Default" do-nothing ft->resize implementation (for vectors) More...

int	cr8r_default_cmp (const cr8r_base_ft , const void a, const void *b)
	"Default" ft->cmp implementation More...

void	cr8r_default_swap (cr8r_base_ft , void a, void *b)
	"Default" ft->swap implementation (for vectors) More...

uint64_t	cr8r_default_hash_u64 (const cr8r_base_ft , const void )
	"Default" ft->hash implementation for uint64_t (for hash tables) More...

uint64_t	cr8r_default_hash (const cr8r_base_ft , const void )
	"Default" ft->hash implementation (for hash tables) More...

uint64_t	cr8r_default_hash_cstr (const cr8r_base_ft , const void )
	"Default" ft->hash implementation for null terminated strings (for hash tables) More...

int	cr8r_default_cmp_u64 (const cr8r_base_ft , const void , const void *)
	"Default" ft->cmp implementation for uint64_t

int	cr8r_default_cmp_u8 (const cr8r_base_ft , const void , const void *)
	"Default" ft->cmp implementation for uint8_t

int	cr8r_default_cmp_i64 (const cr8r_base_ft , const void , const void *)
	"Default" ft->cmp implementation for int64_t

int	cr8r_default_cmp_cstr (const cr8r_base_ft , const void , const void *)
	"Default" ft->cmp implementation for null terminated strings

int	cr8r_default_replace (cr8r_base_ft , void _a, void *_b)
	"Default" ft->add implementation (for avl trees and hash tables) More...

void	cr8r_default_free_pass (cr8r_base_ft , void )
	ft->free implementation (for avl trees or circular lists) that does nothing More...

void *	cr8r_default_alloc_sla (cr8r_base_ft *)
	ft->alloc implementation (for avl trees or circular lists) More...

void	cr8r_default_free_sla (cr8r_base_ft , void )
	ft->free implementation (for avl trees or circular lists) More...

void	cr8r_default_free (cr8r_base_ft , void )
	ft->del implementation (for hash tables or vectors) More...

void	cr8r_default_copy_cstr (cr8r_base_ft , void , const void *)
	ft->copy implementation for null terminated strings More...

uint64_t	cr8r_powmod (uint64_t b, uint64_t e, uint64_t n)
	Raise b to the power of e modulo n using binary exponentiation.

uint64_t	cr8r_pow_u64 (uint64_t b, uint64_t e)
	Raise b to the power of e using binary exponentiation.

Macro Definition Documentation

◆ CR8R_OUTER

#define CR8R_OUTER	(	ptr,
		T,
		memb
	)	((T)((void)(ptr) - offsetof(T, memb)))

Convert a pointer to an intrusive data structure to a pointer to the outer structure containing it, based on the type of the outer structure.

Parameters

[in]	ptr	pointer to the intrusive data structure
[in]	T	type of the outer structure (NOT a pointer to its type)
[in]	memb	the name of the intrusive data structure member within the outer structure

Returns: pointer to the outer structure

Definition at line 176 of file container.h.

◆ CR8R_OUTER_S

#define CR8R_OUTER_S	(	ptr,
		ft
	)	(((void*)(ptr) - (ft)->base.size))

Convert a pointer to an intrusive data structure to a pointer to the outer structure containing it, based on a function table.

Parameters

[in]	ptr	pointer to the intrusive data structure
[in]	ft	function table pointer with ft->base.size equal to the offset of the intrusive data structure within the outer data structure

Returns: pointer to the outer structure

Definition at line 184 of file container.h.

◆ CR8R_INNER

#define CR8R_INNER	(	ptr,
		T,
		memb
	)	(((void*)(ptr) + offsetof(T, memb)))

Convert a pointer to an outer data structure to a pointer to the intrusive data structure within it, based on the type of the outer structure.

Parameters

[in]	ptr	pointer to the outer data structure
[in]	T	type of the outer structure (NOT a pointer to its type)
[in]	memb	the name of the intrusive data structure member within the outer structure

Returns: pointer to the intrusive data structure

Definition at line 192 of file container.h.

◆ CR8R_INNER_S

#define CR8R_INNER_S	(	ptr,
		ft
	)	(((void*)(ptr) + (ft)->base.size))

Convert a pointer to an outer data structure to a pointer to the intrusive data structure within it, based on a function table.

Parameters

[in]	ptr	pointer to the outer data structure
[in]	ft	function table pointer with ft->base.size equal to the offset of the intrusive data structure within the outer data structure

Returns: pointer to the intrusive data structure

Definition at line 200 of file container.h.

Function Documentation

◆ cr8r_default_new_size()

uint64_t cr8r_default_new_size	(	cr8r_base_ft *	,
		uint64_t	cap
	)

"Default" ft->new_size implementation (for vectors)

Doubles the capacity if it is nonzero, otherwise returns 8.

Parameters

[in] cap the capacity before resizing

Returns: what capacity the vector should grow to

◆ cr8r_default_bump_size()

uint64_t cr8r_default_bump_size	(	cr8r_base_ft *	,
		uint64_t	cap
	)

"Default" increase-by-one ft->new_size implementation (for vectors)

Increases the capacity by 1.

Parameters

[in] cap the capacity before resizing

Returns: what capacity the vector should grow to

◆ cr8r_default_resize()

void* cr8r_default_resize	(	cr8r_base_ft *	,
		void *	p,
		uint64_t	cap
	)

"Default" ft->resize implementation (for vectors)

Calls "free" if the given capacity is 0 (note that freeing NULL is a valid no-op), otherwise calls realloc (note that reallocing NULL is valid and allocates a new buffer).

Parameters

[in]	p	the buffer to resize
[in]	cap	the capacity to resize to

Returns: a pointer to the resized buffer, or NULL on failure or if cap is 0

◆ cr8r_default_resize_pass()

void* cr8r_default_resize_pass	(	cr8r_base_ft *	,
		void *	p,
		uint64_t	cap
	)

"Default" do-nothing ft->resize implementation (for vectors)

Always returns NULL, indicating the buffer could not be resized. This is convenient if you want to wrap a stack/static/thread local array as a vector, since such an array cannot be resized.

Returns: NULL

◆ cr8r_default_cmp()

int cr8r_default_cmp	(	const cr8r_base_ft *	,
		const void *	a,
		const void *	b
	)

"Default" ft->cmp implementation

Calls memcmp(a, b, ft->base.size) WARNING: this may have problems with padded structs or doubles since equal values can have different representations in memory. A custom implementation is preferable for padded structs, anything containing doubles, or scalar types.

Parameters

[in] a,b the elements to compare

Returns: -1 if a < b, 0 if a == b, 1 if a > b

◆ cr8r_default_swap()

void cr8r_default_swap	(	cr8r_base_ft *	,
		void *	a,
		void *	b
	)

"Default" ft->swap implementation (for vectors)

Creates a temporary buffer and swaps with memcpy, if a != b.

Parameters

[in] a,b the elements to swap

◆ cr8r_default_hash_u64()

uint64_t cr8r_default_hash_u64	(	const cr8r_base_ft *	,
		const void *
	)

"Default" ft->hash implementation for uint64_t (for hash tables)

Multiplies the value by a fixed prime and xors the high and low words of the 128 bit result

◆ cr8r_default_hash()

uint64_t cr8r_default_hash	(	const cr8r_base_ft *	,
		const void *
	)

"Default" ft->hash implementation (for hash tables)

WARNING: this may have problems with padded structs or doubles since equal values can have different representations in memory. A custom implementation is preferable for padded structs, anything containing doubles, or scalar types.

◆ cr8r_default_hash_cstr()

uint64_t cr8r_default_hash_cstr	(	const cr8r_base_ft *	,
		const void *
	)

"Default" ft->hash implementation for null terminated strings (for hash tables)

Uses the djb2 algorithm

◆ cr8r_default_replace()

int cr8r_default_replace	(	cr8r_base_ft *	,
		void *	_a,
		void *	_b
	)

"Default" ft->add implementation (for avl trees and hash tables)

Simply replaces the existing value with the new value

◆ cr8r_default_free_pass()

void cr8r_default_free_pass	(	cr8r_base_ft *	,
		void *
	)

ft->free implementation (for avl trees or circular lists) that does nothing

Useful to allow temporarily adding stack allocated nodes, or to temporarily disable freeing nodes so one can be removed but still have some processing done on it via an existing pointer before freeing it.

◆ cr8r_default_alloc_sla()

void* cr8r_default_alloc_sla ( cr8r_base_ft * )

ft->alloc implementation (for avl trees or circular lists)

Wraps a slab allocator. WARNING: ft->base.data must point to a slab allocator ( cr8r_sla ) with the appropriate element size. Remember, the element size of the slab allocator should be the node size, not the element size, of the container (avl tree or circular list). See cr8r_avl_ft_initsla and cr8r_cll_ft_initsla.

◆ cr8r_default_free_sla()

void cr8r_default_free_sla	(	cr8r_base_ft *	,
		void *
	)

ft->free implementation (for avl trees or circular lists)

Wraps a slab allocator. WARNING: ft->base.data must point to a slab allocator ( cr8r_sla ) with the appropriate element size. Remember, the element size of the slab allocator should be the node size, not the element size, of the container (avl tree or circular list). See cr8r_cll_ft_initsla and cr8r_cll_ft_initsla.

◆ cr8r_default_free()

void cr8r_default_free	(	cr8r_base_ft *	,
		void *
	)

ft->del implementation (for hash tables or vectors)

Wraps free(). Keep in mind that the second argument is a pointer to an element and is dereferenced before being freed. For example, malloc'd C strings are stored as single pointers, so a vector of C strings is really a vector of pointers, and a pointer to an element of such a vector is a pointer to a pointer to some null terminated character sequence.

◆ cr8r_default_copy_cstr()

void cr8r_default_copy_cstr	(	cr8r_base_ft *	,
		void *	,
		const void *
	)

ft->copy implementation for null terminated strings

Wraps strdup.

Detailed Description

LICENSE

DESCRIPTION

Data Structures

Macros

Enumerations

Functions

Macro Definition Documentation

◆ CR8R_OUTER

◆ CR8R_OUTER_S

◆ CR8R_INNER

◆ CR8R_INNER_S

Function Documentation

◆ cr8r_default_new_size()

◆ cr8r_default_bump_size()

◆ cr8r_default_resize()

◆ cr8r_default_resize_pass()

◆ cr8r_default_cmp()

◆ cr8r_default_swap()

◆ cr8r_default_hash_u64()

◆ cr8r_default_hash()

◆ cr8r_default_hash_cstr()

◆ cr8r_default_replace()

◆ cr8r_default_free_pass()

◆ cr8r_default_alloc_sla()

◆ cr8r_default_free_sla()

◆ cr8r_default_free()

◆ cr8r_default_copy_cstr()