From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 19154 invoked by alias); 30 Jan 2002 05:54:31 -0000 Mailing-List: contact gdb-patches-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sources.redhat.com Received: (qmail 19008 invoked from network); 30 Jan 2002 05:54:25 -0000 Received: from unknown (HELO nevyn.them.org) (128.2.145.6) by sources.redhat.com with SMTP; 30 Jan 2002 05:54:25 -0000 Received: from drow by nevyn.them.org with local (Exim 3.34 #1 (Debian)) id 16VnhW-0007Y7-00; Wed, 30 Jan 2002 00:54:30 -0500 Date: Tue, 29 Jan 2002 21:54:00 -0000 From: Daniel Jacobowitz To: gdb-patches@sources.redhat.com, insight@sources.redhat.com Cc: keiths@cygnus.com, Elena Zannoni Subject: [RFA] Sorting symbols. Again. Message-ID: <20020130005430.A28900@nevyn.them.org> Mail-Followup-To: gdb-patches@sources.redhat.com, insight@sources.redhat.com, keiths@cygnus.com, Elena Zannoni Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.3.23i X-SW-Source: 2002-01/txt/msg00769.txt.bz2 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. -- 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 * gdbtk-cmds.c (sort_funcVals): New function. (gdb_listfuncs): Sort symbols after searching rather than before. 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/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/30 05:42:36 @@ -1452,6 +1452,19 @@ gdb_search (clientData, interp, objc, ob return TCL_OK; } +static int +sort_funcVals (const void *fa, const void *fb) +{ + Tcl_Obj *funcVal_a = *(Tcl_Obj **)fa; + Tcl_Obj *funcVal_b = *(Tcl_Obj **)fb; + Tcl_Obj *func_a, *func_b; + + Tcl_ListObjIndex (NULL, funcVal_a, 0, &func_a); + Tcl_ListObjIndex (NULL, funcVal_b, 0, &func_b); + + return strcmp (Tcl_GetString (func_a), Tcl_GetString (func_b)); +} + /* This implements the tcl command gdb_listfuncs * It lists all the functions defined in a given file @@ -1477,6 +1490,8 @@ gdb_listfuncs (clientData, interp, objc, struct symbol *sym; int i, j; Tcl_Obj *funcVals[2]; + int list_objc; + Tcl_Obj **list_objv, **new_objv; if (objc != 2) { @@ -1506,9 +1521,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) @@ -1544,6 +1556,17 @@ gdb_listfuncs (clientData, interp, objc, Tcl_NewListObj (2, funcVals)); } } + Tcl_ListObjGetElements (NULL, result_ptr->obj_ptr, &list_objc, &list_objv); + new_objv = (Tcl_Obj **) malloc (sizeof (Tcl_Obj *) * list_objc); + memcpy (new_objv, list_objv, sizeof (Tcl_Obj *) * list_objc); + qsort (new_objv, list_objc, sizeof (Tcl_Obj *), sort_funcVals); + for (j = 0; j < list_objc; j++) + Tcl_IncrRefCount (list_objv[j]); + Tcl_SetListObj (result_ptr->obj_ptr, list_objc, new_objv); + Tcl_ListObjGetElements (NULL, result_ptr->obj_ptr, &list_objc, &list_objv); + for (j = 0; j < list_objc; j++) + Tcl_DecrRefCount (list_objv[j]); + free (new_objv); } return TCL_OK; }