# Help me fix my code



## hellrazor (Sep 5, 2012)

Lately I've been trying to implement an interval implementation in C. Unfortunately I'm not as good with C as I should be, and I think pointers and slightly complicated structures have gotten the best of me. Anyways, here's the code (it'll probably make your eyes bleed, but whatever), I've tried to add a lot of comments around the things that are related to the problem.

First is the actual header:

```
#include "inttypes.h"
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
//#include "tgmath.h"

//Make a more scalable/architecture-independant version where uint64_t is replaced by uintmax_t?

//Add some error checking to this shit
//Sprinkle a few restricts where appropriate

//Stop using string and start using char* for strings

uint8_t INTVL_SORT = 0;
uint8_t DEBUG = 1;

struct INTVL_LEAF{//This should never be touched outside of this file
    uint64_t stop;
    char *attribute;};

struct INTVL_SEGMENTTREE{
    uint64_t length;//How many branches are in it
    uint64_t *starts;//Pointer to array of when each branch starts
    uint64_t *branchlens;//pointer to array of how many leaves are in each branch
    struct INTVL_LEAF **branches;};//an array of pointers to each array of leaves


int leafqsort(const void *l_a, const void *l_b){//const INTVL_LEAF?
    //restrict?
    //register? Maybe if significantly faster, but I think it'll do it anyways
    const struct INTVL_LEAF *leaf_a = l_a;
    const struct INTVL_LEAF *leaf_b = l_b;
    if (leaf_a->stop > leaf_b->stop){
        return 1;}//a>b
    if (leaf_a->stop < leaf_b->stop){
        return -1;}//a<b
    return 0;}//a==b

int qleafqsort(const void *l_a, const void *l_b){//Might be less stable, should be faster
    const struct INTVL_LEAF *leaf_a = l_a;
    const struct INTVL_LEAF *leaf_b = l_b;
    return (int)(leaf_a->stop - leaf_b->stop);}




uint64_t INTVL_addleaf(struct INTVL_SEGMENTTREE *tree, uint64_t start, uint64_t stop, char *attribute){//This should be fixed
    if (DEBUG){
        printf("----------\nAdding... Tree length: %llu\n", tree->length);
        printf("Stop: %llu\n", stop);}
    if (tree == NULL){//Make-a-tree-for-me mode
        //This will return NULL on failure, unlike the other modes which return non-zero
        struct INTVL_SEGMENTTREE *newtree = NULL;
        newtree = malloc(sizeof(struct INTVL_SEGMENTTREE));
        if (!newtree){//Should start checking suff like this twice
            newtree = malloc(sizeof(struct INTVL_SEGMENTTREE));
            if (!newtree){
                tree = 0;//?
                return 1;}}
        //init newtree
        newtree->length = 0;
        newtree->starts = NULL;
        newtree->branchlens = NULL;
        newtree->branches = NULL;
        //Add leaf
        //return address of newtree
        tree = &newtree;//I think this is wrong
        return 0;}
    if (tree->length){
        for (uint64_t branch = 0; tree->starts[branch] <= start && branch < tree->length; branch++){
            if (tree->starts[branch] == start){
                if (!realloc(tree->branches[branch], sizeof(struct INTVL_LEAF)* tree->branchlens[branch]+1)){//Attempt ro realloc to new size, might be broken
                    return 1;}
                tree->branchlens[branch]++;//add to lengths
                
                tree->branches[branch][tree->branchlens[branch]-1].stop = stop;//Turn over a new leaf :)
                strcpy(tree->branches[branch][tree->branchlens[branch]-1].attribute, attribute);
                
                switch (INTVL_SORT){
                    case 0:
                        qsort(tree->branches[branch], tree->branchlens[branch], sizeof(struct INTVL_LEAF), leafqsort);
                        break;
                    case 1:
                        qsort(tree->branches[branch], tree->branchlens[branch], sizeof(struct INTVL_LEAF), qleafqsort);
                        break;
                    case 2:
                        //American flag radix sort
                        break;
                    case 3:
                        //Move (copy) over and insert
                        break;
                    default:
                        //error
                if (DEBUG){
                    printf("----------\n");}
                return 0;}
                }
            }
        }
        //realloc new starts, branches, and branchlens
        //q = realloc()
    else{//Initialize the tree
        if (DEBUG){
            printf("Tree has not been initialized! Initializing!\n");}
        //This shit is <del>probably<del> fucked up: Secondly, error checking for all them mallocs
        tree->starts = malloc(sizeof(uint64_t));
        tree->starts[0] = 0;
        //Make tree->branches here
        //Fix this shit:
        struct INTVL_LEAF *leafarray[1] = {NULL};
        leafarray[0] = malloc(sizeof(struct INTVL_LEAF));//This might be broken
        tree->branches = leafarray;
        tree->branchlens = malloc(sizeof(uint64_t));
        if (DEBUG){
            printf("mallocs done!!\n");}
        
        //Set the lengths to prepare for adding leaf, etc.
        tree->length = 1;
        tree->branchlens[0] = 1;
        
        //Set when the branch starts
        tree->starts[0] = start;
        if (DEBUG){
            printf("start: %llu\n", start);
            printf("tree->start: %llu\n", tree->starts[0]);}
        
        //Start writing leaf
        tree->branches[0][0].stop = stop;//stop
        printf("tree->branches[0][0].stop = %llu\n\0", tree->branches[0][0].stop);
        
        //Now this crashes it all of a sudden
        printf("tree->branches[0][0].attribute = %s\n\0", tree->branches[0][0].attribute);
        strcpy(tree->branches[0][0].attribute, attribute);//attribute
        printf("Got through!");
        //
        if (DEBUG){
            printf("----------\n");}
        return 0;}
    return 1;}

unsigned int INTVL_removeleaf(struct INTVL_SEGMENTTREE *tree, uint64_t start, char *att){
    for (uint64_t branch = 0; tree->starts[branch] <= start; branch++){
        if (tree->starts[branch] == start){
            for (uint64_t leaf = 0; leaf < tree->branchlens[branch]; leaf++){
                if (!strcmp(tree->branches[branch][leaf].attribute, att)){
                    //Move farther leaves over the one being deleted
                    tree->branchlens[branch]--;//Lower branch length
                    //realloc array
                    tree->branches[branch] = realloc(tree->branches[branch], tree->branchlens[branch]*sizeof(struct INTVL_LEAF));//Might be broken
                    if (!tree->branches[branch]){
                        return 1;}
                    //return
                    return 0;}
                }
            }
        }
    return 1;}

unsigned int INTVL_readleaves(struct INTVL_SEGMENTTREE *tree, uint64_t *attc, char **atts, uint64_t position){//attc and atts should both be modified by this function
    if (DEBUG){
        printf("----------\n\0");
        printf("tree->starts[0]: %llu, position: %llu\n\0", tree->starts[0], position);}
    if (tree->length && tree->starts[0] <= position){
        if (DEBUG){
            printf("A-Okay up to the first if statement!\n\0");}
        for (uint64_t branch = 0; tree->starts[branch] <= position && branch < tree->length; branch++){
            if (DEBUG){
                printf("A-Okay up to the first for statement!\n\0");
                printf("stop: %llu > position: %llu\n\0", tree->branches[branch][0].stop, position);
                printf("branch: %llu\n\0", tree->branchlens[branch]);
                printf("Crash!\n\0");}
            //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            for (uint64_t leaf = 0; tree->branches[branch][leaf].stop >= position; leaf++){
                if (DEBUG){
                    printf("Got through all the culling stuff!\n\0");}
                //printf ("leaf < tree->branchlens[branch]: %llu < %llu\n", leaf, tree->branchlens[branch]);
                if (leaf < (tree->branchlens[branch])){//<- Fix this, put it back in the for loop
                    printf("Got past the second comparison");
                    *attc++;//
                    //This still seems flaky and slow to me:
                    atts = realloc(atts, (*attc) * (sizeof(*tree->branches[branch][leaf].attribute)));//////////Fix this shit
                    if (!atts){
                        return 1;}
                    //add to the end of atts
                    strcpy(atts[*attc], tree->branches[branch][leaf].attribute);}}
            }
        if (DEBUG){
            printf("Passed the for loop!");}
        return 0;}
    return 1;}

unsigned int INTVL_splitleaf(struct INTVL_SEGMENTTREE *tree, uint64_t start, char *att, uint64_t newstop, uint64_t newstart){
    if (!(start < newstop && newstop < newstart)){
        return 1;}
    for (uint64_t branch = 0; branch < tree->length; branch++){
        if (tree->starts[branch] == start){
            for (uint64_t leaf = 0; leaf < tree->branchlens[branch]; leaf++){
                if (tree->branches[branch][leaf].attribute == att){
                    if (!newstart < tree->branches[branch][leaf].stop){
                        return 1;}
                    if (INTVL_addleaf(tree, newstart, tree->branches[branch][leaf].stop, att)){//Add new (farthest) leaf, branch if needed
                        return 1;}
                    tree->branches[branch][leaf].stop = newstop;//Change the old (closest) leaf's stop to newstop
                    return 0;}
                }
            }
        }
    return 1;}

unsigned int INTVL_prune(struct INTVL_SEGMENTTREE *tree){//Clean up, etc.
    if (tree->length){
        //go through, fix stuff
        
        //step 1: Errors
            //fix improperly sorted leaves (there better not be be any!)
        for (uint64_t branch = 0; branch < tree->length; branch++){//Maybe just qsort it again instead of all this?
            for (uint64_t leaf = 0; leaf < tree->branchlens[branch]; leaf++){
                }
            }
            //remove leaves that stop before they start (there better not be be any of them, either!)
        for (uint64_t branch = 0; branch < tree->length; branch++){
            for (uint64_t leaf = 0; leaf < tree->branchlens[branch]; leaf++){
                }
            }
            //remove leaves that share an attribute and a start
        //step 2: Optimizations
            //fix leaves with the same attribute that overlap or start and stop right next to each other
        return 0;}
    return 1;}

unsigned int INTVL_chop(struct INTVL_SEGMENTTREE *tree){//free everything in the tree (leaf attributes, arrays of leaves, branch array, etc., etc.
    return 1;}
```

And here is the code that's supposed to test it:

```
#include "interval.h"
#include "stdlib.h"
#include "stdio.h"

//lc64 tester_for_interval.c
//tester_for_interval.exe

//should do some error-checking

int main(int argc, char **argv){
    unsigned int r = 0;
    //Make a tree, add a leaf
    struct INTVL_SEGMENTTREE tree;
    tree.length = 0;
    tree.starts = NULL;
    tree.branchlens = NULL;
    tree.branches = NULL;
    
    printf("Starting!\n");
    r = INTVL_addleaf(&tree, 5, 25, "it works!!");
    printf("leaf.stop: %llu\n", tree.branches[0][0].stop);//leaf.stop = 25
    printf("Added leaf, errors: %u\n", r);
    printf("leaf.stop: %llu\n", tree.branches[0][0].stop);//leaf.stop = 16
                                                          //What the fuck!?!?!
    
    //read a position
    uint64_t count = 0;
    char *attributes[] = NULL;
    r = INTVL_readleaves(&tree, &count, &attributes, 13);
    printf("Reading at 13, failure: %u\n", r);
    printf("position 13 attribute count: %llu\n", count);
    for(uint64_t i = 0; i < count; i++){//print attributes off
        printf("position 13 attribute %llu: %s\n", i, attributes[i]);
        attributes[i] = NULL;}
    
    
    
    
    //Split the leaf
    r = INTVL_splitleaf(&tree, 0, "it works!", 10, 15);
    printf("Splitting leaf: %u\n", r);
    
    //read position
    count = 0;
    r = INTVL_readleaves(&tree, &count, &attributes, 5);
    printf("Reading at 13, leaf: %u\n", r);
    printf("position 5 attribute count: %llu\n", count);
    for(uint64_t i = 0; i < count; i++){//print attributes off
        printf("position 5 attribute %llu: %s\n", i, attributes[i]);
        attributes[i] = NULL;}
    
    //read another
    count = 0;
    r = INTVL_readleaves(&tree, &count, &attributes, 13);
    printf("Reading at 13, leaf: %u\n", r);
    printf("position 13 attribute count: %llu\n", count);
    for(uint64_t i = 0; i < count; i++){//print attributes off
        printf("position 13 attribute %llu: %s\n", i, attributes[i]);
        attributes[i] = NULL;}
    
    //read another
    count = 0;
    r = INTVL_readleaves(&tree, &count, &attributes, 20);
    printf("Reading at 13, leaf: %u\n", r);
    printf("position 20 attribute count: %llu\n", count);
    for(uint64_t i = 0; i < count; i++){//print attributes off
        printf("position 20 attribute %llu: %s\n", i, attributes[i]);
        attributes[i] = NULL;}
    
    
    
    //Remove a leaf
    INTVL_removeleaf(&tree, 15, "it works!");
    INTVL_readleaves(&tree, &count, &attributes, 5);
    printf("Adding leaf: %u\n", r);
    //print attributes off
    count = 0;
    INTVL_readleaves(&tree, &count, &attributes, 13);
    printf("Adding leaf: %u\n", r);
    //print attributes off
    
    //free tree, etc.
    return 0;}
```

I'm using lcc, and it currently crashes at line 133 of interval.h (if you look really hard you'll notice it also crashes at line 177, I'll worry about that later). Ask me any questions if you need to (also remember that it is quite unfinished).


----------



## hellrazor (Sep 5, 2012)

Okay, I got it. Here's the new header:

```
#include "inttypes.h"
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
//#include "tgmath.h"

//Make a more scalable/architecture-independant version where uint64_t is replaced by uintmax_t?

//Add some error checking to this shit
//Sprinkle a few restricts where appropriate

//Stop using string and start using char* for strings

uint8_t INTVL_SORT = 0;
uint8_t DEBUG = 1;

struct INTVL_LEAF{//This should never be touched outside of this file
    uint64_t stop;
    char *attribute;};

struct INTVL_SEGMENTTREE{
    uint64_t length;//How many branches are in it
    uint64_t *starts;//Pointer to array of when each branch starts
    uint64_t *branchlens;//pointer to array of how many leaves are in each branch
    struct INTVL_LEAF **branches;};//an array of pointers to each array of leaves


int leafqsort(const void *l_a, const void *l_b){//const INTVL_LEAF?
    //restrict?
    //register? Maybe if significantly faster, but I think it'll do it anyways
    const struct INTVL_LEAF *leaf_a = l_a;
    const struct INTVL_LEAF *leaf_b = l_b;
    if (leaf_a->stop > leaf_b->stop){
        return 1;}//a>b
    if (leaf_a->stop < leaf_b->stop){
        return -1;}//a<b
    return 0;}//a==b

int qleafqsort(const void *l_a, const void *l_b){//Might be less stable, should be faster
    const struct INTVL_LEAF *leaf_a = l_a;
    const struct INTVL_LEAF *leaf_b = l_b;
    return (int)(leaf_a->stop - leaf_b->stop);}




uint64_t INTVL_addleaf(struct INTVL_SEGMENTTREE *tree, uint64_t start, uint64_t stop, char *attribute){//This should be fixed
    if (DEBUG){
        printf("----------\nAdding... Tree length: %llu\n", tree->length);
        printf("Stop: %llu\n", stop);}
    if (tree == NULL){//Make-a-tree-for-me mode
        //This will return NULL on failure, unlike the other modes which return non-zero
        struct INTVL_SEGMENTTREE *newtree = NULL;
        newtree = malloc(sizeof(struct INTVL_SEGMENTTREE));
        if (!newtree){//Should start checking suff like this twice
            newtree = malloc(sizeof(struct INTVL_SEGMENTTREE));
            if (!newtree){
                tree = 0;//?
                return 1;}}
        //init newtree
        newtree->length = 0;
        newtree->starts = NULL;
        newtree->branchlens = NULL;
        newtree->branches = NULL;
        //Add leaf
        //return address of newtree
        tree = &newtree;//I think this is wrong
        return 0;}
    if (tree->length){
        for (uint64_t branch = 0; tree->starts[branch] <= start && branch < tree->length; branch++){
            if (tree->starts[branch] == start){
                if (!realloc(tree->branches[branch], sizeof(struct INTVL_LEAF)* tree->branchlens[branch]+1)){//Attempt ro realloc to new size, might be broken
                    return 1;}
                tree->branchlens[branch]++;//add to lengths
                
                tree->branches[branch][tree->branchlens[branch]-1].stop = stop;//Turn over a new leaf :)
                strcpy(tree->branches[branch][tree->branchlens[branch]-1].attribute, attribute);
                
                switch (INTVL_SORT){
                    case 0:
                        qsort(tree->branches[branch], tree->branchlens[branch], sizeof(struct INTVL_LEAF), leafqsort);
                        break;
                    case 1:
                        qsort(tree->branches[branch], tree->branchlens[branch], sizeof(struct INTVL_LEAF), qleafqsort);
                        break;
                    case 2:
                        //American flag radix sort
                        break;
                    case 3:
                        //Move (copy) over and insert
                        break;
                    default:
                        //error
                if (DEBUG){
                    printf("----------\n");}
                return 0;}
                }
            }
        }
        //realloc new starts, branches, and branchlens
        //q = realloc()
    else{//Initialize the tree
        if (DEBUG){
            printf("Tree has not been initialized! Initializing!\n");}
        //This shit is <del>probably<del> fucked up: Secondly, error checking for all them mallocs
        tree->starts = malloc(sizeof(uint64_t));
        tree->starts[0] = 0;
        //Make tree->branches here
        //Fix this shit:
        struct INTVL_LEAF *leafarray[1] = {NULL};
        leafarray[0] = malloc(sizeof(struct INTVL_LEAF));//This might be broken
        tree->branches = leafarray;
        tree->branchlens = malloc(sizeof(uint64_t));
        if (DEBUG){
            printf("mallocs done!!\n");}
        
        //Set the lengths to prepare for adding leaf, etc.
        tree->length = 1;
        tree->branchlens[0] = 1;
        
        //Set when the branch starts
        tree->starts[0] = start;
        if (DEBUG){
            printf("start: %llu\n", start);
            printf("tree->start: %llu\n", tree->starts[0]);}
        
        //Start writing leaf
        tree->branches[0][0].stop = stop;//stop
        printf("tree->branches[0][0].stop = %llu\n\0", tree->branches[0][0].stop);
        tree->branches[0][0].attribute = malloc(sizeof(attribute));
        printf("tree->branches[0][0].attribute = %llu\n\0", tree->branches[0][0].attribute);
        strcpy(tree->branches[0][0].attribute, attribute);//attribute
        printf("Got through!");
        //
        if (DEBUG){
            printf("----------\n");}
        return 0;}
    return 1;}

unsigned int INTVL_removeleaf(struct INTVL_SEGMENTTREE *tree, uint64_t start, char *att){
    for (uint64_t branch = 0; tree->starts[branch] <= start; branch++){
        if (tree->starts[branch] == start){
            for (uint64_t leaf = 0; leaf < tree->branchlens[branch]; leaf++){
                if (!strcmp(tree->branches[branch][leaf].attribute, att)){
                    //Move farther leaves over the one being deleted
                    tree->branchlens[branch]--;//Lower branch length
                    //realloc array
                    tree->branches[branch] = realloc(tree->branches[branch], tree->branchlens[branch]*sizeof(struct INTVL_LEAF));//Might be broken
                    if (!tree->branches[branch]){
                        return 1;}
                    //return
                    return 0;}
                }
            }
        }
    return 1;}

unsigned int INTVL_readleaves(struct INTVL_SEGMENTTREE *tree, uint64_t *attc, char **atts, uint64_t position){//attc and atts should both be modified by this function
    if (DEBUG){
        printf("----------\n\0");
        printf("tree->starts[0]: %llu, position: %llu\n\0", tree->starts[0], position);}
    if (tree->length && tree->starts[0] <= position){
        if (DEBUG){
            printf("A-Okay up to the first if statement!\n\0");}
        for (uint64_t branch = 0; tree->starts[branch] <= position && branch < tree->length; branch++){
            if (DEBUG){
                printf("A-Okay up to the first for statement!\n\0");
                printf("stop: %llu > position: %llu\n\0", tree->branches[branch][0].stop, position);
                printf("branch: %llu\n\0", tree->branchlens[branch]);
                printf("Crash!\n\0");}
            //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            for (uint64_t leaf = 0; tree->branches[branch][leaf].stop >= position; leaf++){
                if (DEBUG){
                    printf("Got through all the culling stuff!\n\0");}
                //printf ("leaf < tree->branchlens[branch]: %llu < %llu\n", leaf, tree->branchlens[branch]);
                if (leaf < (tree->branchlens[branch])){//<- Fix this, put it back in the for loop
                    printf("Got past the second comparison");
                    *attc++;
                    //This still seems flaky and slow to me:
                    atts = realloc(atts, (*attc) * (sizeof(*tree->branches[branch][leaf].attribute)));//////////Fix this shit
                    if (!atts){
                        return 1;}
                    //add to the end of atts
                    strcpy(atts[*attc], tree->branches[branch][leaf].attribute);}}
            }
        if (DEBUG){
            printf("Passed the for loop!");}
        return 0;}
    return 1;}

unsigned int INTVL_splitleaf(struct INTVL_SEGMENTTREE *tree, uint64_t start, char *att, uint64_t newstop, uint64_t newstart){
    if (!(start < newstop && newstop < newstart)){
        return 1;}
    for (uint64_t branch = 0; branch < tree->length; branch++){
        if (tree->starts[branch] == start){
            for (uint64_t leaf = 0; leaf < tree->branchlens[branch]; leaf++){
                if (tree->branches[branch][leaf].attribute == att){
                    if (!newstart < tree->branches[branch][leaf].stop){
                        return 1;}
                    if (INTVL_addleaf(tree, newstart, tree->branches[branch][leaf].stop, att)){//Add new (farthest) leaf, branch if needed
                        return 1;}
                    tree->branches[branch][leaf].stop = newstop;//Change the old (closest) leaf's stop to newstop
                    return 0;}
                }
            }
        }
    return 1;}

unsigned int INTVL_prune(struct INTVL_SEGMENTTREE *tree){//Clean up, etc.
    if (tree->length){
        //go through, fix stuff
        
        //step 1: Errors
            //fix improperly sorted leaves (there better not be be any!)
        for (uint64_t branch = 0; branch < tree->length; branch++){//Maybe just qsort it again instead of all this?
            for (uint64_t leaf = 0; leaf < tree->branchlens[branch]; leaf++){
                }
            }
            //remove leaves that stop before they start (there better not be be any of them, either!)
        for (uint64_t branch = 0; branch < tree->length; branch++){
            for (uint64_t leaf = 0; leaf < tree->branchlens[branch]; leaf++){
                }
            }
            //remove leaves that share an attribute and a start
        //step 2: Optimizations
            //fix leaves with the same attribute that overlap or start and stop right next to each other
        return 0;}
    return 1;}

unsigned int INTVL_chop(struct INTVL_SEGMENTTREE *tree){//free everything in the tree (leaf attributes, arrays of leaves, branch array, etc., etc.
    return 1;}
```


----------



## rascal27 (Sep 24, 2012)

oops too genius is here....what i'm doing here.......


----------



## librin.so.1 (Sep 25, 2012)

I started reading and I quite promply had a couple of questions popping in my mind:

1. Why do You have Your code _inside_ a header? 
2. Is this C99?


----------

