minheap.cpp File Reference

#include "minheap.h"
#include "global.h"
#include <stdlib.h>

Include dependency graph for minheap.cpp:

Go to the source code of this file.

Functions
void	minheap_free (MinHeap *to_free)
	Cleans the minheap. More...
static int	minheap_get_left (int index)
	Get the index of the left child in the heap. More...
static int	minheap_get_parent (int index)
	Get the index of the parent in the heap. More...
static int	minheap_get_right (int index)
	Get the index of the right child in the heap. More...
MinHeap *	minheap_init (int amt, int(*measure_func)(const void *), void(*cleanup_func)(void *))
	Function to intialize the minheap. More...
void	minheap_init_static (MinHeap *heap, void **arr, int amt, int(*measure_func)(const void *))
	Initialize the minheap using statically allocated components. More...
int	minheap_insert (MinHeap *heap, void *ob)
	Inserts an element into the min-heap. More...
static void	minheap_normalize (MinHeap *heap)
	Normalize the minheap. More...
void *	minheap_remove (MinHeap *heap)
	Pops the top of the minheap off. More...

Detailed Description

Implements a minheap.

Initial use is for the A* pathing algorithm in monster AI, but is designed to be generic enough that anything that needs a minheap can use it.

Definition in file minheap.cpp.

Function Documentation

minheap_free()

void minheap_free

(

MinHeap *

to_free

)

Cleans the minheap.

Parameters

to_free

The minheap to free.

Definition at line 226 of file minheap.cpp.

References MinHeap::arr, MinHeap::element_cleanup, and MinHeap::len.

minheap_get_left()

static int minheap_get_left ( int  index )

inlinestatic

Get the index of the left child in the heap.

left child is index * 2 + 1.

Returns

the index of the left child of the provided index.

Definition at line 34 of file minheap.cpp.

Referenced by minheap_normalize().

Here is the caller graph for this function:

minheap_get_parent()

static int minheap_get_parent ( int  index )

inlinestatic

Get the index of the parent in the heap.

parent is (index - 1) / 2 (rounded down).

Returns

the index of the parent of the provided index, or -1 if provided index was the root of the tree.

Definition at line 59 of file minheap.cpp.

Referenced by minheap_insert().

Here is the caller graph for this function:

minheap_get_right()

static int minheap_get_right ( int  index )

inlinestatic

Get the index of the right child in the heap.

right child is index * 2 + 2.

Returns

the index of the right child of the provided index.

Definition at line 47 of file minheap.cpp.

Referenced by minheap_normalize().

Here is the caller graph for this function:

minheap_init()

MinHeap* minheap_init	(	int	amt,
		int(*)(const void *)	measure_func,
		void(*)(void *)	cleanup_func
	)

Function to intialize the minheap.

Parameters

amt	The capacity of the min-heap.
measure_func	Pointer to the function to measure the data we're storing.
cleanup_func	Pointer to a given element's cleanup function. Can be NULL if the data does not need to be cleaned up for any reason.

Returns

Pointer to the allocated min-heap. Errors out if allocation fails.

Definition at line 129 of file minheap.cpp.

References MinHeap::arr, MinHeap::capacity, MinHeap::element_cleanup, fatal(), MinHeap::get_measure, MinHeap::len, and OUT_OF_MEMORY.

Here is the call graph for this function:

minheap_init_static()

void minheap_init_static	(	MinHeap *	heap,
		void **	arr,
		int	amt,
		int(*)(const void *)	measure_func
	)

Initialize the minheap using statically allocated components.

It is expected the caller will do any necessary cleanup on data before the components fall out of scope.

It is also expected that the caller ensured arr can hold amt elements.

Parameters

heap	Pointer to the heap we are initializing.
arr	Pointer to the array of elements we are using.
amt	The capacity of the heap
measure_func	Pointer to the function that gives the calculation the minheap uses to organize elements.

Definition at line 162 of file minheap.cpp.

References MinHeap::arr, MinHeap::capacity, MinHeap::element_cleanup, MinHeap::get_measure, and MinHeap::len.

Referenced by monster_compute_path().

Here is the caller graph for this function:

minheap_insert()

int minheap_insert	(	MinHeap *	heap,
		void *	ob
	)

Inserts an element into the min-heap.

Parameters

heap	Heap to insert into.
ob	The data object being inserted.

Returns

0 if successful, -1 if the heap is already full.

Definition at line 184 of file minheap.cpp.

References MinHeap::arr, MinHeap::capacity, MinHeap::len, minheap_get_parent(), and minheap_normalize().

Referenced by monster_compute_path().

Here is the call graph for this function:

Here is the caller graph for this function:

minheap_normalize()

static void minheap_normalize ( MinHeap *  heap )

static

Normalize the minheap.

It is expcted that the value at arr[0] is the only element violating the minheap.

That element will be pushed down the tree to its proper place.

Definition at line 71 of file minheap.cpp.

References MinHeap::arr, MinHeap::get_measure, MinHeap::len, minheap_get_left(), and minheap_get_right().

Referenced by minheap_insert(), and minheap_remove().

Here is the call graph for this function:

Here is the caller graph for this function:

minheap_remove()

void* minheap_remove

(

MinHeap *

heap

)

Pops the top of the minheap off.

Parameters

heap	Heap to pop from.

Returns

The popped element, or NULL if the heap is empty.

Definition at line 209 of file minheap.cpp.

References MinHeap::arr, MinHeap::len, and minheap_normalize().

Referenced by monster_compute_path().

Here is the call graph for this function:

Here is the caller graph for this function: