Crossfire Server, Trunk
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)
 
static int minheap_get_left (int index)
 
static int minheap_get_parent (int index)
 
static int minheap_get_right (int index)
 
MinHeapminheap_init (int amt, int(*measure_func)(const void *), void(*cleanup_func)(void *))
 
void minheap_init_static (MinHeap *heap, void **arr, int amt, int(*measure_func)(const void *))
 
int minheap_insert (MinHeap *heap, void *ob)
 
static void minheap_normalize (MinHeap *heap)
 
void * minheap_remove (MinHeap *heap)
 

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_freeThe minheap to free.

Definition at line 226 of file minheap.cpp.

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

Referenced by teardown().

+ Here is the caller graph for this function:

◆ 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.

References npc_dialog::index.

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.

References npc_dialog::index.

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.

References npc_dialog::index.

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
amtThe capacity of the min-heap.
measure_funcPointer to the function to measure the data we're storing.
cleanup_funcPointer 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.

Referenced by START_TEST().

+ Here is the call graph for this function:
+ Here is the caller 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
heapPointer to the heap we are initializing.
arrPointer to the array of elements we are using.
amtThe capacity of the heap
measure_funcPointer 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(), and START_TEST().

+ 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
heapHeap to insert into.
obThe 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(), minheap_normalize(), and guildjoin::ob.

Referenced by monster_compute_path(), and START_TEST().

+ 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(), minheap_get_right(), and Ice::tmp.

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
heapHeap 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(), and START_TEST().

+ Here is the call graph for this function:
+ Here is the caller graph for this function: