Adding SearchableList for implementing a list with fast search capability.

src/list.h

Index: src/list.h
===================================================================
--- src/list.h	(revision 6353)
+++ src/list.h	(working copy)
@@ -137,6 +137,9 @@
 
   INLINE(void Initialize(int capacity));
 
+ protected:
+  INLINE(T* data() const) { return data_; }
+
  private:
   T* data_;
   int capacity_;
@@ -159,6 +162,48 @@
   DISALLOW_COPY_AND_ASSIGN(List);
 };
 
+
+// The SearchableList is just like the List except that it keeps track of
+// whether its elements are sorted.  If sorted, the Contains method will
+// take advantage of the list having being sorted and use a binary search on
+// it.  Otherwise, it will let the super class List do a linear look up.
+//
+// The SearchableList is not sorted automatically.  The user must call Sort()
+// when appropriate.  This allows multiple Add()s to be called without
+// repeatedly incurring the cost of sorting.
+template <typename T, class P>
+class SearchableList: public List<T, P> {
+ public:
+  explicit SearchableList(int (*cmp)(const T* x, const T* y))
+      : is_sorted_(false), comparator_(cmp) {}
+
+  // Adds a copy of the given 'element' to the end of the list,
+  // expanding the list if necessary.
+  void Add(const T& element);
+
+  // Add all the elements from the argument list to this list.
+  void AddAll(const List<T, P>& other);
+
+  // Added 'count' elements with the value 'value' and returns a
+  // vector that allows access to the elements.  The vector is valid
+  // until the next change is made to this list.
+  Vector<T> AddBlock(T value, int count);
+
+  bool Contains(const T& elm);
+
+  // Sort all list elements (using QuickSort)

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

End comment with period. Extend comment with information that sorting is "free"
if the list is already sorted.

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

Done.

+  void Sort();
+

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

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]

Done.

+ private:
+  bool is_sorted_;
+  int (*comparator_)(const T* x, const T* y);
+
+  bool ContainsSorted(const T& elm);
+
+  DISALLOW_COPY_AND_ASSIGN(SearchableList);
+};
+
+
 } }  // namespace v8::internal
 
 #endif  // V8_LIST_H_