[RFA] Sorting symbols. Again.

[Daniel Jacobowitz <drow@mvista.com>]

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