Adding SearchableList for implementing a list with fast search capability.

src/list.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 119 matching lines @@
   void Iterate(void (*callback)(T* x));
   template<class Visitor>
   void Iterate(Visitor* visitor);
 
   // Sort all list entries (using QuickSort)
   void Sort(int (*cmp)(const T* x, const T* y));
   void Sort();
 
   INLINE(void Initialize(int capacity));
 
+ protected:
+  INLINE(T* data() const) { return data_; }
+
  private:
   T* data_;
   int capacity_;
   int length_;
 
   INLINE(T* NewData(int n))  { return static_cast<T*>(P::New(n * sizeof(T))); }
   INLINE(void DeleteData(T* data))  { P::Delete(data); }
 
   // Increase the capacity of a full list, and add an element.
   // List must be full already.
   void ResizeAdd(const T& element);
 
   // Inlined implementation of ResizeAdd, shared by inlined and
   // non-inlined versions of ResizeAdd.
   void ResizeAddInternal(const T& element);
 
   // Resize the list.
   void Resize(int new_capacity);
 
   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);
+  bool Contains(const T& elm, bool ensure_sorted);
+
+  // Sort all list elements (using QuickSort).  This function only performs
+  // a sort if the list is not already sorted to begin with.
+  void Sort();
+
+  bool is_sorted() const { return is_sorted_; }
+
+ 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_