commit b10368b9bd6ec8414528598b77e7a76f2aa37166
parent 9163d9845da2887b5fdde536482c8b2d05716ccb
Author: amin <dev@aminmesbah.com>
Date: Fri, 12 May 2017 21:03:27 +0000
Fix invalid reads and frees in quadtree.
Every now and then, the program would segfault. Valgrind was complaining
about invalid reads and frees all throughout the quadtree
implementation.
After a lot of debugging, I realized there was a problem with the way I
was passing my quadtree root node to the update function through a
pointer. Changes were being made to the local copy of `cells_root` in
`update()`, but those changes didn't apply back in scope of `main()`.
To address this, I made a `QuadTree` struct which has just one pointer
to the root node of the quadtree. In `main()`, `QuadTree *qt` is
initialized once, then passed to `update()` within the main loop. Update
only makes changes to `qt->root`.
I also made various style changes, and made sure to free `qt` after the
main loop.
I wrote a short blog post about this issue:
https://www.amin.space/blog/2017/5/quadtree_debug/
FossilOrigin-Name: 54ee0e60b5f47590da73bdf363492398deb5b3a54a38bffeb75ecbb56c2b3183
Diffstat:
| M | Makefile | | | 11 | ++++++----- |
| M | barnes_hut.h | | | 96 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------------- |
| M | main.c | | | 68 | ++++++++++++++++++++++++++++++++++---------------------------------- |
3 files changed, 106 insertions(+), 69 deletions(-)
diff --git a/Makefile b/Makefile
@@ -18,9 +18,9 @@ RELDIR = release
RELEXE = $(RELDIR)/$(EXE)
RELCFLAGS = -O2 -Os
-.PHONY: all clean debug prep release run test
+.PHONY: all clean debug memcheck prep release run test
-all: debug
+all: debug release
clean:
rm -f $(RELEXE) $(DBGEXE)
@@ -28,13 +28,14 @@ clean:
debug: prep
$(CC) $(CFLAGS) $(DBGCFLAGS) $(SRC) -o $(DBGEXE) $(LDFLAGS)
+memcheck: debug
+ valgrind --track-origins=yes ./$(DBGEXE)
+
prep:
@mkdir -p $(DBGDIR) $(RELDIR)
release: prep
$(CC) $(CFLAGS) $(RELCFLAGS) $(SRC) -o $(RELEXE) $(LDFLAGS)
-run:
+run: debug
./$(DBGEXE)
-
-test: debug run
diff --git a/barnes_hut.h b/barnes_hut.h
@@ -5,9 +5,8 @@
#ifndef BARNES_HUT_H
#define BARNES_HUT_H
-// TODO: Why is there a segfault when this is set to 0?
-// TODO: Why is there a segfault only very rarely when this is set to 1?
#define MAX_STARS_PER_CELL 1
+// TODO: Limit tree depth
struct Cell
{
@@ -20,13 +19,21 @@ struct Cell
struct QuadTreeNode
{
struct Cell *cell;
- struct QuadTreeNode *children[4];
+ struct QuadTreeNode *ne;
+ struct QuadTreeNode *nw;
+ struct QuadTreeNode *sw;
+ struct QuadTreeNode *se;
};
+struct QuadTree
+{
+ struct QuadTreeNode *root;
+};
-struct Cell* cell_init(float center_x, float center_y, float distance_x, float distance_y)
+
+struct Cell *cell_init(float center_x, float center_y, float distance_x, float distance_y)
{
- struct Cell *cell = (struct Cell*)malloc(sizeof(struct Cell));
+ struct Cell *cell = (struct Cell *)malloc(sizeof(struct Cell));
if (cell)
{
cell->center_x = center_x;
@@ -37,6 +44,16 @@ struct Cell* cell_init(float center_x, float center_y, float distance_x, float d
return cell;
}
+
+void cell_free(struct Cell *c)
+{
+ if (c)
+ {
+ free(c);
+ }
+}
+
+
int cell_count_stars_contained(struct Cell *c, struct Star stars[], int num_stars)
{
int count = 0;
@@ -53,56 +70,75 @@ int cell_count_stars_contained(struct Cell *c, struct Star stars[], int num_star
return count;
}
-struct QuadTreeNode* quad_tree_node_init(float center_x, float center_y, float distance_x, float distance_y)
+
+struct QuadTreeNode *quad_tree_node_init(float center_x, float center_y, float distance_x, float distance_y)
{
- struct QuadTreeNode *node = (struct QuadTreeNode*)malloc(sizeof(struct QuadTreeNode));
+ struct QuadTreeNode *node = (struct QuadTreeNode *)malloc(sizeof (struct QuadTreeNode));
if (node)
{
node->cell = cell_init(center_x, center_y, distance_x, distance_y);
- for (int i = 0; i < 4; ++i)
- {
- node->children[i] = 0;
- }
+ node->ne = NULL;
+ node->nw = NULL;
+ node->sw = NULL;
+ node->se = NULL;
}
return node;
}
+
void quad_tree_node_free(struct QuadTreeNode *node)
{
if (node)
{
- for (int i = 0; i < 4; ++i)
- {
- if (node->children[i])
- {
- quad_tree_node_free(node->children[i]);
- }
- }
+ quad_tree_node_free(node->ne);
+ quad_tree_node_free(node->nw);
+ quad_tree_node_free(node->sw);
+ quad_tree_node_free(node->se);
free(node->cell);
free(node);
}
}
+
void quad_tree_node_subdivide(struct QuadTreeNode *node, struct Star stars[], int num_stars)
{
- if (cell_count_stars_contained(node->cell, stars, num_stars) > MAX_STARS_PER_CELL)
+ if (node && cell_count_stars_contained(node->cell, stars, num_stars) > MAX_STARS_PER_CELL)
{
float child_distance_x = node->cell->distance_x / 2;
float child_distance_y = node->cell->distance_y / 2;
- node->children[0] = quad_tree_node_init(node->cell->center_x + child_distance_x, node->cell->center_y + child_distance_y, child_distance_x, child_distance_y);
- node->children[1] = quad_tree_node_init(node->cell->center_x - child_distance_x, node->cell->center_y + child_distance_y, child_distance_x, child_distance_y);
- node->children[2] = quad_tree_node_init(node->cell->center_x - child_distance_x, node->cell->center_y - child_distance_y, child_distance_x, child_distance_y);
- node->children[3] = quad_tree_node_init(node->cell->center_x + child_distance_x, node->cell->center_y - child_distance_y, child_distance_x, child_distance_y);
+ node->ne = quad_tree_node_init(node->cell->center_x + child_distance_x, node->cell->center_y + child_distance_y, child_distance_x, child_distance_y);
+ node->nw = quad_tree_node_init(node->cell->center_x - child_distance_x, node->cell->center_y + child_distance_y, child_distance_x, child_distance_y);
+ node->sw = quad_tree_node_init(node->cell->center_x - child_distance_x, node->cell->center_y - child_distance_y, child_distance_x, child_distance_y);
+ node->se = quad_tree_node_init(node->cell->center_x + child_distance_x, node->cell->center_y - child_distance_y, child_distance_x, child_distance_y);
- for (int i = 0; i < 4; ++i)
- {
- if (node->children[i])
- {
- quad_tree_node_subdivide(node->children[i], stars, num_stars);
- }
- }
+ quad_tree_node_subdivide(node->ne, stars, num_stars);
+ quad_tree_node_subdivide(node->nw, stars, num_stars);
+ quad_tree_node_subdivide(node->sw, stars, num_stars);
+ quad_tree_node_subdivide(node->se, stars, num_stars);
+ }
+}
+
+
+struct QuadTree *quad_tree_init(void)
+{
+ struct QuadTree *qt = (struct QuadTree *)malloc(sizeof (struct QuadTree));
+ if (qt)
+ {
+ qt->root = NULL;
+ }
+ return qt;
+}
+
+
+void quad_tree_free(struct QuadTree *qt)
+{
+ if (qt)
+ {
+ quad_tree_node_free(qt->root);
+ free(qt);
}
}
+
#endif
diff --git a/main.c b/main.c
@@ -1,11 +1,13 @@
-#include <math.h>
#include <inttypes.h>
+#include <math.h>
#include <SDL.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
+#include <stdlib.h>
#include <string.h>
#include <time.h>
+
#include "star.h"
#include "barnes_hut.h"
@@ -193,7 +195,7 @@ void clear_screen(struct SDLOffscreenBuffer buffer, uint32_t pixel_value)
}
-void update(struct Star stars[], int num_stars, struct QuadTreeNode *cells_root)
+void update(struct Star stars[], int num_stars, struct QuadTree *qt)
{
for (int i = 0; i < num_stars; ++i)
{
@@ -214,42 +216,40 @@ void update(struct Star stars[], int num_stars, struct QuadTreeNode *cells_root)
int dist_x = global_back_buffer.width / 2;
int dist_y = global_back_buffer.height / 2;
- quad_tree_node_free(cells_root);
- cells_root = quad_tree_node_init(center_x, center_y, dist_x, dist_y);
- quad_tree_node_subdivide(cells_root, stars, num_stars);
+ quad_tree_node_free(qt->root);
+ qt->root = quad_tree_node_init(center_x, center_y, dist_x, dist_y);
+ quad_tree_node_subdivide(qt->root, stars, num_stars);
}
+
// TODO: pass a pointer to buffer?
void draw_grid(struct SDLOffscreenBuffer buffer, struct QuadTreeNode *node, uint32_t color)
{
- if (node)
+ if (node && node->ne && node->nw && node->sw && node->se)
{
- for (int i = 0; i < 4; ++i)
+ for (int x = (node->cell->center_x - node->cell->distance_x);
+ x <= (node->cell->center_x + node->cell->distance_x);
+ ++x)
{
- if (node->children[i])
- {
- for (
- int x = (node->cell->center_x - node->cell->distance_x);
- x <= (node->cell->center_x + node->cell->distance_x);
- ++x)
- {
- set_pixel(buffer, x, node->cell->center_y, color);
- }
+ set_pixel(buffer, x, node->cell->center_y, color);
+ }
- for (
- int y = (node->cell->center_y - node->cell->distance_y);
- y <= (node->cell->center_y + node->cell->distance_y);
- ++y)
- {
- set_pixel(buffer, node->cell->center_x, y, color);
- }
- draw_grid(buffer, node->children[i], color);
- }
+ for (int y = (node->cell->center_y - node->cell->distance_y);
+ y <= (node->cell->center_y + node->cell->distance_y);
+ ++y)
+ {
+ set_pixel(buffer, node->cell->center_x, y, color);
}
+
+ draw_grid(buffer, node->ne, color);
+ draw_grid(buffer, node->nw, color);
+ draw_grid(buffer, node->sw, color);
+ draw_grid(buffer, node->se, color);
}
}
-void render(struct SDLOffscreenBuffer buffer, float dt, struct Star stars[], int num_stars, struct QuadTreeNode *cells_root)
+
+void render(struct SDLOffscreenBuffer buffer, float dt, struct Star stars[], int num_stars, struct QuadTree *qt)
{
//printf("%f\n", dt);
for (int i = 0; i < num_stars; ++i)
@@ -261,7 +261,7 @@ void render(struct SDLOffscreenBuffer buffer, float dt, struct Star stars[], int
stars[i].color);
}
- draw_grid(buffer, cells_root, COLOR_GREEN);
+ draw_grid(buffer, qt->root, COLOR_GREEN);
}
@@ -311,11 +311,7 @@ int main(void)
//printf("%f, %f, %f\n", stars[i].angle, stars[i].speed, stars[i].mass);
}
- struct QuadTreeNode *cells_root = quad_tree_node_init(
- global_back_buffer.width / 2,
- global_back_buffer.height / 2,
- global_back_buffer.width / 2,
- global_back_buffer.height / 2);
+ struct QuadTree *qt = quad_tree_init();
while (running)
{
@@ -336,22 +332,26 @@ int main(void)
dimension = sdl_get_window_dimension(window);
+ update(stars, NUM_STARS, qt);
while (lag >= MS_PER_UPDATE)
{
- update(stars, NUM_STARS, cells_root);
+ update(stars, NUM_STARS, qt);
//printf("\t%" PRIu64 ", %f\n", lag, MS_PER_UPDATE);
lag -= MS_PER_UPDATE;
}
+
#ifndef TRAILS
clear_screen(global_back_buffer, COLOR_BACKGROUND);
#endif
- render(global_back_buffer, lag/SECOND, stars, NUM_STARS, cells_root);
+ render(global_back_buffer, lag/SECOND, stars, NUM_STARS, qt);
sdl_update_window(renderer, global_back_buffer);
if (elapsed_ms <= MS_PER_FRAME)
{
SDL_Delay(MS_PER_FRAME - elapsed_ms);
}
}
+
+ quad_tree_free(qt);
}
else
{
