This is the mail archive of the gdb-patches@sources.redhat.com mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [rfa] tweak sorting of partial symbols


David Carlton writes:
 > Right now, partial symbols are sorted via strcmp.  But if you look up
 > NAME in the partial symbols, then what lookup_partial_symbol does is:
 > 
 > * Figure out where NAME fits under the strcmp ordering.
 > 
 > * Then, starting from that place in the partial symbols, look at all
 >   the partial symbols until we either find the right one or until we
 >   find one such that strcmp_iw(SYM_NAME,NAME) doesn't match.
 > 
 > In particular, there's the assumption that all symbols for which
 > strcmp_iw(SYM_NAME,NAME) matches are sorted via strcmp into a group
 > that starts out at the position where strcmp would put NAME.
 > 

It seems innocuous enough, and intuitively it makes sense, but can you
show me a case where it makes a difference? I.e some set of strings
for which the order would change?

I tried a few sets of strings and couldn't trigger any differences.

elena


 > But I can't see why this should be true.  So this patch adds a new
 > function strcmp_iw_ordered (not the best name, perhaps) that is
 > suitable for use via qsort (unlike strcmp_iw, which doesn't provide an
 > ordering or even an equivalence relation) and which does have the
 > desired property.  It does this by ignoring whitespace and by treating
 > '(' as the smallest non-NULL character (because, in some
 > circumstances, strcmp_iw wants to ignore matches where the difference
 > starts with an open parenthesis).
 > 
 > In practice, this should rarely if ever pose a problem, but it's a
 > good idea for the sake of pedanticism.  After this one goes in, I'll
 > also commit that patch to make_symbol_overload_list that we talked
 > about earlier today.
 > 
 > Tested on i686-pc-linux-gnu/GCC3.1/DWARF-2; OK to apply?
 > 
 > David Carlton
 > carlton at math dot stanford dot edu
 > 
 > 2003-02-21  David Carlton  <carlton at math dot stanford dot edu>
 > 
 > 	* symtab.c (lookup_partial_symbol): Use strcmp_iw_ordered to
 > 	do the comparison, not strcmp.
 > 	* symfile.c (compare_psymbols): Ditto.
 > 	* defs.h: Declare strcmp_iw_ordered.
 > 	* utils.c (strcmp_iw_ordered): New function.
 > 
 > Index: symtab.c
 > ===================================================================
 > RCS file: /cvs/src/src/gdb/symtab.c,v
 > retrieving revision 1.90
 > diff -u -p -r1.90 symtab.c
 > --- symtab.c	20 Feb 2003 22:07:38 -0000	1.90
 > +++ symtab.c	22 Feb 2003 01:05:45 -0000
 > @@ -1379,9 +1379,10 @@ lookup_partial_symbol (struct partial_sy
 >        do_linear_search = 0;
 >  
 >        /* Binary search.  This search is guaranteed to end with center
 > -         pointing at the earliest partial symbol with the correct
 > -         name.  At that point *all* partial symbols with that name
 > -         will be checked against the correct namespace. */
 > +         pointing at the earliest partial symbol whose name might be
 > +         correct.  At that point *all* partial symbols with an
 > +         appropriate name will be checked against the correct
 > +         namespace.  */
 >  
 >        bottom = start;
 >        top = start + length - 1;
 > @@ -1396,7 +1397,7 @@ lookup_partial_symbol (struct partial_sy
 >  	    {
 >  	      do_linear_search = 1;
 >  	    }
 > -	  if (strcmp (SYMBOL_PRINT_NAME (*center), name) >= 0)
 > +	  if (strcmp_iw_ordered (SYMBOL_PRINT_NAME (*center), name) >= 0)
 >  	    {
 >  	      top = center;
 >  	    }
 > Index: symfile.c
 > ===================================================================
 > RCS file: /cvs/src/src/gdb/symfile.c,v
 > retrieving revision 1.89
 > diff -u -p -r1.89 symfile.c
 > --- symfile.c	20 Feb 2003 17:17:25 -0000	1.89
 > +++ symfile.c	22 Feb 2003 01:05:40 -0000
 > @@ -213,52 +213,17 @@ compare_symbols (const void *s1p, const 
 >    return (strcmp (SYMBOL_PRINT_NAME (*s1), SYMBOL_PRINT_NAME (*s2)));
 >  }
 >  
 > -/*
 > -
 > -   LOCAL FUNCTION
 > -
 > -   compare_psymbols -- compare two partial symbols by name
 > -
 > -   DESCRIPTION
 > -
 > -   Given pointers to pointers to two partial symbol table entries,
 > -   compare them by name and return -N, 0, or +N (ala strcmp).
 > -   Typically used by sorting routines like qsort().
 > -
 > -   NOTES
 > -
 > -   Does direct compare of first two characters before punting
 > -   and passing to strcmp for longer compares.  Note that the
 > -   original version had a bug whereby two null strings or two
 > -   identically named one character strings would return the
 > -   comparison of memory following the null byte.
 > -
 > - */
 > +/* This compares two partial symbols by names, using strcmp_iw_ordered
 > +   for the comparison.  */
 >  
 >  static int
 >  compare_psymbols (const void *s1p, const void *s2p)
 >  {
 > -  register struct partial_symbol **s1, **s2;
 > -  register char *st1, *st2;
 > -
 > -  s1 = (struct partial_symbol **) s1p;
 > -  s2 = (struct partial_symbol **) s2p;
 > -  st1 = SYMBOL_PRINT_NAME (*s1);
 > -  st2 = SYMBOL_PRINT_NAME (*s2);
 > -
 > +  struct partial_symbol *const *s1 = s1p;
 > +  struct partial_symbol *const *s2 = s2p;
 >  
 > -  if ((st1[0] - st2[0]) || !st1[0])
 > -    {
 > -      return (st1[0] - st2[0]);
 > -    }
 > -  else if ((st1[1] - st2[1]) || !st1[1])
 > -    {
 > -      return (st1[1] - st2[1]);
 > -    }
 > -  else
 > -    {
 > -      return (strcmp (st1, st2));
 > -    }
 > +  return strcmp_iw_ordered (SYMBOL_PRINT_NAME (*s1),
 > +			    SYMBOL_PRINT_NAME (*s2));
 >  }
 >  
 >  void
 > Index: defs.h
 > ===================================================================
 > RCS file: /cvs/src/src/gdb/defs.h,v
 > retrieving revision 1.113
 > diff -u -p -r1.113 defs.h
 > --- defs.h	14 Feb 2003 13:58:05 -0000	1.113
 > +++ defs.h	22 Feb 2003 01:05:31 -0000
 > @@ -305,6 +305,8 @@ extern void notice_quit (void);
 >  
 >  extern int strcmp_iw (const char *, const char *);
 >  
 > +extern int strcmp_iw_ordered (const char *, const char *);
 > +
 >  extern int streq (const char *, const char *);
 >  
 >  extern int subset_compare (char *, char *);
 > Index: utils.c
 > ===================================================================
 > RCS file: /cvs/src/src/gdb/utils.c,v
 > retrieving revision 1.96
 > diff -u -p -r1.96 utils.c
 > --- utils.c	7 Feb 2003 00:27:30 -0000	1.96
 > +++ utils.c	22 Feb 2003 01:05:36 -0000
 > @@ -2358,6 +2358,64 @@ strcmp_iw (const char *string1, const ch
 >    return (*string1 != '\0' && *string1 != '(') || (*string2 != '\0');
 >  }
 >  
 > +/* This is like strcmp except that it ignores whitespace and treats
 > +   '(' as the first non-NULL character in terms of ordering.  Like
 > +   strcmp (and unlike strcmp_iw), it returns negative if STRING1 <
 > +   STRING2, 0 if STRING2 = STRING2, and positive if STRING1 > STRING2
 > +   according to that ordering.
 > +
 > +   If a list is sorted according to this function and if you want to
 > +   find names in the list that match some fixed NAME according to
 > +   strcmp_iw(LIST_ELT, NAME), then the place to start looking is right
 > +   where this function would put NAME.  */
 > +
 > +int
 > +strcmp_iw_ordered (const char *string1, const char *string2)
 > +{
 > +  while ((*string1 != '\0') && (*string2 != '\0'))
 > +    {
 > +      while (isspace (*string1))
 > +	{
 > +	  string1++;
 > +	}
 > +      while (isspace (*string2))
 > +	{
 > +	  string2++;
 > +	}
 > +      if (*string1 != *string2)
 > +	{
 > +	  break;
 > +	}
 > +      if (*string1 != '\0')
 > +	{
 > +	  string1++;
 > +	  string2++;
 > +	}
 > +    }
 > +
 > +  switch (*string1)
 > +    {
 > +      /* Characters are non-equal unless they're both '\0'; we want to
 > +	 make sure we get the comparison right according to our
 > +	 comparison in the cases where one of them is '\0' or '('.  */
 > +    case '\0':
 > +      if (*string2 == '\0')
 > +	return 0;
 > +      else
 > +	return -1;
 > +    case '(':
 > +      if (*string2 == '\0')
 > +	return 1;
 > +      else
 > +	return -1;
 > +    default:
 > +      if (*string2 == '(')
 > +	return 1;
 > +      else
 > +	return *string1 - *string2;
 > +    }
 > +}
 > +
 >  /* A simple comparison function with opposite semantics to strcmp.  */
 >  
 >  int


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]