[RFA] Sorting symbols. Again.

[RFA] Sorting symbols. Again.

[Daniel Jacobowitz]

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;
 }

Re: [RFA] Sorting symbols. Again.

[Syd Polk]

Where is sort_funcVals called from? It it called pretty close to the Tcl 
layer? If so, you might want to use "lsort -command foo" from the tcl 
level and implement the comparison command in C. Given that the sort 
command you are using pares down to a simple strcmp, this would be much 
cleaner than doing what you are doing.

> 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);

You should not have to loop through the objects in list_objv to Incr or 
Decr their refCounts. Tcl_SetListObj does that automatically. They are 
created with a refCount of 0; Tcl_SetListObj incrs them to 1. What you 
are doing is creating them, setting them to 1, calling Tcl_SetListObj 
(which incrs them to 2), and the decrementing them back to 1.

Also, it is really, really slimy to create Tcl_Objs without going 
through Tcl_New*Obj.

I would much prefer that you duplicate the list, and then call "lsort". 
Pseudo-code:

	Tcl_Obj *commandArray[2];

	Tcl_ListObjGetElements (NULL, result_ptr->obj_ptr, &list_objc, 
&list_objv);
	newList = Tcl_NewListObj(list_objc, list_objv);
	commandArray[1] = newList;
	Tcl_IncrRefCount(newList);
	commandArray[0] = Tcl_NewObjFromString("lsort");
	Tcl_IncrRefCount(commandArray[0]);
	result = Tcl_EvalObjv(interp, 2, commandArray);
	Tcl_DecrRefCount(commandArray[0]);
	
	/* newList now has sorted list. */

I am not a maintainer, but I worked in the core of Tcl for a couple of 
years for John O., and doing block allocates of Tcl_Objs is just asking 
for trouble, and will lead to problems if insight is ever compiled to 
TCL_MEM_DEBUG, or other things.


>      }
>    return TCL_OK;
>  }
>
>
Syd Polk
QA and Integration Manager, Mac OS X Development Tools
+1 408 974-0577

Re: [RFA] Sorting symbols. Again.

[Daniel Jacobowitz]

On Wed, Jan 30, 2002 at 02:01:10PM -0800, Syd Polk wrote:
> 
> Where is sort_funcVals called from? It it called pretty close to the Tcl 
> layer? If so, you might want to use "lsort -command foo" from the tcl 
> level and implement the comparison command in C. Given that the sort 
> command you are using pares down to a simple strcmp, this would be much 
> cleaner than doing what you are doing.

It's called from gdb_listfuncs.  Are the TCL functions exported by
insight generally available to some kind of user scripts, or can I
change callers?

In fact, I see that one of the two callers already sorts the list
itself.

> You should not have to loop through the objects in list_objv to Incr or 
> Decr their refCounts. Tcl_SetListObj does that automatically. They are 
> created with a refCount of 0; Tcl_SetListObj incrs them to 1. What you 
> are doing is creating them, setting them to 1, calling Tcl_SetListObj 
> (which incrs them to 2), and the decrementing them back to 1.
> 
> Also, it is really, really slimy to create Tcl_Objs without going 
> through Tcl_New*Obj.
> 
> I would much prefer that you duplicate the list, and then call "lsort". 
> Pseudo-code:
> 
> 	Tcl_Obj *commandArray[2];
> 
> 	Tcl_ListObjGetElements (NULL, result_ptr->obj_ptr, &list_objc, 
> &list_objv);
> 	newList = Tcl_NewListObj(list_objc, list_objv);
> 	commandArray[1] = newList;
> 	Tcl_IncrRefCount(newList);
> 	commandArray[0] = Tcl_NewObjFromString("lsort");
> 	Tcl_IncrRefCount(commandArray[0]);
> 	result = Tcl_EvalObjv(interp, 2, commandArray);
> 	Tcl_DecrRefCount(commandArray[0]);
> 	
> 	/* newList now has sorted list. */
> 
> I am not a maintainer, but I worked in the core of Tcl for a couple of 
> years for John O., and doing block allocates of Tcl_Objs is just asking 
> for trouble, and will lead to problems if insight is ever compiled to 
> TCL_MEM_DEBUG, or other things.

I don't think I did anything of the sort; but perhaps I misunderstood
Tcl_SetListObj.  The documentation doesn't say anything about how to
allocate the objv.  The refcount mess was because of using SetListObj,
but I suppose I understand now that creating a new object and then
destroying the old one would have worked out cleaner.  Hopefully the
above will be accepted and I can delete the sort entirely :)

Thanks for the helpful comments.

-- 
Daniel Jacobowitz                           Carnegie Mellon University
MontaVista Software                         Debian GNU/Linux Developer

Re: [RFA] Sorting symbols. Again.

[Syd Polk]

On Wednesday, January 30, 2002, at 02:37 , Daniel Jacobowitz wrote:

> On Wed, Jan 30, 2002 at 02:01:10PM -0800, Syd Polk wrote:
>
>> You should not have to loop through the objects in list_objv to Incr or
>> Decr their refCounts. Tcl_SetListObj does that automatically. They are
>> created with a refCount of 0; Tcl_SetListObj incrs them to 1. What you
>> are doing is creating them, setting them to 1, calling Tcl_SetListObj
>> (which incrs them to 2), and the decrementing them back to 1.
>>
>> Also, it is really, really slimy to create Tcl_Objs without going
>> through Tcl_New*Obj.
>>
>> I would much prefer that you duplicate the list, and then call "lsort".
>> Pseudo-code:
>>
>> 	Tcl_Obj *commandArray[2];
>>
>> 	Tcl_ListObjGetElements (NULL, result_ptr->obj_ptr, &list_objc,
>> &list_objv);
>> 	newList = Tcl_NewListObj(list_objc, list_objv);
>> 	commandArray[1] = newList;
>> 	Tcl_IncrRefCount(newList);
>> 	commandArray[0] = Tcl_NewObjFromString("lsort");
>> 	Tcl_IncrRefCount(commandArray[0]);
>> 	result = Tcl_EvalObjv(interp, 2, commandArray);
>> 	Tcl_DecrRefCount(commandArray[0]);
>> 	
>> 	/* newList now has sorted list. */
>>
>> I am not a maintainer, but I worked in the core of Tcl for a couple of
>> years for John O., and doing block allocates of Tcl_Objs is just asking
>> for trouble, and will lead to problems if insight is ever compiled to
>> TCL_MEM_DEBUG, or other things.
>
> I don't think I did anything of the sort; but perhaps I misunderstood
> Tcl_SetListObj.  The documentation doesn't say anything about how to
> allocate the objv.  The refcount mess was because of using SetListObj,
> but I suppose I understand now that creating a new object and then
> destroying the old one would have worked out cleaner.  Hopefully the
> above will be accepted and I can delete the sort entirely :)
>

+      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);

This memcpy duplicates Tcl_Obj's without going through approved API. 
This can screw up refcounting of the individual Tcl_Obj's in the list.

> Thanks for the helpful comments.
>
> --
> Daniel Jacobowitz                           Carnegie Mellon University
> MontaVista Software                         Debian GNU/Linux Developer
>
>
Syd Polk
QA and Integration Manager, Mac OS X Development Tools
+1 408 974-0577

Re: [RFA] Sorting symbols. Again.

[Daniel Jacobowitz]

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  <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>

	* 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)

Re: [RFA] Sorting symbols. Again.

[Syd Polk]

Makes me happier, but I am not a maintainer.

On Wednesday, January 30, 2002, at 08:54 , Daniel Jacobowitz wrote:

> 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  <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>
>
> 	* 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)
>
>
Syd Polk
QA and Integration Manager, Mac OS X Development Tools
+1 408 974-0577

Re: [RFA] Sorting symbols. Again.

[Elena Zannoni]

 > > 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?


[I lost some mail, sorry for the random reply]

Ok with me for the symtab part.

Elena


 > >
 > > --
 > > 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>
 > >
 > > 	* 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)
 > >
 > >
 > Syd Polk
 > QA and Integration Manager, Mac OS X Development Tools
 > +1 408 974-0577

Re: [RFA] Sorting symbols. Again.

[Keith Seitz]

[Sorry for the delay -- just back from vacation]

On Wed, 30 Jan 2002, Daniel Jacobowitz wrote:

> -    foreach f $listfuncs {
> +    foreach f [lsort -increasing $listfuncs] {

["increasing" and "ascii" are the defaults for lsort]

Everything looks fine, though.

Thank you for thinking about us!
Keith