1*38fd1498Szrj /* sort.c -- Sort without allocating memory
2*38fd1498Szrj Copyright (C) 2012-2018 Free Software Foundation, Inc.
3*38fd1498Szrj Written by Ian Lance Taylor, Google.
4*38fd1498Szrj
5*38fd1498Szrj Redistribution and use in source and binary forms, with or without
6*38fd1498Szrj modification, are permitted provided that the following conditions are
7*38fd1498Szrj met:
8*38fd1498Szrj
9*38fd1498Szrj (1) Redistributions of source code must retain the above copyright
10*38fd1498Szrj notice, this list of conditions and the following disclaimer.
11*38fd1498Szrj
12*38fd1498Szrj (2) Redistributions in binary form must reproduce the above copyright
13*38fd1498Szrj notice, this list of conditions and the following disclaimer in
14*38fd1498Szrj the documentation and/or other materials provided with the
15*38fd1498Szrj distribution.
16*38fd1498Szrj
17*38fd1498Szrj (3) The name of the author may not be used to
18*38fd1498Szrj endorse or promote products derived from this software without
19*38fd1498Szrj specific prior written permission.
20*38fd1498Szrj
21*38fd1498Szrj THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22*38fd1498Szrj IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
23*38fd1498Szrj WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24*38fd1498Szrj DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
25*38fd1498Szrj INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
26*38fd1498Szrj (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
27*38fd1498Szrj SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28*38fd1498Szrj HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
29*38fd1498Szrj STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
30*38fd1498Szrj IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31*38fd1498Szrj POSSIBILITY OF SUCH DAMAGE. */
32*38fd1498Szrj
33*38fd1498Szrj #include "config.h"
34*38fd1498Szrj
35*38fd1498Szrj #include <stddef.h>
36*38fd1498Szrj #include <sys/types.h>
37*38fd1498Szrj
38*38fd1498Szrj #include "backtrace.h"
39*38fd1498Szrj #include "internal.h"
40*38fd1498Szrj
41*38fd1498Szrj /* The GNU glibc version of qsort allocates memory, which we must not
42*38fd1498Szrj do if we are invoked by a signal handler. So provide our own
43*38fd1498Szrj sort. */
44*38fd1498Szrj
45*38fd1498Szrj static void
swap(char * a,char * b,size_t size)46*38fd1498Szrj swap (char *a, char *b, size_t size)
47*38fd1498Szrj {
48*38fd1498Szrj size_t i;
49*38fd1498Szrj
50*38fd1498Szrj for (i = 0; i < size; i++, a++, b++)
51*38fd1498Szrj {
52*38fd1498Szrj char t;
53*38fd1498Szrj
54*38fd1498Szrj t = *a;
55*38fd1498Szrj *a = *b;
56*38fd1498Szrj *b = t;
57*38fd1498Szrj }
58*38fd1498Szrj }
59*38fd1498Szrj
60*38fd1498Szrj void
backtrace_qsort(void * basearg,size_t count,size_t size,int (* compar)(const void *,const void *))61*38fd1498Szrj backtrace_qsort (void *basearg, size_t count, size_t size,
62*38fd1498Szrj int (*compar) (const void *, const void *))
63*38fd1498Szrj {
64*38fd1498Szrj char *base = (char *) basearg;
65*38fd1498Szrj size_t i;
66*38fd1498Szrj size_t mid;
67*38fd1498Szrj
68*38fd1498Szrj tail_recurse:
69*38fd1498Szrj if (count < 2)
70*38fd1498Szrj return;
71*38fd1498Szrj
72*38fd1498Szrj /* The symbol table and DWARF tables, which is all we use this
73*38fd1498Szrj routine for, tend to be roughly sorted. Pick the middle element
74*38fd1498Szrj in the array as our pivot point, so that we are more likely to
75*38fd1498Szrj cut the array in half for each recursion step. */
76*38fd1498Szrj swap (base, base + (count / 2) * size, size);
77*38fd1498Szrj
78*38fd1498Szrj mid = 0;
79*38fd1498Szrj for (i = 1; i < count; i++)
80*38fd1498Szrj {
81*38fd1498Szrj if ((*compar) (base, base + i * size) > 0)
82*38fd1498Szrj {
83*38fd1498Szrj ++mid;
84*38fd1498Szrj if (i != mid)
85*38fd1498Szrj swap (base + mid * size, base + i * size, size);
86*38fd1498Szrj }
87*38fd1498Szrj }
88*38fd1498Szrj
89*38fd1498Szrj if (mid > 0)
90*38fd1498Szrj swap (base, base + mid * size, size);
91*38fd1498Szrj
92*38fd1498Szrj /* Recurse with the smaller array, loop with the larger one. That
93*38fd1498Szrj ensures that our maximum stack depth is log count. */
94*38fd1498Szrj if (2 * mid < count)
95*38fd1498Szrj {
96*38fd1498Szrj backtrace_qsort (base, mid, size, compar);
97*38fd1498Szrj base += (mid + 1) * size;
98*38fd1498Szrj count -= mid + 1;
99*38fd1498Szrj goto tail_recurse;
100*38fd1498Szrj }
101*38fd1498Szrj else
102*38fd1498Szrj {
103*38fd1498Szrj backtrace_qsort (base + (mid + 1) * size, count - (mid + 1),
104*38fd1498Szrj size, compar);
105*38fd1498Szrj count = mid;
106*38fd1498Szrj goto tail_recurse;
107*38fd1498Szrj }
108*38fd1498Szrj }
109