From 08c49d8a121a637bd45c386af1d9d172264e53b0 Mon Sep 17 00:00:00 2001
From: Sergey Sharybin <sergey.vfx@gmail.com>
Date: Mon, 19 Aug 2013 10:40:47 +0000
Subject: 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
---
 extern/recastnavigation/recast-capi.cpp | 126 --------------------------------
 extern/recastnavigation/recast-capi.h   |   5 --
 2 files changed, 131 deletions(-)

(limited to 'extern')

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
-- 
cgit v1.2.3