From 5a574951a166d294f3b44e889b48ebf9436d964c Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Mon, 1 Sep 2014 00:49:51 -0500 Subject: Add musl's old heap sort --- musl_heapsort.c | 37 +++++++++ musl_qsort.c | 218 ------------------------------------------------------ musl_smoothsort.c | 218 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ sorters.c | 3 +- 4 files changed, 257 insertions(+), 219 deletions(-) create mode 100644 musl_heapsort.c delete mode 100644 musl_qsort.c create mode 100644 musl_smoothsort.c diff --git a/musl_heapsort.c b/musl_heapsort.c new file mode 100644 index 0000000..33a72d5 --- /dev/null +++ b/musl_heapsort.c @@ -0,0 +1,37 @@ +#include + +#include "sorters.h" +#include "common.h" + +/* A simple heap sort implementation.. only in-place O(nlogn) sort I know. */ + +#define MIN(a, b) ((a)<(b) ? (a) : (b)) + +static void sift(char *base, size_t root, size_t nel, size_t width, int (*cmp)(const void *, const void *)) +{ + size_t max; + + while (2*root <= nel) { + max = 2*root; + if (max < nel && cmp(base+max*width, base+(max+1)*width) < 0) + max++; + if (max && cmp(base+root*width, base+max*width) < 0) { + swap(base+root*width, base+max*width, width); + root = max; + } else break; + } +} + +void musl_heapsort(void *_base, size_t nel, size_t width, cmpfun cmp) +{ + char *base = _base; + size_t i; + + if (!nel) return; + for (i=(nel+1)/2; i; i--) + sift(base, i-1, nel-1, width, cmp); + for (i=nel-1; i; i--) { + swap(base, base+i*width, width); + sift(base, 0, i-1, width, cmp); + } +} diff --git a/musl_qsort.c b/musl_qsort.c deleted file mode 100644 index 3792aa1..0000000 --- a/musl_qsort.c +++ /dev/null @@ -1,218 +0,0 @@ -/* Copyright (C) 2011 by Valentin Ochs - * - * 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. - */ - -/* Minor changes by Rich Felker for integration in musl, 2011-04-27. */ - -#include -#include -#include - -#include "sorters.h" - -static inline int ntz(uint64_t x) -{ - __asm__( "bsf %1,%0" : "=r"(x) : "r"(x) ); - return x; -} - -static inline int pntz(size_t p[2]) { - int r = ntz(p[0] - 1); - if(r != 0 || (r = 8*sizeof(size_t) + ntz(p[1])) != 8*sizeof(size_t)) { - return r; - } - return 0; -} - -static void cycle(size_t width, unsigned char* ar[], int n) -{ - unsigned char tmp[256]; - size_t l; - int i; - - if(n < 2) { - return; - } - - ar[n] = tmp; - while(width) { - l = sizeof(tmp) < width ? sizeof(tmp) : width; - memcpy(ar[n], ar[0], l); - for(i = 0; i < n; i++) { - memcpy(ar[i], ar[i + 1], l); - ar[i] += l; - } - width -= l; - } -} - -/* shl() and shr() need n > 0 */ -static inline void shl(size_t p[2], int n) -{ - if(n >= 8 * sizeof(size_t)) { - n -= 8 * sizeof(size_t); - p[1] = p[0]; - p[0] = 0; - } - p[1] <<= n; - p[1] |= p[0] >> (sizeof(size_t) * 8 - n); - p[0] <<= n; -} - -static inline void shr(size_t p[2], int n) -{ - if(n >= 8 * sizeof(size_t)) { - n -= 8 * sizeof(size_t); - p[0] = p[1]; - p[1] = 0; - } - p[0] >>= n; - p[0] |= p[1] << (sizeof(size_t) * 8 - n); - p[1] >>= n; -} - -static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshift, size_t lp[]) -{ - unsigned char *rt, *lf; - unsigned char *ar[14 * sizeof(size_t) + 1]; - int i = 1; - - ar[0] = head; - while(pshift > 1) { - rt = head - width; - lf = head - width - lp[pshift - 2]; - - if((*cmp)(ar[0], lf) >= 0 && (*cmp)(ar[0], rt) >= 0) { - break; - } - if((*cmp)(lf, rt) >= 0) { - ar[i++] = lf; - head = lf; - pshift -= 1; - } else { - ar[i++] = rt; - head = rt; - pshift -= 2; - } - } - cycle(width, ar, i); -} - -static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2], int pshift, int trusty, size_t lp[]) -{ - unsigned char *stepson, - *rt, *lf; - size_t p[2]; - unsigned char *ar[14 * sizeof(size_t) + 1]; - int i = 1; - int trail; - - p[0] = pp[0]; - p[1] = pp[1]; - - ar[0] = head; - while(p[0] != 1 || p[1] != 0) { - stepson = head - lp[pshift]; - if((*cmp)(stepson, ar[0]) <= 0) { - break; - } - if(!trusty && pshift > 1) { - rt = head - width; - lf = head - width - lp[pshift - 2]; - if((*cmp)(rt, stepson) >= 0 || (*cmp)(lf, stepson) >= 0) { - break; - } - } - - ar[i++] = stepson; - head = stepson; - trail = pntz(p); - shr(p, trail); - pshift += trail; - trusty = 0; - } - if(!trusty) { - cycle(width, ar, i); - sift(head, width, cmp, pshift, lp); - } -} - -void musl_qsort(void *base, size_t nel, size_t width, cmpfun cmp) -{ - size_t lp[12*sizeof(size_t)]; - size_t i, size = width * nel; - unsigned char *head, *high; - size_t p[2] = {1, 0}; - int pshift = 1; - int trail; - - if (!size) return; - - head = base; - high = head + size - width; - - /* Precompute Leonardo numbers, scaled by element width */ - for(lp[0]=lp[1]=width, i=2; (lp[i]=lp[i-2]+lp[i-1]+width) < size; i++); - - while(head < high) { - if((p[0] & 3) == 3) { - sift(head, width, cmp, pshift, lp); - shr(p, 2); - pshift += 2; - } else { - if(lp[pshift - 1] >= high - head) { - trinkle(head, width, cmp, p, pshift, 0, lp); - } else { - sift(head, width, cmp, pshift, lp); - } - - if(pshift == 1) { - shl(p, 1); - pshift = 0; - } else { - shl(p, pshift - 1); - pshift = 1; - } - } - - p[0] |= 1; - head += width; - } - - trinkle(head, width, cmp, p, pshift, 0, lp); - - while(pshift != 1 || p[0] != 1 || p[1] != 0) { - if(pshift <= 1) { - trail = pntz(p); - shr(p, trail); - pshift += trail; - } else { - shl(p, 2); - pshift -= 2; - p[0] ^= 7; - shr(p, 1); - trinkle(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, lp); - shl(p, 1); - p[0] |= 1; - trinkle(head - width, width, cmp, p, pshift, 1, lp); - } - head -= width; - } -} diff --git a/musl_smoothsort.c b/musl_smoothsort.c new file mode 100644 index 0000000..4a1dfb1 --- /dev/null +++ b/musl_smoothsort.c @@ -0,0 +1,218 @@ +/* Copyright (C) 2011 by Valentin Ochs + * + * 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. + */ + +/* Minor changes by Rich Felker for integration in musl, 2011-04-27. */ + +#include +#include +#include + +#include "sorters.h" + +static inline int ntz(uint64_t x) +{ + __asm__( "bsf %1,%0" : "=r"(x) : "r"(x) ); + return x; +} + +static inline int pntz(size_t p[2]) { + int r = ntz(p[0] - 1); + if(r != 0 || (r = 8*sizeof(size_t) + ntz(p[1])) != 8*sizeof(size_t)) { + return r; + } + return 0; +} + +static void cycle(size_t width, unsigned char* ar[], int n) +{ + unsigned char tmp[256]; + size_t l; + int i; + + if(n < 2) { + return; + } + + ar[n] = tmp; + while(width) { + l = sizeof(tmp) < width ? sizeof(tmp) : width; + memcpy(ar[n], ar[0], l); + for(i = 0; i < n; i++) { + memcpy(ar[i], ar[i + 1], l); + ar[i] += l; + } + width -= l; + } +} + +/* shl() and shr() need n > 0 */ +static inline void shl(size_t p[2], int n) +{ + if(n >= 8 * sizeof(size_t)) { + n -= 8 * sizeof(size_t); + p[1] = p[0]; + p[0] = 0; + } + p[1] <<= n; + p[1] |= p[0] >> (sizeof(size_t) * 8 - n); + p[0] <<= n; +} + +static inline void shr(size_t p[2], int n) +{ + if(n >= 8 * sizeof(size_t)) { + n -= 8 * sizeof(size_t); + p[0] = p[1]; + p[1] = 0; + } + p[0] >>= n; + p[0] |= p[1] << (sizeof(size_t) * 8 - n); + p[1] >>= n; +} + +static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshift, size_t lp[]) +{ + unsigned char *rt, *lf; + unsigned char *ar[14 * sizeof(size_t) + 1]; + int i = 1; + + ar[0] = head; + while(pshift > 1) { + rt = head - width; + lf = head - width - lp[pshift - 2]; + + if((*cmp)(ar[0], lf) >= 0 && (*cmp)(ar[0], rt) >= 0) { + break; + } + if((*cmp)(lf, rt) >= 0) { + ar[i++] = lf; + head = lf; + pshift -= 1; + } else { + ar[i++] = rt; + head = rt; + pshift -= 2; + } + } + cycle(width, ar, i); +} + +static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2], int pshift, int trusty, size_t lp[]) +{ + unsigned char *stepson, + *rt, *lf; + size_t p[2]; + unsigned char *ar[14 * sizeof(size_t) + 1]; + int i = 1; + int trail; + + p[0] = pp[0]; + p[1] = pp[1]; + + ar[0] = head; + while(p[0] != 1 || p[1] != 0) { + stepson = head - lp[pshift]; + if((*cmp)(stepson, ar[0]) <= 0) { + break; + } + if(!trusty && pshift > 1) { + rt = head - width; + lf = head - width - lp[pshift - 2]; + if((*cmp)(rt, stepson) >= 0 || (*cmp)(lf, stepson) >= 0) { + break; + } + } + + ar[i++] = stepson; + head = stepson; + trail = pntz(p); + shr(p, trail); + pshift += trail; + trusty = 0; + } + if(!trusty) { + cycle(width, ar, i); + sift(head, width, cmp, pshift, lp); + } +} + +void musl_smoothsort(void *base, size_t nel, size_t width, cmpfun cmp) +{ + size_t lp[12*sizeof(size_t)]; + size_t i, size = width * nel; + unsigned char *head, *high; + size_t p[2] = {1, 0}; + int pshift = 1; + int trail; + + if (!size) return; + + head = base; + high = head + size - width; + + /* Precompute Leonardo numbers, scaled by element width */ + for(lp[0]=lp[1]=width, i=2; (lp[i]=lp[i-2]+lp[i-1]+width) < size; i++); + + while(head < high) { + if((p[0] & 3) == 3) { + sift(head, width, cmp, pshift, lp); + shr(p, 2); + pshift += 2; + } else { + if(lp[pshift - 1] >= high - head) { + trinkle(head, width, cmp, p, pshift, 0, lp); + } else { + sift(head, width, cmp, pshift, lp); + } + + if(pshift == 1) { + shl(p, 1); + pshift = 0; + } else { + shl(p, pshift - 1); + pshift = 1; + } + } + + p[0] |= 1; + head += width; + } + + trinkle(head, width, cmp, p, pshift, 0, lp); + + while(pshift != 1 || p[0] != 1 || p[1] != 0) { + if(pshift <= 1) { + trail = pntz(p); + shr(p, trail); + pshift += trail; + } else { + shl(p, 2); + pshift -= 2; + p[0] ^= 7; + shr(p, 1); + trinkle(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, lp); + shl(p, 1); + p[0] |= 1; + trinkle(head - width, width, cmp, p, pshift, 1, lp); + } + head -= width; + } +} diff --git a/sorters.c b/sorters.c index 43a3369..593ab29 100644 --- a/sorters.c +++ b/sorters.c @@ -7,7 +7,8 @@ const struct sorter sorters[] = { { .name = "freebsd", .func = freebsd_qsort }, { .name = "glibc quicksort", .func = glibc_quicksort }, { .name = "glibc mergesort", .func = glibc_mergesort }, - { .name = "musl", .func = musl_qsort }, + { .name = "musl smoothsort", .func = musl_smoothsort }, + { .name = "musl heapsort", .func = musl_heapsort }, { .name = "wikisort", .func = wikisort }, { .name = "wikisort (ref)", .func = wikisort_ref }, { .name = "grailsort", .func = grailsort }, -- cgit v1.2.3