[RFA] remove duplicates in search_symbols

[RFA] remove duplicates in search_symbols

[Doug Evans]

Hi.
Depending on the app a large number of duplicates can be found
by search_symbols.  This patch removes the dups.

It also will change the output of "info fun|var|types" to be sorted
by file name.

Regression tested on amd64-linux, with/without fission.

Ok to check in?

2013-06-15  Doug Evans  <dje@google.com>

	* symtab.c (do_free_search_symbols_cleanup): Change arg to,
	effectively, struct symbol_search **.
	(make_cleanup_free_search_symbols): Change arg to struct symbol_search **.
	All callers updated.
	(compare_search_syms): Compare symtab file name and block as well.
	(search_symbols_equal): New function.
	(sort_search_symbols_remove_dups): Renamed from sort_search_symbols.
	New args new_head, new_tail.  Result is now void.  Remove dups after
	sorting the symbols.
	(search_symbols): Sort all found symbols once, after all have been found,
	and remove duplicates.  Simplify cleanup tracking of result.
	* symtab.h (make_cleanup_free_search_symbols): Update prototype.

Index: symtab.c
===================================================================
RCS file: /cvs/src/src/gdb/symtab.c,v
retrieving revision 1.362
diff -u -p -r1.362 symtab.c
--- symtab.c	30 May 2013 17:20:02 -0000	1.362
+++ symtab.c	16 Jun 2013 03:07:02 -0000
@@ -3305,64 +3305,102 @@ free_search_symbols (struct symbol_searc
 }
 
 static void
-do_free_search_symbols_cleanup (void *symbols)
+do_free_search_symbols_cleanup (void *symbolsp)
 {
+  struct symbol_search *symbols = *(struct symbol_search **) symbolsp;
+
   free_search_symbols (symbols);
 }
 
 struct cleanup *
-make_cleanup_free_search_symbols (struct symbol_search *symbols)
+make_cleanup_free_search_symbols (struct symbol_search **symbolsp)
 {
-  return make_cleanup (do_free_search_symbols_cleanup, symbols);
+  return make_cleanup (do_free_search_symbols_cleanup, symbolsp);
 }
 
-/* Helper function for sort_search_symbols and qsort.  Can only
+/* Helper function for sort_search_symbols_remove_dups 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;
+  struct symbol_search *sym_a = *(struct symbol_search **) sa;
+  struct symbol_search *sym_b = *(struct symbol_search **) sb;
+  int c;
+
+  c = strcmp (sym_a->symtab->filename, sym_b->symtab->filename);
+  if (c != 0)
+    return c;
 
-  return strcmp (SYMBOL_PRINT_NAME ((*sym_a)->symbol),
-		 SYMBOL_PRINT_NAME ((*sym_b)->symbol));
+  if (sym_a->block != sym_b->block)
+    return sym_a->block - sym_b->block;
+
+  return strcmp (SYMBOL_PRINT_NAME (sym_a->symbol),
+		 SYMBOL_PRINT_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.  */
+/* Helper function for sort_search_symbols_remove_dups.
+   Return TRUE if symbols A, B are equal.  */
 
-static struct symbol_search *
-sort_search_symbols (struct symbol_search *prevtail, int nfound)
+static int
+search_symbols_equal (const struct symbol_search *a,
+		      const struct symbol_search *b)
+{
+  return (strcmp (a->symtab->filename, b->symtab->filename) == 0
+	  && a->block == b->block
+	  && strcmp (SYMBOL_PRINT_NAME (a->symbol),
+		     SYMBOL_PRINT_NAME (b->symbol)) == 0);
+}
+
+/* Sort the NFOUND symbols in list FOUND and remove duplicates.
+   The duplicates are freed, and the new list is returned in
+   *NEW_HEAD, *NEW_TAIL.  */
+
+static void
+sort_search_symbols_remove_dups (struct symbol_search *found, int nfound,
+				 struct symbol_search **new_head,
+				 struct symbol_search **new_tail)
 {
   struct symbol_search **symbols, *symp, *old_next;
-  int i;
+  int i, j, nunique;
 
+  gdb_assert (found != NULL && nfound > 0);
+
+  /* Build an array out of the list so we can easily sort them.  */
   symbols = (struct symbol_search **) xmalloc (sizeof (struct symbol_search *)
 					       * nfound);
-  symp = prevtail->next;
+  symp = found;
   for (i = 0; i < nfound; i++)
     {
+      gdb_assert (symp != NULL);
+      gdb_assert (symp->block >= 0 && symp->block <= 1);
       symbols[i] = symp;
       symp = symp->next;
     }
-  /* Generally NULL.  */
-  old_next = symp;
+  gdb_assert (symp == NULL);
 
   qsort (symbols, nfound, sizeof (struct symbol_search *),
 	 compare_search_syms);
 
-  symp = prevtail;
-  for (i = 0; i < nfound; i++)
+  /* Collapse out the dups.  */
+  for (i = 1, j = 1; i < nfound; ++i)
     {
-      symp->next = symbols[i];
-      symp = symp->next;
+      if (! search_symbols_equal (symbols[j - 1], symbols[i]))
+	symbols[j++] = symbols[i];
+      else
+	xfree (symbols[i]);
     }
-  symp->next = old_next;
+  nunique = j;
+  symbols[j - 1]->next = NULL;
+
+  /* Rebuild the linked list.  */
+  for (i = 0; i < nunique - 1; i++)
+    symbols[i]->next = symbols[i + 1];
+  symbols[nunique - 1]->next = NULL;
 
+  *new_head = symbols[0];
+  *new_tail = symbols[nunique - 1];
   xfree (symbols);
-  return symp;
 }
 
 /* An object of this type is passed as the user_data to the
@@ -3410,8 +3448,9 @@ search_symbols_name_matches (const char 
 
    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.  */
+   Within each file the results are sorted locally; each symtab's global and
+   static blocks are separately alphabetized.
+   Duplicate entries are removed.  */
 
 void
 search_symbols (char *regexp, enum search_domain kind,
@@ -3439,10 +3478,10 @@ search_symbols (char *regexp, enum searc
   enum minimal_symbol_type ourtype2;
   enum minimal_symbol_type ourtype3;
   enum minimal_symbol_type ourtype4;
-  struct symbol_search *sr;
-  struct symbol_search *psr;
+  struct symbol_search *found;
   struct symbol_search *tail;
   struct search_symbols_data datum;
+  int nfound;
 
   /* OLD_CHAIN .. RETVAL_CHAIN is always freed, RETVAL_CHAIN .. current
      CLEANUP_CHAIN is freed only in the case of an error.  */
@@ -3456,8 +3495,7 @@ search_symbols (char *regexp, enum searc
   ourtype3 = types3[kind];
   ourtype4 = types4[kind];
 
-  sr = *matches = NULL;
-  tail = NULL;
+  *matches = NULL;
   datum.preg_p = 0;
 
   if (regexp != NULL)
@@ -3529,8 +3567,6 @@ search_symbols (char *regexp, enum searc
 						&datum);
   }
 
-  retval_chain = make_cleanup (null_cleanup, NULL);
-
   /* Here, we search through the minimal symbol tables for functions
      and variables that match, and force their symbols to be read.
      This is in particular necessary for demangled variable names,
@@ -3579,14 +3615,16 @@ search_symbols (char *regexp, enum searc
       }
     }
 
+  found = NULL;
+  tail = NULL;
+  nfound = 0;
+  retval_chain = make_cleanup_free_search_symbols (&found);
+
   ALL_PRIMARY_SYMTABS (objfile, s)
   {
     bv = BLOCKVECTOR (s);
     for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++)
       {
-	struct symbol_search *prevtail = tail;
-	int nfound = 0;
-
 	b = BLOCKVECTOR_BLOCK (bv, i);
 	ALL_BLOCK_SYMBOLS (b, iter, sym)
 	  {
@@ -3621,7 +3659,7 @@ search_symbols (char *regexp, enum searc
 			    && SYMBOL_CLASS (sym) == LOC_TYPEDEF))))
 	      {
 		/* match */
-		psr = (struct symbol_search *)
+		struct symbol_search *psr = (struct symbol_search *)
 		  xmalloc (sizeof (struct symbol_search));
 		psr->block = i;
 		psr->symtab = real_symtab;
@@ -3629,31 +3667,22 @@ search_symbols (char *regexp, enum searc
 		psr->msymbol = NULL;
 		psr->next = NULL;
 		if (tail == NULL)
-		  sr = psr;
+		  found = 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;
-
-		make_cleanup_free_search_symbols (sr);
-	      }
-	    else
-	      tail = sort_search_symbols (prevtail, nfound);
-	  }
       }
   }
 
+  if (found != NULL)
+    {
+      sort_search_symbols_remove_dups (found, nfound, &found, &tail);
+      /* Note: nfound is no longer useful beyond this point.  */
+    }
+
   /* If there are no eyes, avoid all contact.  I mean, if there are
      no debug symbols, then print directly from the msymbol_vector.  */
 
@@ -3685,18 +3714,15 @@ search_symbols (char *regexp, enum searc
 			== NULL)
 		      {
 			/* match */
-			psr = (struct symbol_search *)
+			struct symbol_search *psr = (struct symbol_search *)
 			  xmalloc (sizeof (struct symbol_search));
 			psr->block = i;
 			psr->msymbol = msymbol;
 			psr->symtab = NULL;
 			psr->symbol = NULL;
 			psr->next = NULL;
 			if (tail == NULL)
-			  {
-			    sr = psr;
-			    make_cleanup_free_search_symbols (sr);
-			  }
+			  found = psr;
 			else
 			  tail->next = psr;
 			tail = psr;
@@ -3709,7 +3735,7 @@ search_symbols (char *regexp, enum searc
 
   discard_cleanups (retval_chain);
   do_cleanups (old_chain);
-  *matches = sr;
+  *matches = found;
 }
 
 /* Helper function for symtab_symbol_info, this function uses
@@ -3791,7 +3817,7 @@ symtab_symbol_info (char *regexp, enum s
 
   /* Must make sure that if we're interrupted, symbols gets freed.  */
   search_symbols (regexp, kind, 0, (char **) NULL, &symbols);
-  old_chain = make_cleanup_free_search_symbols (symbols);
+  old_chain = make_cleanup_free_search_symbols (&symbols);
 
   if (regexp != NULL)
     printf_filtered (_("All %ss matching regular expression \"%s\":\n"),
@@ -3893,7 +3919,7 @@ rbreak_command (char *regexp, int from_t
     }
 
   search_symbols (regexp, FUNCTIONS_DOMAIN, nfiles, files, &ss);
-  old_chain = make_cleanup_free_search_symbols (ss);
+  old_chain = make_cleanup_free_search_symbols (&ss);
   make_cleanup (free_current_contents, &string);
 
   start_rbreak_breakpoints ();
Index: symtab.h
===================================================================
RCS file: /cvs/src/src/gdb/symtab.h,v
retrieving revision 1.235
diff -u -p -r1.235 symtab.h
--- symtab.h	12 Apr 2013 14:49:25 -0000	1.235
+++ symtab.h	16 Jun 2013 03:07:02 -0000
@@ -1288,7 +1292,7 @@ struct symbol_search
 
   /* Information describing what was found.
 
-     If symtab abd symbol are NOT NULL, then information was found
+     If symtab and symbol are NOT NULL, then information was found
      for this match.  */
   struct symtab *symtab;
   struct symbol *symbol;
@@ -1305,7 +1309,7 @@ extern void search_symbols (char *, enum
 			    struct symbol_search **);
 extern void free_search_symbols (struct symbol_search *);
 extern struct cleanup *make_cleanup_free_search_symbols (struct symbol_search
-							 *);
+							 **);
 
 /* The name of the ``main'' function.
    FIXME: cagney/2001-03-20: Can't make main_name() const since some

Re: [RFA] remove duplicates in search_symbols

[Doug Evans]

On Sat, Jun 15, 2013 at 8:45 PM, Doug Evans <dje@google.com> wrote:
> Hi.
> Depending on the app a large number of duplicates can be found
> by search_symbols.  This patch removes the dups.
>
> It also will change the output of "info fun|var|types" to be sorted
> by file name.
>
> Regression tested on amd64-linux, with/without fission.
>
> Ok to check in?
>
> 2013-06-15  Doug Evans  <dje@google.com>
>
>         * symtab.c (do_free_search_symbols_cleanup): Change arg to,
>         effectively, struct symbol_search **.
>         (make_cleanup_free_search_symbols): Change arg to struct symbol_search **.
>         All callers updated.
>         (compare_search_syms): Compare symtab file name and block as well.
>         (search_symbols_equal): New function.
>         (sort_search_symbols_remove_dups): Renamed from sort_search_symbols.
>         New args new_head, new_tail.  Result is now void.  Remove dups after
>         sorting the symbols.
>         (search_symbols): Sort all found symbols once, after all have been found,
>         and remove duplicates.  Simplify cleanup tracking of result.
>         * symtab.h (make_cleanup_free_search_symbols): Update prototype.

Ping.

Re: [RFA] remove duplicates in search_symbols

[Tom Tromey]

>>>>> "Doug" == Doug Evans <dje@google.com> writes:

>> 2013-06-15  Doug Evans  <dje@google.com>
>> 
>> * symtab.c (do_free_search_symbols_cleanup): Change arg to,
>> effectively, struct symbol_search **.
>> (make_cleanup_free_search_symbols): Change arg to struct
>> symbol_search **.
>> All callers updated.
>> (compare_search_syms): Compare symtab file name and block as well.
>> (search_symbols_equal): New function.
>> (sort_search_symbols_remove_dups): Renamed from sort_search_symbols.
>> New args new_head, new_tail.  Result is now void.  Remove dups after
>> sorting the symbols.
>> (search_symbols): Sort all found symbols once, after all
>> have been found,
>> and remove duplicates.  Simplify cleanup tracking of result.
>> * symtab.h (make_cleanup_free_search_symbols): Update prototype.

Doug> Ping.

Looks good to me.

It seems make_cleanup_free_search_symbols isn't used outside of
symtab.c.

Tom

Re: [RFA] remove duplicates in search_symbols

[Doug Evans]

Tom Tromey writes:
 > >>>>> "Doug" == Doug Evans <dje@google.com> writes:
 > 
 > >> 2013-06-15  Doug Evans  <dje@google.com>
 > >> 
 > >> * symtab.c (do_free_search_symbols_cleanup): Change arg to,
 > >> effectively, struct symbol_search **.
 > >> (make_cleanup_free_search_symbols): Change arg to struct
 > >> symbol_search **.
 > >> All callers updated.
 > >> (compare_search_syms): Compare symtab file name and block as well.
 > >> (search_symbols_equal): New function.
 > >> (sort_search_symbols_remove_dups): Renamed from sort_search_symbols.
 > >> New args new_head, new_tail.  Result is now void.  Remove dups after
 > >> sorting the symbols.
 > >> (search_symbols): Sort all found symbols once, after all
 > >> have been found,
 > >> and remove duplicates.  Simplify cleanup tracking of result.
 > >> * symtab.h (make_cleanup_free_search_symbols): Update prototype.
 > 
 > Doug> Ping.
 > 
 > Looks good to me.
 > 
 > It seems make_cleanup_free_search_symbols isn't used outside of
 > symtab.c.

Thanks.
Yeah, all of these are not used outside of symtab.c.

struct symbol_search { ... };
extern void search_symbols (char *, enum search_domain, int, char **,
			    struct symbol_search **);
extern void free_search_symbols (struct symbol_search *);
extern struct cleanup *make_cleanup_free_search_symbols (struct symbol_search
							 **);

I'm semi-ambivalent about keeping them as an exported part of the API
so I left making them static for another pass.

Re: [RFA] remove duplicates in search_symbols

[Keith Seitz]

On 08/01/2013 04:49 PM, Doug Evans wrote:
> struct symbol_search { ... };
> extern void search_symbols (char *, enum search_domain, int, char **,
> 			    struct symbol_search **);
> extern void free_search_symbols (struct symbol_search *);
> extern struct cleanup *make_cleanup_free_search_symbols (struct symbol_search
> 							 **);
>
> I'm semi-ambivalent about keeping them as an exported part of the API
> so I left making them static for another pass.

FWIW, Insight uses struct symbol_search, search_symbols, and 
make_cleanup_free_search_symbols. It would be nice if some sort of 
public API for this was maintained.

Keith

Re: [RFA] remove duplicates in search_symbols

[Tom Tromey]

>>>>> "Keith" == Keith Seitz <keiths@redhat.com> writes:

Keith> FWIW, Insight uses struct symbol_search, search_symbols, and
Keith> make_cleanup_free_search_symbols. It would be nice if some sort of
Keith> public API for this was maintained.

Perhaps a comment would be nice.
I have a feeling I've gone though this more than once.

Tom

Re: [RFA] remove duplicates in search_symbols

[Doug Evans]

On Fri, Aug 2, 2013 at 6:46 AM, Tom Tromey <tromey@redhat.com> wrote:
>>>>>> "Keith" == Keith Seitz <keiths@redhat.com> writes:
>
> Keith> FWIW, Insight uses struct symbol_search, search_symbols, and
> Keith> make_cleanup_free_search_symbols. It would be nice if some sort of
> Keith> public API for this was maintained.
>
> Perhaps a comment would be nice.
> I have a feeling I've gone though this more than once.

Heh.  Twas my thought but I went to add such a comment and found one
already there.

/* Symbol searching */
/* Note: struct symbol_search, search_symbols, et.al. are declared
here,
   instead of making them local to symtab.c, for gdbtk's sake.  */

[I could make it more prevalent though.  Say a comment at the
definition site of each function or some such?]

Re: [RFA] remove duplicates in search_symbols

[Tom Tromey]

>>>>> "Doug" == Doug Evans <dje@google.com> writes:

Doug> /* Symbol searching */
Doug> /* Note: struct symbol_search, search_symbols, et.al. are declared
Doug> here,
Doug>    instead of making them local to symtab.c, for gdbtk's sake.  */

Funny.

Doug> [I could make it more prevalent though.  Say a comment at the
Doug> definition site of each function or some such?]

I hope the above is good enough.
I didn't notice it once, but OTOH that implies that I'd probably miss
other comments as well.

Tom