gp_heap.h File Reference

A min/max heap implementation. More...

#include <string.h>
#include <core/gp_debug.h>
#include <core/gp_common.h>
#include <core/gp_compiler.h>
#include <utils/gp_types.h>

Go to the source code of this file.

Functions
gp_heap_head *	gp_heap_ins (gp_heap_head *heap, gp_heap_head *elem, int(*cmp)(gp_heap_head *e1, gp_heap_head *e2))
	Inserts a node into a heap.
static gp_heap_head *	gp_heap_rem_last (gp_heap_head *heap, gp_heap_head **last)
	Removes last element on the last level.
static gp_heap_head *	gp_heap_pop (gp_heap_head *heap, int(*cmp)(gp_heap_head *e1, gp_heap_head *e2))
	Removes top element from the heap.
static gp_heap_head *	gp_heap_rem (gp_heap_head *heap, gp_heap_head *elem, int(*cmp)(gp_heap_head *e1, gp_heap_head *e2))
	Removes element from a heap.

Detailed Description

A min/max heap implementation.

Definition in file gp_heap.h.

Function Documentation

gp_heap_ins()

gp_heap_head * gp_heap_ins	(	gp_heap_head *	heap,
		gp_heap_head *	elem,
		int(*)(gp_heap_head *e1, gp_heap_head *e2)	cmp
	)

Inserts a node into a heap.

Parameters

heap	An heep tree root.
elem	An element to be insterted.
cmp	An element comparsion callback.

Returns

A new tree root.

Definition at line 157 of file gp_heap.h.

gp_heap_pop()

static gp_heap_head * gp_heap_pop ( gp_heap_head *  heap, int(*)(gp_heap_head *e1, gp_heap_head *e2)  cmp  )

inlinestatic

Removes top element from the heap.

Parameters

heap	Old heap pointer.

Returns

New heap pointer.

Definition at line 223 of file gp_heap.h.

References gp_heap_rem_last().

gp_heap_rem()

static gp_heap_head * gp_heap_rem ( gp_heap_head *  heap, gp_heap_head *  elem, int(*)(gp_heap_head *e1, gp_heap_head *e2)  cmp  )

inlinestatic

Removes element from a heap.

Does a buble down on a (sub) heap starting at the removed element and fixes the links afterwards.

Parameters

heap	An heep tree root.
elem	An element to be removed.
cmp	An element comparsion callback.

Returns

A new tree root.

Definition at line 280 of file gp_heap.h.

References gp_heap_rem_last().

gp_heap_rem_last()

static gp_heap_head * gp_heap_rem_last ( gp_heap_head *  heap, gp_heap_head **  last  )

inlinestatic

Removes last element on the last level.

The head pointer only changes if we remove last element from heap.

Parameters

heap	A heap pointer.
last	A pointer to store the last element to.

Returns

A pointer to new head.

Definition at line 172 of file gp_heap.h.

References gp_heap_rem_last().

Referenced by gp_heap_pop(), gp_heap_rem(), and gp_heap_rem_last().