So I’ve been trying to debug this for two days now and I think I just need another developer to look at it to see the issue.
I need a balanced binary search tree implementation for a sweep-line algorithm. The red-black tree implementation, that’s already in BLI, does not fit the requirements that I need (namely deletion, no tests, and limitations in the data structure). So I decided to implement a WAVL tree. I tried to do TDD for this as much as possible, so write a test first, then implement and fix till the test passes, and so on.
The test for rebalancing the tree after a deletion failed with a segfault. No issue so far, but when I looked into it, it got weird. The test creates a tree and then tries to insert three nodes - a root, a left child and a right child. Then it deletes the root node and checks if everything is fine. But when it tries to inserts the second child, the node structure that gets allocated overwrites the memory for the root node. Yes, MEM_mallocN returns with a pointer pointing to the same memory location as the root node. Surely there must be something horribly wrong, but I am running out of ideas.
Here is the diff if you want to take a look at it: https://developer.blender.org/D7092
The last test is the one with the issue described.
Thank you.
Update: With the help of LazyDodo, I was able to find and fix the issue.
1 Like
I didn’t download and try the patch, but this looked suspicious to me:
BLI_wavlTree_free frees the memory pointed to by the argument tree, and then after that, assigns a value to tree->root, etc. You shouldn’t use any memory after you’ve given it to MEM_freeN.
Similarly suspicious is that in your tests, you end with
EXPECT_TRUE(BLI_wavlTree_empty(tree));
right after having called BLI_wavlTree_free(tree, free_sample_data), which will have freed the memory pointed at by tree, so you shouldn’t look inside tree anymore, yet BLI_wavTree_empty does just that.
P.S., out of curiousity, what sweep-line algorithm are you implementing?
Thinking more about your problem, I think the problem I pointed out in the previous post is probably not where your problem lies. I suspect that somehow one of your free_wavl_node calls may be freeing a node that you are still holding on to a value of (mistakenly). One way to track down this, is so, would be to print out a node pointer and some indication of where you are in the source before each free_wavl_node, and then print out the whole tree (with pointer values) every once in a while, and see if your tree contains pointers that you have freed earlier.
You’re absolutely right! I shouldn’t assign anything after the free…
Updated the diff. The problem still remains though 
As for what this will be used: The idea is to improve the fill tools in grease pencil.
You might want to check out BLI_delaunay_2d_cdt_calc, which can do intersections of 2D geometry.
This is what I am suspecting as well. Somehow I must free the root node beforehand. Will look into your suggestion, thank you.
Interesting, but as this project is connected to my bachelor thesis, I need to do something (somewhat) new! But this could be useful for when I want to do comparisons to other approaches 
One thing you may find useful/necessary is an exact ‘orient’ test: that is, a test that says for 2d points a,b,c whether or not c is to the left of, on, or to the right of line ab. If you use floating point arithmetic, it is easy to make mistakes and mess up sweep line algorithms.
There is code to do such a test exactly in the BLI_delaunay_2d_cdt calc, which I was lazy and didn’t put into BLI. If you think you want it, let me know and I’ll make it part of BLI.
my current function for that looks like so
/* Helper: check if point p is to the left of the line from prev to next */
static int stroke_point_is_convex(float prev[2], float next[2], float p[2])
{
float a = ((next[0] - p[0])*(p[1] - prev[1]) - (next[1] - p[1])*(p[0] - prev[0]));
if (a > 0.0f) {
return 1;
}
else if (a < 0.0f) {
return -1;
}
return 0; // point is on the line
}
guess that could be an issue because of the substractions (?)
Coming back to my issue: the test that fails never uses any free function before the error, so I don’t know where the free of the root could happen…
Sorry, I don’t have time right now to dig further into your code. You might want to confirm that no free function is being called by, e.g., putting a breakpoint on MEM_freeN after hitting a breakpoint that you could set at the start of the test.
One other piece of code that I found a bit suspicious: in delete_binary_node the setting of replace_is_leaf = false does not, if I am reading this right, reflect reality if node->pred is a leaf.
Re your earlier question about your orient test: yes, the subtraction is the root of the problem. It is quite possible for that floating point expression to end up being the opposite of what is really going on if you do the test exactly. You can web search for Shewchuk and Fast Robust Predicates for more details.
I think this one is best explained as : Dangling pointer in 3…2…1…
1 Like
Looking at the call stack, it looks like this is happening in the test before? I guess that makes sense since the next test will “stumble” over that memory region and cause all kinds of issues… just like the one im seeing. Well thank you kind sir I think i might be able to fix this now! Yay
Not a problem, +1 for having tests from the start!
1 Like
