Reviewers: Michail Naganov, Description: Adding BSearchList for implementing a list with fast search capability.
Please review this at http://codereview.chromium.org/6265002/ SVN Base: http://v8.googlecode.com/svn/branches/bleeding_edge/ Affected files: M src/list-inl.h M src/list.h Index: src/list-inl.h =================================================================== --- src/list-inl.h (revision 6302) +++ src/list-inl.h (working copy) @@ -201,6 +201,49 @@ } +template<typename T, class P> +void BSearchList<T, P>::Add(const T& element) { + is_sorted_ = false; + List<T, P>::Add(element); +} + +template<typename T, class P> +void BSearchList<T, P>::AddAll(const List<T, P>& other) { + is_sorted_ = false; + List<T, P>::AddAll(other); +} + +template<typename T, class P> +Vector<T> BSearchList<T, P>::AddBlock(T value, int count) { + is_sorted_ = false; + return List<T, P>::AddBlock(value, count); +} + +template<typename T, class P> +bool BSearchList<T, P>::Contains(const T& elm) { + if (is_sorted_) { + return BSearchContains(elm); + } + return List<T, P>::Contains(elm); +} + +template<typename T, class P> +void BSearchList<T, P>::Sort() { + if (!is_sorted_) { + List<T, P>::Sort(comparator_); + is_sorted_ = true; + } +} + + +template<typename T, class P> +bool BSearchList<T, P>::BSearchContains(const T& elm) { + typedef int (*RawComparer)(const void*, const void*); + return (NULL != bsearch(&elm, List<T, P>::data(), List<T, P>::length(), + sizeof(T), + reinterpret_cast<RawComparer>(comparator_))); +} + } } // namespace v8::internal #endif // V8_LIST_INL_H_ Index: src/list.h =================================================================== --- src/list.h (revision 6302) +++ 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,40 @@ DISALLOW_COPY_AND_ASSIGN(List); }; + +template <typename T, class P> +class BSearchList: public List<T, P> { + public: + + BSearchList(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 entries (using QuickSort) + void Sort(); + + private: + bool is_sorted_; + int (*comparator_)(const T* x, const T* y); + + bool BSearchContains(const T& elm); + + DISALLOW_COPY_AND_ASSIGN(BSearchList); +}; + } } // namespace v8::internal #endif // V8_LIST_H_ -- v8-dev mailing list v8-dev@googlegroups.com http://groups.google.com/group/v8-dev
