53062 - Move |Find| and |RFind| up into |nsAReadableString|

Status: RESOLVED FIXED

(Core :: XPCOM, defect, P3)

Description

[Scott Collins]

This is critical for Vidur's parser work.

Comment 1

[Scott Collins]

Attachment: Here's member |Find| ... still O(m*n), like what we have now

Comment 2

[Scott Collins]

I still need to test the |Find| patch, above; I'm working on |RFind|.  These 
implementations should have the same performance as our old favorites in |
ns[C]String|.

Comment 3

[Scott Collins]

Ooops.  That first nested |while| should read

  while ( aSearchStart != aSearchEnd && *aPatternStart != *aSearchStart )
  ........................................................^

Sorry.

Comment 4

[Scott Collins]

When I attach the next patch it will include |RFind| and a fixed version of the 
previously attached |Find|

Comment 5

[Scott Collins]

OK, after discussion with Vidur ... we probably don't want to make this signature 
a member function.  The following patch fixes the error mentioned above; moves 
the implementation to non-member functions in "nsReadableUtils.h", and to avoid 
the possibility of `type-unification errors' ... made the visible API be non-
template functions.  The implementation remains templatized.

Comment 6

[Scott Collins]

Attachment: better patch to add |Find| functionality ... this time as a non-member

Comment 7

[Scott Collins]

Note also that error handling is sligtly improved in the above patch (detecting 
empty search range)

Comment 8

[Scott Collins]

OK, new patch includes a (theoretically) working equivalent for |RFind|.  More 
testing to do, and either Vidur or I will also add equivalents for |FindChar|.

Comment 9

[Scott Collins]

Attachment: this is everything for |Find| and |RFind| equivalents (needs testing)

Comment 10

[vidur (gone)]

An iterator version of |FindChar|:

template <class CharT>
inline // probably wishful thinking
PRBool
FindCharInReadable_Impl( CharT aChar,
                         nsReadingIterator<CharT>& aSearchStart,
                         nsReadingIterator<CharT>& aSearchEnd )
  {
    while ( aSearchStart != aSearchEnd )
      {
        PRInt32 fragmentLength;
        if ( SameFragment(aSearchStart, aSearchEnd) ) 
          fragmentLength = aSearchEnd.get() - aSearchStart.get();
        else
          fragmentLength = aSearchStart.size_forward();

        const CharT* charFoundAt = nsCharTraits<CharT>::find(aSearchStart.get(),
fragmentLength, aChar);
        if ( charFoundAt ) {
          aSearchStart.advance( charFoundAt - aSearchStart.get() );
          return PR_TRUE;
        }

        aSearchStart.advance(fragmentLength);
      }

    return PR_FALSE;
  }


NS_COM 
PRBool 
FindCharInReadable( PRUnichar aChar, nsReadingIterator<PRUnichar>& aSearchStart,
nsReadingIterator<PRUnichar>& aSearchEnd )
  {
    return FindCharInReadable_Impl(aChar, aSearchStart, aSearchEnd);
  }

NS_COM 
PRBool 
FindCharInReadable( char aChar, nsReadingIterator<char>& aSearchStart,
nsReadingIterator<char>& aSearchEnd )
  {
    return FindCharInReadable_Impl(aChar, aSearchStart, aSearchEnd);
  } 

Comment 11

[Scott Collins]

Attachment: this complete patch fixes a |Find| bug revealed by testing

Comment 12

[Scott Collins]

well this has been checked in too, right Vidur?  (LXR makes it look like it's
in, anyway)