Use reentrant qsort() in particle codes

Particle system code used global variable to sort hair by orig index,
which is not safe for threading at all.

Replaced this with usage of reentrant version of qsort, which is
now implemented in BLI. It was moved from recast navigation code
to BLI, so more areas could use it (if needed).

--
svn merge -r59086:59087 ^/branches/soc-2013-depsgraph_mt

7 files changed, 215 insertions, 143 deletions

diff --git a/extern/recastnavigation/recast-capi.cpp b/extern/recastnavigation/recast-capi.cpp
index 1c11d87f639..38c14118156 100644
--- a/extern/recastnavigation/recast-capi.cpp
+++ b/extern/recastnavigation/recast-capi.cpp
@@ -270,129 +270,3 @@ unsigned int *recast_polyMeshDetailGetMeshes(struct recast_polyMeshDetail *mesh,
 	return dmesh->meshes;
 }
 
-//  qsort based on FreeBSD source (libkern\qsort.c)
-typedef int	cmp_t(void *, const void *, const void *);
-static inline char	*med3(char *, char *, char *, cmp_t *, void *);
-static inline void	 swapfunc(char *, char *, int, int);
-
-#define min(a, b)	(a) < (b) ? a : b
-#define swapcode(TYPE, parmi, parmj, n)		\
-{											\
-	long i = (n) / sizeof(TYPE); 			\
-	TYPE *pi = (TYPE *) (parmi); 			\
-	TYPE *pj = (TYPE *) (parmj); 			\
-	do { 									\
-		TYPE	t = *pi;					\
-		*pi++ = *pj;						\
-		*pj++ = t;							\
-	} while (--i > 0);						\
-}
-#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
-	es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
-
-static inline void swapfunc(char* a, char* b, int n, int swaptype)
-{
-	if(swaptype <= 1)
-		swapcode(long, a, b, n)
-	else
-	swapcode(char, a, b, n)
-}
-
-#define swap(a, b)					\
-	if (swaptype == 0) {			\
-		long t = *(long *)(a);		\
-		*(long *)(a) = *(long *)(b);\
-		*(long *)(b) = t;			\
-	} else							\
-		swapfunc(a, b, es, swaptype)
-
-#define vecswap(a, b, n) 	if ((n) > 0) swapfunc(a, b, n, swaptype)
-#define	CMP(t, x, y) (cmp((t), (x), (y)))
-
-static inline char *med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk)
-{
-	return CMP(thunk, a, b) < 0 ?
-		(CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
-		:(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
-}
-
-void recast_qsort(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp)
-{
-	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
-	int d, r, swaptype, swap_cnt;
-
-loop:	
-	SWAPINIT(a, es);
-	swap_cnt = 0;
-	if (n < 7) {
-		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
-			for (pl = pm; 
-				pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
-				pl -= es)
-				swap(pl, pl - es);
-		return;
-	}
-	pm = (char *)a + (n / 2) * es;
-	if (n > 7) {
-		pl = (char *)a;
-		pn = (char *)a + (n - 1) * es;
-		if (n > 40) {
-			d = (n / 8) * es;
-			pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
-			pm = med3(pm - d, pm, pm + d, cmp, thunk);
-			pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
-		}
-		pm = med3(pl, pm, pn, cmp, thunk);
-	}
-	swap((char *)a, pm);
-	pa = pb = (char *)a + es;
-
-	pc = pd = (char *)a + (n - 1) * es;
-	for (;;) {
-		while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) {
-			if (r == 0) {
-				swap_cnt = 1;
-				swap(pa, pb);
-				pa += es;
-			}
-			pb += es;
-		}
-		while (pb <= pc && (r = CMP(thunk, pc, a)) >= 0) {
-			if (r == 0) {
-				swap_cnt = 1;
-				swap(pc, pd);
-				pd -= es;
-			}
-			pc -= es;
-		}
-		if (pb > pc)
-			break;
-		swap(pb, pc);
-		swap_cnt = 1;
-		pb += es;
-		pc -= es;
-	}
-	if (swap_cnt == 0) {  /* Switch to insertion sort */
-		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
-			for (pl = pm; 
-				pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
-				pl -= es)
-				swap(pl, pl - es);
-		return;
-	}
-
-	pn = (char *)a + n * es;
-	r = min(pa - (char *)a, pb - pa);
-	vecswap((char *)a, pb - r, r);
-	r = min(pd - pc, pn - pd - es);
-	vecswap(pb, pn - r, r);
-	if ((r = pb - pa) > es)
-		recast_qsort(a, r / es, es, thunk, cmp);
-	if ((r = pd - pc) > es) {
-		/* Iterate rather than recurse to save stack space */
-		a = pn - r;
-		n = r / es;
-		goto loop;
-	}
-}
-
diff --git a/extern/recastnavigation/recast-capi.h b/extern/recastnavigation/recast-capi.h
index 52a8e215ea1..54bf84931c4 100644
--- a/extern/recastnavigation/recast-capi.h
+++ b/extern/recastnavigation/recast-capi.h
@@ -127,11 +127,6 @@ unsigned char *recast_polyMeshDetailGetTris(struct recast_polyMeshDetail *mesh,
 
 unsigned int *recast_polyMeshDetailGetMeshes(struct recast_polyMeshDetail *mesh, int *nmeshes);
 
-/* utility function: quick sort reentrant */
-typedef int	recast_cmp_t(void *ctx, const void *a, const void *b);
-
-void recast_qsort(void *a, size_t n, size_t es, void *thunk, recast_cmp_t *cmp);
-
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/blenkernel/intern/navmesh_conversion.c b/source/blender/blenkernel/intern/navmesh_conversion.c
index 1d662ae3116..68564a1e298 100644
--- a/source/blender/blenkernel/intern/navmesh_conversion.c
+++ b/source/blender/blenkernel/intern/navmesh_conversion.c
@@ -38,6 +38,7 @@
 
 #include "BLI_utildefines.h"
 #include "BLI_math.h"
+#include "BLI_sort.h"
 
 #include "BKE_navmesh_conversion.h"
 #include "BKE_cdderivedmesh.h"
@@ -340,7 +341,7 @@ int buildNavMeshData(const int nverts, const float *verts,
 		trisMapping[i] = i;
 	context.recastData = recastData;
 	context.trisToFacesMap = trisToFacesMap;
-	recast_qsort(trisMapping, ntris, sizeof(int), &context, compareByData);
+	BLI_qsort_r(trisMapping, ntris, sizeof(int), &context, compareByData);
 
 	/* search first valid triangle - triangle of convex polygon */
 	validTriStart = -1;
diff --git a/source/blender/blenkernel/intern/particle_system.c b/source/blender/blenkernel/intern/particle_system.c
index ee3f3332ec3..8cb9404a647 100644
--- a/source/blender/blenkernel/intern/particle_system.c
+++ b/source/blender/blenkernel/intern/particle_system.c
@@ -70,6 +70,7 @@
 #include "BLI_blenlib.h"
 #include "BLI_kdtree.h"
 #include "BLI_kdopbvh.h"
+#include "BLI_sort.h"
 #include "BLI_threads.h"
 #include "BLI_linklist.h"
 
@@ -1010,12 +1011,11 @@ static void *distribute_threads_exec_cb(void *data)
 	return 0;
 }
 
-/* not thread safe, but qsort doesn't take userdata argument */
-static int *COMPARE_ORIG_INDEX = NULL;
-static int distribute_compare_orig_index(const void *p1, const void *p2)
+static int distribute_compare_orig_index(void *user_data, const void *p1, const void *p2)
 {
-	int index1 = COMPARE_ORIG_INDEX[*(const int *)p1];
-	int index2 = COMPARE_ORIG_INDEX[*(const int *)p2];
+	int *orig_index = (int *) user_data;
+	int index1 = orig_index[*(const int *)p1];
+	int index2 = orig_index[*(const int *)p2];
 
 	if (index1 < index2)
 		return -1;
@@ -1332,20 +1332,19 @@ static int distribute_threads_init_data(ParticleThread *threads, Scene *scene, D
 	/* For hair, sort by origindex (allows optimization's in rendering), */
 	/* however with virtual parents the children need to be in random order. */
 	if (part->type == PART_HAIR && !(part->childtype==PART_CHILD_FACES && part->parents!=0.0f)) {
-		COMPARE_ORIG_INDEX = NULL;
+		int *orig_index = NULL;
 
 		if (from == PART_FROM_VERT) {
 			if (dm->numVertData)
-				COMPARE_ORIG_INDEX= dm->getVertDataArray(dm, CD_ORIGINDEX);
+				orig_index = dm->getVertDataArray(dm, CD_ORIGINDEX);
 		}
 		else {
 			if (dm->numTessFaceData)
-				COMPARE_ORIG_INDEX= dm->getTessFaceDataArray(dm, CD_ORIGINDEX);
+				orig_index = dm->getTessFaceDataArray(dm, CD_ORIGINDEX);
 		}
 
-		if (COMPARE_ORIG_INDEX) {
-			qsort(particle_element, totpart, sizeof(int), distribute_compare_orig_index);
-			COMPARE_ORIG_INDEX = NULL;
+		if (orig_index) {
+			BLI_qsort_r(particle_element, totpart, sizeof(int), orig_index, distribute_compare_orig_index);
 		}
 	}
 
diff --git a/source/blender/blenlib/BLI_sort.h b/source/blender/blenlib/BLI_sort.h
new file mode 100644
index 00000000000..9e533aac758
--- /dev/null
+++ b/source/blender/blenlib/BLI_sort.h
@@ -0,0 +1,41 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Benoit Bolsee,
+ *                 Sergey Sharybin.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BLI_SORT_H__
+#define __BLI_SORT_H__
+
+/** \file BLI_sort.h
+ *  \ingroup bli
+ */
+
+/* Quick sort reentrant */
+typedef int (*BLI_sort_cmp_t)(void *ctx, const void *a, const void *b);
+
+void BLI_qsort_r(void *a, size_t n, size_t es, void *thunk, BLI_sort_cmp_t cmp);
+
+#endif  /* __BLI_SORT_H__ */
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 8b604e41824..70665521ca8 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -86,6 +86,7 @@ set(SRC
 	intern/rct.c
 	intern/scanfill.c
 	intern/smallhash.c
+	intern/sort.c
 	intern/stack.c
 	intern/storage.c
 	intern/string.c
@@ -147,6 +148,7 @@ set(SRC
 	BLI_rect.h
 	BLI_scanfill.h
 	BLI_smallhash.h
+	BLI_sort.h
 	BLI_stack.h
 	BLI_string.h
 	BLI_string_cursor_utf8.h
diff --git a/source/blender/blenlib/intern/sort.c b/source/blender/blenlib/intern/sort.c
new file mode 100644
index 00000000000..5ba608e5ec2
--- /dev/null
+++ b/source/blender/blenlib/intern/sort.c
@@ -0,0 +1,160 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2013 Blender Foundation
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Benoit Bolsee,
+ *                 Sergey Sharybin.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/blenlib/intern/sort.c
+ *  \ingroup bli
+ */
+
+#include "BLI_utildefines.h"
+
+#include "BLI_sort.h"
+
+/* **** qsort based on FreeBSD source (libkern\qsort.c) **** */
+BLI_INLINE char	*med3(char *, char *, char *, BLI_sort_cmp_t, void *);
+BLI_INLINE void	 swapfunc(char *, char *, int, int);
+
+#define min(a, b)	(a) < (b) ? a : b
+#define swapcode(TYPE, parmi, parmj, n)		\
+{											\
+	long i = (n) / sizeof(TYPE); 			\
+	TYPE *pi = (TYPE *) (parmi); 			\
+	TYPE *pj = (TYPE *) (parmj); 			\
+	do { 									\
+		TYPE	t = *pi;					\
+		*pi++ = *pj;						\
+		*pj++ = t;							\
+	} while (--i > 0);						\
+}
+#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
+	es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
+
+BLI_INLINE void swapfunc(char* a, char* b, int n, int swaptype)
+{
+	if(swaptype <= 1)
+		swapcode(long, a, b, n)
+	else
+	swapcode(char, a, b, n)
+}
+
+#define swap(a, b)					\
+	if (swaptype == 0) {			\
+		long t = *(long *)(a);		\
+		*(long *)(a) = *(long *)(b);\
+		*(long *)(b) = t;			\
+	} else							\
+		swapfunc(a, b, es, swaptype)
+
+#define vecswap(a, b, n) 	if ((n) > 0) swapfunc(a, b, n, swaptype)
+#define	CMP(t, x, y) (cmp((t), (x), (y)))
+
+BLI_INLINE char *med3(char *a, char *b, char *c, BLI_sort_cmp_t cmp, void *thunk)
+{
+	return CMP(thunk, a, b) < 0 ?
+		(CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
+		:(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
+}
+
+void BLI_qsort_r(void *a, size_t n, size_t es, void *thunk, BLI_sort_cmp_t cmp)
+{
+	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
+	int d, r, swaptype, swap_cnt;
+
+loop:
+	SWAPINIT(a, es);
+	swap_cnt = 0;
+	if (n < 7) {
+		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+			for (pl = pm;
+				pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
+				pl -= es)
+				swap(pl, pl - es);
+		return;
+	}
+	pm = (char *)a + (n / 2) * es;
+	if (n > 7) {
+		pl = (char *)a;
+		pn = (char *)a + (n - 1) * es;
+		if (n > 40) {
+			d = (n / 8) * es;
+			pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
+			pm = med3(pm - d, pm, pm + d, cmp, thunk);
+			pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
+		}
+		pm = med3(pl, pm, pn, cmp, thunk);
+	}
+	swap((char *)a, pm);
+	pa = pb = (char *)a + es;
+
+	pc = pd = (char *)a + (n - 1) * es;
+	for (;;) {
+		while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) {
+			if (r == 0) {
+				swap_cnt = 1;
+				swap(pa, pb);
+				pa += es;
+			}
+			pb += es;
+		}
+		while (pb <= pc && (r = CMP(thunk, pc, a)) >= 0) {
+			if (r == 0) {
+				swap_cnt = 1;
+				swap(pc, pd);
+				pd -= es;
+			}
+			pc -= es;
+		}
+		if (pb > pc)
+			break;
+		swap(pb, pc);
+		swap_cnt = 1;
+		pb += es;
+		pc -= es;
+	}
+	if (swap_cnt == 0) {  /* Switch to insertion sort */
+		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+			for (pl = pm;
+				pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
+				pl -= es)
+				swap(pl, pl - es);
+		return;
+	}
+
+	pn = (char *)a + n * es;
+	r = min(pa - (char *)a, pb - pa);
+	vecswap((char *)a, pb - r, r);
+	r = min(pd - pc, pn - pd - es);
+	vecswap(pb, pn - r, r);
+	if ((r = pb - pa) > es)
+		BLI_qsort_r(a, r / es, es, thunk, cmp);
+	if ((r = pd - pc) > es) {
+		/* Iterate rather than recurse to save stack space */
+		a = pn - r;
+		n = r / es;
+		goto loop;
+	}
+}