lash_tree.c.old (6951B)
1 #include <stdlib.h> 2 #include "liblash/lash_tree.h" 3 4 lash_tree_t *lashTreeInit(lash_tree_t *tree, const unsigned int size) { 5 int i; 6 tree = (lash_tree_t*)malloc(sizeof(lash_tree_t)); 7 tree->heap = (long int*)malloc(sizeof(long int) * size); 8 //tree->content = (void*)malloc(sizeof(void*) * size); 9 tree->local = (unsigned int*)calloc(size, sizeof(unsigned int*)); 10 tree->idx = (unsigned int*)malloc(sizeof(unsigned int) * size); 11 if (tree->heap == NULL || tree->idx == NULL) 12 return NULL; 13 14 tree->position = 0; 15 tree->capacity = size; 16 *tree->idx = 0; 17 18 return tree; 19 } 20 21 22 //int lashTreePush(lash_tree_t *ptree, const long int sortvalue, void *content) { 23 int lashTreePush(lash_tree_t *tree, const long int sortvalue, const int local) { 24 25 if (tree->position == tree->capacity) 26 return -1; 27 28 tree->position++; 29 30 // put the new number at the end of the content array and update the current position 31 *(tree->idx + tree->position - 1) = tree->position - 1; 32 *(tree->heap + tree->position - 1) = sortvalue; 33 *(tree->local + tree->position - 1) = local; 34 35 // put the content array index to the new number on the index array 36 37 38 // increase the average (for faster searching later) 39 int tmpaverage = tree->average; 40 tmpaverage *= (tree->position - 1); 41 tmpaverage += sortvalue; 42 tmpaverage /= tree->position; 43 tree->average = tmpaverage; 44 45 return lashTreeItemProcess(tree, tree->position); 46 } 47 48 int lashTreeShift(lash_tree_t *tree, long int *number, unsigned int *local) { 49 return lashTreeRemove(tree, 0, number, local); 50 } 51 52 // note that here position is 1 for first, not 0 53 int lashTreeRemove(lash_tree_t *tree, unsigned int position, long int *number, unsigned int *local) { 54 long int currentnumber; 55 long int currentindex; 56 int i; 57 58 if (tree->position == 0) 59 return -1; 60 61 if (position > tree->position) 62 return -1; 63 64 // if there is only one item, retrieve this and finish 65 if (tree->position == 1) { 66 if (number != NULL) 67 *number = *(tree->heap + *tree->idx); 68 if (local != NULL) 69 *local = *(tree->local + *tree->idx); 70 tree->position = 0; 71 //tree->idx = 0; 72 return 0; 73 } 74 75 // if no position is set, then take the top of the heap 76 if (position == 0) 77 position = 1; 78 79 // remove the number on the supplied index, and move the number from the bottom in its place 80 currentindex = *(tree->idx + position - 1); 81 currentnumber = *(tree->heap + currentindex); 82 83 if (number != NULL) 84 *number = currentnumber; 85 if (local != NULL) 86 *local = *(tree->local + currentindex); 87 88 *(tree->local + currentindex) = *(tree->local + *(tree->idx + tree->position - 1)); 89 *(tree->heap + currentindex) = *(tree->heap + *(tree->idx + tree->position - 1)); 90 *(tree->idx + position - 1) = *(tree->idx + tree->position - 1); 91 *(tree->idx + tree->position - 1) = currentindex; 92 93 tree->position--; 94 95 // decrease the average (for faster searching later) 96 if (tree->position == 0) { 97 tree->average = 0; 98 } else { 99 int tmpaverage = tree->average; 100 tmpaverage *= (tree->position + 1); 101 //tmpaverage -= *number; 102 tmpaverage -= currentnumber; 103 tmpaverage /= tree->position; 104 tree->average = tmpaverage; 105 } 106 107 return lashTreeItemProcess(tree, position); 108 109 } 110 111 // note that here currentposition is 1 for first, not 0 112 int lashTreeItemProcess(lash_tree_t *tree, unsigned int currentposition) { 113 114 // choose direction (-1 is up, 1 is down) 115 int direction = 0; 116 unsigned int newposition = 0; 117 118 if (tree->position == 1) { 119 return (int)1; 120 } else if (currentposition <= 1) { 121 currentposition = 1; 122 direction = 1; 123 newposition = currentposition * 2; 124 // if it's the first value 125 126 } else if (currentposition * 2 <= tree->position) { 127 if (*(tree->heap + *(tree->idx + currentposition - 1)) > *(tree->heap + *(tree->idx + (currentposition * 2) - 1)) || *(tree->heap + *(tree->idx + currentposition - 1)) > *(tree->heap + *(tree->idx + (currentposition * 2)))) { 128 direction = 1; 129 newposition = (currentposition * 2); 130 } 131 } else if (*(tree->heap + *(tree->idx + currentposition - 1)) < *(tree->heap + *(tree->idx + (int)(currentposition / 2) - 1))) { 132 direction = -1; 133 newposition = (unsigned int)currentposition / 2; 134 } 135 136 switch (direction) { 137 case -1: 138 // move the content index up the index array until the number above in the heap is smaller or equal, or until we hit the start of the heap 139 while (newposition > 0) { 140 if (*(tree->heap + *(tree->idx + newposition - 1)) > *(tree->heap + *(tree->idx + currentposition - 1))) { 141 int tmpindex = *(tree->idx + newposition - 1); 142 *(tree->idx + newposition - 1) = *(tree->idx + currentposition - 1); 143 *(tree->idx + currentposition - 1) = tmpindex; 144 } else { 145 break; 146 } 147 currentposition = newposition; 148 newposition = (unsigned int)newposition / 2; 149 } 150 break; 151 case 1: 152 // until end of heap is reached, or the next number is higher 153 while (newposition <= tree->position) { 154 unsigned int swapposition = currentposition; 155 // move to next level if the next level child is higher 156 if (*(tree->heap + *(tree->idx + newposition - 1)) < *(tree->heap + *(tree->idx + currentposition - 1))) { 157 swapposition = newposition; 158 // check if either of the left or right children are higher (if there are two children, if not we're at the end of the heap) 159 if (newposition + 1 <= tree->position) 160 // if the right child is higher, then move there 161 if (*(tree->heap + *(tree->idx + newposition)) < *(tree->heap + *(tree->idx + newposition - 1))) 162 swapposition = newposition + 1; 163 } else if (newposition + 1 <= tree->position) { 164 if (*(tree->heap + *(tree->idx + newposition)) < *(tree->heap + *(tree->idx + currentposition - 1))) 165 // if the right child is higher, then move there 166 if (*(tree->heap + *(tree->idx + newposition)) < *(tree->heap + *(tree->idx + newposition - 1))) 167 swapposition = newposition + 1; 168 } 169 170 // if a move has taken place 171 if (swapposition != currentposition) { 172 unsigned int tmpindex = *(tree->idx + currentposition - 1); 173 *(tree->idx + currentposition - 1) = *(tree->idx + swapposition - 1); 174 *(tree->idx + swapposition - 1) = tmpindex; 175 } else { 176 break; 177 } 178 179 currentposition = swapposition; 180 newposition = swapposition * 2; 181 } 182 break; 183 default: 184 currentposition = 0; 185 newposition = 0; 186 } 187 188 return (int)currentposition; 189 } 190 191 int lashTreeFindByLocal(lash_tree_t *tree, const int local) { 192 int i; 193 for (i = tree->position - 1; i >= 0; i--) { 194 if (*(tree->local + *(tree->idx + i)) == local) 195 return i; 196 } 197 return -1; 198 } 199 200 int lashTreeFindBySort(lash_tree_t *tree, const int sortvalue) { 201 int i; 202 for (i = tree->position - 1; i >= 0; i--) { 203 if (*(tree->heap + *(tree->idx + i)) == sortvalue) 204 return i; 205 } 206 return -1; 207 } 208 209 void lashTreeFree(lash_tree_t *tree) { 210 if (tree != NULL) { 211 if (tree->local != NULL) 212 free(tree->local); 213 if (tree->heap != NULL) 214 free(tree->heap); 215 if (tree->idx != NULL) 216 free(tree->idx); 217 free(tree); 218 } 219 }