From 867cd2048e0e8dd9f0552ac996bb1d352136b9a0 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Thu, 11 Jun 2015 15:13:06 +1000 Subject: 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 --- source/blender/blenlib/intern/listbase.c | 69 +++++++++++++++++--------------- 1 file changed, 37 insertions(+), 32 deletions(-) (limited to 'source/blender/blenlib/intern/listbase.c') diff --git a/source/blender/blenlib/intern/listbase.c b/source/blender/blenlib/intern/listbase.c index 0bc63550850..ebee2c7941c 100644 --- a/source/blender/blenlib/intern/listbase.c +++ b/source/blender/blenlib/intern/listbase.c @@ -42,6 +42,8 @@ #include "BLI_listbase.h" +#include "BLI_strict_flags.h" + /* implementation */ /** @@ -205,6 +207,35 @@ void BLI_freelinkN(ListBase *listbase, void *vlink) MEM_freeN(link); } +/** + * Assigns all #Link.prev pointers from #Link.next + */ +static void listbase_double_from_single(Link *iter, ListBase *listbase) +{ + Link *prev = NULL; + listbase->first = iter; + do { + iter->prev = prev; + prev = iter; + } while ((iter = iter->next)); + listbase->last = prev; +} + +#define SORT_IMPL_LINKTYPE Link + +/* regular call */ +#define SORT_IMPL_FUNC listbase_sort_fn +#include "list_sort_impl.h" +#undef SORT_IMPL_FUNC + +/* reentrant call */ +#define SORT_IMPL_USE_THUNK +#define SORT_IMPL_FUNC listbase_sort_fn_r +#include "list_sort_impl.h" +#undef SORT_IMPL_FUNC +#undef SORT_IMPL_USE_THUNK + +#undef SORT_IMPL_LINKTYPE /** * Sorts the elements of listbase into the order defined by cmp @@ -213,45 +244,19 @@ void BLI_freelinkN(ListBase *listbase, void *vlink) */ void BLI_listbase_sort(ListBase *listbase, int (*cmp)(const void *, const void *)) { - Link *current = NULL; - Link *previous = NULL; - Link *next = NULL; - if (listbase->first != listbase->last) { - for (previous = listbase->first, current = previous->next; current; current = next) { - next = current->next; - previous = current->prev; - - BLI_remlink(listbase, current); - - while (previous && cmp(previous, current) == 1) { - previous = previous->prev; - } - - BLI_insertlinkafter(listbase, previous, current); - } + Link *head = listbase->first; + head = listbase_sort_fn(head, cmp); + listbase_double_from_single(head, listbase); } } void BLI_listbase_sort_r(ListBase *listbase, int (*cmp)(void *, const void *, const void *), void *thunk) { - Link *current = NULL; - Link *previous = NULL; - Link *next = NULL; - if (listbase->first != listbase->last) { - for (previous = listbase->first, current = previous->next; current; current = next) { - next = current->next; - previous = current->prev; - - BLI_remlink(listbase, current); - - while (previous && cmp(thunk, previous, current) == 1) { - previous = previous->prev; - } - - BLI_insertlinkafter(listbase, previous, current); - } + Link *head = listbase->first; + head = listbase_sort_fn_r(head, cmp, thunk); + listbase_double_from_single(head, listbase); } } -- cgit v1.2.3