 |
Blender V4.3
|
|
Blender V4.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 | BLI_LIST_THUNK_APPEND1(a, thunk) a |
| #define | BLI_LIST_THUNK_PREPEND2(thunk, a, b) a, b |
| #define | _BLI_LIST_SORT_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1##MACRO_ARG2 |
| #define | _BLI_LIST_SORT_CONCAT(MACRO_ARG1, MACRO_ARG2) _BLI_LIST_SORT_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) |
| #define | _BLI_LIST_SORT_PREFIX(id) _BLI_LIST_SORT_CONCAT(SORT_IMPL_FUNC, _##id) |
| #define | SortInfo _BLI_LIST_SORT_PREFIX(SortInfo) |
| #define | CompareFn _BLI_LIST_SORT_PREFIX(CompareFn) |
| #define | init_sort_info _BLI_LIST_SORT_PREFIX(init_sort_info) |
| #define | merge_lists _BLI_LIST_SORT_PREFIX(merge_lists) |
| #define | sweep_up _BLI_LIST_SORT_PREFIX(sweep_up) |
| #define | insert_list _BLI_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 _BLI_LIST_SORT_CONCAT | ( | MACRO_ARG1, | |
| MACRO_ARG2 ) _BLI_LIST_SORT_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) |
Definition at line 60 of file list_sort_impl.h.
| #define _BLI_LIST_SORT_CONCAT_AUX | ( | MACRO_ARG1, | |
| MACRO_ARG2 ) MACRO_ARG1##MACRO_ARG2 |
Definition at line 59 of file list_sort_impl.h.
| #define _BLI_LIST_SORT_PREFIX | ( | id | ) | _BLI_LIST_SORT_CONCAT(SORT_IMPL_FUNC, _##id) |
Definition at line 62 of file list_sort_impl.h.
| #define BLI_LIST_THUNK_APPEND1 | ( | a, | |
| thunk ) a |
Definition at line 55 of file list_sort_impl.h.
Referenced by insert_list(), and sweep_up().
Definition at line 56 of file list_sort_impl.h.
Referenced by list_sort_do(), and merge_lists().
| #define CompareFn _BLI_LIST_SORT_PREFIX(CompareFn) |
Definition at line 66 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 115 of file list_sort_impl.h.
| #define init_sort_info _BLI_LIST_SORT_PREFIX(init_sort_info) |
Definition at line 67 of file list_sort_impl.h.
Referenced by list_sort_do().
| #define insert_list _BLI_LIST_SORT_PREFIX(insert_list) |
Definition at line 70 of file list_sort_impl.h.
Referenced by list_sort_do().
| #define list_node SORT_IMPL_LINKTYPE |
Definition at line 42 of file list_sort_impl.h.
Referenced by list_sort_do(), and merge_lists().
| #define list_sort_do SORT_IMPL_FUNC |
Definition at line 43 of file list_sort_impl.h.
| #define MAX_RANKS ((sizeof(size_t) * 8) - FLOOR_LOG2(sizeof(list_node)) - 1) |
Definition at line 117 of file list_sort_impl.h.
Referenced by insert_list().
| #define merge_lists _BLI_LIST_SORT_PREFIX(merge_lists) |
Definition at line 68 of file list_sort_impl.h.
Referenced by insert_list(), and sweep_up().
| #define SORT_ARG | ( | n | ) | (n) |
Definition at line 48 of file list_sort_impl.h.
Referenced by list_sort_do(), and merge_lists().
| #define SortInfo _BLI_LIST_SORT_PREFIX(SortInfo) |
Definition at line 65 of file list_sort_impl.h.
| #define sweep_up _BLI_LIST_SORT_PREFIX(sweep_up) |
Definition at line 69 of file list_sort_impl.h.
Referenced by insert_list(), and list_sort_do().
| typedef int(* CompareFn) (const void *, const void *) |
Definition at line 72 of file list_sort_impl.h.
| BLI_INLINE void init_sort_info | ( | struct SortInfo * | si, |
| CompareFn | func ) |
Definition at line 132 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 220 of file list_sort_impl.h.
References BLI_LIST_THUNK_APPEND1, SortInfo::func, MAX_RANKS, merge_lists, SortInfo::min_rank, SortInfo::n_ranks, NULL, SortInfo::ranks, sweep_up, and UNLIKELY.
| BLI_INLINE list_node * list_sort_do | ( | list_node * | list, |
| CompareFn | func ) |
Main sort function.
Definition at line 265 of file list_sort_impl.h.
References BLI_LIST_THUNK_PREPEND2, init_sort_info, insert_list, list_node, SortInfo::n_ranks, next, NULL, SORT_ARG, SORT_IMPL_USE_THUNK, and sweep_up.
| BLI_INLINE list_node * merge_lists | ( | list_node * | first, |
| list_node * | second, | ||
| CompareFn | func ) |
Definition at line 150 of file list_sort_impl.h.
References BLI_LIST_THUNK_PREPEND2, list_node, NULL, pos, and SORT_ARG.
| 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 181 of file list_sort_impl.h.
References BLI_LIST_THUNK_APPEND1, SortInfo::func, merge_lists, SortInfo::min_rank, NULL, and SortInfo::ranks.