diff options
author | Campbell Barton <ideasman42@gmail.com> | 2015-06-11 08:13:06 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2015-06-11 14:54:06 +0300 |
commit | 867cd2048e0e8dd9f0552ac996bb1d352136b9a0 (patch) | |
tree | 81dc9e65a3d1495779970eded4ed22d99c6aafbe /source/blender/blenlib/intern/BLI_linklist.c | |
parent | b8b57d2da99acca0d68035315b159174a8570271 (diff) |
Replace linked-list insert-sort with merge-sort
Original code from eglib, modified for reuse with multiple linked-list implementations.
Adds sort functions: BLI_linklist_sort, BLI_linklist_sort_r
Diffstat (limited to 'source/blender/blenlib/intern/BLI_linklist.c')
-rw-r--r-- | source/blender/blenlib/intern/BLI_linklist.c | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/source/blender/blenlib/intern/BLI_linklist.c b/source/blender/blenlib/intern/BLI_linklist.c index f0efe49cfdb..394f6e3db8a 100644 --- a/source/blender/blenlib/intern/BLI_linklist.c +++ b/source/blender/blenlib/intern/BLI_linklist.c @@ -38,6 +38,8 @@ #include "BLI_memarena.h" #include "BLI_mempool.h" +#include "BLI_strict_flags.h" + int BLI_linklist_length(LinkNode *list) { int len; @@ -308,3 +310,40 @@ void BLI_linklist_apply(LinkNode *list, LinkNodeApplyFP applyfunc, void *userdat for (; list; list = list->next) applyfunc(list->link, userdata); } + +/* -------------------------------------------------------------------- */ +/* Sort */ +#define SORT_IMPL_LINKTYPE LinkNode +#define SORT_IMPL_LINKTYPE_DATA link + +/* regular call */ +#define SORT_IMPL_FUNC linklist_sort_fn +#include "list_sort_impl.h" +#undef SORT_IMPL_FUNC + +/* reentrant call */ +#define SORT_IMPL_USE_THUNK +#define SORT_IMPL_FUNC linklist_sort_fn_r +#include "list_sort_impl.h" +#undef SORT_IMPL_FUNC +#undef SORT_IMPL_USE_THUNK + +#undef SORT_IMPL_LINKTYPE +#undef SORT_IMPL_LINKTYPE_DATA + + +LinkNode *BLI_linklist_sort(LinkNode *list, int (*cmp)(const void *, const void *)) +{ + if (list && list->next) { + list = linklist_sort_fn(list, cmp); + } + return list; +} + +LinkNode *BLI_linklist_sort_r(LinkNode *list, int (*cmp)(void *, const void *, const void *), void *thunk) +{ + if (list && list->next) { + list = linklist_sort_fn_r(list, cmp, thunk); + } + return list; +} |