dali/internal/common/ordered-set.h

   1 #ifndef DALI_INTERNAL_ORDERED_SET_H
   2 #define DALI_INTERNAL_ORDERED_SET_H
   3
   4 /*
   5  * Copyright (c) 2023 Samsung Electronics Co., Ltd.
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  * http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  *
  19  */
  20
  21 // EXTERNAL INCLUDES
  22 #include <unordered_map>
  23
  24 // INTERNAL INCLUDES
  25 #include <dali/public-api/common/dali-common.h>
  26 #include <dali/public-api/common/list-wrapper.h>
  27
  28 namespace Dali
  29 {
  30 namespace Internal
  31 {
  32 /**
  33  * @brief Container of data which has strong point to Find & Erase.
  34  * It will be useful when we need to iterate the order of data insertion.
  35  * and need to check whether some object is exist or not very fast.
  36  * @note Since the data's memory is not continuos, iteration is slower than normal vector contianer.
  37  *
  38  * @tparam T The type of class
  39  * @tparam owned True if data is owned, So we will automatcally release the memory
  40  *               False if data is not owned by this set. Default as true.
  41  * @tparam Hash Custom hash function of const T* type for MapContainer.
  42  *              Note that if two const T* return true at KeyEqual, Hash should return same value.
  43  *              Default as std::hash<const T*>
  44  * @tparam KeyEqual Custom equal function of const T* type for MapContainer.
  45  *                  Return true if two const T* type is equal. Default as std::equal_to<const T*>
  46  */
  47 template<class T, bool owned = true, class Hash = std::hash<const T*>, class KeyEqual = std::equal_to<const T*>>
  48 class OrderedSet
  49 {
  50 public:
  51   // Real data owned container.
  52   using ListContainer = typename std::list<T*>;
  53   using Iterator      = typename ListContainer::iterator;
  54   using ConstIterator = typename ListContainer::const_iterator;
  55
  56   // Find helper map container.
  57   using MapContainer = typename std::unordered_map<const T*, Iterator, Hash, KeyEqual>;
  58
  59   using SizeType = std::size_t;
  60
  61   /**
  62    * @brief Construct a new OrderedSet object
  63    */
  64   OrderedSet() = default;
  65
  66   /**
  67    * @brief Move construct
  68    */
  69   OrderedSet(OrderedSet&& rhs)
  70   : mMap(std::move(rhs.mMap)),
  71     mList(std::move(rhs.mList))
  72   {
  73     rhs.mMap.clear();
  74     rhs.mMap.rehash(0);
  75     rhs.mList.clear();
  76   }
  77
  78   /**
  79    * @brief Move assign
  80    */
  81   OrderedSet& operator=(OrderedSet&& rhs)
  82   {
  83     Clear();
  84     mMap  = std::move(rhs.mMap);
  85     mList = std::move(rhs.mList);
  86     rhs.mMap.clear();
  87     rhs.mMap.rehash(0);
  88     rhs.mList.clear();
  89     return *this;
  90   }
  91
  92   ~OrderedSet()
  93   {
  94     Clear();
  95   }
  96
  97   /**
  98    * @brief Iterator of begin & end
  99    */
 100   Iterator Begin()
 101   {
 102     return mList.begin();
 103   }
 104   Iterator End()
 105   {
 106     return mList.end();
 107   }
 108   ConstIterator Begin() const
 109   {
 110     return mList.begin();
 111   }
 112   ConstIterator End() const
 113   {
 114     return mList.end();
 115   }
 116
 117   // Support for C++11 Range-based for loop: for( item : container ).
 118   Iterator begin()
 119   {
 120     return Begin();
 121   }
 122   Iterator end()
 123   {
 124     return End();
 125   }
 126   ConstIterator begin() const
 127   {
 128     return Begin();
 129   }
 130   ConstIterator end() const
 131   {
 132     return End();
 133   }
 134
 135   /**
 136    * @brief Get the number of elements.
 137    *
 138    * @return The number of elements that this container owned.
 139    */
 140   SizeType Count() const
 141   {
 142     return mMap.size();
 143   }
 144
 145   /**
 146    * @brief Reserves space in the ordered set.
 147    *
 148    * @param[in] count Count of elements to reserve
 149    */
 150   void Reserve(SizeType count)
 151   {
 152     if(mMap.size() < count)
 153     {
 154       mMap.rehash(count);
 155     }
 156   }
 157
 158   /**
 159    * @brief Find and get iterator of object. If not exist, return End().
 160    *
 161    * @param[in] object The object pointer what we want to find.
 162    * @return Iterator of object, or End().
 163    */
 164   Iterator Find(T* object)
 165   {
 166     auto mapIter = mMap.find(object);
 167     if(mapIter == mMap.end())
 168     {
 169       return End();
 170     }
 171     return mapIter->second;
 172   }
 173   ConstIterator Find(const T* object) const
 174   {
 175     auto mapIter = mMap.find(object);
 176     if(mapIter == mMap.end())
 177     {
 178       return End();
 179     }
 180     return mapIter->second;
 181   }
 182
 183   /**
 184    * @brief PushBack and keep ownership of object.
 185    * @note Iterator will keep order of PushBack API call.
 186    *
 187    * @param[in] object The object pointer what we want to insert.
 188    */
 189   void PushBack(T* object)
 190   {
 191     DALI_ASSERT_DEBUG(Find(object) == End());
 192     auto newIter = mList.insert(mList.end(), object);
 193     mMap.insert({object, newIter});
 194   }
 195
 196   /**
 197    * @brief Erase and remove memory of object.
 198    *
 199    * @param[in] object The object pointer what we want to erase.
 200    */
 201   void EraseObject(T* object)
 202   {
 203     // TODO : Should we allow duplicated erase?
 204     //DALI_ASSERT_DEBUG(Find(object) != End());
 205     Erase(Find(object));
 206   }
 207   void EraseObject(const T* object)
 208   {
 209     // TODO : Should we allow duplicated erase?
 210     //DALI_ASSERT_DEBUG(Find(object) != End());
 211     Erase(Find(object));
 212   }
 213
 214   /**
 215    * @brief Erase and remove memory of object by iterator.
 216    *
 217    * @param[in] iter The iterator what we want to erase.
 218    */
 219   Iterator Erase(Iterator iter)
 220   {
 221     Iterator ret = mList.end();
 222     if(iter != mList.end())
 223     {
 224       // Erase mMap first.
 225       auto mapIter = mMap.find(*iter);
 226       DALI_ASSERT_DEBUG(mapIter != mMap.end());
 227       mMap.erase(mapIter);
 228
 229       // Erase owned object.
 230       if constexpr(owned)
 231       {
 232         delete *iter;
 233       }
 234       ret = mList.erase(iter);
 235     }
 236     return ret;
 237   }
 238   ConstIterator Erase(ConstIterator iter)
 239   {
 240     ConstIterator ret = mList.end();
 241     if(iter != mList.end())
 242     {
 243       // Erase mMap first.
 244       auto mapIter = mMap.find(*iter);
 245       DALI_ASSERT_DEBUG(mapIter != mMap.end());
 246       mMap.erase(mapIter);
 247
 248       // Erase owned object.
 249       if constexpr(owned)
 250       {
 251         delete *iter;
 252       }
 253       ret = mList.erase(iter);
 254     }
 255     return ret;
 256   }
 257
 258   /**
 259    * @brief Release and move ownership of object.
 260    * This API do not remove memory.
 261    *
 262    * @param[in] iter The iterator what we want to release.
 263    */
 264   T* Release(Iterator iter)
 265   {
 266     T* result = (*iter);
 267
 268     // Erase mMap first.
 269     auto mapIter = mMap.find(result);
 270     DALI_ASSERT_DEBUG(mapIter != mMap.end());
 271     mMap.erase(mapIter);
 272
 273     // Erase without delete reference
 274     mList.erase(iter);
 275     return result;
 276   }
 277   T* Release(ConstIterator iter)
 278   {
 279     const T* result = (*iter);
 280
 281     // Erase mMap first.
 282     auto mapIter = mMap.find(result);
 283     DALI_ASSERT_DEBUG(mapIter != mMap.end());
 284     mMap.erase(mapIter);
 285
 286     // Erase without delete reference
 287     mList.erase(iter);
 288     return result;
 289   }
 290
 291   /**
 292    * @brief Remove all data and release memory if we owned data.
 293    */
 294   void Clear()
 295   {
 296     // Delete memory
 297     if constexpr(owned)
 298     {
 299       for(auto&& iter : mList)
 300       {
 301         delete iter;
 302       }
 303     }
 304     mMap.clear();
 305     mMap.rehash(0);
 306     mList.clear();
 307   }
 308
 309 private:
 310   // Delete copy operation.
 311   OrderedSet(const OrderedSet&) = delete;
 312   OrderedSet& operator=(const OrderedSet&) = delete;
 313
 314 private:
 315   MapContainer  mMap{};  ///< Helper cache map to find item fast.
 316   ListContainer mList{}; ///< Ordered by PushBack API called. Actual ownership will be stored here.
 317 };
 318 } // namespace Internal
 319
 320 } // namespace Dali
 321
 322 #endif // DALI_INTERNAL_ORDERED_SET_H