1. Welcome to TechPowerUp Forums, Guest! Please check out our forum guidelines for info related to our community.

Help me fix my code

Discussion in 'Programming & Webmastering' started by hellrazor, Sep 5, 2012.

  1. hellrazor

    hellrazor

    Joined:
    Feb 18, 2010
    Messages:
    1,572 (0.96/day)
    Thanks Received:
    315
    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:
    Code:
    #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:
    Code:
    #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).
  2. hellrazor

    hellrazor

    Joined:
    Feb 18, 2010
    Messages:
    1,572 (0.96/day)
    Thanks Received:
    315
    Okay, I got it. Here's the new header:
    Code:
    #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 says thanks.
  3. rascal27 New Member

    Joined:
    Sep 24, 2012
    Messages:
    5 (0.01/day)
    Thanks Received:
    0
    oops too genius is here....what i'm doing here.......:banghead:
  4. Vinska

    Vinska

    Joined:
    Jul 23, 2011
    Messages:
    1,406 (1.25/day)
    Thanks Received:
    1,244
    Location:
    Kaunas, Lithuania
    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? :wtf:
    2. Is this C99?
    Crunching for Team TPU

Currently Active Users Viewing This Thread: 1 (0 members and 1 guest)

Share This Page