tree.c_intindex (4905B)
1 #include <stdlib.h> 2 #include <stdio.h> 3 #include <string.h> 4 5 #include "tree.h" 6 7 lash_tree_t *lashTreeInit(lash_tree_t *tree, const unsigned int size) { 8 tree = (lash_tree_t*)malloc(sizeof(lash_tree_t)); 9 tree->key = (lash_tree_key_t*)malloc(sizeof(lash_tree_key_t*) * size + 1); 10 tree->item = (void*)malloc(sizeof(void*) * size + 1); 11 12 if (tree->key == NULL || tree->item == NULL) 13 return NULL; 14 15 tree->count = 0; 16 tree->shiftpos = 0; 17 tree->capacity = size; 18 tree->foldbackthreshold = tree->capacity / 2; 19 20 return tree; 21 } 22 23 void lashTreeFree(lash_tree_t *tree) { 24 if (tree == NULL) 25 return; 26 27 if (tree->key != NULL) 28 free(tree->key); 29 30 if (tree->item != NULL) 31 free(tree->item); 32 33 free(tree); 34 } 35 36 int lashTreePush(lash_tree_t *tree, lash_tree_key_t *key, void *item) { 37 //printf("%p", item); 38 39 if (tree->count == tree->capacity) 40 return 0; 41 42 tree->count++; 43 44 *(tree->key + tree->shiftpos + tree->count - 1) = key; 45 *(tree->item + tree->shiftpos + tree->count - 1) = item; 46 47 lashTreeProcess(tree, tree->count, -1); 48 49 return tree->count; 50 } 51 52 int lashTreeShift(lash_tree_t *tree, void **item) { 53 return lashTreeRemove(tree, 0, item); 54 } 55 56 int lashTreeRemove(lash_tree_t *tree, unsigned int position, void **item) { 57 58 if (tree->count == 0) 59 return 0; 60 61 // retrieve the values from the position from the argument 62 *item = *(tree->item + tree->shiftpos + position); 63 64 // move the values from the end of the tree to the position from the argument 65 *(tree->key + tree->shiftpos + position) = *(tree->key + tree->shiftpos + tree->count - 1); 66 *(tree->item + tree->shiftpos + position) = *(tree->item + tree->shiftpos + tree->count - 1); 67 68 // reduce the count of the tree 69 tree->count--; 70 71 // iterate the new value down the tree to its proper place 72 lashTreeProcess(tree, position + 1, 1); 73 74 return tree->count; 75 } 76 int lashTreeProcess(lash_tree_t *tree, unsigned int currentposition, int direction) { 77 78 // towards end of pointer is downwards in the tree 79 // the direction to sort, -1 is from end towards start, 1 is from startposition towards end 80 81 while (direction != 0) { 82 83 lash_tree_key_t *currentkey = *(tree->key + tree->shiftpos + currentposition - 1); 84 lash_tree_key_t *nextkey = NULL; 85 lash_tree_key_t *swapkey; 86 //lash_tree_key_t swapkey; 87 void *swapitem;; 88 void *currentitem; 89 void *nextitem; 90 91 unsigned int nextposition; 92 93 switch(direction) { 94 95 // if there is still room to ascend in the tree, that is if the current position isn't 0 already. 96 case -1: 97 if (currentposition == 1) { 98 direction = 0; 99 } else { 100 nextposition = currentposition >> 1; 101 nextkey = *(tree->key + tree->shiftpos + nextposition - 1); 102 if (*currentkey < *nextkey) { 103 /*swapkey = *currentkey; 104 *currentkey = *nextkey; 105 *nextkey = swapkey;*/ 106 107 currentitem = *(tree->item + tree->shiftpos + currentposition - 1); 108 nextitem = *(tree->item + tree->shiftpos + nextposition - 1); 109 110 // if the position of the key is not in the first address of the item we need to move it separately 111 if ((lash_tree_key_t *)currentitem != currentkey) { 112 swapkey = currentkey; 113 *(tree->key + tree->shiftpos + currentposition - 1) = nextkey; 114 *(tree->key + tree->shiftpos + nextposition - 1) = swapkey; 115 } 116 117 swapitem = currentitem; 118 *(tree->item + tree->shiftpos + currentposition - 1) = nextitem; 119 *(tree->item + tree->shiftpos + nextposition - 1) = swapitem; 120 121 currentposition = nextposition; 122 } else { 123 direction = 0; 124 } 125 } 126 break; 127 128 // if there is still room from the current position to descend one level in the tree): 129 // level 0 has 2^0 = entry 1 130 // level 1 has 2^1 = entries 2-3 131 // level 2 has 2^2 = entries 4-7 132 // if we're at position 3, the check will be 3*2 = 6, which is within bounds of level 2, and points to elements 6 and 7 (the children of 3) 133 // If we're at position 4, the check will be 4*2 = 8, which is out of bounds of level 2. 134 135 case 1: 136 nextposition = currentposition << 1; 137 138 if (nextposition <= tree->count) { 139 140 // compare both the child values, to pick the higher one 141 nextkey = *(tree->key + tree->shiftpos + nextposition - 1); 142 if (*nextkey > *(nextkey + 1)) { 143 nextkey = (nextkey + 1); 144 nextposition++; 145 } 146 147 // compare the values, set nextkey back to null to stop the swapping if the value is not higher 148 if (*currentkey <= *nextkey) { 149 nextkey = NULL; 150 } 151 152 if (nextkey != NULL) { 153 /*swapkey = *currentkey; 154 *currentkey = *nextkey; 155 *nextkey = swapkey;*/ 156 swapkey = currentkey; 157 currentkey = nextkey; 158 nextkey = swapkey; 159 currentposition = nextposition; 160 } else { 161 direction = 0; 162 } 163 } else { 164 direction = 0; 165 } 166 break; 167 default: 168 direction = 0; 169 } 170 } 171 172 return currentposition; 173 }