Crossfire Server, Trunk

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) 
MinHeap *  minheap_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) 
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.
void minheap_free  (  MinHeap *  to_free  ) 
Cleans the minheap
to_free  The minheap to free. 
Definition at line 226 of file minheap.cpp.
References MinHeap::arr, MinHeap::element_cleanup, and MinHeap::len.
Referenced by teardown().

inlinestatic 
Get the index of the left child in the heap. left child is index * 2 + 1.
Definition at line 34 of file minheap.cpp.
References npc_dialog::index.
Referenced by minheap_normalize().

inlinestatic 
Get the index of the parent in the heap. parent is (index  1) / 2 (rounded down).
Definition at line 59 of file minheap.cpp.
References npc_dialog::index.
Referenced by minheap_insert().

inlinestatic 
Get the index of the right child in the heap. right child is index * 2 + 2.
Definition at line 47 of file minheap.cpp.
References npc_dialog::index.
Referenced by minheap_normalize().
MinHeap* minheap_init  (  int  amt, 
int(*)(const void *)  measure_func,  
void(*)(void *)  cleanup_func  
) 
Function to intialize the minheap
amt  The capacity of the minheap. 
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. 
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().
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.
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(), and START_TEST().
int minheap_insert  (  MinHeap *  heap, 
void *  ob  
) 
Inserts an element into the minheap
heap  Heap to insert into. 
ob  The data object being inserted. 
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().

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().
void* minheap_remove  (  MinHeap *  heap  ) 
Pops the top of the minheap off.
heap  Heap to pop from. 
Definition at line 209 of file minheap.cpp.
References MinHeap::arr, MinHeap::len, and minheap_normalize().
Referenced by monster_compute_path(), and START_TEST().