From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 29345 invoked by alias); 31 Jan 2002 04:54:26 -0000 Mailing-List: contact insight-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: insight-owner@sources.redhat.com Received: (qmail 29253 invoked from network); 31 Jan 2002 04:54:21 -0000 Received: from unknown (HELO nevyn.them.org) (128.2.145.6) by sources.redhat.com with SMTP; 31 Jan 2002 04:54:21 -0000 Received: from drow by nevyn.them.org with local (Exim 3.34 #1 (Debian)) id 16W9Ez-0005rs-00; Wed, 30 Jan 2002 23:54:29 -0500 Date: Wed, 30 Jan 2002 20:54:00 -0000 From: Daniel Jacobowitz To: gdb-patches@sources.redhat.com, insight@sources.redhat.com, keiths@cygnus.com, Elena Zannoni Subject: Re: [RFA] Sorting symbols. Again. Message-ID: <20020130235429.A22536@nevyn.them.org> Mail-Followup-To: gdb-patches@sources.redhat.com, insight@sources.redhat.com, keiths@cygnus.com, Elena Zannoni References: <20020130005430.A28900@nevyn.them.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20020130005430.A28900@nevyn.them.org> User-Agent: Mutt/1.3.23i X-SW-Source: 2002-q1/txt/msg00083.txt.bz2 On Wed, Jan 30, 2002 at 12:54:30AM -0500, Daniel Jacobowitz wrote: > I think I got it right this time... After a tremendous epic of linked list > management bugs, this kills the two dubious uses of BLOCK_SHOULD_SORT() and > replaces them with code to sort lists after finishing with the search. It's > not the prettiest set of sorts I've ever written - especially the Insight > part - but it works and is reasonably fast. The lists are generally small, > too. > > Elena, you implicitly approved this back in November, but I'd appreciate you > looking over it again. Keith (or someone else on the insight list, of > course), I'd appreciate it if you'd double-check my Tcl. I loathe Tcl, did > I mention? I'm reasonably sure I got the refcounting right now. OK, let's be less dirty to TCL. Having reached the decision that the output of gdb_listfuncs does not, in fact, need to be sorted, the patch is somewhat simpler. This version OK? -- Daniel Jacobowitz Carnegie Mellon University MontaVista Software Debian GNU/Linux Developer 2002-01-30 Daniel Jacobowitz * symtab.c (compare_search_syms): New function. (sort_search_symbols): New function. (search_symbols): Sort symbols after searching rather than before. 2002-01-30 Daniel Jacobowitz * generic/gdbtk-cmds.c (gdb_listfuncs): Don't call BLOCK_SHOULD_SORT. * library/browserwin.itb (BrowserWin::_fill_funcs_combo): Sort the output of gdb_listfuncs. Index: symtab.c =================================================================== RCS file: /cvs/src/src/gdb/symtab.c,v retrieving revision 1.52 diff -u -p -r1.52 symtab.c --- symtab.c 2002/01/17 22:15:17 1.52 +++ symtab.c 2002/01/30 05:42:35 @@ -2380,6 +2380,52 @@ make_cleanup_free_search_symbols (struct return make_cleanup (do_free_search_symbols_cleanup, symbols); } +/* Helper function for sort_search_symbols and qsort. Can only + sort symbols, not minimal symbols. */ +static int +compare_search_syms (const void *sa, const void *sb) +{ + struct symbol_search **sym_a = (struct symbol_search **) sa; + struct symbol_search **sym_b = (struct symbol_search **) sb; + + return strcmp (SYMBOL_SOURCE_NAME ((*sym_a)->symbol), + SYMBOL_SOURCE_NAME ((*sym_b)->symbol)); +} + +/* Sort the ``nfound'' symbols in the list after prevtail. Leave + prevtail where it is, but update its next pointer to point to + the first of the sorted symbols. */ +static struct symbol_search * +sort_search_symbols (struct symbol_search *prevtail, int nfound) +{ + struct symbol_search **symbols, *symp, *old_next; + int i; + + symbols = (struct symbol_search **) xmalloc (sizeof (struct symbol_search *) + * nfound); + symp = prevtail->next; + for (i = 0; i < nfound; i++) + { + symbols[i] = symp; + symp = symp->next; + } + /* Generally NULL. */ + old_next = symp; + + qsort (symbols, nfound, sizeof (struct symbol_search *), + compare_search_syms); + + symp = prevtail; + for (i = 0; i < nfound; i++) + { + symp->next = symbols[i]; + symp = symp->next; + } + symp->next = old_next; + + free (symbols); + return symp; +} /* Search the symbol table for matches to the regular expression REGEXP, returning the results in *MATCHES. @@ -2392,6 +2438,9 @@ make_cleanup_free_search_symbols (struct and constants (enums) free_search_symbols should be called when *MATCHES is no longer needed. + + The results are sorted locally; each symtab's global and static blocks are + separately alphabetized. */ void search_symbols (char *regexp, namespace_enum kind, int nfiles, char *files[], @@ -2581,10 +2630,9 @@ search_symbols (char *regexp, namespace_ if (bv != prev_bv) for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++) { + struct symbol_search *prevtail = tail; + int nfound = 0; b = BLOCKVECTOR_BLOCK (bv, i); - /* Skip the sort if this block is always sorted. */ - if (!BLOCK_SHOULD_SORT (b)) - sort_block_syms (b); for (j = 0; j < BLOCK_NSYMS (b); j++) { QUIT; @@ -2606,14 +2654,27 @@ search_symbols (char *regexp, namespace_ psr->msymbol = NULL; psr->next = NULL; if (tail == NULL) - { - sr = psr; - old_chain = make_cleanup_free_search_symbols (sr); - } + sr = psr; else tail->next = psr; tail = psr; + nfound ++; + } + } + if (nfound > 0) + { + if (prevtail == NULL) + { + struct symbol_search dummy; + + dummy.next = sr; + tail = sort_search_symbols (&dummy, nfound); + sr = dummy.next; + + old_chain = make_cleanup_free_search_symbols (sr); } + else + tail = sort_search_symbols (prevtail, nfound); } } prev_bv = bv; Index: gdbtk/library/browserwin.itb =================================================================== RCS file: /cvs/src/src/gdb/gdbtk/library/browserwin.itb,v retrieving revision 1.2 diff -u -p -r1.2 browserwin.itb --- browserwin.itb 2001/03/15 19:44:30 1.2 +++ browserwin.itb 2002/01/31 04:49:18 @@ -911,7 +911,7 @@ body BrowserWin::_fill_funcs_combo {name -message "This file can not be found or does not contain\ndebugging information." return } - foreach f $listfuncs { + foreach f [lsort -increasing $listfuncs] { lassign $f func mang if {$func == "global constructors keyed to main"} {continue} set _mangled_func($func) $mang Index: gdbtk/generic/gdbtk-cmds.c =================================================================== RCS file: /cvs/src/src/gdb/gdbtk/generic/gdbtk-cmds.c,v retrieving revision 1.48 diff -u -p -r1.48 gdbtk-cmds.c --- gdbtk-cmds.c 2002/01/08 20:21:44 1.48 +++ gdbtk-cmds.c 2002/01/31 04:52:46 @@ -1506,9 +1506,6 @@ gdb_listfuncs (clientData, interp, objc, for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++) { b = BLOCKVECTOR_BLOCK (bv, i); - /* Skip the sort if this block is always sorted. */ - if (!BLOCK_SHOULD_SORT (b)) - sort_block_syms (b); ALL_BLOCK_SYMBOLS (b, j, sym) { if (SYMBOL_CLASS (sym) == LOC_BLOCK)