Adding SearchableList for implementing a list with fast search capability.

src/list-inl.h

 // Copyright 2006-2009 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 183 matching lines @@
 
 template<typename T, class P>
 void List<T, P>::Initialize(int capacity) {
   ASSERT(capacity >= 0);
   data_ = (capacity > 0) ? NewData(capacity) : NULL;
   capacity_ = capacity;
   length_ = 0;
 }
 
 
+template<typename T, class P>
+void SearchableList<T, P>::Add(const T& element) {
+  is_sorted_ = false;
+  List<T, P>::Add(element);
+}
+
+
+template<typename T, class P>
+void SearchableList<T, P>::AddAll(const List<T, P>& other) {
+  is_sorted_ = false;
+  List<T, P>::AddAll(other);
+}
+
+
+template<typename T, class P>
+Vector<T> SearchableList<T, P>::AddBlock(T value, int count) {
+  is_sorted_ = false;
+  return List<T, P>::AddBlock(value, count);
+}
+
+
+template<typename T, class P>
+bool SearchableList<T, P>::Contains(const T& elm) {

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

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.

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

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. 

+  if (is_sorted_) {
+    return ContainsSorted(elm);
+  }
+  return List<T, P>::Contains(elm);
+}
+
+
+template<typename T, class P>
+void SearchableList<T, P>::Sort() {
+  if (!is_sorted_) {
+    List<T, P>::Sort(comparator_);
+    is_sorted_ = true;
+  }
+}
+
+
+template<typename T, class P>
+bool SearchableList<T, P>::ContainsSorted(const T& elm) {
+  typedef int (*RawComparer)(const void*, const void*);
+  return (NULL != bsearch(&elm, List<T, P>::data(), List<T, P>::length(),

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

One argument per line when splitting.

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

Done.

+                          sizeof(T),
+                          reinterpret_cast<RawComparer>(comparator_)));
+}
+
+
 } }  // namespace v8::internal
 
 #endif  // V8_LIST_INL_H_