1 | /* sort.c -- Sort without allocating memory |
---|---|

2 | Copyright (C) 2012-2017 Free Software Foundation, Inc. |

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 | } |

109 |