use strict flags for kdtree, and replace ints with unsigned ints where possible.

also replace callocs with mallocs since zeroing memory can be avoided.

1 files changed, 79 insertions, 42 deletions

diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c
index 38910534d99..57227dc5d5f 100644
--- a/source/blender/blenlib/intern/BLI_kdtree.c
+++ b/source/blender/blenlib/intern/BLI_kdtree.c
@@ -30,18 +30,19 @@
 #include "BLI_math.h"
 #include "BLI_kdtree.h"
 #include "BLI_utildefines.h"
+#include "BLI_strict_flags.h"
 
 
 typedef struct KDTreeNode {
 	struct KDTreeNode *left, *right;
 	float co[3], nor[3];
 	int index;
-	short d;
+	unsigned int d;  /* range is only (0-2) */
 } KDTreeNode;
 
 struct KDTree {
 	KDTreeNode *nodes;
-	int totnode;
+	unsigned int totnode;
 	KDTreeNode *root;
 };
 
@@ -49,13 +50,17 @@ struct KDTree {
 #define KD_NEAR_ALLOC_INC 100  /* alloc increment for collecting nearest */
 #define KD_FOUND_ALLOC_INC 50  /* alloc increment for collecting nearest */
 
-KDTree *BLI_kdtree_new(int maxsize)
+/**
+ * Creates or free a kdtree
+ */
+KDTree *BLI_kdtree_new(unsigned int maxsize)
 {
 	KDTree *tree;
 
-	tree = MEM_callocN(sizeof(KDTree), "KDTree");
-	tree->nodes = MEM_callocN(sizeof(KDTreeNode) * maxsize, "KDTreeNode");
+	tree = MEM_mallocN(sizeof(KDTree), "KDTree");
+	tree->nodes = MEM_mallocN(sizeof(KDTreeNode) * maxsize, "KDTreeNode");
 	tree->totnode = 0;
+	tree->root = NULL;
 
 	return tree;
 }
@@ -68,20 +73,32 @@ void BLI_kdtree_free(KDTree *tree)
 	}
 }
 
+/**
+ * Construction: first insert points, then call balance. Normal is optional.
+ */
 void BLI_kdtree_insert(KDTree *tree, int index, const float co[3], const float nor[3])
 {
 	KDTreeNode *node = &tree->nodes[tree->totnode++];
 
-	node->index = index;
+	/* note, array isn't calloc'd,
+	 * need to initialize all struct members */
+
+	node->left = node->right = NULL;
 	copy_v3_v3(node->co, co);
-	if (nor) copy_v3_v3(node->nor, nor);
+	if (nor)
+		copy_v3_v3(node->nor, nor);
+	else
+		zero_v3(node->nor);
+
+	node->index = index;
+	node->d = 0;
 }
 
-static KDTreeNode *kdtree_balance(KDTreeNode *nodes, int totnode, int axis)
+static KDTreeNode *kdtree_balance(KDTreeNode *nodes, unsigned int totnode, unsigned int axis)
 {
 	KDTreeNode *node;
 	float co;
-	int left, right, median, i, j;
+	unsigned int left, right, median, i, j;
 
 	if (totnode <= 0)
 		return NULL;
@@ -102,7 +119,9 @@ static KDTreeNode *kdtree_balance(KDTreeNode *nodes, int totnode, int axis)
 			while (nodes[++i].co[axis] < co) ;
 			while (nodes[--j].co[axis] > co && j > left) ;
 
-			if (i >= j) break;
+			if (i >= j)
+				break;
+
 			SWAP(KDTreeNode, nodes[i], nodes[j]);
 		}
 
@@ -147,23 +166,27 @@ static float squared_distance(const float v2[3], const float v1[3], const float
 	return dist;
 }
 
-static KDTreeNode **recalloc_nodes(KDTreeNode **stack, int *totstack, const bool is_alloc)
+static KDTreeNode **realloc_nodes(KDTreeNode **stack, unsigned int *totstack, const bool is_alloc)
 {
 	KDTreeNode **stack_new = MEM_mallocN((*totstack + KD_NEAR_ALLOC_INC) * sizeof(KDTreeNode *), "KDTree.treestack");
 	memcpy(stack_new, stack, *totstack * sizeof(KDTreeNode *));
-	memset(stack_new + *totstack, 0, sizeof(KDTreeNode *) * KD_NEAR_ALLOC_INC);
+	// memset(stack_new + *totstack, 0, sizeof(KDTreeNode *) * KD_NEAR_ALLOC_INC);
 	if (is_alloc)
 		MEM_freeN(stack);
 	*totstack += KD_NEAR_ALLOC_INC;
 	return stack_new;
 }
 
-int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3], KDTreeNearest *nearest)
+/**
+ * Find nearest returns index, and -1 if no node is found.
+ */
+int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3],
+                            KDTreeNearest *r_nearest)
 {
 	KDTreeNode *root, *node, *min_node;
 	KDTreeNode **stack, *defaultstack[KD_STACK_INIT];
 	float min_dist, cur_dist;
-	int totstack, cur = 0;
+	unsigned int totstack, cur = 0;
 
 	if (!tree->root)
 		return -1;
@@ -224,14 +247,14 @@ int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3],
 				stack[cur++] = node->left;
 		}
 		if (UNLIKELY(cur + 3 > totstack)) {
-			stack = recalloc_nodes(stack, &totstack, defaultstack != stack);
+			stack = realloc_nodes(stack, &totstack, defaultstack != stack);
 		}
 	}
 
-	if (nearest) {
-		nearest->index = min_node->index;
-		nearest->dist = sqrtf(min_dist);
-		copy_v3_v3(nearest->co, min_node->co);
+	if (r_nearest) {
+		r_nearest->index = min_node->index;
+		r_nearest->dist = sqrtf(min_dist);
+		copy_v3_v3(r_nearest->co, min_node->co);
 	}
 
 	if (stack != defaultstack)
@@ -240,9 +263,10 @@ int BLI_kdtree_find_nearest(KDTree *tree, const float co[3], const float nor[3],
 	return min_node->index;
 }
 
-static void add_nearest(KDTreeNearest *ptn, int *found, int n, int index, float dist, float *co)
+static void add_nearest(KDTreeNearest *ptn, unsigned int *found, unsigned int n, int index,
+                        float dist, const float *co)
 {
-	int i;
+	unsigned int i;
 
 	if (*found < n) (*found)++;
 
@@ -258,15 +282,23 @@ static void add_nearest(KDTreeNearest *ptn, int *found, int n, int index, float
 	copy_v3_v3(ptn[i].co, co);
 }
 
-/* finds the nearest n entries in tree to specified coordinates */
-int BLI_kdtree_find_n_nearest(KDTree *tree, int n, const float co[3], const float nor[3], KDTreeNearest *nearest)
+/**
+ * Find n nearest returns number of points found, with results in nearest.
+ * Normal is optional, but if given will limit results to points in normal direction from co.
+ *
+ * \param r_nearest  An array of nearest, sized at least \a n.
+ */
+int BLI_kdtree_find_nearest_n(KDTree *tree, const float co[3], const float nor[3],
+                              KDTreeNearest r_nearest[],
+                              unsigned int n)
 {
 	KDTreeNode *root, *node = NULL;
 	KDTreeNode **stack, *defaultstack[KD_STACK_INIT];
 	float cur_dist;
-	int i, totstack, cur = 0, found = 0;
+	unsigned int totstack, cur = 0;
+	unsigned int i, found = 0;
 
-	if (!tree->root)
+	if (!tree->root || n == 0)
 		return 0;
 
 	stack = defaultstack;
@@ -275,7 +307,7 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, const float co[3], const floa
 	root = tree->root;
 
 	cur_dist = squared_distance(root->co, co, root->nor, nor);
-	add_nearest(nearest, &found, n, root->index, cur_dist, root->co);
+	add_nearest(r_nearest, &found, n, root->index, cur_dist, root->co);
 	
 	if (co[root->d] < root->co[root->d]) {
 		if (root->right)
@@ -298,11 +330,11 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, const float co[3], const floa
 		if (cur_dist < 0.0f) {
 			cur_dist = -cur_dist * cur_dist;
 
-			if (found < n || -cur_dist < nearest[found - 1].dist) {
+			if (found < n || -cur_dist < r_nearest[found - 1].dist) {
 				cur_dist = squared_distance(node->co, co, node->nor, nor);
 
-				if (found < n || cur_dist < nearest[found - 1].dist)
-					add_nearest(nearest, &found, n, node->index, cur_dist, node->co);
+				if (found < n || cur_dist < r_nearest[found - 1].dist)
+					add_nearest(r_nearest, &found, n, node->index, cur_dist, node->co);
 
 				if (node->left)
 					stack[cur++] = node->left;
@@ -313,10 +345,10 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, const float co[3], const floa
 		else {
 			cur_dist = cur_dist * cur_dist;
 
-			if (found < n || cur_dist < nearest[found - 1].dist) {
+			if (found < n || cur_dist < r_nearest[found - 1].dist) {
 				cur_dist = squared_distance(node->co, co, node->nor, nor);
-				if (found < n || cur_dist < nearest[found - 1].dist)
-					add_nearest(nearest, &found, n, node->index, cur_dist, node->co);
+				if (found < n || cur_dist < r_nearest[found - 1].dist)
+					add_nearest(r_nearest, &found, n, node->index, cur_dist, node->co);
 
 				if (node->right)
 					stack[cur++] = node->right;
@@ -325,17 +357,17 @@ int BLI_kdtree_find_n_nearest(KDTree *tree, int n, const float co[3], const floa
 				stack[cur++] = node->left;
 		}
 		if (UNLIKELY(cur + 3 > totstack)) {
-			stack = recalloc_nodes(stack, &totstack, defaultstack != stack);
+			stack = realloc_nodes(stack, &totstack, defaultstack != stack);
 		}
 	}
 
 	for (i = 0; i < found; i++)
-		nearest[i].dist = sqrtf(nearest[i].dist);
+		r_nearest[i].dist = sqrtf(r_nearest[i].dist);
 
 	if (stack != defaultstack)
 		MEM_freeN(stack);
 
-	return found;
+	return (int)found;
 }
 
 static int range_compare(const void *a, const void *b)
@@ -350,14 +382,13 @@ static int range_compare(const void *a, const void *b)
 	else
 		return 0;
 }
-static void add_in_range(KDTreeNearest **ptn, int found, int *totfoundstack, int index, float dist, float *co)
+static void add_in_range(KDTreeNearest **ptn, unsigned int found, unsigned int *totfoundstack, int index, float dist, float *co)
 {
 	KDTreeNearest *to;
 
 	if (found >= *totfoundstack) {
 		KDTreeNearest *temp = MEM_mallocN((*totfoundstack + KD_FOUND_ALLOC_INC) * sizeof(KDTreeNode), "KDTree.treefoundstack");
 		memcpy(temp, *ptn, *totfoundstack * sizeof(KDTreeNearest));
-		memset(temp + *totfoundstack, 0, sizeof(KDTreeNearest *) * KD_FOUND_ALLOC_INC);
 		if (*ptn)
 			MEM_freeN(*ptn);
 		*ptn = temp;
@@ -371,13 +402,19 @@ static void add_in_range(KDTreeNearest **ptn, int found, int *totfoundstack, int
 	copy_v3_v3(to->co, co);
 }
 
-int BLI_kdtree_range_search(KDTree *tree, float range, const float co[3], const float nor[3], KDTreeNearest **nearest)
+/**
+ * Range search returns number of points found, with results in nearest
+ * Normal is optional, but if given will limit results to points in normal direction from co.
+ * Remember to free nearest after use!
+ */
+int BLI_kdtree_range_search(KDTree *tree, const float co[3], const float nor[3],
+                            KDTreeNearest **r_nearest, float range)
 {
 	KDTreeNode *root, *node = NULL;
 	KDTreeNode **stack, *defaultstack[KD_STACK_INIT];
 	KDTreeNearest *foundstack = NULL;
 	float range2 = range * range, dist2;
-	int totstack, cur = 0, found = 0, totfoundstack = 0;
+	unsigned int totstack, cur = 0, found = 0, totfoundstack = 0;
 
 	if (!tree || !tree->root)
 		return 0;
@@ -429,7 +466,7 @@ int BLI_kdtree_range_search(KDTree *tree, float range, const float co[3], const
 		}
 
 		if (UNLIKELY(cur + 3 > totstack)) {
-			stack = recalloc_nodes(stack, &totstack, defaultstack != stack);
+			stack = realloc_nodes(stack, &totstack, defaultstack != stack);
 		}
 	}
 
@@ -439,7 +476,7 @@ int BLI_kdtree_range_search(KDTree *tree, float range, const float co[3], const
 	if (found)
 		qsort(foundstack, found, sizeof(KDTreeNearest), range_compare);
 
-	*nearest = foundstack;
+	*r_nearest = foundstack;
 
-	return found;
+	return (int)found;
 }