Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / blenlib / intern / list_sort_impl.h
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file \ingroup bli
18  *
19  * Common implementation of linked-list a non-recursive mergesort.
20  *
21  * Originally from Mono's eglib, adapted for portable inclusion.
22  * This file is to be directly included in C-source,
23  * with defines to control its use.
24  *
25  * This code requires a typedef named `SORT_IMPL_LINKTYPE` for the list node.
26  * It is assumed that the list type is the type of a pointer to a list
27  * node, and that the node has a field named 'next' that implements to
28  * the linked list.  No additional invariant is maintained
29  * (e.g. the `prev` pointer of a doubly-linked list node is _not_ updated).
30  * Any invariant would require a post-processing pass to update `prev`.
31  *
32  * Source file including this must define:
33  * - `SORT_IMPL_LINKTYPE`:
34  *   Struct type for sorting.
35  * - `SORT_IMPL_LINKTYPE_DATA`:
36  *   Data pointer or leave undefined to pass the link its self.
37  * - `SORT_IMPL_FUNC`:
38  *   Function name of the sort function.
39  *
40  * Optionally:
41  * - `SORT_IMPL_USE_THUNK`:
42  *   Takes an argument for the sort function (like `qsort_r`).
43  */
44
45 /* -------------------------------------------------------------------- */
46 /* Handle External Defines */
47
48 /* check we're not building directly */
49 #if !defined(SORT_IMPL_LINKTYPE) || !defined(SORT_IMPL_FUNC)
50 #  error "This file can't be compiled directly, include in another source file"
51 #endif
52
53 #define list_node SORT_IMPL_LINKTYPE
54 #define list_sort_do SORT_IMPL_FUNC
55
56 #ifdef SORT_IMPL_LINKTYPE_DATA
57 #  define SORT_ARG(n) ((n)->SORT_IMPL_LINKTYPE_DATA)
58 #else
59 #  define SORT_ARG(n) (n)
60 #endif
61
62 #ifdef SORT_IMPL_USE_THUNK
63 #  define THUNK_APPEND1(a, thunk) a, thunk
64 #  define THUNK_PREPEND2(thunk, a, b) thunk, a, b
65 #else
66 #  define THUNK_APPEND1(a, thunk) a
67 #  define THUNK_PREPEND2(thunk, a, b) a, b
68 #endif
69
70 #define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1 ## MACRO_ARG2
71 #define _CONCAT(MACRO_ARG1, MACRO_ARG2) _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
72 #define _SORT_PREFIX(id) _CONCAT(SORT_IMPL_FUNC, _##id)
73
74 /* local identifiers */
75 #define SortInfo                _SORT_PREFIX(SortInfo)
76 #define CompareFn               _SORT_PREFIX(CompareFn)
77 #define init_sort_info  _SORT_PREFIX(init_sort_info)
78 #define merge_lists             _SORT_PREFIX(merge_lists)
79 #define sweep_up                _SORT_PREFIX(sweep_up)
80 #define insert_list             _SORT_PREFIX(insert_list)
81
82 typedef int (* CompareFn)(
83 #ifdef SORT_IMPL_USE_THUNK
84         void *thunk,
85 #endif
86         const void *,
87         const void *);
88
89
90 /* -------------------------------------------------------------------- */
91 /* MIT license from original source */
92
93 /*
94  * Permission is hereby granted, free of charge, to any person obtaining
95  * a copy of this software and associated documentation files (the
96  * "Software"), to deal in the Software without restriction, including
97  * without limitation the rights to use, copy, modify, merge, publish,
98  * distribute, sublicense, and/or sell copies of the Software, and to
99  * permit persons to whom the Software is furnished to do so, subject to
100  * the following conditions:
101  *
102  * The above copyright notice and this permission notice shall be
103  * included in all copies or substantial portions of the Software.
104  *
105  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
106  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
107  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
108  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
109  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
110  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
111  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
112  *
113  * Author:
114  *   Raja R Harinath (rharinath@novell.com)
115  */
116
117 /**
118  * The maximum possible depth of the merge tree
119  * - `ceiling(log2(maximum number of list nodes))`
120  * - `ceiling(log2(maximum possible memory size/size of each list node))`
121  * - number of bits in `'size_t' - floor(log2(sizeof(list_node *)))`
122  *
123  * Also, each list in #SortInfo is at least 2 nodes long:
124  * we can reduce the depth by 1.
125  */
126 #define FLOOR_LOG2(x) \
127         (((x) >= 2) + ((x) >= 4) + ((x) >= 8) + ((x) >= 16) + ((x) >= 32) + ((x) >= 64) + ((x) >= 128))
128 #define MAX_RANKS \
129         ((sizeof(size_t) * 8) - FLOOR_LOG2(sizeof(list_node)) - 1)
130
131 struct SortInfo {
132         unsigned int min_rank, n_ranks;
133         CompareFn func;
134
135 #ifdef SORT_IMPL_USE_THUNK
136         void *thunk;
137 #endif
138
139         /**
140          * Invariant: `ranks[i] == NULL || length(ranks[i]) >= 2**(i+1)`.
141          *
142          * ~ 128 bytes on 32bit, ~ 512 bytes on 64bit */
143         list_node *ranks[MAX_RANKS];
144 };
145
146 BLI_INLINE void init_sort_info(
147         struct SortInfo *si,
148         CompareFn func
149 #ifdef SORT_IMPL_USE_THUNK
150         ,
151         void *thunk
152 #endif
153         )
154 {
155         si->min_rank = si->n_ranks = 0;
156         si->func = func;
157         /* we don't need to initialize si->ranks,
158          * since we never lookup past si->n_ranks. */
159
160 #ifdef SORT_IMPL_USE_THUNK
161         si->thunk = thunk;
162 #endif
163 }
164
165 BLI_INLINE list_node *merge_lists(
166         list_node *first, list_node *second,
167         CompareFn func
168 #ifdef SORT_IMPL_USE_THUNK
169         ,
170         void *thunk
171 #endif
172         )
173 {
174         /* merge the two lists */
175         list_node *list = NULL;
176         list_node **pos = &list;
177         while (first && second) {
178                 if (func(THUNK_PREPEND2(thunk, SORT_ARG(first), SORT_ARG(second))) > 0) {
179                         *pos = second;
180                         second = second->next;
181                 }
182                 else {
183                         *pos = first;
184                         first = first->next;
185                 }
186                 pos = &((*pos)->next);
187         }
188         *pos = first ? first : second;
189         return list;
190 }
191
192 /**
193  * Pre-condition:
194  * `upto <= si->n_ranks, list == NULL || length(list) == 1`
195  */
196 BLI_INLINE list_node *sweep_up(struct SortInfo *si, list_node *list, unsigned int upto)
197 {
198         unsigned int i;
199         for (i = si->min_rank; i < upto; i++) {
200                 list = merge_lists(si->ranks[i], list, THUNK_APPEND1(si->func, si->thunk));
201                 si->ranks[i] = NULL;
202         }
203         return list;
204 }
205
206 /**
207  * The 'ranks' array essentially captures the recursion stack of a mergesort.
208  * The merge tree is built in a bottom-up manner.  The control loop for
209  * updating the 'ranks' array is analogous to incrementing a binary integer,
210  * and the `O(n)` time for counting upto n translates to `O(n)` merges when
211  * inserting `rank-0` lists.
212  * When we plug in the sizes of the lists involved in those merges,
213  * we get the `O(n log n)` time for the sort.
214  *
215  * Inserting higher-ranked lists reduce the height of the merge tree,
216  * and also eliminate a lot of redundant comparisons when merging two lists
217  * that would've been part of the same run.
218  * Adding a `rank-i` list is analogous to incrementing a binary integer by
219  * `2**i` in one operation, thus sharing a similar speedup.
220  *
221  * When inserting higher-ranked lists, we choose to clear out the lower ranks
222  * in the interests of keeping the sort stable, but this makes analysis harder.
223  * Note that clearing the lower-ranked lists is `O(length(list))--` thus it
224  * shouldn't affect the `O(n log n)` behavior.
225  * In other words, inserting one `rank-i` list is equivalent to inserting
226  * `2**i` `rank-0` lists, thus even if we do `i` additional merges
227  * in the clearing-out (taking at most `2**i` time) we are still fine.
228  */
229
230 /**
231  * Pre-condition:
232  * `2**(rank+1) <= length(list) < 2**(rank+2)`
233  * (therefore: `length(list) >= 2`)
234  */
235 BLI_INLINE void insert_list(
236         struct SortInfo *si,
237         list_node *list,
238         unsigned int rank)
239 {
240         unsigned int i;
241
242         if (rank > si->n_ranks) {
243                 if (UNLIKELY(rank > MAX_RANKS)) {
244                         // printf("Rank '%d' should not exceed " STRINGIFY(MAX_RANKS), rank);
245                         rank = MAX_RANKS;
246                 }
247                 list = merge_lists(sweep_up(si, NULL, si->n_ranks), list, THUNK_APPEND1(si->func, si->thunk));
248                 for (i = si->n_ranks; i < rank; ++i) {
249                         si->ranks[i] = NULL;
250                 }
251         }
252         else {
253                 if (rank) {
254                         list = merge_lists(sweep_up(si, NULL, rank), list, THUNK_APPEND1(si->func, si->thunk));
255                 }
256                 for (i = rank; i < si->n_ranks && si->ranks[i]; ++i) {
257                         list = merge_lists(si->ranks[i], list, THUNK_APPEND1(si->func, si->thunk));
258                         si->ranks[i] = NULL;
259                 }
260         }
261
262         /* Will _never_ happen: so we can just devolve into quadratic ;-) */
263         if (UNLIKELY(i == MAX_RANKS)) {
264                 i--;
265         }
266
267         if (i >= si->n_ranks) {
268                 si->n_ranks = i + 1;
269         }
270
271         si->min_rank = i;
272         si->ranks[i] = list;
273 }
274
275 #undef MAX_RANKS
276 #undef FLOOR_LOG2
277
278 /**
279  * Main sort function.
280  */
281 BLI_INLINE list_node *list_sort_do(
282         list_node *list,
283         CompareFn func
284 #ifdef SORT_IMPL_USE_THUNK
285         ,
286         void *thunk
287 #endif
288         )
289 {
290         struct SortInfo si;
291
292         init_sort_info(
293                 &si,
294                 func
295 #ifdef SORT_IMPL_USE_THUNK
296                 ,
297                 thunk
298 #endif
299                 );
300
301         while (list && list->next) {
302                 list_node *next = list->next;
303                 list_node *tail = next->next;
304
305                 if (func(THUNK_PREPEND2(thunk, SORT_ARG(list), SORT_ARG(next))) > 0) {
306                         next->next = list;
307                         next = list;
308                         list = list->next;
309                 }
310                 next->next = NULL;
311
312                 insert_list(&si, list, 0);
313
314                 list = tail;
315         }
316
317         return sweep_up(&si, list, si.n_ranks);
318 }
319
320 #undef _CONCAT_AUX
321 #undef _CONCAT
322 #undef _SORT_PREFIX
323
324 #undef SortInfo
325 #undef CompareFn
326 #undef init_sort_info
327 #undef merge_lists
328 #undef sweep_up
329 #undef insert_list
330
331 #undef list_node
332 #undef list_sort_do
333
334 #undef THUNK_APPEND1
335 #undef THUNK_PREPEND2
336 #undef SORT_ARG