list_sort_impl.h

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2023 Blender Authors
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */

 
/* -------------------------------------------------------------------- */
/* Handle External Defines */
 
#include "BLI_compiler_compat.h"
#include "BLI_utildefines.h"
 
/* check we're not building directly */
#if !defined(SORT_IMPL_LINKTYPE) || !defined(SORT_IMPL_FUNC)
#  error "This file can't be compiled directly, include in another source file"
#endif
 
#define list_node SORT_IMPL_LINKTYPE
#define list_sort_do SORT_IMPL_FUNC
 
#ifdef SORT_IMPL_LINKTYPE_DATA
#  define SORT_ARG(n) ((n)->SORT_IMPL_LINKTYPE_DATA)
#else
#  define SORT_ARG(n) (n)
#endif
 
#ifdef SORT_IMPL_USE_THUNK
#  define BLI_LIST_THUNK_APPEND1(a, thunk) a, thunk
#  define BLI_LIST_THUNK_PREPEND2(thunk, a, b) thunk, a, b
#else
#  define BLI_LIST_THUNK_APPEND1(a, thunk) a
#  define BLI_LIST_THUNK_PREPEND2(thunk, a, b) a, b
#endif
 
#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)
 
/* local identifiers */
#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)
 
typedef int (*CompareFn)(
#ifdef SORT_IMPL_USE_THUNK
    void *thunk,
#endif
    const void *,
    const void *);
 
/* -------------------------------------------------------------------- */
/* MIT license from original source */
 
/*
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 * Author:
 *   Raja R Harinath <rharinath@novell.com>
 */

#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)
 
struct SortInfo {
  unsigned int min_rank, n_ranks;
  CompareFn func;
 
#ifdef SORT_IMPL_USE_THUNK
  void *thunk;
#endif
 
  /* Invariant: `ranks[i] == NULL || length(ranks[i]) >= 2**(i+1)`.
   * ~ 128 bytes on 32bit, ~ 512 bytes on 64bit. */
  list_node *ranks[MAX_RANKS];
};
 
inline void init_sort_info(struct SortInfo *si,
                           CompareFn func
#ifdef SORT_IMPL_USE_THUNK
                           ,
                           void *thunk
#endif
)
{
  si->min_rank = si->n_ranks = 0;
  si->func = func;
  /* we don't need to initialize si->ranks,
   * since we never lookup past si->n_ranks. */
 
#ifdef SORT_IMPL_USE_THUNK
  si->thunk = thunk;
#endif
}
 
inline list_node *merge_lists(list_node *first,
                              list_node *second,
                              CompareFn func
#ifdef SORT_IMPL_USE_THUNK
                              ,
                              void *thunk
#endif
)
{
  /* merge the two lists */
  list_node *list = NULL;
  list_node **pos = &list;
  while (first && second) {
    if (func(BLI_LIST_THUNK_PREPEND2(thunk, SORT_ARG(first), SORT_ARG(second))) > 0) {
      *pos = second;
      second = second->next;
    }
    else {
      *pos = first;
      first = first->next;
    }
    pos = &((*pos)->next);
  }
  *pos = first ? first : second;
  return list;
}

BLI_INLINE list_node *sweep_up(struct SortInfo *si, list_node *list, unsigned int upto)
{
  unsigned int i;
  for (i = si->min_rank; i < upto; i++) {
    list = merge_lists(si->ranks[i], list, BLI_LIST_THUNK_APPEND1(si->func, si->thunk));
    si->ranks[i] = NULL;
  }
  return list;
}


BLI_INLINE void insert_list(struct SortInfo *si, list_node *list, unsigned int rank)
{
  unsigned int i;
 
  if (rank > si->n_ranks) {
    if (UNLIKELY(rank > MAX_RANKS)) {
      // printf("Rank '%d' should not exceed " STRINGIFY(MAX_RANKS), rank);
      rank = MAX_RANKS;
    }
    list = merge_lists(
        sweep_up(si, NULL, si->n_ranks), list, BLI_LIST_THUNK_APPEND1(si->func, si->thunk));
    for (i = si->n_ranks; i < rank; i++) {
      si->ranks[i] = NULL;
    }
  }
  else {
    if (rank) {
      list = merge_lists(
          sweep_up(si, NULL, rank), list, BLI_LIST_THUNK_APPEND1(si->func, si->thunk));
    }
    for (i = rank; i < si->n_ranks && si->ranks[i]; i++) {
      list = merge_lists(si->ranks[i], list, BLI_LIST_THUNK_APPEND1(si->func, si->thunk));
      si->ranks[i] = NULL;
    }
  }
 
  /* Will _never_ happen: so we can just devolve into quadratic ;-) */
  if (UNLIKELY(i == MAX_RANKS)) {
    i--;
  }
 
  if (i >= si->n_ranks) {
    si->n_ranks = i + 1;
  }
 
  si->min_rank = i;
  si->ranks[i] = list;
}
 
#undef MAX_RANKS
#undef FLOOR_LOG2

BLI_INLINE list_node *list_sort_do(list_node *list,
                                   CompareFn func
#ifdef SORT_IMPL_USE_THUNK
                                   ,
                                   void *thunk
#endif
)
{
  struct SortInfo si;
 
  init_sort_info(&si,
                 func
#ifdef SORT_IMPL_USE_THUNK
                 ,
                 thunk
#endif
  );
 
  while (list && list->next) {
    list_node *next = list->next;
    list_node *tail = next->next;
 
    if (func(BLI_LIST_THUNK_PREPEND2(thunk, SORT_ARG(list), SORT_ARG(next))) > 0) {
      next->next = list;
      next = list;
      list = list->next;
    }
    next->next = NULL;
 
    insert_list(&si, list, 0);
 
    list = tail;
  }
 
  return sweep_up(&si, list, si.n_ranks);
}
 
#undef _BLI_LIST_SORT_CONCAT_AUX
#undef _BLI_LIST_SORT_CONCAT
#undef _SORT_PREFIX
 
#undef SortInfo
#undef CompareFn
#undef init_sort_info
#undef merge_lists
#undef sweep_up
#undef insert_list
 
#undef list_node
#undef list_sort_do
 
#undef BLI_LIST_THUNK_APPEND1
#undef BLI_LIST_THUNK_PREPEND2
#undef SORT_ARG