Adding SearchableList for implementing a list with fast search capability.

Adding SearchableList for implementing a list with fast search capability.

[marklam, 2011-01-14 00:16:32]

Mikhail,
FYI, I just got some feedback from Søren on the list implementation and other
bits.  I'll incorporate all these changes and then upload the updates.  I'll let
you know when the revised changes are ready.  Thanks.

[marklam, 2011-01-18 02:50:51]

Mikhail, Søren,
I've incorporated Søren's suggested changes.  Please take a look.  Thanks.

[Søren Thygesen Gjesse, 2011-01-18 07:44:40]

LGTM, with comments addressed.

http://codereview.chromium.org/6265002/diff/6001/src/list-inl.h
File src/list-inl.h (right):

http://codereview.chromium.org/6265002/diff/6001/src/list-inl.h#newcode226
src/list-inl.h:226: bool SearchableList<T, P>::Contains(const T& elm) {
Have you considered just sorting here if the list is not not already sorted? Or
maybe a second argument "bool ensure_sorted"? Maybe this is fine as is - it is
documented.

http://codereview.chromium.org/6265002/diff/6001/src/list-inl.h#newcode246
src/list-inl.h:246: return (NULL != bsearch(&elm, List<T, P>::data(), List<T,
P>::length(),
One argument per line when splitting.

http://codereview.chromium.org/6265002/diff/6001/src/list.h
File src/list.h (right):

http://codereview.chromium.org/6265002/diff/6001/src/list.h#newcode194
src/list.h:194: // Sort all list elements (using QuickSort)
End comment with period. Extend comment with information that sorting is "free"
if the list is already sorted.

http://codereview.chromium.org/6265002/diff/6001/src/list.h#newcode196
src/list.h:196: 
If you stick with the manual sorting I think there should be an accessor for the
is_sorted.

bool is_sorted() { return is_sorted_; }

[marklam, 2011-01-18 22:33:16]

Hi Søren,
I've made the necessary changes and addressed your comments.  I've also added
the globals.h change that should be part of this CL.

However, while investigating the use case for Sort() and Contains(), I
discovered that this SearchableList isn't actually in use in my lol
implementation anymore.  It was previously used in old retainer computation
code, but that code turned out to be slow and was replaced.

What is your policy on taking code like this?  It works.  It's a template and
doesn't cost anything if not instantiated, and it may be useful later, but is
not in use currently.  I don't mind if this CL is rejected.  Just thought I'd
ask to clarify the accepted practice.

Sorry for not verifying that this was still in use before contributing it. 
Thanks.

http://codereview.chromium.org/6265002/diff/6001/src/list-inl.h
File src/list-inl.h (right):

http://codereview.chromium.org/6265002/diff/6001/src/list-inl.h#newcode226
src/list-inl.h:226: bool SearchableList<T, P>::Contains(const T& elm) {
On 2011/01/18 07:44:40, Søren Gjesse wrote:
> Have you considered just sorting here if the list is not not already sorted?
Or
> maybe a second argument "bool ensure_sorted"? Maybe this is fine as is - it is
> documented.

Done.  I added a second Contains() which takes a bool ensure_sorted arg.  The
reason I can't make Contains() just sort is because of the following usage
pattern:

  void addElement(SomeElement* element) {
    if (!list.Contains()) {
      list.Add(element);
      if (list.length() > 5) {
        list.Sort();
      }
    }
  }

In my case, the use case may encounter a lot of lists that are small-ish, and
sorting automatically may cost more than a simple linear look up for the small
list.

http://codereview.chromium.org/6265002/diff/6001/src/list-inl.h#newcode246
src/list-inl.h:246: return (NULL != bsearch(&elm, List<T, P>::data(), List<T,
P>::length(),
On 2011/01/18 07:44:40, Søren Gjesse wrote:
> One argument per line when splitting.

Done.

http://codereview.chromium.org/6265002/diff/6001/src/list.h
File src/list.h (right):

http://codereview.chromium.org/6265002/diff/6001/src/list.h#newcode194
src/list.h:194: // Sort all list elements (using QuickSort)
On 2011/01/18 07:44:40, Søren Gjesse wrote:
> End comment with period. Extend comment with information that sorting is
"free"
> if the list is already sorted.

Done.

http://codereview.chromium.org/6265002/diff/6001/src/list.h#newcode196
src/list.h:196: 
On 2011/01/18 07:44:40, Søren Gjesse wrote:
> If you stick with the manual sorting I think there should be an accessor for
the
> is_sorted.
> 
> bool is_sorted() { return is_sorted_; }

Done.

[Søren Thygesen Gjesse, 2011-01-19 07:43:04]

When scanning through the lol change I did see bsearch used directly, but did
not think further about that.

Anyway if SearchableList will not be used I don't think we should add it to the
codebase. You can just revive this change if needed at some later point.

Just for the record there should also add some tests to test-list.cc as well
(sorry for not mentioning that earlier).

Closing the issue for now.

http://codereview.chromium.org/6265002/diff/13001/src/globals.h
File src/globals.h (right):

http://codereview.chromium.org/6265002/diff/13001/src/globals.h#newcode322
src/globals.h:322: template <typename T, class P = FreeStoreAllocationPolicy>
class BSearchList;
This should be SearchableList