map.hpp

00001 /*
00002  * Copyright (C) 2014 Pavel Kirienko <pavel.kirienko@gmail.com>
00003  */
00004 
00005 #ifndef UAVCAN_UTIL_MAP_HPP_INCLUDED
00006 #define UAVCAN_UTIL_MAP_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 namespace uavcan
00017 {
00018 /**
00019  * Slow but memory efficient KV container.
00020  *
00021  * KV pairs will be allocated in the node's memory pool.
00022  *
00023  * Please be aware that this container does not perform any speed optimizations to minimize memory footprint,
00024  * so the complexity of most operations is O(N).
00025  *
00026  * Type requirements:
00027  *  Both key and value must be copyable, assignable and default constructible.
00028  *  Key must implement a comparison operator.
00029  *  Key's default constructor must initialize the object into invalid state.
00030  *  Size of Key + Value + padding must not exceed MemPoolBlockSize.
00031  */
00032 template <typename Key, typename Value>
00033 class UAVCAN_EXPORT Map : Noncopyable
00034 {
00035 public:
00036     struct KVPair
00037     {
00038         Value value;    // Key and value are swapped because this may allow to reduce padding (depending on types)
00039         Key key;
00040 
00041         KVPair() :
00042             value(),
00043             key()
00044         { }
00045 
00046         KVPair(const Key& arg_key, const Value& arg_value) :
00047             value(arg_value),
00048             key(arg_key)
00049         { }
00050 
00051         bool match(const Key& rhs) const { return rhs == key; }
00052     };
00053 
00054 private:
00055     struct KVGroup : LinkedListNode<KVGroup>
00056     {
00057         enum { NumKV = (MemPoolBlockSize - sizeof(LinkedListNode<KVGroup> )) / sizeof(KVPair) };
00058         KVPair kvs[NumKV];
00059 
00060         KVGroup()
00061         {
00062             StaticAssert<(static_cast<unsigned>(NumKV) > 0)>::check();
00063             IsDynamicallyAllocatable<KVGroup>::check();
00064         }
00065 
00066         static KVGroup* instantiate(IPoolAllocator& allocator)
00067         {
00068             void* const praw = allocator.allocate(sizeof(KVGroup));
00069             if (praw == UAVCAN_NULLPTR)
00070             {
00071                 return UAVCAN_NULLPTR;
00072             }
00073             return new (praw) KVGroup();
00074         }
00075 
00076         static void destroy(KVGroup*& obj, IPoolAllocator& allocator)
00077         {
00078             if (obj != UAVCAN_NULLPTR)
00079             {
00080                 obj->~KVGroup();
00081                 allocator.deallocate(obj);
00082                 obj = UAVCAN_NULLPTR;
00083             }
00084         }
00085 
00086         KVPair* find(const Key& key)
00087         {
00088             for (unsigned i = 0; i < static_cast<unsigned>(NumKV); i++)
00089             {
00090                 if (kvs[i].match(key))
00091                 {
00092                     return kvs + i;
00093                 }
00094             }
00095             return UAVCAN_NULLPTR;
00096         }
00097     };
00098 
00099     LinkedListRoot<KVGroup>  list_;
00100     IPoolAllocator& allocator_;
00101 
00102     KVPair* findKey(const Key& key);
00103 
00104     void compact();
00105 
00106     struct YesPredicate
00107     {
00108         bool operator()(const Key&, const Value&) const { return true; }
00109     };
00110 
00111 public:
00112     Map(IPoolAllocator& allocator) :
00113         allocator_(allocator)
00114     {
00115         UAVCAN_ASSERT(Key() == Key());
00116     }
00117 
00118     ~Map()
00119     {
00120         clear();
00121     }
00122 
00123     /**
00124      * Returns null pointer if there's no such entry.
00125      */
00126     Value* access(const Key& key);
00127 
00128     /**
00129      * If entry with the same key already exists, it will be replaced
00130      */
00131     Value* insert(const Key& key, const Value& value);
00132 
00133     /**
00134      * Does nothing if there's no such entry.
00135      */
00136     void remove(const Key& key);
00137 
00138     /**
00139      * Removes entries where the predicate returns true.
00140      * Predicate prototype:
00141      *  bool (Key& key, Value& value)
00142      */
00143     template <typename Predicate>
00144     void removeAllWhere(Predicate predicate);
00145 
00146     /**
00147      * Returns first entry where the predicate returns true.
00148      * Predicate prototype:
00149      *  bool (const Key& key, const Value& value)
00150      */
00151     template <typename Predicate>
00152     const Key* find(Predicate predicate) const;
00153 
00154     /**
00155      * Removes all items.
00156      */
00157     void clear();
00158 
00159     /**
00160      * Returns a key-value pair located at the specified position from the beginning.
00161      * Note that any insertion or deletion may greatly disturb internal ordering, so use with care.
00162      * If index is greater than or equal the number of pairs, null pointer will be returned.
00163      */
00164     KVPair* getByIndex(unsigned index);
00165     const KVPair* getByIndex(unsigned index) const;
00166 
00167     /**
00168      * Complexity is O(1).
00169      */
00170     bool isEmpty() const { return find(YesPredicate()) == UAVCAN_NULLPTR; }
00171 
00172     /**
00173      * Complexity is O(N).
00174      */
00175     unsigned getSize() const;
00176 };
00177 
00178 // ----------------------------------------------------------------------------
00179 
00180 /*
00181  * Map<>
00182  */
00183 template <typename Key, typename Value>
00184 typename Map<Key, Value>::KVPair* Map<Key, Value>::findKey(const Key& key)
00185 {
00186     KVGroup* p = list_.get();
00187     while (p)
00188     {
00189         KVPair* const kv = p->find(key);
00190         if (kv)
00191         {
00192             return kv;
00193         }
00194         p = p->getNextListNode();
00195     }
00196     return UAVCAN_NULLPTR;
00197 }
00198 
00199 template <typename Key, typename Value>
00200 void Map<Key, Value>::compact()
00201 {
00202     KVGroup* p = list_.get();
00203     while (p)
00204     {
00205         KVGroup* const next = p->getNextListNode();
00206         bool remove_this = true;
00207         for (int i = 0; i < KVGroup::NumKV; i++)
00208         {
00209             if (!p->kvs[i].match(Key()))
00210             {
00211                 remove_this = false;
00212                 break;
00213             }
00214         }
00215         if (remove_this)
00216         {
00217             list_.remove(p);
00218             KVGroup::destroy(p, allocator_);
00219         }
00220         p = next;
00221     }
00222 }
00223 
00224 template <typename Key, typename Value>
00225 Value* Map<Key, Value>::access(const Key& key)
00226 {
00227     UAVCAN_ASSERT(!(key == Key()));
00228     KVPair* const kv = findKey(key);
00229     return kv ? &kv->value : UAVCAN_NULLPTR;
00230 }
00231 
00232 template <typename Key, typename Value>
00233 Value* Map<Key, Value>::insert(const Key& key, const Value& value)
00234 {
00235     UAVCAN_ASSERT(!(key == Key()));
00236     remove(key);
00237 
00238     KVPair* const kv = findKey(Key());
00239     if (kv)
00240     {
00241         *kv = KVPair(key, value);
00242         return &kv->value;
00243     }
00244 
00245     KVGroup* const kvg = KVGroup::instantiate(allocator_);
00246     if (kvg == UAVCAN_NULLPTR)
00247     {
00248         return UAVCAN_NULLPTR;
00249     }
00250     list_.insert(kvg);
00251     kvg->kvs[0] = KVPair(key, value);
00252     return &kvg->kvs[0].value;
00253 }
00254 
00255 template <typename Key, typename Value>
00256 void Map<Key, Value>::remove(const Key& key)
00257 {
00258     UAVCAN_ASSERT(!(key == Key()));
00259     KVPair* const kv = findKey(key);
00260     if (kv)
00261     {
00262         *kv = KVPair();
00263         compact();
00264     }
00265 }
00266 
00267 template <typename Key, typename Value>
00268 template <typename Predicate>
00269 void Map<Key, Value>::removeAllWhere(Predicate predicate)
00270 {
00271     unsigned num_removed = 0;
00272 
00273     KVGroup* p = list_.get();
00274     while (p != UAVCAN_NULLPTR)
00275     {
00276         KVGroup* const next_group = p->getNextListNode();
00277 
00278         for (int i = 0; i < KVGroup::NumKV; i++)
00279         {
00280             const KVPair* const kv = p->kvs + i;
00281             if (!kv->match(Key()))
00282             {
00283                 if (predicate(kv->key, kv->value))
00284                 {
00285                     num_removed++;
00286                     p->kvs[i] = KVPair();
00287                 }
00288             }
00289         }
00290 
00291         p = next_group;
00292     }
00293 
00294     if (num_removed > 0)
00295     {
00296         compact();
00297     }
00298 }
00299 
00300 template <typename Key, typename Value>
00301 template <typename Predicate>
00302 const Key* Map<Key, Value>::find(Predicate predicate) const
00303 {
00304     KVGroup* p = list_.get();
00305     while (p != UAVCAN_NULLPTR)
00306     {
00307         KVGroup* const next_group = p->getNextListNode();
00308 
00309         for (int i = 0; i < KVGroup::NumKV; i++)
00310         {
00311             const KVPair* const kv = p->kvs + i;
00312             if (!kv->match(Key()))
00313             {
00314                 if (predicate(kv->key, kv->value))
00315                 {
00316                     return &p->kvs[i].key;
00317                 }
00318             }
00319         }
00320 
00321         p = next_group;
00322     }
00323     return UAVCAN_NULLPTR;
00324 }
00325 
00326 template <typename Key, typename Value>
00327 void Map<Key, Value>::clear()
00328 {
00329     removeAllWhere(YesPredicate());
00330 }
00331 
00332 template <typename Key, typename Value>
00333 typename Map<Key, Value>::KVPair* Map<Key, Value>::getByIndex(unsigned index)
00334 {
00335     // Slowly crawling through the dynamic storage
00336     KVGroup* p = list_.get();
00337     while (p != UAVCAN_NULLPTR)
00338     {
00339         KVGroup* const next_group = p->getNextListNode();
00340 
00341         for (int i = 0; i < KVGroup::NumKV; i++)
00342         {
00343             KVPair* const kv = p->kvs + i;
00344             if (!kv->match(Key()))
00345             {
00346                 if (index == 0)
00347                 {
00348                     return kv;
00349                 }
00350                 index--;
00351             }
00352         }
00353 
00354         p = next_group;
00355     }
00356 
00357     return UAVCAN_NULLPTR;
00358 }
00359 
00360 template <typename Key, typename Value>
00361 const typename Map<Key, Value>::KVPair* Map<Key, Value>::getByIndex(unsigned index) const
00362 {
00363     return const_cast<Map<Key, Value>*>(this)->getByIndex(index);
00364 }
00365 
00366 template <typename Key, typename Value>
00367 unsigned Map<Key, Value>::getSize() const
00368 {
00369     unsigned num = 0;
00370     KVGroup* p = list_.get();
00371     while (p)
00372     {
00373         for (int i = 0; i < KVGroup::NumKV; i++)
00374         {
00375             const KVPair* const kv = p->kvs + i;
00376             if (!kv->match(Key()))
00377             {
00378                 num++;
00379             }
00380         }
00381         p = p->getNextListNode();
00382     }
00383     return num;
00384 }
00385 
00386 }
00387 
00388 #endif // UAVCAN_UTIL_MAP_HPP_INCLUDED