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

Copyright (C) 2012-2018 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; | |

} | |

} |