Blender  V3.3
Classes | Macros | Typedefs | Functions
list_sort_impl.h File Reference

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_nodemerge_lists (list_node *first, list_node *second, CompareFn func)
 
BLI_INLINE list_nodesweep_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_nodelist_sort_do (list_node *list, CompareFn func)
 

Detailed Description

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:

Optionally:

Definition in file list_sort_impl.h.

Macro Definition Documentation

◆ _CONCAT

#define _CONCAT (   MACRO_ARG1,
  MACRO_ARG2 
)    _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)

Definition at line 58 of file list_sort_impl.h.

◆ _CONCAT_AUX

#define _CONCAT_AUX (   MACRO_ARG1,
  MACRO_ARG2 
)    MACRO_ARG1##MACRO_ARG2

Definition at line 57 of file list_sort_impl.h.

◆ _SORT_PREFIX

#define _SORT_PREFIX (   id)    _CONCAT(SORT_IMPL_FUNC, _##id)

Definition at line 59 of file list_sort_impl.h.

◆ CompareFn

#define CompareFn   _SORT_PREFIX(CompareFn)

Definition at line 63 of file list_sort_impl.h.

◆ FLOOR_LOG2

#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))
  • 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.

Definition at line 112 of file list_sort_impl.h.

◆ init_sort_info

#define init_sort_info   _SORT_PREFIX(init_sort_info)

Definition at line 64 of file list_sort_impl.h.

◆ insert_list

#define insert_list   _SORT_PREFIX(insert_list)

Definition at line 67 of file list_sort_impl.h.

◆ list_node

#define list_node   SORT_IMPL_LINKTYPE

Definition at line 40 of file list_sort_impl.h.

◆ list_sort_do

#define list_sort_do   SORT_IMPL_FUNC

Definition at line 41 of file list_sort_impl.h.

◆ MAX_RANKS

#define MAX_RANKS   ((sizeof(size_t) * 8) - FLOOR_LOG2(sizeof(list_node)) - 1)

Definition at line 114 of file list_sort_impl.h.

◆ merge_lists

#define merge_lists   _SORT_PREFIX(merge_lists)

Definition at line 65 of file list_sort_impl.h.

◆ SORT_ARG

#define SORT_ARG (   n)    (n)

Definition at line 46 of file list_sort_impl.h.

◆ SortInfo

Definition at line 62 of file list_sort_impl.h.

◆ sweep_up

#define sweep_up   _SORT_PREFIX(sweep_up)

Definition at line 66 of file list_sort_impl.h.

◆ THUNK_APPEND1

#define THUNK_APPEND1 (   a,
  thunk 
)    a

Definition at line 53 of file list_sort_impl.h.

◆ THUNK_PREPEND2

#define THUNK_PREPEND2 (   thunk,
  a,
 
)    a, b

Definition at line 54 of file list_sort_impl.h.

Typedef Documentation

◆ CompareFn

typedef int(* CompareFn) (const void *, const void *)

Definition at line 69 of file list_sort_impl.h.

Function Documentation

◆ init_sort_info()

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.

◆ insert_list()

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.

◆ list_sort_do()

BLI_INLINE list_node* list_sort_do ( list_node list,
CompareFn  func 
)

◆ merge_lists()

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.

◆ sweep_up()

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.