A binary tree organized as a heap. More...

Data Structures
struct	cstl_heap_node
	Node to anchor an element within a heap. More...

struct	cstl_heap
	Heap object. More...

Macros
#define	CSTL_HEAP_INITIALIZER(TYPE, MEMB, CMP, PRIV)
	Constant initialization of a heap object.

#define	DECLARE_CSTL_HEAP(NAME, TYPE, MEMB, CMP, PRIV)
	(Statically) declare and initialize a heap

Functions
static void	cstl_heap_init (struct cstl_heap const h, cstl_compare_func_t const cmp, void *const priv, const size_t off)
	Initialize a heap object.

static size_t	cstl_heap_size (const struct cstl_heap *const h)
	Get the number of objects in the heap.

void	cstl_heap_push (struct cstl_heap h, void e)
	Insert a new object into the heap.

const void *	cstl_heap_get (const struct cstl_heap *h)
	Get a pointer to the object at the top of the heap.

void *	cstl_heap_pop (struct cstl_heap *h)
	Remove the highest valued element from the heap.

static void	cstl_heap_clear (struct cstl_heap const h, cstl_xtor_func_t const clr)
	Remove all elements from the heap.

static void	cstl_heap_swap (struct cstl_heap const a, struct cstl_heap const b)
	Swap the heap objects at the two given locations.

Detailed Description

A binary tree organized as a heap.

A heap is a binary tree with the highest valued object (as determined by the associated comparison function) at the root. Every node in the tree is less than or equal to its parent. The highest valued object in the tree can be found in constant time, and adding and removing objects in the tree can be done in O(log n) where n is the number of elements in the heap

Macro Definition Documentation

◆ CSTL_HEAP_INITIALIZER

#define CSTL_HEAP_INITIALIZER	(	TYPE,
		MEMB,
		CMP,
		PRIV
	)

Value:

    {                                                                   \
        .bt = CSTL_BINTREE_INITIALIZER(TYPE, MEMB.bn, CMP, PRIV),       \
    }

Constant initialization of a heap object.

Parameters

TYPE	The type of object that the heap will hold
MEMB	The name of the `heap_node` member within `TYPE`.
CMP	A pointer to a function of type `cstl_compare_func_t` that will be used to compare elements in the heap
PRIV	A pointer to a private data structure that will be passed to calls to the `CMP` function

See also: cstl_heap_node for a description of the relationship between TYPE and MEMB

Definition at line 87 of file heap.h.

◆ DECLARE_CSTL_HEAP

#define DECLARE_CSTL_HEAP	(	NAME,
		TYPE,
		MEMB,
		CMP,
		PRIV
	)

Value:

struct cstl_heap NAME = \

CSTL_HEAP_INITIALIZER(TYPE, MEMB, CMP, PRIV)

cstl_heap

Heap object.

Definition heap.h:62

(Statically) declare and initialize a heap

Parameters

NAME	The name of the variable being declared
TYPE	The type of object that the heap will hold
MEMB	The name of the `cstl_heap_node` member within `TYPE`.
CMP	A pointer to a function of type `cstl_compare_func_t` that will be used to compare elements in the heap
PRIV	A pointer to a private data structure that will be passed to calls to the `CMP` function

See also: cstl_heap_node for a description of the relationship between TYPE and MEMB

Definition at line 105 of file heap.h.

Function Documentation

◆ cstl_heap_clear()

static void cstl_heap_clear	(	struct cstl_heap *const	h,
		cstl_xtor_func_t *const	clr
	)

inlinestatic

Remove all elements from the heap.

Parameters

[in]	h	A pointer to the heap
[in]	clr	A pointer to a function to be called for each element in the tree

All elements are removed from the heap and the clr function is called for each element that was in the heap. The order in which the elements are removed and clr is called is not specified, but the callee may take ownership of an element at the time that clr is called for that element and not before.

Upon return from this function, the heap contains no elements, and is as it was immediately after being initialized. No further operations on the tree are necessary to make it ready to go out of scope or be destroyed.

Definition at line 191 of file heap.h.

◆ cstl_heap_get()

const void * cstl_heap_get ( const struct cstl_heap * h )

Get a pointer to the object at the top of the heap.

Parameters

[in] h A pointer to the heap

Returns: A pointer to the object at the top of the heap

Return values

NULL	The heap is empty

Definition at line 165 of file heap.c.

◆ cstl_heap_init()

static void cstl_heap_init	(	struct cstl_heap *const	h,
		cstl_compare_func_t *const	cmp,
		void *const	priv,
		const size_t	off
	)

inlinestatic

Initialize a heap object.

Parameters

[in,out]	h	A pointer to the object to be initialized
[in]	cmp	A function that can compare objects in the heap
[in]	priv	A pointer to private data that will be passed to the `cmp` function
[in]	off	The offset of the `cstl_heap_node` object within the object(s) that will be stored in the heap

Definition at line 119 of file heap.h.

◆ cstl_heap_pop()

void * cstl_heap_pop ( struct cstl_heap * h )

Remove the highest valued element from the heap.

Parameters

[in] h A pointer to the heap

Returns: The highest valued element in the heap

Return values

NULL	The heap is empty

Definition at line 174 of file heap.c.

◆ cstl_heap_push()

void cstl_heap_push	(	struct cstl_heap *	h,
		void *	e
	)

Insert a new object into the heap.

Parameters

[in]	h	A pointer to the heap
[in]	e	A pointer to the object to be inserted

After insertion, the inserted object must not be modified (in such a way as to affect its comparison with other objects in the heap) as that modification can cause the assumptions about the ordering of elements within the heap to become invalid and lead to undefined behavior.

Definition at line 122 of file heap.c.

◆ cstl_heap_size()

static size_t cstl_heap_size ( const struct cstl_heap *const h )

inlinestatic

Get the number of objects in the heap.

Parameters

[in] h A pointer to the heap

Returns: The number of objects in the heap

Definition at line 135 of file heap.h.

◆ cstl_heap_swap()

static void cstl_heap_swap	(	struct cstl_heap *const	a,
		struct cstl_heap *const	b
	)

inlinestatic

Swap the heap objects at the two given locations.

Parameters

[in,out]	a	A pointer to a heap
[in,out]	b	A pointer to a(nother) heap

The heaps at the given locations will be swapped such that upon return, a will contain the heap previously pointed to by b and vice versa.

Definition at line 206 of file heap.h.

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ CSTL_HEAP_INITIALIZER

◆ DECLARE_CSTL_HEAP

Function Documentation

◆ cstl_heap_clear()

◆ cstl_heap_get()

◆ cstl_heap_init()

◆ cstl_heap_pop()

◆ cstl_heap_push()

◆ cstl_heap_size()

◆ cstl_heap_swap()