This is the mail archive of the
insight@sources.redhat.com
mailing list for the Insight project.
[RFA] Sorting symbols. Again.
- From: Daniel Jacobowitz <drow at mvista dot com>
- To: gdb-patches at sources dot redhat dot com, insight at sources dot redhat dot com
- Cc: keiths at cygnus dot com, Elena Zannoni <ezannoni at cygnus dot com>
- Date: Wed, 30 Jan 2002 00:54:30 -0500
- Subject: [RFA] Sorting symbols. Again.
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 <drow@mvista.com>
* 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 <drow@mvista.com>
* 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;
}