llvm/polly/lib/External/isl/isl_sort.c

/*
 * The code of this file was taken from http://jeffreystedfast.blogspot.be,
 * where it was posted in 2011 by Jeffrey Stedfast under the MIT license.
 * The MIT license text is as follows:
 *
 * 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.
 */

#include <errno.h>
#include <string.h>
#include <stdlib.h>
#include <isl_sort.h>

#define MID(lo, hi) …

/* The code here is an optimized merge sort. Starting from a generic merge sort
 * the following optimizations were applied:
 *
 * o Batching of memcpy() calls: Instead of calling memcpy() to copy each and
 *   every element into a temporary buffer, blocks of elements are copied
 *   at a time.
 *
 * o To reduce the number of memcpy() calls further, copying leading
 *   and trailing elements into our temporary buffer is avoided, in case it is
 *   not necessary to merge them.
 *
 * A further optimization could be to specialize memcpy calls based on the
 * size of the types we compare. For now, this code does not include the
 * relevant optimization, as clang e.g. inlines a very efficient memcpy()
 * implementation. It is not clear, that the specialized version as provided in
 * the blog post, is really superior to the one that will be inlined by
 * default. So we decided to keep the code simple until this optimization was
 * proven to be beneficial.
 */

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int (* compare) (const void *, const void *, void *), void *arg)
{ … }

static int
MergeSort (void *base, size_t nmemb, size_t size,
           int (* compare) (const void *, const void *, void *), void *arg)
{ … }

int isl_sort(void *const pbase, size_t total_elems, size_t size,
	int (*cmp)(const void *, const void *, void *arg), void *arg)
{ … }