Stack-overflow using recursion in C -
i've been looking frantically answer no avail; i've created quadtree supposed sort array of more 1000 objects declared struct:
typedef struct node { char is_leaf; struct particle *p; double m; double center_x; double center_y; double width; struct node *sw; struct node *nw; struct node *se; struct node *ne; } node; into quadtree function:
node* quadtree_insert(node *n, struct particle *p, double center_x, double center_y, double width) { if(n == null) { n = (node*)malloc(sizeof(node)); n->is_leaf = 1; n->p = p; //n->m = 0.1; n->sw = null; n->se = null; n->nw = null; n->ne = null; if(width < 1e-300){ n->width = 1e-300; } else n->width = width; return n; } else{ //n = (node*)malloc(sizeof(node)); double x; double y; if(width < 1e-300){ width = 1e-300; } if(n->is_leaf == 1) //! is, if node not branch { x = (double)n->p->x_pos; y = (double)n->p->y_pos; if(x <= center_x && y <= center_y) //! first quadrant { n->sw = quadtree_insert(n->sw, n->p, center_x * 0.5, center_y * 0.5, width * 0.5); } else if(x <= center_x && y > center_y) //! second quadrant { n->nw = quadtree_insert(n->nw, n->p, center_x * 0.5, center_y + center_y * 0.5, width * 0.5); } else if(x > center_x && y <= center_y) //! third quadrant { n->se = quadtree_insert(n->se, n->p, center_x + center_x * 0.5, center_y * 0.5, width * 0.5); } else //! fourth quadrant { n->ne = quadtree_insert(n->ne, n->p, center_x + center_x * 0.5, center_y + center_y * 0.5, width * 0.5); } n->p = null; //! sets branch pointer nothing... n->is_leaf = 0; } //} x = (double)p->x_pos; y = (double)p->y_pos; if(x <= center_x && y <= center_y) //! first quadrant { n->sw = quadtree_insert(n->sw, p, center_x * 0.5, center_y * 0.5, width * 0.5); } else if(x <= center_x && y > center_y) //! second quadrant { n->nw = quadtree_insert(n->nw, p, center_x * 0.5, center_y + center_y * 0.5, width * 0.5); } else if(x > center_x && y <= center_y) //! third quadrant { n->se = quadtree_insert(n->se, p, center_x + center_x * 0.5, center_y * 0.5, width * 0.5); } else //! fourth quadrant { n->ne = quadtree_insert(n->ne, p, center_x + center_x * 0.5, center_y + center_y * 0.5, width * 0.5); } return n; } } this done by:
node *root = null; root = quadtree_insert(root, &particles[0],0.500,0.5,1); for(i = 1; < nparticles; i++) { quadtree_insert(root, &particles[i],0.5000,0.5,1); } where "particles" passed on on form struct particle* particles. , particle defined such that:
struct particle { double mass; double x_pos; double y_pos; double x_vel; double y_vel; }; typedef struct particle * particle_structure; the root free'd after every iteration, after for-loop, , code works samples smaller ~200 , valgrind gives no errors these. added middle function, performs arithmetic on particles:
double quadtree_calculate_forcey(struct particle *p, node *n, double theta_max, double delta_t, int nump, double epsilon, double g) { if(n != null) { double d_x = (n->center_x - p->x_pos); double d_y = (n->center_y - p->y_pos); double r_2 = d_x * d_x + d_y * d_y; r_2 = sqrt(r_2) + epsilon; if(theta_max <= (n->width / r_2) && !n->is_leaf){ double = 0; if(n->sw != null) += quadtree_calculate_forcey(p, n->sw, theta_max, delta_t, nump, epsilon, g); if(n->nw != null) += quadtree_calculate_forcey(p, n->nw, theta_max, delta_t, nump, epsilon, g); if(n->se != null) += quadtree_calculate_forcey(p, n->se, theta_max, delta_t, nump, epsilon, g); if(n->ne != null) += quadtree_calculate_forcey(p, n->ne, theta_max, delta_t, nump, epsilon, g); return a; } else { double fy; double mass; if(d_x == 0 && d_y == 0){ // comparing same star //printf("rÖÖÖvhatt\n"); return 0; } else{ //printf("mass : %f\n", n->m); mass = n->m; //printf("mass : %f\n", mass); fy = g * (mass * p->mass/ pow(r_2,3)) * d_y; //printf("dy:%f dx:%f r_2:%f massa:%f\n",d_y, d_x, r_2 - epsilon, mass); // printf("hit ska jag: %f\n",d_y); return fy; } } } return 0.0; } the ringer rolls bit (clearing root, , redoing new positions), number of variables in recursion surely cannot problem(?). i'm pretty sure i'm out swimming fishes when comes allocation of pointer declaration. thoughts/help put on side of odin!
edit: example how find mass-center etc. node-mass done same way.
double set_centerx(node *n) { if(n != null) { if(!(n->is_leaf)) { double = set_centerx(n->ne); double b = set_centerx(n->nw); double c = set_centerx(n->se); double d = set_centerx(n->sw); double m1 = get_mass2(n->ne); double m2 = get_mass2(n->nw); double m3 = get_mass2(n->se); double m4 = get_mass2(n->sw); n->center_x = (double)(m1*a + m2*b + m3*c + m4*d)/(m1+m2+m3+m4); return n->center_x; } n->center_x =n->p->x_pos; return n->p->x_pos; } return 0; }
i see several problems code.
in first place, have near-duplication of sizable block of non-trivial code. 2 blocks seem differ in particle reference; begs factored out helper function.
in second place, consider fragment:
else if (x <= center_x && y > center_y) // ! second quadrant { n->nw = quadtree_insert(n->nw, n->p, center_x * 0.5, center_y + center_y * 0.5, width * 0.5); }
i take input center_x , center_y center of square patch of overall area, , width edge length patch. in case, center of northwest quadrant of patch (center_x - width * 0.25, center_y + width * 0.25). in special cases coincide computation in recursive call. can determine width of patch coordinates of center, not directly you're trying do.
similar applies 7 of other recursive calls.
in third place, consider happens if end 2 particles have similar -- or worse, identical -- coordinates. can 2 in simulation.
the first particle gets positioned in node representing whole simulation area. when second inserted, quadtree traversed same node. original particle therefore moved newly created quadrant of original node's area, , insertion process second node resumes. insertion again reaches same node original particle occupies, , process repeats. , maybe repeats again. , again.
there therefore no definite bound recursion. if happen end 2 particles identical coordinates -- example, maybe pinned corner of simulation area -- recurse endlessly, producing stack overflow. if no 2 particles have identical coordinates, however, conceivable 2 close enough recursion go deep enough stack overflow.
i suspect problem aggravated previous issue, not depend on issue.
one way approach problem merge particles come close enough together. allow place firm bound on recursion depth, based on patch width. alternatively, may abort if recursion goes deep. or, let crash in case, does.
for it's worth, here's how think quadtree_insert() ought look:
// adjust needed: #define min_particle_separation 1e-300 void quadtree_insert_helper(node *n, particle *p, double center_x, double center_y, double width) { width *= 0.5; double new_center_x = center_x + width * ((p->x_pos <= center_x) ? -0.5 : 0.5); double new_center_y = center_y + width * ((p->y_pos <= center_y) ? -0.5 : 0.5); node **quad; if (new_center_x <= center_x && new_center_y <= center_y) { //! first quadrant quad = &n->sw; } else if (new_center_x <= center_x && new_center_y > center_y) { //! second quadrant quad = &n->nw; } else if (new_center_x > center_x && new_center_y <= center_y) { //! third quadrant quad = &n->se; } else { //! fourth quadrant quad = &n->ne; } *quad = quadtree_insert(*quad, p, new_center_x, new_center_y, width); } node* quadtree_insert(node *n, struct particle *p, double center_x, double center_y, double width) { if (n == null) { n = malloc(sizeof(*n)); n->is_leaf = 1; n->p = p; //n->m = 0.1; n->sw = null; n->se = null; n->nw = null; n->ne = null; n->center_x = center_x; n->center_y = center_y; n->width = width; } else if (n->is_leaf && (with <= min_particle_separation)) { // ... merge particles ... } else { if (n->is_leaf) { //! is, if node not branch quadtree_insert_helper(n, n->p, center_x, center_y, width); //! node branch n->p = null; n->is_leaf = 0; } quadtree_insert_helper(n, p, center_x, center_y, width); } return n; } 