multiset.hpp

00001 /*
00002  * Copyright (C) 2014 Pavel Kirienko <pavel.kirienko@gmail.com>
00003  */
00004 
00005 #ifndef UAVCAN_UTIL_MULTISET_HPP_INCLUDED
00006 #define UAVCAN_UTIL_MULTISET_HPP_INCLUDED
00007 
00008 #include <cassert>
00009 #include <cstdlib>
00010 #include <uavcan/util/linked_list.hpp>
00011 #include <uavcan/build_config.hpp>
00012 #include <uavcan/dynamic_memory.hpp>
00013 #include <uavcan/util/templates.hpp>
00014 #include <uavcan/util/placement_new.hpp>
00015 
00016 #if !defined(UAVCAN_CPP_VERSION) || !defined(UAVCAN_CPP11)
00017 # error UAVCAN_CPP_VERSION
00018 #endif
00019 
00020 namespace uavcan
00021 {
00022 /**
00023  * Slow but memory efficient unordered multiset. Unlike Map<>, this container does not move objects, so
00024  * they don't have to be copyable.
00025  *
00026  * Items will be allocated in the node's memory pool.
00027  */
00028 template <typename T>
00029 class UAVCAN_EXPORT Multiset : Noncopyable
00030 {
00031     struct Item : ::uavcan::Noncopyable
00032     {
00033         T* ptr;
00034 
00035 #if UAVCAN_CPP_VERSION >= UAVCAN_CPP11
00036         alignas(T) unsigned char pool[sizeof(T)];       ///< Memory efficient version
00037 #else
00038         union
00039         {
00040             unsigned char pool[sizeof(T)];
00041             /*
00042              * Such alignment does not guarantee safety for all types (only for libuavcan internal ones);
00043              * however, increasing it is too memory inefficient. So it is recommended to use C++11, where
00044              * this issue is resolved with alignas() (see above).
00045              */
00046             void* _aligner1_;
00047             long long _aligner2_;
00048         };
00049 #endif
00050 
00051         Item()
00052             : ptr(UAVCAN_NULLPTR)
00053         {
00054             fill_n(pool, sizeof(pool), static_cast<unsigned char>(0));
00055         }
00056 
00057         ~Item() { destroy(); }
00058 
00059         bool isConstructed() const { return ptr != UAVCAN_NULLPTR; }
00060 
00061         void destroy()
00062         {
00063             if (ptr != UAVCAN_NULLPTR)
00064             {
00065                 ptr->~T();
00066                 ptr = UAVCAN_NULLPTR;
00067                 fill_n(pool, sizeof(pool), static_cast<unsigned char>(0));
00068             }
00069         }
00070     };
00071 
00072 private:
00073     struct Chunk : LinkedListNode<Chunk>
00074     {
00075         enum { NumItems = (MemPoolBlockSize - sizeof(LinkedListNode<Chunk> )) / sizeof(Item) };
00076         Item items[NumItems];
00077 
00078         Chunk()
00079         {
00080             StaticAssert<(static_cast<unsigned>(NumItems) > 0)>::check();
00081             IsDynamicallyAllocatable<Chunk>::check();
00082             UAVCAN_ASSERT(!items[0].isConstructed());
00083         }
00084 
00085         static Chunk* instantiate(IPoolAllocator& allocator)
00086         {
00087             void* const praw = allocator.allocate(sizeof(Chunk));
00088             if (praw == UAVCAN_NULLPTR)
00089             {
00090                 return UAVCAN_NULLPTR;
00091             }
00092             return new (praw) Chunk();
00093         }
00094 
00095         static void destroy(Chunk*& obj, IPoolAllocator& allocator)
00096         {
00097             if (obj != UAVCAN_NULLPTR)
00098             {
00099                 obj->~Chunk();
00100                 allocator.deallocate(obj);
00101                 obj = UAVCAN_NULLPTR;
00102             }
00103         }
00104 
00105         Item* findFreeSlot()
00106         {
00107             for (unsigned i = 0; i < static_cast<unsigned>(NumItems); i++)
00108             {
00109                 if (!items[i].isConstructed())
00110                 {
00111                     return items + i;
00112                 }
00113             }
00114             return UAVCAN_NULLPTR;
00115         }
00116     };
00117 
00118     /*
00119      * Data
00120      */
00121     LinkedListRoot<Chunk>  list_;
00122     IPoolAllocator& allocator_;
00123 
00124     /*
00125      * Methods
00126      */
00127     Item* findOrCreateFreeSlot();
00128 
00129     void compact();
00130 
00131     enum RemoveStrategy { RemoveOne, RemoveAll };
00132 
00133     template <typename Predicate>
00134     void removeWhere(Predicate predicate, RemoveStrategy strategy);
00135 
00136     struct YesPredicate
00137     {
00138         bool operator()(const T&) const { return true; }
00139     };
00140 
00141     struct IndexPredicate : ::uavcan::Noncopyable
00142     {
00143         unsigned index;
00144         IndexPredicate(unsigned target_index)
00145             : index(target_index)
00146         { }
00147 
00148         bool operator()(const T&)
00149         {
00150             return index-- == 0;
00151         }
00152     };
00153 
00154     struct ComparingPredicate
00155     {
00156         const T& reference;
00157 
00158         ComparingPredicate(const T& ref)
00159             : reference(ref)
00160         { }
00161 
00162         bool operator()(const T& sample)
00163         {
00164             return reference == sample;
00165         }
00166     };
00167 
00168     template<typename Operator>
00169     struct OperatorToFalsePredicateAdapter : ::uavcan::Noncopyable
00170     {
00171         Operator oper;
00172 
00173         OperatorToFalsePredicateAdapter(Operator o)
00174             : oper(o)
00175         { }
00176 
00177         bool operator()(T& item)
00178         {
00179             oper(item);
00180             return false;
00181         }
00182 
00183         bool operator()(const T& item) const
00184         {
00185             oper(item);
00186             return false;
00187         }
00188     };
00189 
00190 public:
00191     Multiset(IPoolAllocator& allocator)
00192         : allocator_(allocator)
00193     { }
00194 
00195     ~Multiset()
00196     {
00197         clear();
00198     }
00199 
00200     /**
00201      * Creates one item in-place and returns a pointer to it.
00202      * If creation fails due to lack of memory, UAVCAN_NULLPTR will be returned.
00203      * Complexity is O(N).
00204      */
00205     T* emplace()
00206     {
00207         Item* const item = findOrCreateFreeSlot();
00208         if (item == UAVCAN_NULLPTR)
00209         {
00210             return UAVCAN_NULLPTR;
00211         }
00212         UAVCAN_ASSERT(item->ptr == UAVCAN_NULLPTR);
00213         item->ptr = new (item->pool) T();
00214         return item->ptr;
00215     }
00216 
00217     template <typename P1>
00218     T* emplace(P1 p1)
00219     {
00220         Item* const item = findOrCreateFreeSlot();
00221         if (item == UAVCAN_NULLPTR)
00222         {
00223             return UAVCAN_NULLPTR;
00224         }
00225         UAVCAN_ASSERT(item->ptr == UAVCAN_NULLPTR);
00226         item->ptr = new (item->pool) T(p1);
00227         return item->ptr;
00228     }
00229 
00230     template <typename P1, typename P2>
00231     T* emplace(P1 p1, P2 p2)
00232     {
00233         Item* const item = findOrCreateFreeSlot();
00234         if (item == UAVCAN_NULLPTR)
00235         {
00236             return UAVCAN_NULLPTR;
00237         }
00238         UAVCAN_ASSERT(item->ptr == UAVCAN_NULLPTR);
00239         item->ptr = new (item->pool) T(p1, p2);
00240         return item->ptr;
00241     }
00242 
00243     template <typename P1, typename P2, typename P3>
00244     T* emplace(P1 p1, P2 p2, P3 p3)
00245     {
00246         Item* const item = findOrCreateFreeSlot();
00247         if (item == UAVCAN_NULLPTR)
00248         {
00249             return UAVCAN_NULLPTR;
00250         }
00251         UAVCAN_ASSERT(item->ptr == UAVCAN_NULLPTR);
00252         item->ptr = new (item->pool) T(p1, p2, p3);
00253         return item->ptr;
00254     }
00255 
00256     /**
00257      * Removes entries where the predicate returns true.
00258      * Predicate prototype:
00259      *  bool (T& item)
00260      */
00261     template <typename Predicate>
00262     void removeAllWhere(Predicate predicate) { removeWhere<Predicate>(predicate, RemoveAll); }
00263 
00264     template <typename Predicate>
00265     void removeFirstWhere(Predicate predicate) { removeWhere<Predicate>(predicate, RemoveOne); }
00266 
00267     void removeFirst(const T& ref) { removeFirstWhere(ComparingPredicate(ref)); }
00268 
00269     void removeAll(const T& ref) { removeAllWhere(ComparingPredicate(ref)); }
00270 
00271     void clear() { removeAllWhere(YesPredicate()); }
00272 
00273     /**
00274      * Returns first entry where the predicate returns true.
00275      * Predicate prototype:
00276      *  bool (const T& item)
00277      */
00278     template <typename Predicate>
00279     T* find(Predicate predicate);
00280 
00281     template <typename Predicate>
00282     const T* find(Predicate predicate) const
00283     {
00284         return const_cast<Multiset*>(this)->find<Predicate>(predicate);
00285     }
00286 
00287     /**
00288      * Calls Operator for each item of the set.
00289      * Operator prototype:
00290      *  void (T& item)
00291      *  void (const T& item) - const overload
00292      */
00293     template <typename Operator>
00294     void forEach(Operator oper)
00295     {
00296         OperatorToFalsePredicateAdapter<Operator> adapter(oper);
00297         (void)find<OperatorToFalsePredicateAdapter<Operator>&>(adapter);
00298     }
00299 
00300     template <typename Operator>
00301     void forEach(Operator oper) const
00302     {
00303         const OperatorToFalsePredicateAdapter<Operator> adapter(oper);
00304         (void)find<const OperatorToFalsePredicateAdapter<Operator>&>(adapter);
00305     }
00306 
00307     /**
00308      * Returns an item located at the specified position from the beginning.
00309      * Note that addition and removal operations invalidate indices.
00310      * If index is greater than or equal the number of items, null pointer will be returned.
00311      * Complexity is O(N).
00312      */
00313     T* getByIndex(unsigned index)
00314     {
00315         IndexPredicate predicate(index);
00316         return find<IndexPredicate&>(predicate);
00317     }
00318 
00319     const T* getByIndex(unsigned index) const
00320     {
00321         return const_cast<Multiset*>(this)->getByIndex(index);
00322     }
00323 
00324     /**
00325      * Complexity is O(1).
00326      */
00327     bool isEmpty() const { return find(YesPredicate()) == UAVCAN_NULLPTR; }
00328 
00329     /**
00330      * Counts number of items stored.
00331      * Best case complexity is O(N).
00332      */
00333     unsigned getSize() const;
00334 };
00335 
00336 // ----------------------------------------------------------------------------
00337 
00338 /*
00339  * Multiset<>
00340  */
00341 template <typename T>
00342 typename Multiset<T>::Item* Multiset<T>::findOrCreateFreeSlot()
00343 {
00344     // Search
00345     {
00346         Chunk* p = list_.get();
00347         while (p)
00348         {
00349             Item* const dyn = p->findFreeSlot();
00350             if (dyn != UAVCAN_NULLPTR)
00351             {
00352                 return dyn;
00353             }
00354             p = p->getNextListNode();
00355         }
00356     }
00357 
00358     // Create new chunk
00359     Chunk* const chunk = Chunk::instantiate(allocator_);
00360     if (chunk == UAVCAN_NULLPTR)
00361     {
00362         return UAVCAN_NULLPTR;
00363     }
00364     list_.insert(chunk);
00365     return &chunk->items[0];
00366 }
00367 
00368 template <typename T>
00369 void Multiset<T>::compact()
00370 {
00371     Chunk* p = list_.get();
00372     while (p)
00373     {
00374         Chunk* const next = p->getNextListNode();
00375         bool remove_this = true;
00376         for (int i = 0; i < Chunk::NumItems; i++)
00377         {
00378             if (p->items[i].isConstructed())
00379             {
00380                 remove_this = false;
00381                 break;
00382             }
00383         }
00384         if (remove_this)
00385         {
00386             list_.remove(p);
00387             Chunk::destroy(p, allocator_);
00388         }
00389         p = next;
00390     }
00391 }
00392 
00393 template <typename T>
00394 template <typename Predicate>
00395 void Multiset<T>::removeWhere(Predicate predicate, const RemoveStrategy strategy)
00396 {
00397     unsigned num_removed = 0;
00398 
00399     Chunk* p = list_.get();
00400     while (p != UAVCAN_NULLPTR)
00401     {
00402         Chunk* const next_chunk = p->getNextListNode(); // For the case if the current entry gets modified
00403 
00404         if ((num_removed > 0) && (strategy == RemoveOne))
00405         {
00406             break;
00407         }
00408 
00409         for (int i = 0; i < Chunk::NumItems; i++)
00410         {
00411             Item& item = p->items[i];
00412             if (item.isConstructed())
00413             {
00414                 if (predicate(*item.ptr))
00415                 {
00416                     num_removed++;
00417                     item.destroy();
00418                     if (strategy == RemoveOne)
00419                     {
00420                         break;
00421                     }
00422                 }
00423             }
00424         }
00425 
00426         p = next_chunk;
00427     }
00428 
00429     if (num_removed > 0)
00430     {
00431         compact();
00432     }
00433 }
00434 
00435 template <typename T>
00436 template <typename Predicate>
00437 T* Multiset<T>::find(Predicate predicate)
00438 {
00439     Chunk* p = list_.get();
00440     while (p != UAVCAN_NULLPTR)
00441     {
00442         Chunk* const next_chunk = p->getNextListNode(); // For the case if the current entry gets modified
00443 
00444         for (int i = 0; i < Chunk::NumItems; i++)
00445         {
00446             if (p->items[i].isConstructed())
00447             {
00448                 if (predicate(*p->items[i].ptr))
00449                 {
00450                     return p->items[i].ptr;
00451                 }
00452             }
00453         }
00454 
00455         p = next_chunk;
00456     }
00457     return UAVCAN_NULLPTR;
00458 }
00459 
00460 template <typename T>
00461 unsigned Multiset<T>::getSize() const
00462 {
00463     unsigned num = 0;
00464     Chunk* p = list_.get();
00465     while (p)
00466     {
00467         for (int i = 0; i < Chunk::NumItems; i++)
00468         {
00469             num += p->items[i].isConstructed() ? 1U : 0U;
00470         }
00471         p = p->getNextListNode();
00472     }
00473     return num;
00474 }
00475 
00476 }
00477 
00478 #endif // Include guard