heap.h File Reference

#include <stddef.h>
#include "arena.h"

Data Structures
struct	Heap
	Represents a binary heap (min-heap by default) More...
struct	HeapItem
	Represents a single item in the heap. More...

Macros
#define	heap_for_each(item, self)   for (auto(item) = (self)->begin; item; (item) = (item)->next)
	Iterate over all items of a heap.

Typedefs
typedef int	HeapDataCompare(const void *, const void *, void *)
	Data comparison function.
typedef void *	HeapDataCopy(Arena *, void *, const void *, long)
	Data copy function.

Functions
static Heap	heap_create (Arena *arena, long size, HeapDataCompare *compare)
	Create a new heap.
static void	heap_push (Heap *self, void *data, void *context)
	Insert a new item into a heap.
static void *	heap_pop (Heap *self, void *context)
	Remove the root item from the heap.
static void *	heap_peek (const Heap *self)
	Retrieve the root item of the heap.
static Heap	heap_clone (const Heap *self, void *context, Arena *arena)
	Create a clone of a heap.
static HeapItem *	heap_items (const Heap *self, Arena *arena)
	Retrieve an array of heap items.

Macro Definition Documentation

heap_for_each

#define heap_for_each	(		item,
			self
	)		for (auto(item) = (self)->begin; item; (item) = (item)->next)

Iterate over all items of a heap.

Parameters

item	Current heap item
self	Pointer to a heap

Function Documentation

heap_create()

static Heap heap_create ( Arena *  arena, long  size, HeapDataCompare *  compare  )

static

Create a new heap.

Parameters

arena	Pointer to an arena allocator
size	Size of item data in bytes (optional)
compare	Pointer to a data comparison function

Returns

New heap instance

Note

If size == 0, the data pointers will be directly assigned rather than copied

heap_push()

static void heap_push ( Heap *  self, void *  data, void *  context  )

static

Insert a new item into a heap.

Parameters

self	Pointer to a heap
data	Pointer to the item data
context	Pointer to a user-provided context for the comparison function (optional)

heap_pop()

static void * heap_pop ( Heap *  self, void *  context  )

static

Remove the root item from the heap.

Parameters

self	Pointer to a heap
context	Pointer to a user-provided context for the comparison function (optional)

Returns

Pointer to the item data, or nullptr if the heap is empty

heap_peek()

static void * heap_peek ( const Heap *  self )

static

Retrieve the root item of the heap.

Parameters

self	Pointer to a heap

Returns

Pointer to the item data, or nullptr if the heap is empty

heap_clone()

static Heap heap_clone ( const Heap *  self, void *  context, Arena *  arena  )

static

Create a clone of a heap.

Parameters

self	Pointer to a heap
context	Pointer to a user-provided context for the comparison function (optional)
arena	Pointer to an arena allocator (optional)

Returns

Cloned heap instance

Note

If no arena allocator is passed, the arena allocator of the heap is used

heap_items()

static HeapItem * heap_items ( const Heap *  self, Arena *  arena  )

static

Retrieve an array of heap items.

Parameters

self	Pointer to a heap
arena	Pointer to an arena allocator (optional)

Returns

Pointer to an array of items

Note

If no arena allocator is passed, the arena allocator of the heap is used