liblash

A bianry tree implementation used for game development from scratch
git clone git://holbrook.no/liblash.git
Log | Files | Refs | LICENSE

commit 32fa4534790b12832492f5930f91373ba068d94d
parent 401812317e3bc69b5f0070b979492099283e5dac
Author: nolash <dev@holbrook.no>
Date:   Wed,  8 Jan 2020 20:58:53 +0100

autoconf

Diffstat:
A.old/lash_tree.c | 236+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A.old/lash_tree.c.fail | 234+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A.old/lash_tree.c.old | 219+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A.old/lash_tree.h | 141+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A.old/lash_tree2.c | 152+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A.old/lash_tree2.h | 31+++++++++++++++++++++++++++++++
A.old/lash_tree2_dump.c | 64++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A.old/lash_tree2_dump.h | 18++++++++++++++++++
A.old/lash_tree_dump.c | 77+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A.old/lash_tree_dump.h | 12++++++++++++
Rtree.c_intindex -> .old/tree.c_intindex | 0
ACOPYING | 2++
AINSTALL | 2++
DMakefile | 20--------------------
AMakefile.am | 9+++++++++
AMakefile.old | 21+++++++++++++++++++++
Aconfigure.ac | 29+++++++++++++++++++++++++++++
17 files changed, 1247 insertions(+), 20 deletions(-)

diff --git a/.old/lash_tree.c b/.old/lash_tree.c @@ -0,0 +1,236 @@ +#include <stdlib.h> +#include "liblash/lash_tree.h" +#include <stdio.h> +#include "liblash/lash_tree_dump.h" + +lash_tree_t *lash_treeInit(lash_tree_t *tree, const unsigned int size) { + int i; + tree = (lash_tree_t*)malloc(sizeof(lash_tree_t)); + tree->heap = (long int*)malloc(sizeof(long int) * size); + tree->local = (unsigned int*)calloc(size, sizeof(unsigned int*)); + tree->idx = (int*)malloc(sizeof(int) * size); + if (tree->heap == NULL || tree->idx == NULL) + return NULL; + + for (i = 0; i < size; i++) + *(tree->idx + i) = -1; + + tree->position = 0; + tree->capacity = size; + *tree->idx = 0; + + return tree; +} + + +//int lash_treePush(lash_tree_t *ptree, const long int sortvalue, void *content) { +int lash_treePush(lash_tree_t *tree, const long int sortvalue, const int local) { + + if (tree->position == tree->capacity) + return -1; + + tree->position++; + + // put the new number at the end of the content array and update the current position + *(tree->idx + tree->position - 1) = tree->position - 1; + *(tree->heap + tree->position - 1) = sortvalue; + *(tree->local + tree->position - 1) = local; + + // put the content array index to the new number on the index array + + + // increase the average (for faster searching later) + int tmpaverage = tree->average; + tmpaverage *= (tree->position - 1); + tmpaverage += sortvalue; + tmpaverage /= tree->position; + tree->average = tmpaverage; + + return lash_treeItemProcess(tree, tree->position); +} + +int lash_treeShift(lash_tree_t *tree, long int *number, unsigned int *local) { + return lash_treeRemove(tree, 0, number, local); +} + +// note that here position is 1 for first, not 0 +int lash_treeRemove(lash_tree_t *tree, unsigned int position, long int *number, unsigned int *local) { + long int currentnumber; + long int currentindex; + int i; + int result; + + if (tree->position == 0) + return -1; + + if (position > tree->position) + return -1; + + // if there is only one item, retrieve this and finish + if (tree->position == 1) { + if (number != NULL) + *number = *(tree->heap + *tree->idx); + if (local != NULL) + *local = *(tree->local + *tree->idx); + tree->position = 0; + //tree->idx = 0; + return 0; + } + + // if no position is set, then take the top of the heap + if (position == 0) + position = 1; + + // remove the number on the supplied index, and move the number from the bottom in its place + currentindex = *(tree->idx + position - 1); + currentnumber = *(tree->heap + currentindex); + + if (number != NULL) + *number = currentnumber; + if (local != NULL) + *local = *(tree->local + currentindex); + + *(tree->idx + currentindex) = tree->position - 1; + + //*(tree->local + currentindex) = *(tree->local + *(tree->idx + tree->position - 1)); + //*(tree->heap + currentindex) = *(tree->heap + *(tree->idx + tree->position - 1)); + //*(tree->idx + position - 1) = *(tree->idx + tree->position - 1); + //*(tree->idx + tree->position - 1) = currentindex; + + tree->position--; + + // decrease the average (for faster searching later) + if (tree->position == 0) { + tree->average = 0; + } else { + int tmpaverage = tree->average; + tmpaverage *= (tree->position + 1); + //tmpaverage -= *number; + tmpaverage -= currentnumber; + tmpaverage /= tree->position; + tree->average = tmpaverage; + } + + result = lash_treeItemProcess(tree, position); + + // this probably defeats the speed gain from binary tree. + for (i = position; i <= tree->position; i++) { + *(tree->heap + i - 1) = *(tree->heap + i); + *(tree->local + i - 1) = *(tree->local + i); + *(tree->idx + i - 1) -= 1; + } + + return result; + + +} + +// note that here currentposition is 1 for first, not 0 +int lash_treeItemProcess(lash_tree_t *tree, unsigned int currentposition) { + + // choose direction (-1 is up, 1 is down) + int direction = 0; + unsigned int newposition = 0; + + if (tree->position == 1) { + return (int)1; + } else if (currentposition <= 1) { + currentposition = 1; + direction = 1; + newposition = currentposition * 2; + // if it's the first value + + } else if (currentposition * 2 <= tree->position) { + 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)))) { + direction = 1; + newposition = (currentposition * 2); + } + } else if (*(tree->heap + *(tree->idx + currentposition - 1)) < *(tree->heap + *(tree->idx + (int)(currentposition / 2) - 1))) { + direction = -1; + newposition = (unsigned int)currentposition / 2; + } + + switch (direction) { + case -1: + // 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 + while (newposition > 0) { + if (*(tree->heap + *(tree->idx + newposition - 1)) > *(tree->heap + *(tree->idx + currentposition - 1))) { + int tmpindex = *(tree->idx + newposition - 1); + *(tree->idx + newposition - 1) = *(tree->idx + currentposition - 1); + *(tree->idx + currentposition - 1) = tmpindex; + } else { + break; + } + currentposition = newposition; + newposition = (unsigned int)newposition / 2; + } + break; + case 1: + // until end of heap is reached, or the next number is higher + while (newposition <= tree->position) { + unsigned int swapposition = currentposition; + // move to next level if the next level child is higher + if (*(tree->heap + *(tree->idx + newposition - 1)) < *(tree->heap + *(tree->idx + currentposition - 1))) { + swapposition = newposition; + // 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) + if (newposition + 1 <= tree->position) + // if the right child is higher, then move there + if (*(tree->heap + *(tree->idx + newposition)) < *(tree->heap + *(tree->idx + newposition - 1))) + swapposition = newposition + 1; + } else if (newposition + 1 <= tree->position) { + if (*(tree->heap + *(tree->idx + newposition)) < *(tree->heap + *(tree->idx + currentposition - 1))) + // if the right child is higher, then move there + if (*(tree->heap + *(tree->idx + newposition)) < *(tree->heap + *(tree->idx + newposition - 1))) + swapposition = newposition + 1; + } + + // if a move has taken place + if (swapposition != currentposition) { + unsigned int tmpindex = *(tree->idx + currentposition - 1); + *(tree->idx + currentposition - 1) = *(tree->idx + swapposition - 1); + *(tree->idx + swapposition - 1) = tmpindex; + } else { + break; + } + + currentposition = swapposition; + newposition = swapposition * 2; + } + break; + default: + currentposition = 0; + newposition = 0; + } + + return (int)currentposition; +} + +int lash_treeFindByLocal(lash_tree_t *tree, const int local) { + int i; + for (i = tree->position - 1; i >= 0; i--) { + if (*(tree->local + *(tree->idx + i)) == local) + return i; + } + return -1; +} + +int lash_treeFindBySort(lash_tree_t *tree, const int sortvalue) { + int i; + for (i = tree->position - 1; i >= 0; i--) { + if (*(tree->heap + *(tree->idx + i)) == sortvalue) + return i; + } + return -1; +} + +void lash_treeFree(lash_tree_t *tree) { + if (tree != NULL) { + if (tree->local != NULL) + free(tree->local); + if (tree->heap != NULL) + free(tree->heap); + if (tree->idx != NULL) + free(tree->idx); + free(tree); + } +} diff --git a/.old/lash_tree.c.fail b/.old/lash_tree.c.fail @@ -0,0 +1,234 @@ +#include <stdlib.h> +#include "liblash/lash_tree.h" +#include <stdio.h> + +lash_tree_t *lashTreeInit(lash_tree_t *tree, const unsigned int size) { + int i; + tree = (lash_tree_t*)malloc(sizeof(lash_tree_t)); + tree->heap = (long int*)malloc(sizeof(long int) * size); + //tree->content = (void*)malloc(sizeof(void*) * size); + tree->local = (unsigned int*)calloc(size, sizeof(unsigned int*)); + tree->idx = (unsigned int*)malloc(sizeof(unsigned int) * size); + if (tree->heap == NULL || tree->idx == NULL) + return NULL; + + tree->position = 0; + tree->capacity = size; + *tree->idx = 0; + + return tree; +} + + +int lashTreePush(lash_tree_t *tree, const long int sortvalue, const int local) { + + if (tree->position == tree->capacity) + return -1; + + tree->position++; + + // put the new number at the end of the content array and update the current position + if (*(tree->idx + tree->position - 1) == 0) + *(tree->idx + tree->position - 1) = tree->position; + *(tree->heap + tree->position - 1) = sortvalue; + *(tree->local + tree->position - 1) = local; + + // put the content array index to the new number on the index array + + + // increase the average (for faster searching later) + int tmpaverage = tree->average; + tmpaverage *= (tree->position - 1); + tmpaverage += sortvalue; + tmpaverage /= tree->position; + tree->average = tmpaverage; + + return lashTreeItemProcess(tree, tree->position); +} + +int lashTreeShift(lash_tree_t *tree, long int *number, unsigned int *local) { + return lashTreeRemove(tree, 0, number, local); +} + +// note that here position is 1 for first, not 0 +int lashTreeRemove(lash_tree_t *tree, unsigned int position, long int *number, unsigned int *local) { + long int currentnumber; + long int currentindex; + int i; + + if (tree->position == 0) + return -1; + + if (position > tree->position) + return -1; + + // if there is only one item, retrieve this and finish + if (tree->position == 1) { + if (number != NULL) + *number = *(tree->heap + *(tree->idx) - 1); + if (local != NULL) + *local = *(tree->local + *(tree->idx) - 1); + tree->position = 0; + //tree->idx = 0; + return 0; + } + + // if no position is set, then take the top of the heap + if (position == 0) + position = 1; + + // remove the number on the supplied index, and move the number from the bottom in its place + currentindex = *(tree->idx + position - 1); + currentnumber = *(tree->heap + currentindex - 1); + + if (number != NULL) + *number = currentnumber; + if (local != NULL) + *local = *(tree->local + currentindex - 1); + + *(tree->local + currentindex - 1) = *(tree->local + *(tree->idx + tree->position - 1) - 1); + *(tree->heap + currentindex - 1) = *(tree->heap + *(tree->idx + tree->position - 1) - 1); + *(tree->idx + position - 1) = *(tree->idx + tree->position - 1); + *(tree->idx + tree->position - 1) = currentindex; + + tree->position--; + + // decrease the average (for faster searching later) + if (tree->position == 0) { + tree->average = 0; + } else { + int tmpaverage = tree->average; + tmpaverage *= (tree->position + 1); + //tmpaverage -= *number; + tmpaverage -= currentnumber; + tmpaverage /= tree->position; + tree->average = tmpaverage; + } + + return lashTreeItemProcess(tree, position); + +} + +// note that here currentposition is 1 for first, not 0 +int lashTreeItemProcess(lash_tree_t *tree, unsigned int currentposition) { + + // choose direction (-1 is up / push, 1 is down / shift) + int direction = 0; + unsigned int newposition = 0; + + fprintf(stderr, "processing pos %d for heap value %li\n", currentposition, *(tree->heap + *(tree->idx + currentposition - 1) - 1)); + + // if it has only one element, there is nothing to do + if (tree->position == 1) { + return (int)1; + fprintf(stderr, "is only element\n"); + // if it's at the top, we can only go down + } else if (currentposition <= 1) { + currentposition = 1; + direction = 1; + newposition = currentposition * 2; + fprintf(stderr, "is topelement, direction is down, newposition is %d\n", newposition); + // if it's the first value + + // if the current position is not at the end of the array it's replacing a value that was removed, and there is room to move it down one level in the tree + } else if (currentposition * 2 <= tree->position) { + // this it must traverse down the tree, compare to the position of twice the value, and also the value adjacent ("right") to it to see if those values are lower, in which case they should be swapped + if (*(tree->heap + *(tree->idx + currentposition - 1) - 1) > *(tree->heap + *(tree->idx + (currentposition * 2) - 1) - 1) || *(tree->heap + *(tree->idx + currentposition - 1) - 1) > *(tree->heap + *(tree->idx + (currentposition * 2)) - 1)) { + direction = 1; + newposition = (currentposition * 2); + fprintf(stderr, "inside tree, has lower value below, direction is down, newposition is %d\n", newposition); + } + // if the value in the current position is lower than the value halfway up the array (up one level in the tree), then it should be swapped + } else if (*(tree->heap + *(tree->idx + currentposition - 1) - 1) < *(tree->heap + *(tree->idx + (int)(currentposition / 2) - 1) - 1)) { + direction = -1; + newposition = (unsigned int)currentposition / 2; + fprintf(stderr, "at bottom, has lower value halfway up, direction is up, newposition is %d\n", newposition); + } + + switch (direction) { + case -1: + // 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 + while (newposition > 0) { + long int newheap = *(tree->heap + *(tree->idx + newposition - 1) - 1); + long int oldheap = *(tree->heap + *(tree->idx + currentposition - 1) - 1); + fprintf(stderr, "Comparing old %li pos %d to new %li pos %d\n", oldheap, currentposition, newheap, newposition); + if (*(tree->heap + *(tree->idx + newposition - 1) - 1) > *(tree->heap + *(tree->idx + currentposition - 1) - 1)) { + unsigned int tmpindex = *(tree->idx + newposition - 1); + *(tree->idx + newposition - 1) = *(tree->idx + currentposition - 1); + *(tree->idx + currentposition - 1) = tmpindex; + } else { + break; + } + currentposition = newposition; + newposition = (unsigned int)newposition / 2; + } + break; + case 1: + // until end of heap is reached, or the next number is higher + while (newposition <= tree->position) { + unsigned int swapposition = currentposition; + // move to next level if the next level child is higher + if (*(tree->heap + *(tree->idx + newposition - 1) - 1) < *(tree->heap + *(tree->idx + currentposition - 1) - 1)) { + swapposition = newposition; + // 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) + if (newposition + 1 <= tree->position) + // if the right child is higher, then move there + if (*(tree->heap + *(tree->idx + newposition) - 1) < *(tree->heap + *(tree->idx + newposition - 1) - 1)) + swapposition = newposition + 1; + } else if (newposition + 1 <= tree->position) { + if (*(tree->heap + *(tree->idx + newposition) - 1) < *(tree->heap + *(tree->idx + currentposition - 1) - 1)) + // if the right child is higher, then move there + if (*(tree->heap + *(tree->idx + newposition) - 1) < *(tree->heap + *(tree->idx + newposition - 1) - 1)) + swapposition = newposition + 1; + } + + // if a move has taken place + if (swapposition != currentposition) { + unsigned int tmpindex = *(tree->idx + currentposition - 1); + *(tree->idx + currentposition - 1) = *(tree->idx + swapposition - 1); + *(tree->idx + swapposition - 1) = tmpindex; + } else { + break; + } + + currentposition = swapposition; + newposition = swapposition * 2; + } + break; + default: + currentposition = 0; + newposition = 0; + } + + return (int)currentposition; +} + +int lashTreeFindByLocal(lash_tree_t *tree, const int local) { + int i; + for (i = tree->position - 1; i >= 0; i--) { + if (*(tree->local + *(tree->idx + i) - 1) == local) + return i; + } + return -1; +} + +int lashTreeFindBySort(lash_tree_t *tree, const int sortvalue) { + int i; + for (i = tree->position - 1; i >= 0; i--) { + if (*(tree->heap + *(tree->idx + i) - 1) == sortvalue) + return i; + } + return -1; +} + +void lashTreeFree(lash_tree_t *tree) { + if (tree != NULL) { + if (tree->local != NULL) + free(tree->local); + if (tree->heap != NULL) + free(tree->heap); + if (tree->idx != NULL) + free(tree->idx); + free(tree); + } +} diff --git a/.old/lash_tree.c.old b/.old/lash_tree.c.old @@ -0,0 +1,219 @@ +#include <stdlib.h> +#include "liblash/lash_tree.h" + +lash_tree_t *lashTreeInit(lash_tree_t *tree, const unsigned int size) { + int i; + tree = (lash_tree_t*)malloc(sizeof(lash_tree_t)); + tree->heap = (long int*)malloc(sizeof(long int) * size); + //tree->content = (void*)malloc(sizeof(void*) * size); + tree->local = (unsigned int*)calloc(size, sizeof(unsigned int*)); + tree->idx = (unsigned int*)malloc(sizeof(unsigned int) * size); + if (tree->heap == NULL || tree->idx == NULL) + return NULL; + + tree->position = 0; + tree->capacity = size; + *tree->idx = 0; + + return tree; +} + + +//int lashTreePush(lash_tree_t *ptree, const long int sortvalue, void *content) { +int lashTreePush(lash_tree_t *tree, const long int sortvalue, const int local) { + + if (tree->position == tree->capacity) + return -1; + + tree->position++; + + // put the new number at the end of the content array and update the current position + *(tree->idx + tree->position - 1) = tree->position - 1; + *(tree->heap + tree->position - 1) = sortvalue; + *(tree->local + tree->position - 1) = local; + + // put the content array index to the new number on the index array + + + // increase the average (for faster searching later) + int tmpaverage = tree->average; + tmpaverage *= (tree->position - 1); + tmpaverage += sortvalue; + tmpaverage /= tree->position; + tree->average = tmpaverage; + + return lashTreeItemProcess(tree, tree->position); +} + +int lashTreeShift(lash_tree_t *tree, long int *number, unsigned int *local) { + return lashTreeRemove(tree, 0, number, local); +} + +// note that here position is 1 for first, not 0 +int lashTreeRemove(lash_tree_t *tree, unsigned int position, long int *number, unsigned int *local) { + long int currentnumber; + long int currentindex; + int i; + + if (tree->position == 0) + return -1; + + if (position > tree->position) + return -1; + + // if there is only one item, retrieve this and finish + if (tree->position == 1) { + if (number != NULL) + *number = *(tree->heap + *tree->idx); + if (local != NULL) + *local = *(tree->local + *tree->idx); + tree->position = 0; + //tree->idx = 0; + return 0; + } + + // if no position is set, then take the top of the heap + if (position == 0) + position = 1; + + // remove the number on the supplied index, and move the number from the bottom in its place + currentindex = *(tree->idx + position - 1); + currentnumber = *(tree->heap + currentindex); + + if (number != NULL) + *number = currentnumber; + if (local != NULL) + *local = *(tree->local + currentindex); + + *(tree->local + currentindex) = *(tree->local + *(tree->idx + tree->position - 1)); + *(tree->heap + currentindex) = *(tree->heap + *(tree->idx + tree->position - 1)); + *(tree->idx + position - 1) = *(tree->idx + tree->position - 1); + *(tree->idx + tree->position - 1) = currentindex; + + tree->position--; + + // decrease the average (for faster searching later) + if (tree->position == 0) { + tree->average = 0; + } else { + int tmpaverage = tree->average; + tmpaverage *= (tree->position + 1); + //tmpaverage -= *number; + tmpaverage -= currentnumber; + tmpaverage /= tree->position; + tree->average = tmpaverage; + } + + return lashTreeItemProcess(tree, position); + +} + +// note that here currentposition is 1 for first, not 0 +int lashTreeItemProcess(lash_tree_t *tree, unsigned int currentposition) { + + // choose direction (-1 is up, 1 is down) + int direction = 0; + unsigned int newposition = 0; + + if (tree->position == 1) { + return (int)1; + } else if (currentposition <= 1) { + currentposition = 1; + direction = 1; + newposition = currentposition * 2; + // if it's the first value + + } else if (currentposition * 2 <= tree->position) { + 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)))) { + direction = 1; + newposition = (currentposition * 2); + } + } else if (*(tree->heap + *(tree->idx + currentposition - 1)) < *(tree->heap + *(tree->idx + (int)(currentposition / 2) - 1))) { + direction = -1; + newposition = (unsigned int)currentposition / 2; + } + + switch (direction) { + case -1: + // 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 + while (newposition > 0) { + if (*(tree->heap + *(tree->idx + newposition - 1)) > *(tree->heap + *(tree->idx + currentposition - 1))) { + int tmpindex = *(tree->idx + newposition - 1); + *(tree->idx + newposition - 1) = *(tree->idx + currentposition - 1); + *(tree->idx + currentposition - 1) = tmpindex; + } else { + break; + } + currentposition = newposition; + newposition = (unsigned int)newposition / 2; + } + break; + case 1: + // until end of heap is reached, or the next number is higher + while (newposition <= tree->position) { + unsigned int swapposition = currentposition; + // move to next level if the next level child is higher + if (*(tree->heap + *(tree->idx + newposition - 1)) < *(tree->heap + *(tree->idx + currentposition - 1))) { + swapposition = newposition; + // 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) + if (newposition + 1 <= tree->position) + // if the right child is higher, then move there + if (*(tree->heap + *(tree->idx + newposition)) < *(tree->heap + *(tree->idx + newposition - 1))) + swapposition = newposition + 1; + } else if (newposition + 1 <= tree->position) { + if (*(tree->heap + *(tree->idx + newposition)) < *(tree->heap + *(tree->idx + currentposition - 1))) + // if the right child is higher, then move there + if (*(tree->heap + *(tree->idx + newposition)) < *(tree->heap + *(tree->idx + newposition - 1))) + swapposition = newposition + 1; + } + + // if a move has taken place + if (swapposition != currentposition) { + unsigned int tmpindex = *(tree->idx + currentposition - 1); + *(tree->idx + currentposition - 1) = *(tree->idx + swapposition - 1); + *(tree->idx + swapposition - 1) = tmpindex; + } else { + break; + } + + currentposition = swapposition; + newposition = swapposition * 2; + } + break; + default: + currentposition = 0; + newposition = 0; + } + + return (int)currentposition; +} + +int lashTreeFindByLocal(lash_tree_t *tree, const int local) { + int i; + for (i = tree->position - 1; i >= 0; i--) { + if (*(tree->local + *(tree->idx + i)) == local) + return i; + } + return -1; +} + +int lashTreeFindBySort(lash_tree_t *tree, const int sortvalue) { + int i; + for (i = tree->position - 1; i >= 0; i--) { + if (*(tree->heap + *(tree->idx + i)) == sortvalue) + return i; + } + return -1; +} + +void lashTreeFree(lash_tree_t *tree) { + if (tree != NULL) { + if (tree->local != NULL) + free(tree->local); + if (tree->heap != NULL) + free(tree->heap); + if (tree->idx != NULL) + free(tree->idx); + free(tree); + } +} diff --git a/.old/lash_tree.h b/.old/lash_tree.h @@ -0,0 +1,141 @@ +#ifndef LASH_TREE_H_ +#define LASH_TREE_H_ + +typedef struct lash_tree_t lash_tree_t; + +struct lash_tree_t { + long int *heap; + unsigned int *idx; + //void *content; + unsigned int *local; + unsigned int position; + unsigned int capacity; + int average; +}; + +#ifdef __cplusplus +extern "C" { +#endif +lash_tree_t * lash_treeInit(lash_tree_t *tree, const unsigned int size) ; +//int lash_treePush(lash_tree_t *tree, const long int sortvalue, void *content); +int lash_treePush(lash_tree_t *tree, const long int sortvalue, const int local); +int lash_treeShift(lash_tree_t *tree, long int *number, unsigned int *local); +int lash_treeRemove(lash_tree_t *tree, unsigned int position, long int *number, unsigned int *local); +int lash_treeItemProcess(lash_tree_t *tree, unsigned int currentposition); +int lash_treeFindByLocal(lash_tree_t *tree, const int local); +int lash_treeFindBySort(lash_tree_t *tree, const int sortvalue); +void lash_treeFree(lash_tree_t *tree); +#ifdef __cplusplus +} +#endif + + +#endif // LASH_TREE_H_ + +/** + * \file lash_tree.h + * \brief LASH bittree implementation + * + * \todo tree name seems to be global, interferes if local symbols have same name + */ + +/** + * \fn void lash_treeFree(lash_tree_t *tree) + * \brief Frees memory of the given tree's heap, idx and local arrays, and lately the allocation to the tree itself. + * \param tree Pointer to the tree to operate on + */ +/** + * \fn int lash_treeFindBySort(lash_tree_t *tree, const int sortvalue) + * \brief Find a sort index by a heap-value + * \param tree Pointer to the tree to operate on + * \param local the value to search for + * + * Returns the sort position (the value's position in the idx array) + */ + +/** + * \fn int lash_treeFindByLocal(lash_tree_t *tree, const int local) + * \brief Find a sort index by an associated value + * \param tree Pointer to the tree to operate on + * \param local the associate value to search for + * + * Returns the sort position (the value's position in the idx array) + */ + +/** + * \fn int lash_treeItemProcess(lash_tree_t *tree, unsigned int currentposition) + * \brief Sort the value at given position + * \param tree Pointer to the tree to operate on + * \param currentposition The position of the value to sort + * + * Places the value at the specified position (of the \ref lash_tree::idx array) at the appropriate ascending sort position. + * 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. + * If currentposition is not given, then the value at the top of the tree is selected. + * Returns the end position of the value + * + */ + +/** + * \fn int lash_treeRemove(lash_tree_t *tree, unsigned int position, long int *number, unsigned int *local) + * \brief Removes an item at a certain index from tree + * \param tree Pointer to the tree to operate on + * \param position The position to remove + * \param number If not NULL, the shifted heap value is stored here + * \param local If not NULL, the shifted associate heap value is stored here + * + * Decrements position counter, If the number and local params are not NULL respectively, the extracted values are copied to them. + * Updates the average, and calls \ref lash_treeProcess() to update the sort order + * + */ + +/** + * \fn int lash_treeShift(lash_tree_t *tree, long int *number, unsigned int *local) + * \brief Shift the first item from the tree + * \param tree Pointer to the tree to operate on + * \param number If not NULL, the shifted heap value is stored here + * \param local If not NULL, the shifted associate heap value is stored here + * + * Alias for \ref lashTreeRemove with position 0 + * + * \see lashTreeRemove + */ + +/** + * \fn int lash_treePush(lash_tree_t *tree, const long int sortvalue, const int local); + * \brief Add item to tree + * \param tree Pointer to the tree to operate on + * \param sortvalue The value to add + * \param local the (optional) associated value to add + * + * Appends the value to the heap array, adds the index to the index array, updates the average and calls lashTreeItemProcess to update the sort. + * Returns the value returned from lash_treeItemProcess() + * + * \see lashTreeItemProcess + * + */ + +/** + * \struct lash_tree + * \brief struct holding the bittree contents. + * \var lash_tree::heap + * The values to be sorted + * \var lash_tree::idx + * The sort order, pointing to incides of the heap array + * \var lash_tree::local + * A foreign value associated with the value in the heap + * \var lash_tree::position + * Index of the last current element in the array + * \var lash_tree::capacity + * Maximal number of elements the array can hold + * \var lash_tree::average + * The average value of all elements in the array (used for shortening the search by hinting at the value in the middle) + */ + +/** + * \fn lash_tree_t * lash_treeInit(lash_tree_t *tree, const unsigned int size) + * \brief Prepares the bittree for use. + * \param *tree Pointer to the tree struct to initialize + * \param size Max number of units for the bittree + * + * Clears position, sets capacity to specified size and allocates memory. Returns NULL if memory could not be allocated. + */ diff --git a/.old/lash_tree2.c b/.old/lash_tree2.c @@ -0,0 +1,152 @@ +#include <stdlib.h> +#include <stdio.h> +#include <string.h> + +#include "liblash/lash_tree2.h" + +lash_tree_t *lash_treeInit(lash_tree_t *tree, const unsigned int size) { + tree = (lash_tree_t*)malloc(sizeof(lash_tree_t)); + tree->val = (long int*)malloc(sizeof(long int) * size); + tree->item = (void*)malloc(sizeof(void*) * size); + + if (tree->val == NULL || tree->item == NULL) + return NULL; + + tree->count = 0; + tree->shiftpos = 0; + tree->capacity = size; + tree->foldbackthreshold = tree->capacity / 2; + + return tree; +} + +void lash_treeFree(lash_tree_t *tree) { + if (tree == NULL) + return; + + if (tree->val != NULL) + free(tree->val); + + if (tree->item != NULL) + free(tree->item); + + free(tree); +} + +int lash_treePush(lash_tree_t *tree, const long int sortvalue, void *item) { + //printf("%p", item); + + if (tree->count == tree->capacity) + return 0; + + tree->count++; + *(tree->val + tree->shiftpos + tree->count - 1) = sortvalue; + *(tree->item + tree->shiftpos + tree->count - 1) = item; + + lash_treeProcess(tree, tree->count, -1); + + return tree->count; +} + +int lash_treeShift(lash_tree_t *tree, long int *sortvalue, void **item) { + return lash_treeRemove(tree, 0, sortvalue, item); +} + +int lash_treeRemove(lash_tree_t *tree, unsigned int position, long int *sortvalue, void **item) { + + if (tree->count == 0) + return 0; + + // retrieve the values from the position from the argument + *sortvalue = *(tree->val + tree->shiftpos + position); + *item = *(tree->item + tree->shiftpos + position); + + // move the values from the end of the tree to the position from the argument + *(tree->val + tree->shiftpos + position) = *(tree->val + tree->shiftpos + tree->count - 1); + *(tree->item + tree->shiftpos + position) = *(tree->item + tree->shiftpos + tree->count - 1); + + // reduce the count of the tree + tree->count--; + + // iterate the new value down the tree to its proper place + lash_treeProcess(tree, position + 1, 1); + + return tree->count; +} + +int lash_treeProcess(lash_tree_t *tree, unsigned int currentposition, int direction) { + + // towards end of pointer is downwards in the tree + // the direction to sort, -1 is from end towards start, 1 is from startposition towards end + + while (direction != 0) { + + long int *currentval = (tree->val + tree->shiftpos + currentposition - 1); + long int *nextval = NULL; + long int swapval = -1; + unsigned int nextposition; + + switch(direction) { + + // if there is still room to ascend in the tree, that is if the current position isn't 0 already. + case -1: + if (currentposition == 1) { + direction = 0; + } else { + nextposition = currentposition >> 1; + nextval = (tree->val + tree->shiftpos + nextposition - 1); + if (*currentval < *nextval) { + swapval = *currentval; + *currentval = *nextval; + *nextval = swapval; + currentposition = nextposition; + } else { + direction = 0; + } + } + break; + + // if there is still room from the current position to descend one level in the tree): + // level 0 has 2^0 = entry 1 + // level 1 has 2^1 = entries 2-3 + // level 2 has 2^2 = entries 4-7 + // 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) + // If we're at position 4, the check will be 4*2 = 8, which is out of bounds of level 2. + + case 1: + nextposition = currentposition << 1; + + if (nextposition <= tree->count) { + + // compare both the child values, to pick the higher one + nextval = (tree->val + tree->shiftpos + nextposition - 1); + if (*nextval > *(nextval + 1)) { + nextval = (nextval + 1); + nextposition++; + } + + // compare the values, set nextval back to null to stop the swapping if the value is not higher + if (*currentval <= *nextval) { + nextval = NULL; + } + + if (nextval != NULL) { + swapval = *currentval; + *currentval = *nextval; + *nextval = swapval; + currentposition = nextposition; + } else { + direction = 0; + } + } else { + direction = 0; + } + break; + default: + direction = 0; + } + } + + return currentposition; +} + diff --git a/.old/lash_tree2.h b/.old/lash_tree2.h @@ -0,0 +1,31 @@ +#ifndef LASH_TREE_H_ +#define LASH_TREE_H_ + +typedef struct lash_tree_t lash_tree_t; + +struct lash_tree_t { + long int *val; + void **item; + unsigned int shiftpos; + unsigned int count; + unsigned int capacity; + unsigned int foldbackthreshold; + int average; +}; + +#ifdef __cplusplus +extern "C" { +#endif + +lash_tree_t * lash_treeInit(lash_tree_t *tree, const unsigned int size) ; +int lash_treePush(lash_tree_t *tree, const long int sortvalue, void *item); +int lash_treeShift(lash_tree_t *tree, long int *sortvalue, void **item); +int lash_treeRemove(lash_tree_t *tree, unsigned int position, long int *sortvalue, void **item); +void lash_treeFree(lash_tree_t *tree); +int lash_treeProcess(lash_tree_t *tree, unsigned int currentposition, int direction); +#ifdef __cplusplus +} +#endif + + +#endif // LASH_TREE_H_ diff --git a/.old/lash_tree2_dump.c b/.old/lash_tree2_dump.c @@ -0,0 +1,64 @@ +#include "liblash/lash_tree2_dump.h" +#include "liblash/lash_tree2.h" +#include <stdio.h> +#include <stdlib.h> + +struct lash_tree_dump_monitor { + lash_tree_t **tree; + char **name; +} lash_tree_dump_monitor; + +unsigned int lash_tree_dump_monitor_capacity; +unsigned int lash_tree_dump_monitor_count; + +void lash_treeDump(lash_tree_t *dumptree, char *comment) { + int i; + int j; + + lash_tree_t *currenttree; + + for (i = 0; i < lash_tree_dump_monitor_count; i++) { + currenttree = *(lash_tree_dump_monitor.tree + i); + if (dumptree != NULL) + if (dumptree != currenttree) + continue; + + printf("'%s' size %d", *(lash_tree_dump_monitor.name + i), currenttree->count); + if (comment != NULL) + printf(" (%s)", comment); + printf(": "); + + for (j = 0; j < currenttree->count; j++) { + printf("i:%2d v:%3li, ", j, *(currenttree->val + currenttree->shiftpos + j)); + } + printf("\n"); + } +} + +int lash_treeDumpInit(unsigned int count) { + + lash_tree_dump_monitor.tree = (lash_tree_t*)malloc(sizeof(lash_tree_t*) * count); + if (lash_tree_dump_monitor.tree == NULL) + return -1; + + lash_tree_dump_monitor.name = (char*)malloc(sizeof(char) * 128 * count); + if (lash_tree_dump_monitor.name == NULL) + return -1; + + lash_tree_dump_monitor_capacity = count; + lash_tree_dump_monitor_count = 0; + + return 0; +} + +int lash_treeDumpAdd(lash_tree_t *dumptree, char *name) { + if (lash_tree_dump_monitor_count == lash_tree_dump_monitor_capacity) + return -1; + + *(lash_tree_dump_monitor.tree + lash_tree_dump_monitor_count) = dumptree; + *(lash_tree_dump_monitor.name + lash_tree_dump_monitor_count) = name; + + lash_tree_dump_monitor_count++; + + return 0; +} diff --git a/.old/lash_tree2_dump.h b/.old/lash_tree2_dump.h @@ -0,0 +1,18 @@ +#ifndef LASH_TREE_DUMP_H_ +#define LASH_TREE_DUMP_H_ + +#include "liblash/lash_tree2.h" + +#ifdef __cplusplus +extern "C" { +#endif +void lash_treeDump(lash_tree_t *dumptree, char *comment); +int lash_treeDumpInit(unsigned int count); +int lash_treeDumpAdd(lash_tree_t *dumptree, char *name); + +#ifdef __cplusplus +} +#endif + + +#endif // LASH_TREE_DUMP_H_ diff --git a/.old/lash_tree_dump.c b/.old/lash_tree_dump.c @@ -0,0 +1,77 @@ +#include "lash_tree_dump.h" +#include "lash_tree.h" +#include <stdio.h> +#include <stdlib.h> + +struct lash_tree_dump_monitor { + lash_tree_t **tree; + char **name; +} lash_tree_dump_monitor; + +unsigned int lash_tree_dump_monitor_capacity; +unsigned int lash_tree_dump_monitor_count; + +void lash_treeDump(lash_tree_t *dumptree, char *comment) { + int i; + int j; + //long int lastn = 0; + int falsesort = 0; + long int nn; + long int nc; + long int ni; + lash_tree_t *currenttree; + + for (i = 0; i < lash_tree_dump_monitor_count; i++) { + currenttree = *(lash_tree_dump_monitor.tree + i); + if (dumptree != NULL) + if (dumptree != currenttree) + continue; + + printf("Tree '%s' is now size %d", *(lash_tree_dump_monitor.name + i), currenttree->position); + if (comment != NULL) + printf(" (%s)", comment); + printf(": "); + + for (j = 1; j <= currenttree->position; j++) { + int ti = *(currenttree->idx + j - 1); + nn = *(currenttree->heap + ti); + ni = *(currenttree->local + ti); + nc = *(currenttree->heap + *(currenttree->idx + (int)(j/ 2) - 1)); + printf("i%u:s%u,h%li,i%li ", j, ti, nn, ni); + if (nn < nc && j > 1) + falsesort = 1; + } + if (falsesort == 1) { + printf("SORTERROR!\n"); + } + printf("\n"); + } +} + +int lash_treeDumpInit(unsigned int count) { + + lash_tree_dump_monitor.tree = (lash_tree_t*)malloc(sizeof(lash_tree_t*) * count); + if (lash_tree_dump_monitor.tree == NULL) + return -1; + + lash_tree_dump_monitor.name = (char*)malloc(sizeof(char) * 128 * count); + if (lash_tree_dump_monitor.name == NULL) + return -1; + + lash_tree_dump_monitor_capacity = count; + lash_tree_dump_monitor_count = 0; + + return 0; +} + +int lash_treeDumpAdd(lash_tree_t *tree, char *name) { + if (lash_tree_dump_monitor_count == lash_tree_dump_monitor_capacity) + return -1; + + *(lash_tree_dump_monitor.tree + lash_tree_dump_monitor_count) = tree; + *(lash_tree_dump_monitor.name + lash_tree_dump_monitor_count) = name; + + lash_tree_dump_monitor_count++; + + return 0; +} diff --git a/.old/lash_tree_dump.h b/.old/lash_tree_dump.h @@ -0,0 +1,12 @@ +#include "lash_tree.h" + +#ifdef __cplusplus +extern "C" { +#endif +void lash_treeDump(lash_tree_t *tree, char *comment); +int lash_treeDumpInit(unsigned int count); +int lash_treeDumpAdd(lash_tree_t *tree, char *name); + +#ifdef __cplusplus +} +#endif diff --git a/tree.c_intindex b/.old/tree.c_intindex diff --git a/COPYING b/COPYING @@ -0,0 +1 @@ +/usr/share/automake-1.16/COPYING +\ No newline at end of file diff --git a/INSTALL b/INSTALL @@ -0,0 +1 @@ +/usr/share/automake-1.16/INSTALL +\ No newline at end of file diff --git a/Makefile b/Makefile @@ -1,20 +0,0 @@ -CFLAGS = -I./include - -src = $(wildcard *.c) - -all: liblash.a - -liblash.a: $(src:.c=.o) - ar cq $@ $^ - -#shared: -# $(CC) -Wall $(CFLAGS) -o lash_tree_lib.o -fPIC -c lash_tree3.c -# $(CC) -Wall $(CFLAGS) -o lash_tree_dump_lib.o -fPIC -c lash_tree3_dump.c -# $(CC) -shared -Wl,-soname,liblash.so.0 -o $(SHAREDOBJECTDIR)liblash.so lash_tree_lib.o lash_tree_dump_lib.o -# $(CC) -Wall $(CFLAGS) -o lash_debug_log_lib.o -fPIC -c lash_debug_log.c -# $(CC) -Wall $(CFLAGS) -o lash_debug_timer_lib.o -fPIC -c lash_debug_timer.c -# $(CC) -shared -Wl,-soname,liblashdebug.so.0 -o $(SHAREDOBJECTDIR)liblashdebug.so lash_debug_log_lib.o lash_debug_timer_lib.o - -.PHONY: clean -clean: - rm -rf *.a *.o $(TESTDIR)*.o $(TESTDIR)*_bin diff --git a/Makefile.am b/Makefile.am @@ -0,0 +1,9 @@ +lib_LTLIBRARIES = liblash.la libbtree.la libdebug.la +liblash_la_SOURCES = hex.c endian.c tree.c +liblash_la_CFLAGS = -I./include + +libbtree_la_SOURCES = tree.c +libbtree_la_CFLAGS = -I./include + +libdebug_la_SOURCES = debug_log.c debug_timer.c +libdebug_la_CFLAGS = -I./include diff --git a/Makefile.old b/Makefile.old @@ -0,0 +1,21 @@ +CFLAGS = -I./include + +src = $(wildcard *.c) + +all: liblash.a + +liblash.a: $(src:.c=.o) + ar cq $@ $^ + +#shared: +# $(CC) -Wall $(CFLAGS) -o lash_tree_lib.o -fPIC -c lash_tree3.c +# $(CC) -Wall $(CFLAGS) -o lash_tree_dump_lib.o -fPIC -c lash_tree3_dump.c +# $(CC) -shared -Wl,-soname,liblash.so.0 -o $(SHAREDOBJECTDIR)liblash.so lash_tree_lib.o lash_tree_dump_lib.o +# $(CC) -Wall $(CFLAGS) -o lash_debug_log_lib.o -fPIC -c lash_debug_log.c +# $(CC) -Wall $(CFLAGS) -o lash_debug_timer_lib.o -fPIC -c lash_debug_timer.c +# $(CC) -shared -Wl,-soname,liblashdebug.so.0 -o $(SHAREDOBJECTDIR)liblashdebug.so lash_debug_log_lib.o lash_debug_timer_lib.o + +.PHONY: clean +clean: + rm -rf *.a *.o $(TESTDIR)*.o $(TESTDIR)*_bin + diff --git a/configure.ac b/configure.ac @@ -0,0 +1,29 @@ +# -*- Autoconf -*- +# Process this file with autoconf to produce a configure script. + +AC_PREREQ([2.69]) +AC_INIT([liblash], [0.1.2], [dev@holbrook.no]) +AM_INIT_AUTOMAKE([foreign -Wall -Werror]) +AC_CONFIG_SRCDIR([hex.c]) +AC_CONFIG_HEADERS([config.h]) + +# Checks for programs. +AC_PROG_CC +AM_PROG_AR +LT_INIT +AC_PROG_LIBTOOL([libtool]) + +# Checks for libraries. + +# Checks for header files. +AC_CHECK_HEADERS([limits.h stdlib.h string.h]) + +# Checks for typedefs, structures, and compiler characteristics. +AC_TYPE_SIZE_T + +# Checks for library functions. +AC_FUNC_MALLOC +AC_CHECK_FUNCS([clock_gettime memset regcomp]) + +AC_CONFIG_FILES([Makefile]) +AC_OUTPUT