- Joined
- Feb 18, 2010
- Messages
- 1,850 (0.36/day)
System Name | Eldritch |
---|---|
Processor | AMD Ryzen 5 5800X3D |
Motherboard | ASUS TUF X570 Pro Wifi |
Cooling | Satan's butthole after going to Taco Bell |
Memory | 64 GB G.Skill TridentZ |
Video Card(s) | Vega 56 |
Storage | 6*8TB Western Digital Blues in RAID 6, 2*512 GB Samsung 960 Pros |
Display(s) | Acer CB281HK |
Case | Phanteks Enthoo Pro PH-ES614P_BK |
Audio Device(s) | ASUS Xonar DX |
Power Supply | EVGA Supernova 750 G2 |
Mouse | Razer Viper 8K |
Software | Debian Bullseye |
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:
And here is the code that's supposed to test it:
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).
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).