gts/heap.c File Reference

#include <stdlib.h>
#include "gts.h"

Include dependency graph for gts/heap.c:

Go to the source code of this file.

Data Structures
struct	_GtsHeap
Defines
#define	PARENT(i)   ((i) >= 2 ? (i)/2 : 0)
#define	LEFT_CHILD(i)   (2*(i))
#define	RIGHT_CHILD(i)   (2*(i) + 1)
Functions
GtsHeap *	gts_heap_new (GCompareFunc compare_func)
static void	sift_up (GtsHeap *heap, guint i)
void	gts_heap_insert (GtsHeap *heap, gpointer p)
static void	sift_down (GtsHeap *heap, guint i)
gpointer	gts_heap_remove_top (GtsHeap *heap)
gpointer	gts_heap_top (GtsHeap *heap)
void	gts_heap_destroy (GtsHeap *heap)
void	gts_heap_thaw (GtsHeap *heap)
void	gts_heap_foreach (GtsHeap *heap, GFunc func, gpointer user_data)
void	gts_heap_freeze (GtsHeap *heap)
guint	gts_heap_size (GtsHeap *heap)

---

Define Documentation

#define LEFT_CHILD

(

i

)

(2*(i))

Definition at line 24 of file gts/heap.c.

Referenced by sift_down().

#define PARENT

(

i

)

((i) >= 2 ? (i)/2 : 0)

Definition at line 23 of file gts/heap.c.

Referenced by sift_up().

#define RIGHT_CHILD

(

i

)

(2*(i) + 1)

Definition at line 25 of file gts/heap.c.

Referenced by sift_down().

---

Function Documentation

void gts_heap_destroy

(

GtsHeap *

heap

)

gts_heap_destroy: : a GtsHeap.

Free all the memory allocated for .

Definition at line 181 of file gts/heap.c.

References _GtsHeap::elts, and TRUE.

Referenced by partition_update().

void gts_heap_foreach	(	GtsHeap *	heap,
		GFunc	func,
		gpointer	user_data
	)

gts_heap_foreach: : a GtsHeap. : the function to call for each element in the heap. : to pass to .

Definition at line 217 of file gts/heap.c.

References _GtsHeap::elts.

void gts_heap_freeze

(

GtsHeap *

heap

)

gts_heap_freeze: : a GtsHeap.

Freezes the heap. Any subsequent operation will not preserve the heap property. Used in conjunction with gts_heap_insert() and gts_heap_thaw() to create a heap in O(n) time.

Definition at line 240 of file gts/heap.c.

References _GtsHeap::frozen, and TRUE.

void gts_heap_insert	(	GtsHeap *	heap,
		gpointer	p
	)

gts_heap_insert: : a GtsHeap. : a pointer to add to the heap.

Inserts a new element in the heap.

Definition at line 79 of file gts/heap.c.

References _GtsHeap::elts, _GtsHeap::frozen, and sift_up().

Referenced by partition_update().

Here is the call graph for this function:

GtsHeap* gts_heap_new

(

GCompareFunc

compare_func

)

gts_heap_new: : a GCompareFunc.

Returns: a new GtsHeap using as a sorting function.

Definition at line 39 of file gts/heap.c.

References _GtsHeap::elts, FALSE, _GtsHeap::frozen, and _GtsHeap::func.

Referenced by partition_update().

gpointer gts_heap_remove_top

(

GtsHeap *

heap

)

gts_heap_remove_top: : a GtsHeap.

Removes the element at the top of the heap.

Returns: the element at the top of the heap.

Definition at line 134 of file gts/heap.c.

References _GtsHeap::elts, len, and sift_down().

Referenced by partition_update().

Here is the call graph for this function:

guint gts_heap_size

(

GtsHeap *

heap

)

gts_heap_size: : a GtsHeap.

Returns: the number of items in .

Definition at line 253 of file gts/heap.c.

References _GtsHeap::elts.

void gts_heap_thaw

(

GtsHeap *

heap

)

gts_heap_thaw: : a GtsHeap.

If has been frozen previously using gts_heap_freeze(), reorder it in O(n) time and unfreeze it.

Definition at line 196 of file gts/heap.c.

References _GtsHeap::elts, FALSE, _GtsHeap::frozen, and sift_down().

Here is the call graph for this function:

gpointer gts_heap_top

(

GtsHeap *

heap

)

gts_heap_top: : a GtsHeap.

Returns: the element at the top of the heap.

Definition at line 161 of file gts/heap.c.

References _GtsHeap::elts, and len.

static void sift_down	(	GtsHeap *	heap,
		guint	i
	)		[static]

Definition at line 88 of file gts/heap.c.

References c, _GtsHeap::elts, _GtsHeap::func, LEFT_CHILD, len, and RIGHT_CHILD.

Referenced by gts_heap_remove_top(), and gts_heap_thaw().

static void sift_up	(	GtsHeap *	heap,
		guint	i
	)		[static]

Definition at line 52 of file gts/heap.c.

References _GtsHeap::elts, _GtsHeap::func, and PARENT.

Referenced by gts_heap_insert().