diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2013-08-19 14:40:47 +0400 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2013-08-19 14:40:47 +0400 |
commit | 08c49d8a121a637bd45c386af1d9d172264e53b0 (patch) | |
tree | fc11c2cd24dc4185e1ea9626ca1d7972ee093b75 /extern/recastnavigation | |
parent | 018ab045e3b9c20e35b5dc658fe35f3327048bbf (diff) |
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
Diffstat (limited to 'extern/recastnavigation')
-rw-r--r-- | extern/recastnavigation/recast-capi.cpp | 126 | ||||
-rw-r--r-- | extern/recastnavigation/recast-capi.h | 5 |
2 files changed, 0 insertions, 131 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 |