[Bf-blender-cvs] [c2dba7e] master: BLI_kdopbvh: Replace realloc's with BLI_stack

[Campbell Barton]

Commit: c2dba7e344ef1121ab6dba198b7d82174ebfa6ca
Author: Campbell Barton
Date:   Tue Jul 15 21:35:50 2014 +1000
https://developer.blender.org/rBc2dba7e344ef1121ab6dba198b7d82174ebfa6ca

BLI_kdopbvh: Replace realloc's with BLI_stack

===================================================================

M	source/blender/blenlib/BLI_kdopbvh.h
M	source/blender/blenlib/intern/BLI_kdopbvh.c

===================================================================

diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index 7b00fd9..99a5fad 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -93,7 +93,7 @@ int BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const f
 void BLI_bvhtree_update_tree(BVHTree *tree);
 
 /* collision/overlap: check two trees if they overlap, alloc's *overlap with length of the int return value */
-BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int *result);
+BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int *r_overlap_tot);
 
 float BLI_bvhtree_getepsilon(const BVHTree *tree);
 
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 6b1fbe8..58c0173 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -34,6 +34,7 @@
 #include "MEM_guardedalloc.h"
 
 #include "BLI_utildefines.h"
+#include "BLI_stack.h"
 #include "BLI_kdopbvh.h"
 #include "BLI_math.h"
 #include "BLI_strict_flags.h"
@@ -77,9 +78,7 @@ BLI_STATIC_ASSERT((sizeof(void *) == 8 && sizeof(BVHTree) <= 48) ||
 
 typedef struct BVHOverlapData {
 	BVHTree *tree1, *tree2; 
-	BVHTreeOverlap *overlap; 
-	unsigned int i;
-	unsigned int max_overlap; /* i is number of overlaps */
+	struct BLI_Stack *overlap;  /* store BVHTreeOverlap */
 	axis_t start_axis, stop_axis;
 } BVHOverlapData;
 
@@ -1038,27 +1037,16 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2)
 		if (!node1->totnode) {
 			/* check if node2 is a leaf */
 			if (!node2->totnode) {
+				BVHTreeOverlap *overlap;
 
 				if (node1 == node2) {
 					return;
 				}
 
-				if (data->i >= data->max_overlap) {
-					/* try to make alloc'ed memory bigger */
-					data->overlap = realloc(data->overlap, sizeof(BVHTreeOverlap) * (size_t)data->max_overlap * 2);
-					
-					if (!data->overlap) {
-						printf("Out of Memory in traverse\n");
-						return;
-					}
-					data->max_overlap *= 2;
-				}
-				
 				/* both leafs, insert overlap! */
-				data->overlap[data->i].indexA = node1->index;
-				data->overlap[data->i].indexB = node2->index;
-
-				data->i++;
+				overlap = BLI_stack_push_r(data->overlap);
+				overlap->indexA = node1->index;
+				overlap->indexB = node2->index;
 			}
 			else {
 				for (j = 0; j < data->tree2->tree_type; j++) {
@@ -1077,10 +1065,10 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2)
 	return;
 }
 
-BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int *result)
+BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int *r_overlap_tot)
 {
 	int j;
-	unsigned int total = 0;
+	size_t total = 0;
 	BVHTreeOverlap *overlap = NULL, *to = NULL;
 	BVHOverlapData **data;
 	
@@ -1102,11 +1090,9 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int
 		data[j] = MEM_callocN(sizeof(BVHOverlapData), "BVHOverlapData");
 		
 		/* init BVHOverlapData */
-		data[j]->overlap = malloc(sizeof(BVHTreeOverlap) * (size_t)max_ii(tree1->totleaf, tree2->totleaf));
+		data[j]->overlap = BLI_stack_new(sizeof(BVHTreeOverlap), __func__);
 		data[j]->tree1 = tree1;
 		data[j]->tree2 = tree2;
-		data[j]->max_overlap = (unsigned int)max_ii(tree1->totleaf, tree2->totleaf);
-		data[j]->i = 0;
 		data[j]->start_axis = min_axis(tree1->start_axis, tree2->start_axis);
 		data[j]->stop_axis  = min_axis(tree1->stop_axis,  tree2->stop_axis);
 	}
@@ -1117,22 +1103,23 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int
 	}
 	
 	for (j = 0; j < tree1->tree_type; j++)
-		total += data[j]->i;
+		total += BLI_stack_count(data[j]->overlap);
 	
-	to = overlap = MEM_callocN(sizeof(BVHTreeOverlap) * total, "BVHTreeOverlap");
+	to = overlap = MEM_mallocN(sizeof(BVHTreeOverlap) * total, "BVHTreeOverlap");
 	
 	for (j = 0; j < tree1->tree_type; j++) {
-		memcpy(to, data[j]->overlap, data[j]->i * sizeof(BVHTreeOverlap));
-		to += data[j]->i;
+		unsigned int count = (unsigned int)BLI_stack_count(data[j]->overlap);
+		BLI_stack_pop_n(data[j]->overlap, to, count);
+		BLI_stack_free(data[j]->overlap);
+		to += count;
 	}
 	
 	for (j = 0; j < tree1->tree_type; j++) {
-		free(data[j]->overlap);
 		MEM_freeN(data[j]);
 	}
 	MEM_freeN(data);
 	
-	(*result) = total;
+	*r_overlap_tot = (unsigned int)total;
 	return overlap;
 }