list_sort_impl.h File Reference

#include "BLI_compiler_compat.h"
#include "BLI_utildefines.h"

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)
#define	BLI_LIST_THUNK_APPEND1(a, thunk)
#define	BLI_LIST_THUNK_PREPEND2(thunk, a, b)
#define	_BLI_LIST_SORT_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
#define	_BLI_LIST_SORT_CONCAT(MACRO_ARG1, MACRO_ARG2)
#define	_BLI_LIST_SORT_PREFIX(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)
#define	MAX_RANKS   ((sizeof(size_t) * 8) - FLOOR_LOG2(sizeof(list_node)) - 1)

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

Functions
void	init_sort_info (struct SortInfo *si, CompareFn func)
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)

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:

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

Macro Definition Documentation

_BLI_LIST_SORT_CONCAT

#define _BLI_LIST_SORT_CONCAT	(		MACRO_ARG1,
			MACRO_ARG2 )

Value:

_BLI_LIST_SORT_CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)

Definition at line 63 of file list_sort_impl.h.

_BLI_LIST_SORT_CONCAT_AUX

#define _BLI_LIST_SORT_CONCAT_AUX	(		MACRO_ARG1,
			MACRO_ARG2 )

Value:

MACRO_ARG1##MACRO_ARG2

Definition at line 62 of file list_sort_impl.h.

_BLI_LIST_SORT_PREFIX

#define _BLI_LIST_SORT_PREFIX

(

id

)

Value:

_BLI_LIST_SORT_CONCAT(SORT_IMPL_FUNC, _##id)

Definition at line 65 of file list_sort_impl.h.

BLI_LIST_THUNK_APPEND1

#define BLI_LIST_THUNK_APPEND1	(		a,
			thunk )

Value:

a

Definition at line 58 of file list_sort_impl.h.

Referenced by insert_list(), and sweep_up().

BLI_LIST_THUNK_PREPEND2

#define BLI_LIST_THUNK_PREPEND2	(		thunk,
			a,
			b )

Value:

a, b

Definition at line 59 of file list_sort_impl.h.

Referenced by list_sort_do(), and merge_lists().

CompareFn

#define CompareFn   _BLI_LIST_SORT_PREFIX(CompareFn)

Definition at line 69 of file list_sort_impl.h.

Referenced by init_sort_info(), list_sort_do(), and merge_lists().

FLOOR_LOG2

#define FLOOR_LOG2

(

x

)

Value:

(((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 118 of file list_sort_impl.h.

init_sort_info

#define init_sort_info   _BLI_LIST_SORT_PREFIX(init_sort_info)

Definition at line 70 of file list_sort_impl.h.

Referenced by list_sort_do().

insert_list

#define insert_list   _BLI_LIST_SORT_PREFIX(insert_list)

Definition at line 73 of file list_sort_impl.h.

Referenced by list_sort_do().

list_node

#define list_node   SORT_IMPL_LINKTYPE

Definition at line 45 of file list_sort_impl.h.

Referenced by insert_list(), list_sort_do(), merge_lists(), and sweep_up().

list_sort_do

#define list_sort_do   SORT_IMPL_FUNC

Definition at line 46 of file list_sort_impl.h.

MAX_RANKS

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

Definition at line 120 of file list_sort_impl.h.

Referenced by insert_list().

merge_lists

#define merge_lists   _BLI_LIST_SORT_PREFIX(merge_lists)

Definition at line 71 of file list_sort_impl.h.

Referenced by insert_list(), and sweep_up().

SORT_ARG

#define SORT_ARG

(

n

)

Value:

(n)

Definition at line 51 of file list_sort_impl.h.

Referenced by list_sort_do(), and merge_lists().

SortInfo

#define SortInfo   _BLI_LIST_SORT_PREFIX(SortInfo)

Definition at line 68 of file list_sort_impl.h.

Referenced by init_sort_info(), insert_list(), list_sort_do(), and sweep_up().

sweep_up

#define sweep_up   _BLI_LIST_SORT_PREFIX(sweep_up)

Definition at line 72 of file list_sort_impl.h.

Referenced by insert_list(), and list_sort_do().

Typedef Documentation

CompareFn

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

Definition at line 75 of file list_sort_impl.h.

Function Documentation

init_sort_info()

void init_sort_info ( struct SortInfo * si, CompareFn func )

inline

Definition at line 135 of file list_sort_impl.h.

References CompareFn, SortInfo::func, SortInfo::min_rank, SortInfo::n_ranks, SORT_IMPL_USE_THUNK, and SortInfo.

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 223 of file list_sort_impl.h.

References BLI_INLINE, BLI_LIST_THUNK_APPEND1, SortInfo::func, i, list_node, MAX_RANKS, merge_lists, SortInfo::min_rank, SortInfo::n_ranks, SortInfo::ranks, SortInfo, sweep_up, and UNLIKELY.

list_sort_do()

BLI_INLINE list_node * list_sort_do	(	list_node *	list,
		CompareFn	func )

Main sort function.

Definition at line 268 of file list_sort_impl.h.

References BLI_INLINE, BLI_LIST_THUNK_PREPEND2, CompareFn, init_sort_info, insert_list, list_node, SortInfo::n_ranks, next, SORT_ARG, SORT_IMPL_USE_THUNK, SortInfo, and sweep_up.

merge_lists()

list_node * merge_lists ( list_node * first, list_node * second, CompareFn func )

inline

Definition at line 153 of file list_sort_impl.h.

References BLI_LIST_THUNK_PREPEND2, CompareFn, list_node, pos, SORT_ARG, and SORT_IMPL_USE_THUNK.

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 184 of file list_sort_impl.h.

References BLI_INLINE, BLI_LIST_THUNK_APPEND1, SortInfo::func, i, list_node, merge_lists, SortInfo::min_rank, SortInfo::ranks, and SortInfo.