[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [59279] trunk/blender: Use reentrant qsort () in particle codes
Sergey Sharybin
sergey.vfx at gmail.com
Mon Aug 19 12:40:47 CEST 2013
Revision: 59279
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=59279
Author: nazgul
Date: 2013-08-19 10:40:47 +0000 (Mon, 19 Aug 2013)
Log Message:
-----------
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
Revision Links:
--------------
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=59086
Modified Paths:
--------------
trunk/blender/extern/recastnavigation/recast-capi.cpp
trunk/blender/extern/recastnavigation/recast-capi.h
trunk/blender/source/blender/blenkernel/intern/navmesh_conversion.c
trunk/blender/source/blender/blenkernel/intern/particle_system.c
trunk/blender/source/blender/blenlib/CMakeLists.txt
Added Paths:
-----------
trunk/blender/source/blender/blenlib/BLI_sort.h
trunk/blender/source/blender/blenlib/intern/sort.c
Property Changed:
----------------
trunk/blender/
trunk/blender/source/blender/editors/interface/interface.c
trunk/blender/source/blender/editors/space_outliner/
Property changes on: trunk/blender
___________________________________________________________________
Modified: svn:mergeinfo
- /branches/ge_dev:58091-58422
/branches/ge_harmony:42255,42279-42282,42286,42302,42338,42349,42616,42620,42698-42699,42739,42753,42773-42774,42832,44568,44597-44598,44793-44794
/branches/soc-2011-cucumber:37517,38166-38167,38177,38179-38180,38187,38242,38384,38387,38403-38404,38407,38968,38970,38973,39045,40845,42997-42998,43439
/branches/soc-2011-tomato:42376,42378-42379,42383,42385,42395,42397-42400,42407,42411,42418,42443-42444,42446,42467,42472,42486,42650-42652,42654-42655,42709-42710,42733-42734,42801,43872,44130,44141,44147-44149,44151-44152,44229-44230,45623-45625,46037,48089,48092,48551-48552,48679,48790,48792-48793,49076,49087,49292,49294,49466,49894,50052,50126,52854-52856,54573,58822,58989
/branches/soc-2013-depsgraph_mt:57516,57900,57939-57940,57945,57958-57961,58151,58155-58156,58169,58277-58279,58282-58283,58711,58787,58789,58796,59259
/branches/soc-2013-dingto:57424,57487,57507,57525,57599,57670,57918-57919,57981,58091,58245,58253,58587,58772,58774-58775,58828,58835,59032
/tags/blender-2.67b-release/blender:57122
+ /branches/ge_dev:58091-58422
/branches/ge_harmony:42255,42279-42282,42286,42302,42338,42349,42616,42620,42698-42699,42739,42753,42773-42774,42832,44568,44597-44598,44793-44794
/branches/soc-2011-cucumber:37517,38166-38167,38177,38179-38180,38187,38242,38384,38387,38403-38404,38407,38968,38970,38973,39045,40845,42997-42998,43439
/branches/soc-2011-tomato:42376,42378-42379,42383,42385,42395,42397-42400,42407,42411,42418,42443-42444,42446,42467,42472,42486,42650-42652,42654-42655,42709-42710,42733-42734,42801,43872,44130,44141,44147-44149,44151-44152,44229-44230,45623-45625,46037,48089,48092,48551-48552,48679,48790,48792-48793,49076,49087,49292,49294,49466,49894,50052,50126,52854-52856,54573,58822,58989
/branches/soc-2013-depsgraph_mt:57516,57900,57939-57940,57945,57958-57961,58151,58155-58156,58169,58277-58279,58282-58283,58711,58787,58789,58796,59087,59259
/branches/soc-2013-dingto:57424,57487,57507,57525,57599,57670,57918-57919,57981,58091,58245,58253,58587,58772,58774-58775,58828,58835,59032
/tags/blender-2.67b-release/blender:57122
Modified: trunk/blender/extern/recastnavigation/recast-capi.cpp
===================================================================
--- trunk/blender/extern/recastnavigation/recast-capi.cpp 2013-08-19 10:38:27 UTC (rev 59278)
+++ trunk/blender/extern/recastnavigation/recast-capi.cpp 2013-08-19 10:40:47 UTC (rev 59279)
@@ -270,129 +270,3 @@
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;
- }
-}
-
Modified: trunk/blender/extern/recastnavigation/recast-capi.h
===================================================================
--- trunk/blender/extern/recastnavigation/recast-capi.h 2013-08-19 10:38:27 UTC (rev 59278)
+++ trunk/blender/extern/recastnavigation/recast-capi.h 2013-08-19 10:40:47 UTC (rev 59279)
@@ -127,11 +127,6 @@
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
Modified: trunk/blender/source/blender/blenkernel/intern/navmesh_conversion.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/navmesh_conversion.c 2013-08-19 10:38:27 UTC (rev 59278)
+++ trunk/blender/source/blender/blenkernel/intern/navmesh_conversion.c 2013-08-19 10:40:47 UTC (rev 59279)
@@ -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 @@
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;
Modified: trunk/blender/source/blender/blenkernel/intern/particle_system.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/particle_system.c 2013-08-19 10:38:27 UTC (rev 59278)
+++ trunk/blender/source/blender/blenkernel/intern/particle_system.c 2013-08-19 10:40:47 UTC (rev 59279)
@@ -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 @@
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 @@
/* 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);
}
}
Copied: trunk/blender/source/blender/blenlib/BLI_sort.h (from rev 59087, branches/soc-2013-depsgraph_mt/source/blender/blenlib/BLI_sort.h)
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_sort.h (rev 0)
+++ trunk/blender/source/blender/blenlib/BLI_sort.h 2013-08-19 10:40:47 UTC (rev 59279)
@@ -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.
+ *
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list