You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
108 lines
3.1 KiB
108 lines
3.1 KiB
/* sort.c -- Sort without allocating memory |
|
Copyright (C) 2012-2021 Free Software Foundation, Inc. |
|
Written by Ian Lance Taylor, Google. |
|
|
|
Redistribution and use in source and binary forms, with or without |
|
modification, are permitted provided that the following conditions are |
|
met: |
|
|
|
(1) Redistributions of source code must retain the above copyright |
|
notice, this list of conditions and the following disclaimer. |
|
|
|
(2) Redistributions in binary form must reproduce the above copyright |
|
notice, this list of conditions and the following disclaimer in |
|
the documentation and/or other materials provided with the |
|
distribution. |
|
|
|
(3) The name of the author may not be used to |
|
endorse or promote products derived from this software without |
|
specific prior written permission. |
|
|
|
THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
|
IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
|
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
|
DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, |
|
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
|
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR |
|
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
|
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
|
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING |
|
IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
|
POSSIBILITY OF SUCH DAMAGE. */ |
|
|
|
#include "config.h" |
|
|
|
#include <stddef.h> |
|
#include <sys/types.h> |
|
|
|
#include "backtrace.h" |
|
#include "internal.h" |
|
|
|
/* The GNU glibc version of qsort allocates memory, which we must not |
|
do if we are invoked by a signal handler. So provide our own |
|
sort. */ |
|
|
|
static void |
|
swap (char *a, char *b, size_t size) |
|
{ |
|
size_t i; |
|
|
|
for (i = 0; i < size; i++, a++, b++) |
|
{ |
|
char t; |
|
|
|
t = *a; |
|
*a = *b; |
|
*b = t; |
|
} |
|
} |
|
|
|
void |
|
backtrace_qsort (void *basearg, size_t count, size_t size, |
|
int (*compar) (const void *, const void *)) |
|
{ |
|
char *base = (char *) basearg; |
|
size_t i; |
|
size_t mid; |
|
|
|
tail_recurse: |
|
if (count < 2) |
|
return; |
|
|
|
/* The symbol table and DWARF tables, which is all we use this |
|
routine for, tend to be roughly sorted. Pick the middle element |
|
in the array as our pivot point, so that we are more likely to |
|
cut the array in half for each recursion step. */ |
|
swap (base, base + (count / 2) * size, size); |
|
|
|
mid = 0; |
|
for (i = 1; i < count; i++) |
|
{ |
|
if ((*compar) (base, base + i * size) > 0) |
|
{ |
|
++mid; |
|
if (i != mid) |
|
swap (base + mid * size, base + i * size, size); |
|
} |
|
} |
|
|
|
if (mid > 0) |
|
swap (base, base + mid * size, size); |
|
|
|
/* Recurse with the smaller array, loop with the larger one. That |
|
ensures that our maximum stack depth is log count. */ |
|
if (2 * mid < count) |
|
{ |
|
backtrace_qsort (base, mid, size, compar); |
|
base += (mid + 1) * size; |
|
count -= mid + 1; |
|
goto tail_recurse; |
|
} |
|
else |
|
{ |
|
backtrace_qsort (base + (mid + 1) * size, count - (mid + 1), |
|
size, compar); |
|
count = mid; |
|
goto tail_recurse; |
|
} |
|
}
|
|
|