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