diff options
| -rw-r--r-- | source/blender/blenlib/BLI_linklist.h | 2 | ||||
| -rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/BLI_linklist.c | 39 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/list_sort_impl.h | 341 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/listbase.c | 69 |
5 files changed, 420 insertions, 32 deletions
diff --git a/source/blender/blenlib/BLI_linklist.h b/source/blender/blenlib/BLI_linklist.h index 8dbf7b4a908..d0dc7fc7b2f 100644 --- a/source/blender/blenlib/BLI_linklist.h +++ b/source/blender/blenlib/BLI_linklist.h @@ -74,6 +74,8 @@ void BLI_linklist_free(struct LinkNode *list, LinkNodeFreeFP freefunc); void BLI_linklist_freeN(struct LinkNode *list); void BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool); void BLI_linklist_apply(struct LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata); +struct LinkNode *BLI_linklist_sort(LinkNode *list, int (*cmp)(const void *, const void *)); +struct LinkNode *BLI_linklist_sort_r(LinkNode *list, int (*cmp)(void *, const void *, const void *), void *thunk); #define BLI_linklist_prepend_alloca(listp, ptr) \ BLI_linklist_prepend_nlink(listp, ptr, alloca(sizeof(LinkNode))) diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index e39202d35fd..cc6e934d619 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -72,6 +72,7 @@ set(SRC intern/hash_mm2a.c intern/jitter.c intern/lasso.c + intern/list_sort_impl.h intern/listbase.c intern/math_base.c intern/math_base_inline.c 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; +} diff --git a/source/blender/blenlib/intern/list_sort_impl.h b/source/blender/blenlib/intern/list_sort_impl.h new file mode 100644 index 00000000000..249ed470d6e --- /dev/null +++ b/source/blender/blenlib/intern/list_sort_impl.h @@ -0,0 +1,341 @@ +/* + * ***** 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. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/list_sort_impl.h + * \ingroup bli + * + * Common implementation of linked-list a non-recursive mergesort. + * + * Originally from Mono's eglib, adapted for portable inclusion. + * This file is to be directly included in C-source, + * with defines to control its use. + * + * This code requires a typedef named `SORT_IMPL_LINKTYPE` for the list node. + * It is assumed that the list type is the type of a pointer to a list + * node, and that the node has a field named 'next' that implements to + * the linked list. No additional invariant is maintained + * (e.g. the `prev` pointer of a doubly-linked list node is _not_ updated). + * Any invariant would require a post-processing pass to update `prev`. + * + * Source file including this must define: + * - `SORT_IMPL_LINKTYPE`: + * Struct type for sorting. + * - `SORT_IMPL_LINKTYPE_DATA`: + * Data pointer or leave undefined to pass the link its self. + * - `SORT_IMPL_FUNC`: + * Function name of the sort function. + * + * Optionally: + * - `SORT_IMPL_USE_THUNK`: + * Takes an argument for the sort function (like `qsort_r`). + */ + +/* -------------------------------------------------------------------- */ +/* Handle External Defines */ + +/* check we're not building directly */ +#if !defined(SORT_IMPL_LINKTYPE) || !defined(SORT_IMPL_FUNC) +# error "This file can't be compiled directly, include in another source file" +#endif + +#define list_node SORT_IMPL_LINKTYPE +#define list_sort_do SORT_IMPL_FUNC + +#ifdef SORT_IMPL_LINKTYPE_DATA +# define SORT_ARG(n) ((n)->SORT_IMPL_LINKTYPE_DATA) +#else +# define SORT_ARG(n) (n) +#endif + +#ifdef SORT_IMPL_USE_THUNK +# define THUNK_APPEND1(a, thunk) a, thunk +# define THUNK_PREPEND2(thunk, a, b) thunk, a, b +#else +# define THUNK_APPEND1(a, thunk) a +# define THUNK_PREPEND2(thunk, a, b) a, b +#endif + +#define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1 ## MACRO_ARG2 +#define _CONCAT(MACRO_ARG1, MACRO_ARG2) _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) +#define _SORT_PREFIX(id) _CONCAT(SORT_IMPL_FUNC, _##id) + +/* local identifiers */ +#define SortInfo _SORT_PREFIX(SortInfo) +#define CompareFn _SORT_PREFIX(CompareFn) +#define init_sort_info _SORT_PREFIX(init_sort_info) +#define merge_lists _SORT_PREFIX(merge_lists) +#define sweep_up _SORT_PREFIX(sweep_up) +#define insert_list _SORT_PREFIX(insert_list) + +typedef int (* CompareFn)( +#ifdef SORT_IMPL_USE_THUNK + void *thunk, +#endif + const void *, + const void *); + + +/* -------------------------------------------------------------------- */ +/* MIT license from original source */ + +/* + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * + * Author: + * Raja R Harinath (rharinath@novell.com) + */ + +/** + * The maximum possible depth of the merge tree + * - `ceiling(log2(maximum number of list nodes))` + * - `ceiling(log2(maximum possible memory size/size of each list node))` + * - number of bits in `'size_t' - floor(log2(sizeof(list_node *)))` + * + * Also, each list in #SortInfo is at least 2 nodes long: + * we can reduce the depth by 1. + */ +#define FLOOR_LOG2(x) \ + (((x) >= 2) + ((x) >= 4) + ((x) >= 8) + ((x) >= 16) + ((x) >= 32) + ((x) >= 64) + ((x) >= 128)) +#define MAX_RANKS \ + ((sizeof(size_t) * 8) - FLOOR_LOG2(sizeof(list_node)) - 1) + +struct SortInfo { + unsigned int min_rank, n_ranks; + CompareFn func; + +#ifdef SORT_IMPL_USE_THUNK + void *thunk; +#endif + + /** + * Invariant: `ranks[i] == NULL || length(ranks[i]) >= 2**(i+1)`. + * + * ~ 128 bytes on 32bit, ~ 512 bytes on 64bit */ + list_node *ranks[MAX_RANKS]; +}; + +BLI_INLINE void init_sort_info( + struct SortInfo *si, + CompareFn func +#ifdef SORT_IMPL_USE_THUNK + , + void *thunk +#endif + ) +{ + si->min_rank = si->n_ranks = 0; + si->func = func; + /* we don't need to initialize si->ranks, + * since we never lookup past si->n_ranks. */ + +#ifdef SORT_IMPL_USE_THUNK + si->thunk = thunk; +#endif +} + +BLI_INLINE list_node *merge_lists( + list_node *first, list_node *second, + CompareFn func +#ifdef SORT_IMPL_USE_THUNK + , + void *thunk +#endif + ) +{ + /* merge the two lists */ + list_node *list = NULL; + list_node **pos = &list; + while (first && second) { + if (func(THUNK_PREPEND2(thunk, SORT_ARG(first), SORT_ARG(second))) > 0) { + *pos = second; + second = second->next; + } + else { + *pos = first; + first = first->next; + } + pos = &((*pos)->next); + } + *pos = first ? first : second; + return list; +} + +/** + * Pre-condition: + * `upto <= si->n_ranks, list == NULL || length(list) == 1` + */ +BLI_INLINE list_node *sweep_up(struct SortInfo *si, list_node *list, unsigned int upto) +{ + unsigned int i; + for (i = si->min_rank; i < upto; i++) { + list = merge_lists(si->ranks[i], list, THUNK_APPEND1(si->func, si->thunk)); + si->ranks[i] = NULL; + } + return list; +} + +/** + * The 'ranks' array essentially captures the recursion stack of a mergesort. + * The merge tree is built in a bottom-up manner. The control loop for + * updating the 'ranks' array is analogous to incrementing a binary integer, + * and the `O(n)` time for counting upto n translates to `O(n)` merges when + * inserting `rank-0` lists. + * When we plug in the sizes of the lists involved in those merges, + * we get the `O(n log n)` time for the sort. + * + * Inserting higher-ranked lists reduce the height of the merge tree, + * and also eliminate a lot of redundant comparisons when merging two lists + * that would've been part of the same run. + * Adding a `rank-i` list is analogous to incrementing a binary integer by + * `2**i` in one operation, thus sharing a similar speedup. + * + * When inserting higher-ranked lists, we choose to clear out the lower ranks + * in the interests of keeping the sort stable, but this makes analysis harder. + * Note that clearing the lower-ranked lists is `O(length(list))--` thus it + * shouldn't affect the `O(n log n)` behaviour. + * In other words, inserting one `rank-i` list is equivalent to inserting + * `2**i` `rank-0` lists, thus even if we do `i` additional merges + * in the clearing-out (taking at most `2**i` time) we are still fine. + */ + +/** + * Pre-condition: + * `2**(rank+1) <= length(list) < 2**(rank+2)` + * (therefore: `length(list) >= 2`) + */ +BLI_INLINE void insert_list( + struct SortInfo *si, + list_node *list, + unsigned int rank) +{ + unsigned int i; + + if (rank > si->n_ranks) { + if (UNLIKELY(rank > MAX_RANKS)) { + // printf("Rank '%d' should not exceed " STRINGIFY(MAX_RANKS), rank); + rank = MAX_RANKS; + } + list = merge_lists(sweep_up(si, NULL, si->n_ranks), list, THUNK_APPEND1(si->func, si->thunk)); + for (i = si->n_ranks; i < rank; ++i) { + si->ranks[i] = NULL; + } + } + else { + if (rank) { + list = merge_lists(sweep_up(si, NULL, rank), list, THUNK_APPEND1(si->func, si->thunk)); + } + for (i = rank; i < si->n_ranks && si->ranks[i]; ++i) { + list = merge_lists(si->ranks[i], list, THUNK_APPEND1(si->func, si->thunk)); + si->ranks[i] = NULL; + } + } + + /* Will _never_ happen: so we can just devolve into quadratic ;-) */ + if (UNLIKELY(i == MAX_RANKS)) { + i--; + } + + if (i >= si->n_ranks) { + si->n_ranks = i + 1; + } + + si->min_rank = i; + si->ranks[i] = list; +} + +#undef MAX_RANKS +#undef FLOOR_LOG2 + +/** + * Main sort function. + */ +BLI_INLINE list_node *list_sort_do( + list_node *list, + CompareFn func +#ifdef SORT_IMPL_USE_THUNK + , + void *thunk +#endif + ) +{ + struct SortInfo si; + + init_sort_info( + &si, + func +#ifdef SORT_IMPL_USE_THUNK + , + thunk +#endif + ); + + while (list && list->next) { + list_node *next = list->next; + list_node *tail = next->next; + + if (func(THUNK_PREPEND2(thunk, SORT_ARG(list), SORT_ARG(next))) > 0) { + next->next = list; + next = list; + list = list->next; + } + next->next = NULL; + + insert_list(&si, list, 0); + + list = tail; + } + + return sweep_up(&si, list, si.n_ranks); +} + +#undef _CONCAT_AUX +#undef _CONCAT +#undef _SORT_PREFIX + +#undef SortInfo +#undef CompareFn +#undef init_sort_info +#undef merge_lists +#undef sweep_up +#undef insert_list + +#undef list_node +#undef list_sort_do + +#undef THUNK_APPEND1 +#undef THUNK_PREPEND2 +#undef SORT_ARG 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); } } |