lash_tree.h (5153B)
1 #ifndef LASH_TREE_H_ 2 #define LASH_TREE_H_ 3 4 typedef struct lash_tree_t lash_tree_t; 5 6 struct lash_tree_t { 7 long int *heap; 8 unsigned int *idx; 9 //void *content; 10 unsigned int *local; 11 unsigned int position; 12 unsigned int capacity; 13 int average; 14 }; 15 16 #ifdef __cplusplus 17 extern "C" { 18 #endif 19 lash_tree_t * lash_treeInit(lash_tree_t *tree, const unsigned int size) ; 20 //int lash_treePush(lash_tree_t *tree, const long int sortvalue, void *content); 21 int lash_treePush(lash_tree_t *tree, const long int sortvalue, const int local); 22 int lash_treeShift(lash_tree_t *tree, long int *number, unsigned int *local); 23 int lash_treeRemove(lash_tree_t *tree, unsigned int position, long int *number, unsigned int *local); 24 int lash_treeItemProcess(lash_tree_t *tree, unsigned int currentposition); 25 int lash_treeFindByLocal(lash_tree_t *tree, const int local); 26 int lash_treeFindBySort(lash_tree_t *tree, const int sortvalue); 27 void lash_treeFree(lash_tree_t *tree); 28 #ifdef __cplusplus 29 } 30 #endif 31 32 33 #endif // LASH_TREE_H_ 34 35 /** 36 * \file lash_tree.h 37 * \brief LASH bittree implementation 38 * 39 * \todo tree name seems to be global, interferes if local symbols have same name 40 */ 41 42 /** 43 * \fn void lash_treeFree(lash_tree_t *tree) 44 * \brief Frees memory of the given tree's heap, idx and local arrays, and lately the allocation to the tree itself. 45 * \param tree Pointer to the tree to operate on 46 */ 47 /** 48 * \fn int lash_treeFindBySort(lash_tree_t *tree, const int sortvalue) 49 * \brief Find a sort index by a heap-value 50 * \param tree Pointer to the tree to operate on 51 * \param local the value to search for 52 * 53 * Returns the sort position (the value's position in the idx array) 54 */ 55 56 /** 57 * \fn int lash_treeFindByLocal(lash_tree_t *tree, const int local) 58 * \brief Find a sort index by an associated value 59 * \param tree Pointer to the tree to operate on 60 * \param local the associate value to search for 61 * 62 * Returns the sort position (the value's position in the idx array) 63 */ 64 65 /** 66 * \fn int lash_treeItemProcess(lash_tree_t *tree, unsigned int currentposition) 67 * \brief Sort the value at given position 68 * \param tree Pointer to the tree to operate on 69 * \param currentposition The position of the value to sort 70 * 71 * Places the value at the specified position (of the \ref lash_tree::idx array) at the appropriate ascending sort position. 72 * The function check to see which "direction" the lower value is (if it's at pos/2 or one of pos*2 pos*2+1. If both the higher indices are lower, the highest index will be chosen. 73 * If currentposition is not given, then the value at the top of the tree is selected. 74 * Returns the end position of the value 75 * 76 */ 77 78 /** 79 * \fn int lash_treeRemove(lash_tree_t *tree, unsigned int position, long int *number, unsigned int *local) 80 * \brief Removes an item at a certain index from tree 81 * \param tree Pointer to the tree to operate on 82 * \param position The position to remove 83 * \param number If not NULL, the shifted heap value is stored here 84 * \param local If not NULL, the shifted associate heap value is stored here 85 * 86 * Decrements position counter, If the number and local params are not NULL respectively, the extracted values are copied to them. 87 * Updates the average, and calls \ref lash_treeProcess() to update the sort order 88 * 89 */ 90 91 /** 92 * \fn int lash_treeShift(lash_tree_t *tree, long int *number, unsigned int *local) 93 * \brief Shift the first item from the tree 94 * \param tree Pointer to the tree to operate on 95 * \param number If not NULL, the shifted heap value is stored here 96 * \param local If not NULL, the shifted associate heap value is stored here 97 * 98 * Alias for \ref lashTreeRemove with position 0 99 * 100 * \see lashTreeRemove 101 */ 102 103 /** 104 * \fn int lash_treePush(lash_tree_t *tree, const long int sortvalue, const int local); 105 * \brief Add item to tree 106 * \param tree Pointer to the tree to operate on 107 * \param sortvalue The value to add 108 * \param local the (optional) associated value to add 109 * 110 * Appends the value to the heap array, adds the index to the index array, updates the average and calls lashTreeItemProcess to update the sort. 111 * Returns the value returned from lash_treeItemProcess() 112 * 113 * \see lashTreeItemProcess 114 * 115 */ 116 117 /** 118 * \struct lash_tree 119 * \brief struct holding the bittree contents. 120 * \var lash_tree::heap 121 * The values to be sorted 122 * \var lash_tree::idx 123 * The sort order, pointing to incides of the heap array 124 * \var lash_tree::local 125 * A foreign value associated with the value in the heap 126 * \var lash_tree::position 127 * Index of the last current element in the array 128 * \var lash_tree::capacity 129 * Maximal number of elements the array can hold 130 * \var lash_tree::average 131 * The average value of all elements in the array (used for shortening the search by hinting at the value in the middle) 132 */ 133 134 /** 135 * \fn lash_tree_t * lash_treeInit(lash_tree_t *tree, const unsigned int size) 136 * \brief Prepares the bittree for use. 137 * \param *tree Pointer to the tree struct to initialize 138 * \param size Max number of units for the bittree 139 * 140 * Clears position, sets capacity to specified size and allocates memory. Returns NULL if memory could not be allocated. 141 */