Blender  V3.3
list_sort_impl.h
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
32 /* -------------------------------------------------------------------- */
33 /* Handle External Defines */
34 
35 /* check we're not building directly */
36 #if !defined(SORT_IMPL_LINKTYPE) || !defined(SORT_IMPL_FUNC)
37 # error "This file can't be compiled directly, include in another source file"
38 #endif
39 
40 #define list_node SORT_IMPL_LINKTYPE
41 #define list_sort_do SORT_IMPL_FUNC
42 
43 #ifdef SORT_IMPL_LINKTYPE_DATA
44 # define SORT_ARG(n) ((n)->SORT_IMPL_LINKTYPE_DATA)
45 #else
46 # define SORT_ARG(n) (n)
47 #endif
48 
49 #ifdef SORT_IMPL_USE_THUNK
50 # define THUNK_APPEND1(a, thunk) a, thunk
51 # define THUNK_PREPEND2(thunk, a, b) thunk, a, b
52 #else
53 # define THUNK_APPEND1(a, thunk) a
54 # define THUNK_PREPEND2(thunk, a, b) a, b
55 #endif
56 
57 #define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1##MACRO_ARG2
58 #define _CONCAT(MACRO_ARG1, MACRO_ARG2) _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
59 #define _SORT_PREFIX(id) _CONCAT(SORT_IMPL_FUNC, _##id)
60 
61 /* local identifiers */
62 #define SortInfo _SORT_PREFIX(SortInfo)
63 #define CompareFn _SORT_PREFIX(CompareFn)
64 #define init_sort_info _SORT_PREFIX(init_sort_info)
65 #define merge_lists _SORT_PREFIX(merge_lists)
66 #define sweep_up _SORT_PREFIX(sweep_up)
67 #define insert_list _SORT_PREFIX(insert_list)
68 
69 typedef int (*CompareFn)(
70 #ifdef SORT_IMPL_USE_THUNK
71  void *thunk,
72 #endif
73  const void *,
74  const void *);
75 
76 /* -------------------------------------------------------------------- */
77 /* MIT license from original source */
78 
79 /*
80  * Permission is hereby granted, free of charge, to any person obtaining
81  * a copy of this software and associated documentation files (the
82  * "Software"), to deal in the Software without restriction, including
83  * without limitation the rights to use, copy, modify, merge, publish,
84  * distribute, sublicense, and/or sell copies of the Software, and to
85  * permit persons to whom the Software is furnished to do so, subject to
86  * the following conditions:
87  *
88  * The above copyright notice and this permission notice shall be
89  * included in all copies or substantial portions of the Software.
90  *
91  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
92  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
93  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
94  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
95  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
96  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
97  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
98  *
99  * Author:
100  * Raja R Harinath <rharinath@novell.com>
101  */
102 
112 #define FLOOR_LOG2(x) \
113  (((x) >= 2) + ((x) >= 4) + ((x) >= 8) + ((x) >= 16) + ((x) >= 32) + ((x) >= 64) + ((x) >= 128))
114 #define MAX_RANKS ((sizeof(size_t) * 8) - FLOOR_LOG2(sizeof(list_node)) - 1)
115 
116 struct SortInfo {
117  unsigned int min_rank, n_ranks;
119 
120 #ifdef SORT_IMPL_USE_THUNK
121  void *thunk;
122 #endif
123 
129 };
130 
132  CompareFn func
133 #ifdef SORT_IMPL_USE_THUNK
134  ,
135  void *thunk
136 #endif
137 )
138 {
139  si->min_rank = si->n_ranks = 0;
140  si->func = func;
141  /* we don't need to initialize si->ranks,
142  * since we never lookup past si->n_ranks. */
143 
144 #ifdef SORT_IMPL_USE_THUNK
145  si->thunk = thunk;
146 #endif
147 }
148 
150  list_node *second,
151  CompareFn func
152 #ifdef SORT_IMPL_USE_THUNK
153  ,
154  void *thunk
155 #endif
156 )
157 {
158  /* merge the two lists */
159  list_node *list = NULL;
160  list_node **pos = &list;
161  while (first && second) {
162  if (func(THUNK_PREPEND2(thunk, SORT_ARG(first), SORT_ARG(second))) > 0) {
163  *pos = second;
164  second = second->next;
165  }
166  else {
167  *pos = first;
168  first = first->next;
169  }
170  pos = &((*pos)->next);
171  }
172  *pos = first ? first : second;
173  return list;
174 }
175 
180 BLI_INLINE list_node *sweep_up(struct SortInfo *si, list_node *list, unsigned int upto)
181 {
182  unsigned int i;
183  for (i = si->min_rank; i < upto; i++) {
184  list = merge_lists(si->ranks[i], list, THUNK_APPEND1(si->func, si->thunk));
185  si->ranks[i] = NULL;
186  }
187  return list;
188 }
189 
219 BLI_INLINE void insert_list(struct SortInfo *si, list_node *list, unsigned int rank)
220 {
221  unsigned int i;
222 
223  if (rank > si->n_ranks) {
224  if (UNLIKELY(rank > MAX_RANKS)) {
225  // printf("Rank '%d' should not exceed " STRINGIFY(MAX_RANKS), rank);
226  rank = MAX_RANKS;
227  }
228  list = merge_lists(sweep_up(si, NULL, si->n_ranks), list, THUNK_APPEND1(si->func, si->thunk));
229  for (i = si->n_ranks; i < rank; i++) {
230  si->ranks[i] = NULL;
231  }
232  }
233  else {
234  if (rank) {
235  list = merge_lists(sweep_up(si, NULL, rank), list, THUNK_APPEND1(si->func, si->thunk));
236  }
237  for (i = rank; i < si->n_ranks && si->ranks[i]; i++) {
238  list = merge_lists(si->ranks[i], list, THUNK_APPEND1(si->func, si->thunk));
239  si->ranks[i] = NULL;
240  }
241  }
242 
243  /* Will _never_ happen: so we can just devolve into quadratic ;-) */
244  if (UNLIKELY(i == MAX_RANKS)) {
245  i--;
246  }
247 
248  if (i >= si->n_ranks) {
249  si->n_ranks = i + 1;
250  }
251 
252  si->min_rank = i;
253  si->ranks[i] = list;
254 }
255 
256 #undef MAX_RANKS
257 #undef FLOOR_LOG2
258 
263  CompareFn func
264 #ifdef SORT_IMPL_USE_THUNK
265  ,
266  void *thunk
267 #endif
268 )
269 {
270  struct SortInfo si;
271 
272  init_sort_info(&si,
273  func
274 #ifdef SORT_IMPL_USE_THUNK
275  ,
276  thunk
277 #endif
278  );
279 
280  while (list && list->next) {
281  list_node *next = list->next;
282  list_node *tail = next->next;
283 
284  if (func(THUNK_PREPEND2(thunk, SORT_ARG(list), SORT_ARG(next))) > 0) {
285  next->next = list;
286  next = list;
287  list = list->next;
288  }
289  next->next = NULL;
290 
291  insert_list(&si, list, 0);
292 
293  list = tail;
294  }
295 
296  return sweep_up(&si, list, si.n_ranks);
297 }
298 
299 #undef _CONCAT_AUX
300 #undef _CONCAT
301 #undef _SORT_PREFIX
302 
303 #undef SortInfo
304 #undef CompareFn
305 #undef init_sort_info
306 #undef merge_lists
307 #undef sweep_up
308 #undef insert_list
309 
310 #undef list_node
311 #undef list_sort_do
312 
313 #undef THUNK_APPEND1
314 #undef THUNK_PREPEND2
315 #undef SORT_ARG
#define BLI_INLINE
#define UNLIKELY(x)
uint pos
#define SORT_ARG(n)
#define merge_lists
#define list_node
#define list_sort_do
#define init_sort_info
#define CompareFn
#define THUNK_PREPEND2(thunk, a, b)
#define insert_list
#define MAX_RANKS
#define THUNK_APPEND1(a, thunk)
#define sweep_up
static ulong * next
CompareFn func
list_node * ranks[MAX_RANKS]
unsigned int min_rank
unsigned int n_ranks