| /* |
| * 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) (lo + ((hi - lo) >> 1)) |
| |
| /* 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) |
| { |
| char *a1, *al, *am, *ah, *ls, *hs, *lo, *hi, *b; |
| size_t copied = 0; |
| size_t mid; |
| |
| mid = MID (low, high); |
| |
| if (mid + 1 < high) |
| msort (array, buf, mid + 1, high, size, compare, arg); |
| |
| if (mid > low) |
| msort (array, buf, low, mid, size, compare, arg); |
| |
| ah = ((char *) array) + ((high + 1) * size); |
| am = ((char *) array) + ((mid + 1) * size); |
| a1 = al = ((char *) array) + (low * size); |
| |
| b = (char *) buf; |
| lo = al; |
| hi = am; |
| |
| do { |
| ls = lo; |
| hs = hi; |
| |
| if (lo > al || hi > am) { |
| /* our last loop already compared lo & hi and found lo <= hi */ |
| lo += size; |
| } |
| |
| while (lo < am && compare (lo, hi, arg) <= 0) |
| lo += size; |
| |
| if (lo < am) { |
| if (copied == 0) { |
| /* avoid copying the leading items */ |
| a1 = lo; |
| ls = lo; |
| } |
| |
| /* our last compare tells us hi < lo */ |
| hi += size; |
| |
| while (hi < ah && compare (hi, lo, arg) < 0) |
| hi += size; |
| |
| if (lo > ls) { |
| memcpy (b, ls, lo - ls); |
| copied += (lo - ls); |
| b += (lo - ls); |
| } |
| |
| memcpy (b, hs, hi - hs); |
| copied += (hi - hs); |
| b += (hi - hs); |
| } else if (copied) { |
| memcpy (b, ls, lo - ls); |
| copied += (lo - ls); |
| b += (lo - ls); |
| |
| /* copy everything we needed to re-order back into array */ |
| memcpy (a1, buf, copied); |
| return; |
| } else { |
| /* everything already in order */ |
| return; |
| } |
| } while (hi < ah); |
| |
| if (lo < am) { |
| memcpy (b, lo, am - lo); |
| copied += (am - lo); |
| } |
| |
| memcpy (a1, buf, copied); |
| } |
| |
| static int |
| MergeSort (void *base, size_t nmemb, size_t size, |
| int (* compare) (const void *, const void *, void *), void *arg) |
| { |
| void *tmp; |
| |
| if (nmemb < 2) |
| return 0; |
| |
| if (!(tmp = malloc (nmemb * size))) { |
| errno = ENOMEM; |
| return -1; |
| } |
| |
| msort (base, tmp, 0, nmemb - 1, size, compare, arg); |
| |
| free (tmp); |
| |
| return 0; |
| } |
| |
| int isl_sort(void *const pbase, size_t total_elems, size_t size, |
| int (*cmp)(const void *, const void *, void *arg), void *arg) |
| { |
| return MergeSort (pbase, total_elems, size, cmp, arg); |
| } |