Blender
V3.3
|
Go to the source code of this file.
Classes | |
struct | SortInfo |
Macros | |
#define | list_node SORT_IMPL_LINKTYPE |
#define | list_sort_do SORT_IMPL_FUNC |
#define | SORT_ARG(n) (n) |
#define | THUNK_APPEND1(a, thunk) a |
#define | THUNK_PREPEND2(thunk, a, b) a, b |
#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) |
#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) |
#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) |
Typedefs | |
typedef int(* | CompareFn) (const void *, const void *) |
Functions | |
BLI_INLINE void | init_sort_info (struct SortInfo *si, CompareFn func) |
BLI_INLINE list_node * | merge_lists (list_node *first, list_node *second, CompareFn func) |
BLI_INLINE list_node * | sweep_up (struct SortInfo *si, list_node *list, unsigned int upto) |
BLI_INLINE void | insert_list (struct SortInfo *si, list_node *list, unsigned int rank) |
BLI_INLINE list_node * | list_sort_do (list_node *list, CompareFn func) |
Common implementation of linked-list a non-recursive merge-sort.
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 itself.SORT_IMPL_FUNC
: Function name of the sort function.Optionally:
SORT_IMPL_USE_THUNK
: Takes an argument for the sort function (like qsort_r
). Definition in file list_sort_impl.h.
#define _CONCAT | ( | MACRO_ARG1, | |
MACRO_ARG2 | |||
) | _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) |
Definition at line 58 of file list_sort_impl.h.
#define _CONCAT_AUX | ( | MACRO_ARG1, | |
MACRO_ARG2 | |||
) | MACRO_ARG1##MACRO_ARG2 |
Definition at line 57 of file list_sort_impl.h.
#define _SORT_PREFIX | ( | id | ) | _CONCAT(SORT_IMPL_FUNC, _##id) |
Definition at line 59 of file list_sort_impl.h.
#define CompareFn _SORT_PREFIX(CompareFn) |
Definition at line 63 of file list_sort_impl.h.
#define FLOOR_LOG2 | ( | x | ) | (((x) >= 2) + ((x) >= 4) + ((x) >= 8) + ((x) >= 16) + ((x) >= 32) + ((x) >= 64) + ((x) >= 128)) |
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))
Also, each list in SortInfo is at least 2 nodes long: we can reduce the depth by 1.
Definition at line 112 of file list_sort_impl.h.
#define init_sort_info _SORT_PREFIX(init_sort_info) |
Definition at line 64 of file list_sort_impl.h.
#define insert_list _SORT_PREFIX(insert_list) |
Definition at line 67 of file list_sort_impl.h.
#define list_node SORT_IMPL_LINKTYPE |
Definition at line 40 of file list_sort_impl.h.
#define list_sort_do SORT_IMPL_FUNC |
Definition at line 41 of file list_sort_impl.h.
#define MAX_RANKS ((sizeof(size_t) * 8) - FLOOR_LOG2(sizeof(list_node)) - 1) |
Definition at line 114 of file list_sort_impl.h.
#define merge_lists _SORT_PREFIX(merge_lists) |
Definition at line 65 of file list_sort_impl.h.
#define SORT_ARG | ( | n | ) | (n) |
Definition at line 46 of file list_sort_impl.h.
Definition at line 62 of file list_sort_impl.h.
#define sweep_up _SORT_PREFIX(sweep_up) |
Definition at line 66 of file list_sort_impl.h.
#define THUNK_APPEND1 | ( | a, | |
thunk | |||
) | a |
Definition at line 53 of file list_sort_impl.h.
#define THUNK_PREPEND2 | ( | thunk, | |
a, | |||
b | |||
) | a, b |
Definition at line 54 of file list_sort_impl.h.
Definition at line 69 of file list_sort_impl.h.
BLI_INLINE void init_sort_info | ( | struct SortInfo * | si, |
CompareFn | func | ||
) |
Definition at line 131 of file list_sort_impl.h.
References SortInfo::func, SortInfo::min_rank, and SortInfo::n_ranks.
BLI_INLINE void insert_list | ( | struct SortInfo * | si, |
list_node * | list, | ||
unsigned int | rank | ||
) |
The 'ranks' array essentially captures the recursion stack of a merge-sort. 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)
behavior. 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
)
Definition at line 219 of file list_sort_impl.h.
References SortInfo::func, MAX_RANKS, merge_lists, SortInfo::min_rank, SortInfo::n_ranks, NULL, SortInfo::ranks, sweep_up, THUNK_APPEND1, and UNLIKELY.
BLI_INLINE list_node* list_sort_do | ( | list_node * | list, |
CompareFn | func | ||
) |
Main sort function.
Definition at line 262 of file list_sort_impl.h.
References SortInfo::func, init_sort_info, insert_list, list_node, SortInfo::n_ranks, next, NULL, SORT_ARG, SORT_IMPL_USE_THUNK, sweep_up, and THUNK_PREPEND2.
BLI_INLINE list_node* merge_lists | ( | list_node * | first, |
list_node * | second, | ||
CompareFn | func | ||
) |
Definition at line 149 of file list_sort_impl.h.
References list_node, NULL, pos, SORT_ARG, and THUNK_PREPEND2.
BLI_INLINE list_node* sweep_up | ( | struct SortInfo * | si, |
list_node * | list, | ||
unsigned int | upto | ||
) |
Pre-condition: upto <= si->n_ranks, list == NULL || length(list) == 1
Definition at line 180 of file list_sort_impl.h.
References SortInfo::func, merge_lists, SortInfo::min_rank, NULL, SortInfo::ranks, and THUNK_APPEND1.