tree.h (4476B)
1 #ifndef LASH_TREE_H_ 2 #define LASH_TREE_H_ 3 4 typedef long int lash_tree_key_t; 5 6 typedef struct lash_tree_t { 7 lash_tree_key_t **key; 8 void **item; 9 //unsigned int shiftpos; 10 unsigned int count; 11 unsigned int capacity; 12 //unsigned int foldbackthreshold; 13 int average; 14 } lash_tree_t; 15 16 #ifdef __cplusplus 17 extern "C" { 18 #endif 19 20 lash_tree_t * lash_treeInit(lash_tree_t *tree, const unsigned int size) ; 21 int lash_treePush(lash_tree_t *tree, void *item, lash_tree_key_t *key); 22 int lash_treeShift(lash_tree_t *tree, void **item); 23 int lash_treeRemove(lash_tree_t *tree, unsigned int position, void **item); 24 int _lash_treeProcess(lash_tree_t *tree, unsigned int currentposition, int direction); 25 void lash_treeFree(lash_tree_t *tree); 26 #ifdef __cplusplus 27 } 28 #endif 29 30 31 #endif // LASH_TREE_H_ 32 33 /** 34 * \file lash_tree3.h 35 * \brief Implementation of binary tree for sorting generic objects 36 * 37 * \author Louis Holbrook 38 * \version 0.2 39 * 40 * \todo Possibility to remove from other positions in the tree than start 41 * 42 * This library aims to be a fast and small way of storing generic structs (or even just integers) in a binary tree for fast retrieval in sorted order. 43 * It was written as a backend for A* pathfinding code 44 * 45 * Structs are stored as *void* pointers, which means they can reference anything at all. 46 * Every "entry" in the tree will have one *void* pointer and one pointer to the sort value. At least one member of the struct must be of `lash_tree_key_t` type, which this pointer will point to. 47 * Theoretically, different struct types can be stored in the different entries of the tree. 48 * 49 */ 50 /** 51 * \var typedef lash_tree_key_t 52 * \param lash_tree_key_t Sort value type for `lash_tree_t` 53 */ 54 55 /** 56 * \var typedef lash_tree_t 57 * \param **key Pointers to the sort key values 58 * \param **item Pointers to the sorted data structures 59 * \param count Current amount of items in the tree 60 * \param capacity Maximum amount of items allocated 61 * \param average Sort value at the middle of the array (currently unused) 62 */ 63 64 /** 65 * \struct lash_tree_t 66 * \param **key Pointers to the sort key values 67 * \param **item Pointers to the sorted data structures 68 * \param count Current amount of items in the tree 69 * \param capacity Maximum amount of items allocated 70 * \param average Sort value at the middle of the array (currently unused) 71 */ 72 73 74 /** 75 * \fn lash_treeInit(lash_tree_t *tree, const unsigned int size) 76 * \brief Allocates memory and initializes members 77 * 78 * \param *tree Pointer to allocate memory to 79 * \param size Amount of items to allocate 80 * \return NULL if not successful 81 * 82 */ 83 84 /** 85 * \fn lash_treeFree(lash_tree_t *tree) 86 * \brief Frees up memory 87 * 88 * \param *tree Tree struct to free 89 * 90 */ 91 92 /** 93 * \fn lash_treePush(lash_tree_t *tree, void *item, lash_tree_key_t *key) 94 * \brief Add a new item to the tree 95 * 96 * \param *tree Tree struct to add to 97 * \param *item Data structure to add 98 * \param *key Pointer to the sort key value in `*item` 99 * \return Number of items in the tree after adding. If tree is full -1 is returned. 100 * 101 * The data structure must have one member of type `lash_tree_key_t` 102 * if `*key` is omitted, it will be assumed that the first position at the address of `*item` is of this type, and will be used as the sort value for this item. 103 * The item is added to the end of the tree, and stepwise moved up the tree until it meets a lower value. 104 * 105 */ 106 107 /** 108 * \fn lash_treeShift(lash_tree_t *tree, void **item) 109 * \brief Retrieves and removes the first item from the tree 110 * 111 * \param *tree Tree struct to shift from 112 * \param **item Pointer to pass the retrieved data structure pointer in 113 * \return Wrapper for `lash_treeRemove` with position argument 0 114 * 115 * \sa lash_treeRemove 116 * 117 */ 118 119 /** 120 * \fn lash_treeRemove(lash_tree_t *tree, unsigned int position, void **item) 121 * \brief Retrieves and removes an item from the tree 122 * 123 * \param *tree Tree struct to shift from 124 * \param position What sort position to remove from. 125 * \param **item Pointer to pass the retrieved data structure pointer in 126 * \return Number of items in the tree after removal. If the tree was already empty -1 is returned. 127 * 128 * \sa lash_treePush 129 * 130 * \warning Currently only position 0 is tested. Setting another value causes undefined behavior and will probably not work. 131 * 132 * After the item is retrieved, the item at the end of the tree is moved up to replace it, and stepwise moved down the tree until meets a higher value. 133 * 134 * 135 */