* sort.c: New file.
* stest.c: New file.
* internal.h (backtrace_qsort): Declare.
* dwarf.c (read_abbrevs): Call backtrace_qsort instead of qsort.
(read_line_info, read_function_entry): Likewise.
(read_function_info, build_dwarf_data): Likewise.
* elf.c (elf_initialize_syminfo): Likewise.
* Makefile.am (libbacktrace_la_SOURCES): Add sort.c.
(stest_SOURCES, stest_LDADD): Define.
(check_PROGRAMS): Add stest.
From-SVN: r208392
+2014-03-06 Ian Lance Taylor <iant@google.com>
+
+ * sort.c: New file.
+ * stest.c: New file.
+ * internal.h (backtrace_qsort): Declare.
+ * dwarf.c (read_abbrevs): Call backtrace_qsort instead of qsort.
+ (read_line_info, read_function_entry): Likewise.
+ (read_function_info, build_dwarf_data): Likewise.
+ * elf.c (elf_initialize_syminfo): Likewise.
+ * Makefile.am (libbacktrace_la_SOURCES): Add sort.c.
+ (stest_SOURCES, stest_LDADD): Define.
+ (check_PROGRAMS): Add stest.
+
2014-02-07 Misty De Meo <misty@brew.sh>
PR target/58710
internal.h \
posix.c \
print.c \
+ sort.c \
state.c
BACKTRACE_FILES = \
check_PROGRAMS += btest
+stest_SOURCES = stest.c
+stest_LDADD = libbacktrace.la
+
+check_PROGRAMS += stest
+
endif NATIVE
# We can't use automake's automatic dependency tracking, because it
host_triplet = @host@
target_triplet = @target@
check_PROGRAMS = $(am__EXEEXT_1)
-@NATIVE_TRUE@am__append_1 = btest
+@NATIVE_TRUE@am__append_1 = btest stest
subdir = .
DIST_COMMON = README ChangeLog $(srcdir)/Makefile.in \
$(srcdir)/Makefile.am $(top_srcdir)/configure \
LTLIBRARIES = $(noinst_LTLIBRARIES)
am__DEPENDENCIES_1 =
am_libbacktrace_la_OBJECTS = atomic.lo dwarf.lo fileline.lo posix.lo \
- print.lo state.lo
+ print.lo sort.lo state.lo
libbacktrace_la_OBJECTS = $(am_libbacktrace_la_OBJECTS)
-@NATIVE_TRUE@am__EXEEXT_1 = btest$(EXEEXT)
+@NATIVE_TRUE@am__EXEEXT_1 = btest$(EXEEXT) stest$(EXEEXT)
@NATIVE_TRUE@am_btest_OBJECTS = btest-btest.$(OBJEXT)
btest_OBJECTS = $(am_btest_OBJECTS)
@NATIVE_TRUE@btest_DEPENDENCIES = libbacktrace.la
btest_LINK = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \
--mode=link $(CCLD) $(btest_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) \
$(LDFLAGS) -o $@
+@NATIVE_TRUE@am_stest_OBJECTS = stest.$(OBJEXT)
+stest_OBJECTS = $(am_stest_OBJECTS)
+@NATIVE_TRUE@stest_DEPENDENCIES = libbacktrace.la
DEFAULT_INCLUDES = -I.@am__isrc@
depcomp =
am__depfiles_maybe =
--mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) \
$(LDFLAGS) -o $@
SOURCES = $(libbacktrace_la_SOURCES) $(EXTRA_libbacktrace_la_SOURCES) \
- $(btest_SOURCES)
+ $(btest_SOURCES) $(stest_SOURCES)
MULTISRCTOP =
MULTIBUILDTOP =
MULTIDIRS =
internal.h \
posix.c \
print.c \
+ sort.c \
state.c
BACKTRACE_FILES = \
@NATIVE_TRUE@btest_SOURCES = btest.c
@NATIVE_TRUE@btest_CFLAGS = $(AM_CFLAGS) -g -O
@NATIVE_TRUE@btest_LDADD = libbacktrace.la
+@NATIVE_TRUE@stest_SOURCES = stest.c
+@NATIVE_TRUE@stest_LDADD = libbacktrace.la
# We can't use automake's automatic dependency tracking, because it
# breaks when using bootstrap-lean. Automatic dependency tracking
btest$(EXEEXT): $(btest_OBJECTS) $(btest_DEPENDENCIES)
@rm -f btest$(EXEEXT)
$(btest_LINK) $(btest_OBJECTS) $(btest_LDADD) $(LIBS)
+stest$(EXEEXT): $(stest_OBJECTS) $(stest_DEPENDENCIES)
+ @rm -f stest$(EXEEXT)
+ $(LINK) $(stest_OBJECTS) $(stest_LDADD) $(LIBS)
mostlyclean-compile:
-rm -f *.$(OBJEXT)
++num_abbrevs;
}
- qsort (abbrevs->abbrevs, abbrevs->num_abbrevs, sizeof (struct abbrev),
- abbrev_compare);
+ backtrace_qsort (abbrevs->abbrevs, abbrevs->num_abbrevs,
+ sizeof (struct abbrev), abbrev_compare);
return 1;
goto fail;
ln = (struct line *) vec.vec.base;
- qsort (ln, vec.count, sizeof (struct line), line_compare);
+ backtrace_qsort (ln, vec.count, sizeof (struct line), line_compare);
*lines = ln;
*lines_count = vec.count;
return 0;
faddrs = (struct function_addrs *) fvec.vec.base;
- qsort (faddrs, fvec.count,
- sizeof (struct function_addrs),
- function_addrs_compare);
+ backtrace_qsort (faddrs, fvec.count,
+ sizeof (struct function_addrs),
+ function_addrs_compare);
function->function_addrs = faddrs;
function->function_addrs_count = fvec.count;
fvec->count = 0;
}
- qsort (addrs, addrs_count, sizeof (struct function_addrs),
- function_addrs_compare);
+ backtrace_qsort (addrs, addrs_count, sizeof (struct function_addrs),
+ function_addrs_compare);
*ret_addrs = addrs;
*ret_addrs_count = addrs_count;
return NULL;
addrs = (struct unit_addrs *) addrs_vec.vec.base;
addrs_count = addrs_vec.count;
- qsort (addrs, addrs_count, sizeof (struct unit_addrs), unit_addrs_compare);
+ backtrace_qsort (addrs, addrs_count, sizeof (struct unit_addrs),
+ unit_addrs_compare);
fdata = ((struct dwarf_data *)
backtrace_alloc (state, sizeof (struct dwarf_data),
++j;
}
- qsort (elf_symbols, elf_symbol_count, sizeof (struct elf_symbol),
- elf_symbol_compare);
+ backtrace_qsort (elf_symbols, elf_symbol_count, sizeof (struct elf_symbol),
+ elf_symbol_compare);
sdata->next = NULL;
sdata->symbols = elf_symbols;
backtrace_error_callback error_callback,
void *data);
+/* Sort without using memory. */
+
+extern void backtrace_qsort (void *base, size_t count, size_t size,
+ int (*compar) (const void *, const void *));
+
/* Allocate memory. This is like malloc. */
extern void *backtrace_alloc (struct backtrace_state *state, size_t size,
--- /dev/null
+/* sort.c -- Sort without allocating memory
+ Copyright (C) 2012-2014 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;
+
+ 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;
+ }
+}
--- /dev/null
+/* stest.c -- Test for libbacktrace internal sort function
+ Copyright (C) 2012-2014 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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+
+#include "backtrace.h"
+#include "internal.h"
+
+/* Test the local qsort implementation. */
+
+#define MAX 10
+
+struct test
+{
+ size_t count;
+ int input[MAX];
+ int output[MAX];
+};
+
+static struct test tests[] =
+ {
+ {
+ 10,
+ { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 },
+ { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
+ },
+ {
+ 9,
+ { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
+ { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
+ },
+ {
+ 10,
+ { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 },
+ { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 },
+ },
+ {
+ 9,
+ { 9, 8, 7, 6, 5, 4, 3, 2, 1 },
+ { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
+ },
+ {
+ 10,
+ { 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 },
+ { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 },
+ },
+ {
+ 5,
+ { 4, 5, 3, 1, 2 },
+ { 1, 2, 3, 4, 5 },
+ },
+ {
+ 5,
+ { 1, 1, 1, 1, 1 },
+ { 1, 1, 1, 1, 1 },
+ },
+ {
+ 5,
+ { 1, 1, 2, 1, 1 },
+ { 1, 1, 1, 1, 2 },
+ },
+ {
+ 5,
+ { 2, 1, 1, 1, 1 },
+ { 1, 1, 1, 1, 2 },
+ },
+ };
+
+static int
+compare (const void *a, const void *b)
+{
+ const int *ai = (const int *) a;
+ const int *bi = (const int *) b;
+
+ return *ai - *bi;
+}
+
+int
+main (int argc ATTRIBUTE_UNUSED, char **argv ATTRIBUTE_UNUSED)
+{
+ int failures;
+ size_t i;
+ int a[MAX];
+
+ failures = 0;
+ for (i = 0; i < sizeof tests / sizeof tests[0]; i++)
+ {
+ memcpy (a, tests[i].input, tests[i].count * sizeof (int));
+ backtrace_qsort (a, tests[i].count, sizeof (int), compare);
+ if (memcmp (a, tests[i].output, tests[i].count * sizeof (int)) != 0)
+ {
+ size_t j;
+
+ fprintf (stderr, "test %d failed:", (int) i);
+ for (j = 0; j < tests[i].count; j++)
+ fprintf (stderr, " %d", a[j]);
+ fprintf (stderr, "\n");
+ ++failures;
+ }
+ }
+
+ exit (failures > 0 ? EXIT_FAILURE : EXIT_SUCCESS);
+}
git://gcc.gnu.org / gcc.git / commitdiff