| 61 | } |
| 62 | |
| 63 | void |
| 64 | backtrace_qsort (void *basearg, size_t count, size_t size, |
| 65 | int (*compar) (const void *, const void *)) |
| 66 | { |
| 67 | char *base = (char *) basearg; |
| 68 | size_t i; |
| 69 | size_t mid; |
| 70 | |
| 71 | tail_recurse: |
| 72 | if (count < 2) |
| 73 | return; |
| 74 | |
| 75 | /* The symbol table and DWARF tables, which is all we use this |
| 76 | routine for, tend to be roughly sorted. Pick the middle element |
| 77 | in the array as our pivot point, so that we are more likely to |
| 78 | cut the array in half for each recursion step. */ |
| 79 | swap (base, base + (count / 2) * size, size); |
| 80 | |
| 81 | mid = 0; |
| 82 | for (i = 1; i < count; i++) |
| 83 | { |
| 84 | if ((*compar) (base, base + i * size) > 0) |
| 85 | { |
| 86 | ++mid; |
| 87 | if (i != mid) |
| 88 | swap (base + mid * size, base + i * size, size); |
| 89 | } |
| 90 | } |
| 91 | |
| 92 | if (mid > 0) |
| 93 | swap (base, base + mid * size, size); |
| 94 | |
| 95 | /* Recurse with the smaller array, loop with the larger one. That |
| 96 | ensures that our maximum stack depth is log count. */ |
| 97 | if (2 * mid < count) |
| 98 | { |
| 99 | backtrace_qsort (base, mid, size, compar); |
| 100 | base += (mid + 1) * size; |
| 101 | count -= mid + 1; |
| 102 | goto tail_recurse; |
| 103 | } |
| 104 | else |
| 105 | { |
| 106 | backtrace_qsort (base + (mid + 1) * size, count - (mid + 1), |
| 107 | size, compar); |
| 108 | count = mid; |
| 109 | goto tail_recurse; |
| 110 | } |
| 111 | } |
| 112 | |
| 113 | } |
no test coverage detected