lash_tree2.c (4149B)
1 #include <stdlib.h> 2 #include <stdio.h> 3 #include <string.h> 4 5 #include "liblash/lash_tree2.h" 6 7 lash_tree_t *lash_treeInit(lash_tree_t *tree, const unsigned int size) { 8 tree = (lash_tree_t*)malloc(sizeof(lash_tree_t)); 9 tree->val = (long int*)malloc(sizeof(long int) * size); 10 tree->item = (void*)malloc(sizeof(void*) * size); 11 12 if (tree->val == 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 lash_treeFree(lash_tree_t *tree) { 24 if (tree == NULL) 25 return; 26 27 if (tree->val != NULL) 28 free(tree->val); 29 30 if (tree->item != NULL) 31 free(tree->item); 32 33 free(tree); 34 } 35 36 int lash_treePush(lash_tree_t *tree, const long int sortvalue, void *item) { 37 //printf("%p", item); 38 39 if (tree->count == tree->capacity) 40 return 0; 41 42 tree->count++; 43 *(tree->val + tree->shiftpos + tree->count - 1) = sortvalue; 44 *(tree->item + tree->shiftpos + tree->count - 1) = item; 45 46 lash_treeProcess(tree, tree->count, -1); 47 48 return tree->count; 49 } 50 51 int lash_treeShift(lash_tree_t *tree, long int *sortvalue, void **item) { 52 return lash_treeRemove(tree, 0, sortvalue, item); 53 } 54 55 int lash_treeRemove(lash_tree_t *tree, unsigned int position, long int *sortvalue, void **item) { 56 57 if (tree->count == 0) 58 return 0; 59 60 // retrieve the values from the position from the argument 61 *sortvalue = *(tree->val + tree->shiftpos + position); 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->val + tree->shiftpos + position) = *(tree->val + 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 lash_treeProcess(tree, position + 1, 1); 73 74 return tree->count; 75 } 76 77 int lash_treeProcess(lash_tree_t *tree, unsigned int currentposition, int direction) { 78 79 // towards end of pointer is downwards in the tree 80 // the direction to sort, -1 is from end towards start, 1 is from startposition towards end 81 82 while (direction != 0) { 83 84 long int *currentval = (tree->val + tree->shiftpos + currentposition - 1); 85 long int *nextval = NULL; 86 long int swapval = -1; 87 unsigned int nextposition; 88 89 switch(direction) { 90 91 // if there is still room to ascend in the tree, that is if the current position isn't 0 already. 92 case -1: 93 if (currentposition == 1) { 94 direction = 0; 95 } else { 96 nextposition = currentposition >> 1; 97 nextval = (tree->val + tree->shiftpos + nextposition - 1); 98 if (*currentval < *nextval) { 99 swapval = *currentval; 100 *currentval = *nextval; 101 *nextval = swapval; 102 currentposition = nextposition; 103 } else { 104 direction = 0; 105 } 106 } 107 break; 108 109 // if there is still room from the current position to descend one level in the tree): 110 // level 0 has 2^0 = entry 1 111 // level 1 has 2^1 = entries 2-3 112 // level 2 has 2^2 = entries 4-7 113 // 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) 114 // If we're at position 4, the check will be 4*2 = 8, which is out of bounds of level 2. 115 116 case 1: 117 nextposition = currentposition << 1; 118 119 if (nextposition <= tree->count) { 120 121 // compare both the child values, to pick the higher one 122 nextval = (tree->val + tree->shiftpos + nextposition - 1); 123 if (*nextval > *(nextval + 1)) { 124 nextval = (nextval + 1); 125 nextposition++; 126 } 127 128 // compare the values, set nextval back to null to stop the swapping if the value is not higher 129 if (*currentval <= *nextval) { 130 nextval = NULL; 131 } 132 133 if (nextval != NULL) { 134 swapval = *currentval; 135 *currentval = *nextval; 136 *nextval = swapval; 137 currentposition = nextposition; 138 } else { 139 direction = 0; 140 } 141 } else { 142 direction = 0; 143 } 144 break; 145 default: 146 direction = 0; 147 } 148 } 149 150 return currentposition; 151 } 152