| // Copyright 2014 The Android Open Source Project |
| // |
| // This software is licensed under the terms of the GNU General Public |
| // License version 2, as published by the Free Software Foundation, and |
| // may be copied, distributed, and modified under those terms. |
| // |
| // This program is distributed in the hope that it will be useful, |
| // but WITHOUT ANY WARRANTY; without even the implied warranty of |
| // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| // GNU General Public License for more details. |
| |
| #pragma once |
| |
| #include "android/base/Compiler.h" |
| #include "android/base/containers/HashUtils.h" |
| |
| namespace android { |
| namespace base { |
| |
| // A PointerSet<T> models a set referencing heap-allocated objects of type T. |
| // |
| // The objects are not owned by the PointerSet<T>, see ScopedPointerSet<T> |
| // instead if you want the set to also own the objects. |
| // |
| // Each object is identified by its address which serves as the hashing |
| // key. This makes the implementation simple, but also ensures that |
| // iterating over the same-constructed set will not provide the same |
| // result between two runs of the same program. |
| // |
| // Usage example: |
| // |
| // PointerSet<Foo> setOfFoos; // Creates new empty set. |
| // setOfFoos.add(foo1); // Add foo1 to the set. |
| // if (setOfFoos.contains(foo1)) { // Test whether the set contains foo1 |
| // setOfFoos.remove(foo1); // Remove foo1 from set. |
| // } |
| // CHECK(setOfFoos.empty()); |
| // CHECK(setOfFoos.size() == 0); |
| // |
| // Iterating over a set: |
| // |
| // PointerSet<Foo>::Iterator iter(&setOfFoos); |
| // while (iter.hasNext()) { |
| // Foo* foo = iter.next(); |
| // .. do something with foo |
| // } |
| // |
| // Note that the iterator becomes invalid if you add or remove objects |
| // to/from the set. |
| |
| class PointerSetBase { |
| public: |
| PointerSetBase(); |
| ~PointerSetBase(); |
| |
| class Iterator { |
| public: |
| explicit Iterator(PointerSetBase* set); |
| ~Iterator() {} |
| |
| inline bool hasNext() const { |
| return (mPos < mCapacity); |
| } |
| |
| void* next(); |
| private: |
| // No default constructor |
| Iterator(); |
| |
| DISALLOW_COPY_AND_ASSIGN(Iterator); |
| |
| void** mItems; |
| size_t mCapacity; |
| size_t mPos; |
| }; |
| |
| typedef size_t (*HashFunction)(const void* obj); |
| |
| struct DefaultTraits { |
| static size_t hash(const void* obj) { |
| return ::android::base::internal::pointerHash(obj); |
| } |
| }; |
| |
| protected: |
| bool empty() const { |
| return mCount == 0; |
| } |
| |
| size_t size() const { |
| return mCount; |
| } |
| |
| bool contains(const void* obj, HashFunction hashFunc) const; |
| |
| void clear(); |
| |
| void* addItem(void* obj, HashFunction hashFunc); |
| |
| void* removeItem(void* obj, HashFunction hashFunc); |
| |
| void** toArray() const; |
| |
| private: |
| //friend class PointerSetBase::Iterator; |
| |
| void maybeResize(HashFunction hashFunc); |
| |
| size_t mShift; |
| size_t mCount; |
| void** mItems; |
| }; |
| |
| template <typename T, |
| typename TRAITS = typename ::android::base::PointerSetBase::DefaultTraits> |
| class PointerSet : public PointerSetBase { |
| public: |
| // Default constructor creates an empty set. |
| PointerSet() : PointerSetBase() {}; |
| |
| // Destructor simply destroys the set, not the objects in it. |
| ~PointerSet() {} |
| |
| // Return true iff the set is empty. |
| bool empty() const { |
| return PointerSetBase::empty(); |
| } |
| |
| // Return the number of objects in the set. |
| size_t size() const { |
| return PointerSetBase::size(); |
| } |
| |
| // Return true iff the set contains object |obj|. Always return false |
| // if |obj| is NULL. |
| bool contains(const T* obj) const { |
| return PointerSetBase::contains(static_cast<const void*>(obj), |
| TRAITS::hash); |
| } |
| |
| // Remove all objects from the set. |
| void clear() { |
| PointerSetBase::clear(); |
| } |
| |
| // Add object |obj| to the set. Return true if the object was added, |
| // and false if it was already in the set. Always return false if |
| // |obj| is NULL. |
| bool add(T* obj) { |
| return PointerSetBase::addItem(obj, TRAITS::hash) != NULL; |
| } |
| |
| // Remove object |obj| from the set. Return true if the object was |
| // already in the set, and false otherwise. Return false if |obj| |
| // is NULL. |
| bool remove(T* obj) { |
| return PointerSetBase::removeItem(obj, TRAITS::hash) != NULL; |
| } |
| |
| // Iterator class for this set. Note that adding or removing items |
| // in the set makes the iterator invalid. Usage example is: |
| // |
| // PointerSet<Foo>::Iterator iter(&fooSet); |
| // while (iter.hasNext()) { |
| // Foo* foo = iter.next(); |
| // .. do something with |foo| |
| // } |
| class Iterator : public PointerSetBase::Iterator { |
| public: |
| Iterator(PointerSet* set) : PointerSetBase::Iterator(set) {} |
| |
| bool hasNext() const { |
| return PointerSetBase::Iterator::hasNext(); |
| } |
| |
| T* next() { |
| return reinterpret_cast<T*>(PointerSetBase::Iterator::next()); |
| } |
| }; |
| |
| // Create a heap-allocated array of size() pointers to the objects |
| // contained in the set. The array must be free()-ed by the caller. |
| // Return NULL if the set is empty. |
| T** toArray() const { |
| return reinterpret_cast<T**>(PointerSetBase::toArray()); |
| } |
| }; |
| |
| } // namespace base |
| } // namespace android |