unordered_map.h

00001 ///\file
00002 
00003 /******************************************************************************
00004 The MIT License(MIT)
00005 
00006 Embedded Template Library.
00007 https://github.com/ETLCPP/etl
00008 http://www.etlcpp.com
00009 
00010 Copyright(c) 2016 jwellbelove
00011 
00012 Permission is hereby granted, free of charge, to any person obtaining a copy
00013 of this software and associated documentation files(the "Software"), to deal
00014 in the Software without restriction, including without limitation the rights
00015 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
00016 copies of the Software, and to permit persons to whom the Software is
00017 furnished to do so, subject to the following conditions :
00018 
00019 The above copyright notice and this permission notice shall be included in all
00020 copies or substantial portions of the Software.
00021 
00022 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00023 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00024 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
00025 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00026 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00027 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
00028 SOFTWARE.
00029 ******************************************************************************/
00030 
00031 #ifndef __ETL_UNORDERED_MAP__
00032 #define __ETL_UNORDERED_MAP__
00033 
00034 #include <stddef.h>
00035 #include <iterator>
00036 #include <functional>
00037 #include <algorithm>
00038 #include <functional>
00039 #include <utility>
00040 
00041 #include "platform.h "
00042 #include "container.h "
00043 #include "pool.h "
00044 #include "array.h "
00045 #include "intrusive_forward_list.h "
00046 #include "hash.h "
00047 #include "type_traits.h "
00048 #include "parameter_type.h "
00049 #include "nullptr.h "
00050 #include "vector.h "
00051 #include "error_handler.h "
00052 #include "exception.h "
00053 #include "debug_count.h "
00054 
00055 #undef ETL_FILE
00056 #define ETL_FILE "16"
00057 
00058 //*****************************************************************************
00059 ///\defgroup unordered_map unordered_map
00060 /// A unordered_map with the capacity defined at compile time.
00061 ///\ingroup containers
00062 //*****************************************************************************
00063 
00064 namespace etl
00065 {
00066   //***************************************************************************
00067   /// Exception for the unordered_map.
00068   ///\ingroup unordered_map
00069   //***************************************************************************
00070   class unordered_map_exception : public etl::exception
00071   {
00072   public:
00073 
00074     unordered_map_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00075       : etl::exception(reason_, file_name_, line_number_)
00076     {
00077     }
00078   };
00079 
00080   //***************************************************************************
00081   /// Full exception for the unordered_map.
00082   ///\ingroup unordered_map
00083   //***************************************************************************
00084   class unordered_map_full : public etl::unordered_map_exception
00085   {
00086   public:
00087 
00088     unordered_map_full(string_type file_name_, numeric_type line_number_)
00089       : etl::unordered_map_exception(ETL_ERROR_TEXT("unordered_map:full", ETL_FILE"A"), file_name_, line_number_)
00090     {
00091     }
00092   };
00093 
00094   //***************************************************************************
00095   /// Out of range exception for the unordered_map.
00096   ///\ingroup unordered_map
00097   //***************************************************************************
00098   class unordered_map_out_of_range : public etl::unordered_map_exception
00099   {
00100   public:
00101 
00102     unordered_map_out_of_range(string_type file_name_, numeric_type line_number_)
00103       : etl::unordered_map_exception(ETL_ERROR_TEXT("unordered_map:range", ETL_FILE"B"), file_name_, line_number_)
00104     {}
00105   };
00106 
00107   //***************************************************************************
00108   /// Iterator exception for the unordered_map.
00109   ///\ingroup unordered_map
00110   //***************************************************************************
00111   class unordered_map_iterator : public etl::unordered_map_exception
00112   {
00113   public:
00114 
00115     unordered_map_iterator(string_type file_name_, numeric_type line_number_)
00116       : etl::unordered_map_exception(ETL_ERROR_TEXT("unordered_map:iterator", ETL_FILE"C"), file_name_, line_number_)
00117     {
00118     }
00119   };
00120 
00121   //***************************************************************************
00122   /// The base class for specifically sized unordered_map.
00123   /// Can be used as a reference type for all unordered_map containing a specific type.
00124   ///\ingroup unordered_map
00125   //***************************************************************************
00126   template <typename TKey, typename T, typename THash = etl::hash<TKey>, typename TKeyEqual = std::equal_to<TKey> >
00127   class iunordered_map
00128   {
00129   public:
00130 
00131     typedef std::pair<const TKey, T> value_type;
00132 
00133     typedef TKey              key_type;
00134     typedef T                 mapped_type;
00135     typedef THash             hasher;
00136     typedef TKeyEqual         key_equal;
00137     typedef value_type&       reference;
00138     typedef const value_type& const_reference;
00139     typedef value_type*       pointer;
00140     typedef const value_type* const_pointer;
00141     typedef size_t            size_type;
00142 
00143 
00144     typedef typename etl::parameter_type<TKey>::type key_parameter_t;
00145 
00146     typedef etl::forward_link<0>  link_t ; // Default link.
00147 
00148                                          // The nodes that store the elements.
00149     struct node_t : public link_t 
00150     {
00151       node_t(const value_type& key_value_pair_)
00152         : key_value_pair(key_value_pair_)
00153       {
00154       }
00155 
00156       value_type key_value_pair;
00157     };
00158 
00159   private:
00160 
00161     typedef etl::intrusive_forward_list<node_t, link_t> bucket_t;
00162     typedef etl::ipool pool_t;
00163 
00164   public:
00165 
00166     // Local iterators iterate over one bucket.
00167     typedef typename bucket_t::iterator       local_iterator;
00168     typedef typename bucket_t::const_iterator local_const_iterator;
00169 
00170     //*********************************************************************
00171     class iterator : public std::iterator<std::forward_iterator_tag, T>
00172     {
00173     public:
00174 
00175       typedef typename iunordered_map::value_type      value_type;
00176       typedef typename iunordered_map::key_type        key_type;
00177       typedef typename iunordered_map::mapped_type     mapped_type;
00178       typedef typename iunordered_map::hasher          hasher;
00179       typedef typename iunordered_map::key_equal       key_equal;
00180       typedef typename iunordered_map::reference       reference;
00181       typedef typename iunordered_map::const_reference const_reference;
00182       typedef typename iunordered_map::pointer         pointer;
00183       typedef typename iunordered_map::const_pointer   const_pointer;
00184       typedef typename iunordered_map::size_type       size_type;
00185 
00186       friend class iunordered_map;
00187 
00188       //*********************************
00189       iterator()
00190       {
00191       }
00192 
00193       //*********************************
00194       iterator(const iterator& other)
00195         : pbuckets_end(other.pbuckets_end),
00196         pbucket(other.pbucket),
00197         inode(other.inode)
00198       {
00199       }
00200 
00201       //*********************************
00202       iterator& operator ++()
00203       {
00204         ++inode;
00205 
00206         // The end of this node list?
00207         if (inode == pbucket->end())
00208         {
00209           // Search for the next non-empty bucket.
00210           ++pbucket;
00211           while ((pbucket != pbuckets_end) && (pbucket->empty()))
00212           {
00213             ++pbucket;
00214           }
00215 
00216           // If not past the end, get the first node in the bucket.
00217           if (pbucket != pbuckets_end)
00218           {
00219             inode = pbucket->begin();
00220           }
00221         }
00222 
00223         return *this;
00224       }
00225 
00226       //*********************************
00227       iterator operator ++(int)
00228       {
00229         iterator temp(*this);
00230         operator++();
00231         return temp;
00232       }
00233 
00234       //*********************************
00235       iterator operator =(const iterator& other)
00236       {
00237         pbuckets_end = other.pbuckets_end;
00238         pbucket = other.pbucket;
00239         inode = other.inode;
00240         return *this;
00241       }
00242 
00243       //*********************************
00244       std::pair<const TKey, T> operator *()
00245       {
00246         return inode->key_value_pair;
00247       }
00248 
00249       //*********************************
00250       const_reference operator *() const
00251       {
00252         return inode->key_value_pair;
00253       }
00254 
00255       //*********************************
00256       pointer operator &()
00257       {
00258         return &(inode->key_value_pair);
00259       }
00260 
00261       //*********************************
00262       const_pointer operator &() const
00263       {
00264         return &(inode->key_value_pair);
00265       }
00266 
00267       //*********************************
00268       pointer operator ->()
00269       {
00270         return &(inode->key_value_pair);
00271       }
00272 
00273       //*********************************
00274       const_pointer operator ->() const
00275       {
00276         return &(inode->key_value_pair);
00277       }
00278 
00279       //*********************************
00280       friend bool operator == (const iterator& lhs, const iterator& rhs)
00281       {
00282         return lhs.compare(rhs);
00283       }
00284 
00285       //*********************************
00286       friend bool operator != (const iterator& lhs, const iterator& rhs)
00287       {
00288         return !(lhs == rhs);
00289       }
00290 
00291     private:
00292 
00293       //*********************************
00294       iterator(bucket_t* pbuckets_end_, bucket_t* pbucket_, local_iterator inode_)
00295         : pbuckets_end(pbuckets_end_),
00296           pbucket(pbucket_),
00297           inode(inode_)
00298       {
00299       }
00300 
00301       //*********************************
00302       bool compare(const iterator& rhs) const
00303       {
00304         return rhs.inode == inode;
00305       }
00306 
00307       //*********************************
00308       bucket_t& get_bucket()
00309       {
00310         return *pbucket;
00311       }
00312 
00313       //*********************************
00314       bucket_t* get_bucket_list_iterator()
00315       {
00316         return pbucket;
00317       }
00318 
00319       //*********************************
00320       local_iterator get_local_iterator()
00321       {
00322         return inode;
00323       }
00324 
00325       bucket_t* pbuckets_end;
00326       bucket_t* pbucket;
00327       local_iterator inode;
00328     };
00329 
00330     //*********************************************************************
00331     class const_iterator : public std::iterator<std::forward_iterator_tag, const T>
00332     {
00333     public:
00334 
00335       typedef typename iunordered_map::value_type      value_type;
00336       typedef typename iunordered_map::key_type        key_type;
00337       typedef typename iunordered_map::mapped_type     mapped_type;
00338       typedef typename iunordered_map::hasher          hasher;
00339       typedef typename iunordered_map::key_equal       key_equal;
00340       typedef typename iunordered_map::reference       reference;
00341       typedef typename iunordered_map::const_reference const_reference;
00342       typedef typename iunordered_map::pointer         pointer;
00343       typedef typename iunordered_map::const_pointer   const_pointer;
00344       typedef typename iunordered_map::size_type       size_type;
00345 
00346       friend class iunordered_map;
00347       friend class iterator;
00348 
00349       //*********************************
00350       const_iterator()
00351       {
00352       }
00353 
00354       //*********************************
00355       const_iterator(const typename iunordered_map::iterator& other)
00356         : pbuckets_end(other.pbuckets_end),
00357           pbucket(other.pbucket),
00358           inode(other.inode)
00359       {
00360       }
00361 
00362       //*********************************
00363       const_iterator(const const_iterator& other)
00364         : pbuckets_end(other.pbuckets_end),
00365           pbucket(other.pbucket),
00366           inode(other.inode)
00367       {
00368       }
00369 
00370       //*********************************
00371       const_iterator& operator ++()
00372       {
00373         ++inode;
00374 
00375         // The end of this node list?
00376         if (inode == pbucket->end())
00377         {
00378           // Search for the next non-empty bucket.
00379           ++pbucket;
00380           while ((pbucket != pbuckets_end) && (pbucket->empty()))
00381           {
00382             ++pbucket;
00383           }
00384 
00385           // If not past the end, get the first node in the bucket.
00386           if (pbucket != pbuckets_end)
00387           {
00388             inode = pbucket->begin();
00389           }
00390         }
00391 
00392         return *this;
00393       }
00394 
00395       //*********************************
00396       const_iterator operator ++(int)
00397       {
00398         const_iterator temp(*this);
00399         operator++();
00400         return temp;
00401       }
00402 
00403       //*********************************
00404       const_iterator operator =(const const_iterator& other)
00405       {
00406         pbuckets_end = other.pbuckets_end;
00407         pbucket = other.pbucket;
00408         inode = other.inode;
00409         return *this;
00410       }
00411 
00412       //*********************************
00413       const_reference operator *() const
00414       {
00415         return inode->key_value_pair;
00416       }
00417 
00418       //*********************************
00419       const_pointer operator &() const
00420       {
00421         return &(inode->key_value_pair);
00422       }
00423 
00424       //*********************************
00425       const_pointer operator ->() const
00426       {
00427         return &(inode->key_value_pair);
00428       }
00429 
00430       //*********************************
00431       friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
00432       {
00433         return lhs.compare(rhs);
00434       }
00435 
00436       //*********************************
00437       friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
00438       {
00439         return !(lhs == rhs);
00440       }
00441 
00442     private:
00443 
00444       //*********************************
00445       const_iterator(bucket_t* pbuckets_end_, bucket_t* pbucket_, local_iterator inode_)
00446         : pbuckets_end(pbuckets_end_),
00447           pbucket(pbucket_),
00448           inode(inode_)
00449       {
00450       }
00451 
00452       //*********************************
00453       bool compare(const const_iterator& rhs) const
00454       {
00455         return rhs.inode == inode;
00456       }
00457 
00458       //*********************************
00459       bucket_t& get_bucket()
00460       {
00461         return *pbucket;
00462       }
00463 
00464       //*********************************
00465       bucket_t* get_bucket_list_iterator()
00466       {
00467         return pbucket;
00468       }
00469 
00470       //*********************************
00471       local_iterator get_local_iterator()
00472       {
00473         return inode;
00474       }
00475 
00476       bucket_t* pbuckets_end;
00477       bucket_t* pbucket;
00478       local_iterator inode;
00479     };
00480 
00481     typedef typename std::iterator_traits<iterator>::difference_type difference_type;
00482 
00483     //*********************************************************************
00484     /// Returns an iterator to the beginning of the unordered_map.
00485     ///\return An iterator to the beginning of the unordered_map.
00486     //*********************************************************************
00487     iterator begin()
00488     {
00489       return iterator((pbuckets + number_of_buckets), first, first->begin());
00490     }
00491 
00492     //*********************************************************************
00493     /// Returns a const_iterator to the beginning of the unordered_map.
00494     ///\return A const iterator to the beginning of the unordered_map.
00495     //*********************************************************************
00496     const_iterator begin() const
00497     {
00498       return const_iterator((pbuckets + number_of_buckets), first, first->begin());
00499     }
00500 
00501     //*********************************************************************
00502     /// Returns a const_iterator to the beginning of the unordered_map.
00503     ///\return A const iterator to the beginning of the unordered_map.
00504     //*********************************************************************
00505     const_iterator cbegin() const
00506     {
00507       return const_iterator((pbuckets + number_of_buckets), first, first->begin());
00508     }
00509 
00510     //*********************************************************************
00511     /// Returns an iterator to the beginning of the unordered_map bucket.
00512     ///\return An iterator to the beginning of the unordered_map bucket.
00513     //*********************************************************************
00514     local_iterator begin(size_t i)
00515     {
00516       return (*pbuckets)[i].begin();
00517     }
00518 
00519     //*********************************************************************
00520     /// Returns a const_iterator to the beginning of the unordered_map bucket.
00521     ///\return A const iterator to the beginning of the unordered_map bucket.
00522     //*********************************************************************
00523     local_const_iterator begin(size_t i) const
00524     {
00525       return (*pbuckets)[i].cbegin();
00526     }
00527 
00528     //*********************************************************************
00529     /// Returns a const_iterator to the beginning of the unordered_map bucket.
00530     ///\return A const iterator to the beginning of the unordered_map bucket.
00531     //*********************************************************************
00532     local_const_iterator cbegin(size_t i) const
00533     {
00534       return (*pbuckets)[i].cbegin();
00535     }
00536 
00537     //*********************************************************************
00538     /// Returns an iterator to the end of the unordered_map.
00539     ///\return An iterator to the end of the unordered_map.
00540     //*********************************************************************
00541     iterator end()
00542     {
00543       return iterator((pbuckets + number_of_buckets), last, last->end());
00544     }
00545 
00546     //*********************************************************************
00547     /// Returns a const_iterator to the end of the unordered_map.
00548     ///\return A const iterator to the end of the unordered_map.
00549     //*********************************************************************
00550     const_iterator end() const
00551     {
00552       return const_iterator((pbuckets + number_of_buckets), last, last->end());
00553     }
00554 
00555     //*********************************************************************
00556     /// Returns a const_iterator to the end of the unordered_map.
00557     ///\return A const iterator to the end of the unordered_map.
00558     //*********************************************************************
00559     const_iterator cend() const
00560     {
00561       return const_iterator((pbuckets + number_of_buckets), last, last->end());
00562     }
00563 
00564     //*********************************************************************
00565     /// Returns an iterator to the end of the unordered_map bucket.
00566     ///\return An iterator to the end of the unordered_map bucket.
00567     //*********************************************************************
00568     local_iterator end(size_t i)
00569     {
00570       return (*pbuckets)[i].end();
00571     }
00572 
00573     //*********************************************************************
00574     /// Returns a const_iterator to the end of the unordered_map bucket.
00575     ///\return A const iterator to the end of the unordered_map bucket.
00576     //*********************************************************************
00577     local_const_iterator end(size_t i) const
00578     {
00579       return (*pbuckets)[i].cend();
00580     }
00581 
00582     //*********************************************************************
00583     /// Returns a const_iterator to the end of the unordered_map bucket.
00584     ///\return A const iterator to the end of the unordered_map bucket.
00585     //*********************************************************************
00586     local_const_iterator cend(size_t i) const
00587     {
00588       return (*pbuckets)[i].cend();
00589     }
00590 
00591     //*********************************************************************
00592     /// Returns the bucket index for the key.
00593     ///\return The bucket index for the key.
00594     //*********************************************************************
00595     size_type get_bucket_index(key_parameter_t key) const
00596     {
00597       return key_hash_function(key) % number_of_buckets;
00598     }
00599 
00600     //*********************************************************************
00601     /// Returns the size of the bucket key.
00602     ///\return The bucket size of the bucket key.
00603     //*********************************************************************
00604     size_type bucket_size(key_parameter_t key) const
00605     {
00606       size_t index = bucket(key);
00607 
00608       return std::distance((*pbuckets)[index].begin(), (*pbuckets)[index].end());
00609     }
00610 
00611     //*********************************************************************
00612     /// Returns the maximum number of the buckets the container can hold.
00613     ///\return The maximum number of the buckets the container can hold.
00614     //*********************************************************************
00615     size_type max_bucket_count() const
00616     {
00617       return number_of_buckets;
00618     }
00619 
00620     //*********************************************************************
00621     /// Returns the number of the buckets the container holds.
00622     ///\return The number of the buckets the container holds.
00623     //*********************************************************************
00624     size_type bucket_count() const
00625     {
00626       return number_of_buckets;
00627     }
00628 
00629     //*********************************************************************
00630     /// Returns a reference to the value at index 'key'
00631     ///\param key The key.
00632     ///\return A reference to the value at index 'key'
00633     //*********************************************************************
00634     mapped_type& operator [](key_parameter_t key)
00635     {
00636       // Find the bucket.
00637       bucket_t* pbucket = pbuckets + get_bucket_index(key);
00638 
00639       // Find the first node in the bucket.
00640       local_iterator inode = pbucket->begin();
00641 
00642       // Walk the list looking for the right one.
00643       while (inode != pbucket->end())
00644       {
00645         // Equal keys?
00646         if (key_equal_function(key, inode->key_value_pair.first))
00647         {
00648           // Found a match.
00649           return inode->key_value_pair.second;
00650         }
00651         else
00652         {
00653           ++inode;
00654         }
00655       }
00656 
00657       // Doesn't exist, so add a new one.
00658       // Get a new node.
00659       node_t& node = *pnodepool->allocate<node_t>();
00660       ::new (&node.key_value_pair) value_type(key, T());
00661       ++construct_count;
00662 
00663       pbucket->insert_after(pbucket->before_begin(), node);
00664 
00665       return pbucket->begin()->key_value_pair.second;
00666     }
00667 
00668     //*********************************************************************
00669     /// Returns a reference to the value at index 'key'
00670     /// If asserts or exceptions are enabled, emits an etl::unordered_map_out_of_range if the key is not in the range.
00671     ///\param key The key.
00672     ///\return A reference to the value at index 'key'
00673     //*********************************************************************
00674     mapped_type& at(key_parameter_t key)
00675     {
00676       // Find the bucket.
00677       bucket_t* pbucket = pbuckets + get_bucket_index(key);
00678 
00679       // Find the first node in the bucket.
00680       local_iterator inode = pbucket->begin();
00681 
00682       // Walk the list looking for the right one.
00683       while (inode != pbucket->end())
00684       {
00685         // Equal keys?
00686         if (key_equal_function(key, inode->key_value_pair.first))
00687         {
00688           // Found a match.
00689           return inode->key_value_pair.second;
00690         }
00691         else
00692         {
00693           ++inode;
00694         }
00695       }
00696 
00697       // Doesn't exist.
00698       ETL_ASSERT(false, ETL_ERROR(unordered_map_out_of_range));
00699 
00700       return begin()->second;
00701     }
00702 
00703     //*********************************************************************
00704     /// Returns a const reference to the value at index 'key'
00705     /// If asserts or exceptions are enabled, emits an etl::unordered_map_out_of_range if the key is not in the range.
00706     ///\param key The key.
00707     ///\return A const reference to the value at index 'key'
00708     //*********************************************************************
00709     const mapped_type& at(key_parameter_t key) const
00710     {
00711       // Find the bucket.
00712       bucket_t* pbucket = pbuckets + get_bucket_index(key);
00713 
00714       // Find the first node in the bucket.
00715       local_iterator inode = pbucket->begin();
00716 
00717       // Walk the list looking for the right one.
00718       while (inode != pbucket->end())
00719       {
00720         // Equal keys?
00721         if (key_equal_function(key, inode->key_value_pair.first))
00722         {
00723           // Found a match.
00724           return inode->key_value_pair.second;
00725         }
00726         else
00727         {
00728           ++inode;
00729         }
00730       }
00731 
00732       // Doesn't exist.
00733       ETL_ASSERT(false, ETL_ERROR(unordered_map_out_of_range));
00734 
00735       return begin()->second;
00736     }
00737 
00738     //*********************************************************************
00739     /// Assigns values to the unordered_map.
00740     /// If asserts or exceptions are enabled, emits unordered_map_full if the unordered_map does not have enough free space.
00741     /// If asserts or exceptions are enabled, emits unordered_map_iterator if the iterators are reversed.
00742     ///\param first The iterator to the first element.
00743     ///\param last  The iterator to the last element + 1.
00744     //*********************************************************************
00745     template <typename TIterator>
00746     void assign(TIterator first_, TIterator last_)
00747     {
00748 #if defined(ETL_DEBUG)
00749       difference_type d = std::distance(first_, last_);
00750       ETL_ASSERT(d >= 0, ETL_ERROR(unordered_map_iterator));
00751       ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_map_full));
00752 #endif
00753 
00754       clear();
00755 
00756       while (first_ != last_)
00757       {
00758         insert(*first_++);
00759       }
00760     }
00761 
00762     //*********************************************************************
00763     /// Inserts a value to the unordered_map.
00764     /// If asserts or exceptions are enabled, emits unordered_map_full if the unordered_map is already full.
00765     ///\param value The value to insert.
00766     //*********************************************************************
00767     std::pair<iterator, bool> insert(const value_type& key_value_pair)
00768     {
00769       std::pair<iterator, bool> result(end(), false);
00770 
00771       ETL_ASSERT(!full(), ETL_ERROR(unordered_map_full));
00772 
00773       const key_type&    key = key_value_pair.first;
00774       const mapped_type& mapped = key_value_pair.second;
00775 
00776       // Get the hash index.
00777       size_t index = get_bucket_index(key);
00778 
00779       // Get the bucket & bucket iterator.
00780       bucket_t* pbucket = pbuckets + index;
00781       bucket_t& bucket = *pbucket;
00782 
00783       size_t s = pbuckets->size();
00784 
00785       // The first one in the bucket?
00786       if (bucket.empty())
00787       {
00788         // Get a new node.
00789         node_t& node = *pnodepool->allocate<node_t>();
00790         ::new (&node.key_value_pair) value_type(key_value_pair);
00791         ++construct_count;
00792 
00793         // Just add the pointer to the bucket;
00794         bucket.insert_after(bucket.before_begin(), node);
00795 
00796         result.first = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
00797         result.second = true;
00798 
00799         adjust_first_last_markers(pbucket);
00800       }
00801       else
00802       {
00803         // Step though the bucket looking for a place to insert.
00804         local_iterator inode_previous = bucket.before_begin();
00805         local_iterator inode = bucket.begin();
00806 
00807         while (inode != bucket.end())
00808         {
00809           // Do we already have this key?
00810           if (inode->key_value_pair.first == key)
00811           {
00812             break;
00813           }
00814 
00815           ++inode_previous;
00816           ++inode;
00817         }
00818 
00819         // Not already there?
00820         if (inode == bucket.end())
00821         {
00822           // Get a new node.
00823           node_t& node = *pnodepool->allocate<node_t>();
00824           ::new (&node.key_value_pair) value_type(key_value_pair);
00825           ++construct_count;
00826 
00827           // Add the node to the end of the bucket;
00828           bucket.insert_after(inode_previous, node);
00829           ++inode_previous;
00830 
00831           result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
00832           result.second = true;
00833         }
00834       }
00835 
00836       return result;
00837     }
00838 
00839     //*********************************************************************
00840     /// Inserts a value to the unordered_map.
00841     /// If asserts or exceptions are enabled, emits unordered_map_full if the unordered_map is already full.
00842     ///\param position The position to insert at.
00843     ///\param value    The value to insert.
00844     //*********************************************************************
00845     iterator insert(const_iterator position, const value_type& key_value_pair)
00846     {
00847       return insert(key_value_pair).first;
00848     }
00849 
00850     //*********************************************************************
00851     /// Inserts a range of values to the unordered_map.
00852     /// If asserts or exceptions are enabled, emits unordered_map_full if the unordered_map does not have enough free space.
00853     ///\param position The position to insert at.
00854     ///\param first    The first element to add.
00855     ///\param last     The last + 1 element to add.
00856     //*********************************************************************
00857     template <class TIterator>
00858     void insert(TIterator first_, TIterator last_)
00859     {
00860       while (first_ != last_)
00861       {
00862         insert(*first_++);
00863       }
00864     }
00865 
00866     //*********************************************************************
00867     /// Erases an element.
00868     ///\param key The key to erase.
00869     ///\return The number of elements erased. 0 or 1.
00870     //*********************************************************************
00871     size_t erase(key_parameter_t key)
00872     {
00873       size_t n = 0;
00874       size_t index = get_bucket_index(key);
00875 
00876       bucket_t& bucket = pbuckets[index];
00877 
00878       local_iterator iprevious = bucket.before_begin();
00879       local_iterator icurrent = bucket.begin();
00880 
00881       // Search for the key, if we have it.
00882       while ((icurrent != bucket.end()) && (icurrent->key_value_pair.first != key))
00883       {
00884         ++iprevious;
00885         ++icurrent;
00886       }
00887 
00888       // Did we find it?
00889       if (icurrent != bucket.end())
00890       {
00891         bucket.erase_after(iprevious);          // Unlink from the bucket.
00892         icurrent->key_value_pair.~value_type(); // Destroy the value.
00893         pnodepool->release(&*icurrent);         // Release it back to the pool.
00894         n = 1;
00895         --construct_count;
00896       }
00897 
00898       return n;
00899     }
00900 
00901     //*********************************************************************
00902     /// Erases an element.
00903     ///\param ielement Iterator to the element.
00904     //*********************************************************************
00905     iterator erase(const_iterator ielement)
00906     {
00907       // Make a note of the next one.
00908       iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
00909       ++inext;
00910 
00911       bucket_t&      bucket = ielement.get_bucket();
00912       local_iterator iprevious = bucket.before_begin();
00913       local_iterator icurrent = ielement.get_local_iterator();
00914 
00915       // Find the node previous to the one we're interested in.
00916       while (iprevious->etl_next != &*icurrent)
00917       {
00918         ++iprevious;
00919       }
00920 
00921       bucket.erase_after(iprevious);          // Unlink from the bucket.
00922       icurrent->key_value_pair.~value_type(); // Destroy the value.
00923       pnodepool->release(&*icurrent);         // Release it back to the pool.
00924       --construct_count;
00925 
00926       return inext;
00927     }
00928 
00929     //*********************************************************************
00930     /// Erases a range of elements.
00931     /// The range includes all the elements between first and last, including the
00932     /// element pointed by first, but not the one pointed to by last.
00933     ///\param first Iterator to the first element.
00934     ///\param last  Iterator to the last element.
00935     //*********************************************************************
00936     iterator erase(const_iterator first_, const_iterator last_)
00937     {
00938       // Make a note of the last.
00939       iterator result((pbuckets + number_of_buckets), last_.get_bucket_list_iterator(), last_.get_local_iterator());
00940 
00941       // Get the starting point.
00942       bucket_t*      pbucket   = first_.get_bucket_list_iterator();
00943       local_iterator iprevious = pbucket->before_begin();
00944       local_iterator icurrent  = first_.get_local_iterator();
00945       local_iterator iend      = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
00946 
00947       // Find the node previous to the first one.
00948       while (iprevious->etl_next != &*icurrent)
00949       {
00950         ++iprevious;
00951       }
00952 
00953       while (icurrent != iend)
00954       {
00955 
00956         local_iterator inext = pbucket->erase_after(iprevious); // Unlink from the bucket.
00957         icurrent->key_value_pair.~value_type(); // Destroy the value.
00958         pnodepool->release(&*icurrent);         // Release it back to the pool.
00959         --construct_count;
00960 
00961         icurrent = inext;
00962 
00963         // Are we there yet?
00964         if (icurrent != iend)
00965         {
00966           // At the end of this bucket?
00967           if ((icurrent == pbucket->end()))
00968           {
00969             // Find the next non-empty one.
00970             do
00971             {
00972               ++pbucket;
00973             } while (pbucket->empty());
00974 
00975             iprevious = pbucket->before_begin();
00976             icurrent = pbucket->begin();
00977           }
00978         }
00979       }
00980 
00981       return result;
00982     }
00983 
00984     //*************************************************************************
00985     /// Clears the unordered_map.
00986     //*************************************************************************
00987     void clear()
00988     {
00989       initialise();
00990     }
00991 
00992     //*********************************************************************
00993     /// Counts an element.
00994     ///\param key The key to search for.
00995     ///\return 1 if the key exists, otherwise 0.
00996     //*********************************************************************
00997     size_t count(key_parameter_t key) const
00998     {
00999       return (find(key) == end()) ? 0 : 1;
01000     }
01001 
01002     //*********************************************************************
01003     /// Finds an element.
01004     ///\param key The key to search for.
01005     ///\return An iterator to the element if the key exists, otherwise end().
01006     //*********************************************************************
01007     iterator find(key_parameter_t key)
01008     {
01009       size_t index = get_bucket_index(key);
01010 
01011       bucket_t* pbucket = pbuckets + index;
01012       bucket_t& bucket = *pbucket;
01013 
01014       // Is the bucket not empty?
01015       if (!bucket.empty())
01016       {
01017         // Step though the list until we find the end or an equivalent key.
01018         local_iterator inode = bucket.begin();
01019         local_iterator iend = bucket.end();
01020 
01021         while (inode != iend)
01022         {
01023           // Do we have this one?
01024           if (key_equal_function(key, inode->key_value_pair.first))
01025           {
01026             return iterator((pbuckets + number_of_buckets), pbucket, inode);
01027           }
01028 
01029           ++inode;
01030         }
01031       }
01032 
01033       return end();
01034     }
01035 
01036     //*********************************************************************
01037     /// Finds an element.
01038     ///\param key The key to search for.
01039     ///\return An iterator to the element if the key exists, otherwise end().
01040     //*********************************************************************
01041     const_iterator find(key_parameter_t key) const
01042     {
01043       size_t index = get_bucket_index(key);
01044 
01045       bucket_t* pbucket = pbuckets + index;
01046       bucket_t& bucket = *pbucket;
01047 
01048       // Is the bucket not empty?
01049       if (!bucket.empty())
01050       {
01051         // Step though the list until we find the end or an equivalent key.
01052         local_iterator inode = bucket.begin();
01053         local_iterator iend = bucket.end();
01054 
01055         while (inode != iend)
01056         {
01057           // Do we have this one?
01058           if (key_equal_function(key, inode->key_value_pair.first))
01059           {
01060             return iterator((pbuckets + number_of_buckets), pbucket, inode);
01061           }
01062 
01063           ++inode;
01064         }
01065       }
01066 
01067       return end();
01068     }
01069 
01070     //*********************************************************************
01071     /// Returns a range containing all elements with key key in the container.
01072     /// The range is defined by two iterators, the first pointing to the first
01073     /// element of the wanted range and the second pointing past the last
01074     /// element of the range.
01075     ///\param key The key to search for.
01076     ///\return An iterator pair to the range of elements if the key exists, otherwise end().
01077     //*********************************************************************
01078     std::pair<iterator, iterator> equal_range(key_parameter_t key)
01079     {
01080       iterator f = find(key);
01081       iterator l = f;
01082 
01083       if (l != end())
01084       {
01085         ++l;
01086       }
01087 
01088       return std::pair<iterator, iterator>(f, l);
01089     }
01090 
01091     //*********************************************************************
01092     /// Returns a range containing all elements with key key in the container.
01093     /// The range is defined by two iterators, the first pointing to the first
01094     /// element of the wanted range and the second pointing past the last
01095     /// element of the range.
01096     ///\param key The key to search for.
01097     ///\return A const iterator pair to the range of elements if the key exists, otherwise end().
01098     //*********************************************************************
01099     std::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
01100     {
01101       const_iterator f = find(key);
01102       const_iterator l = f;
01103 
01104       if (l != end())
01105       {
01106         ++l;
01107       }
01108 
01109       return std::pair<const_iterator, const_iterator>(f, l);
01110     }
01111 
01112     //*************************************************************************
01113     /// Gets the size of the unordered_map.
01114     //*************************************************************************
01115     size_type size() const
01116     {
01117       return pnodepool->size();
01118     }
01119 
01120     //*************************************************************************
01121     /// Gets the maximum possible size of the unordered_map.
01122     //*************************************************************************
01123     size_type max_size() const
01124     {
01125       return pnodepool->max_size();
01126     }
01127 
01128     //*************************************************************************
01129     /// Checks to see if the unordered_map is empty.
01130     //*************************************************************************
01131     bool empty() const
01132     {
01133       return pnodepool->empty();
01134     }
01135 
01136     //*************************************************************************
01137     /// Checks to see if the unordered_map is full.
01138     //*************************************************************************
01139     bool full() const
01140     {
01141       return pnodepool->full();
01142     }
01143 
01144     //*************************************************************************
01145     /// Returns the remaining capacity.
01146     ///\return The remaining capacity.
01147     //*************************************************************************
01148     size_t available() const
01149     {
01150       return pnodepool->available();
01151     }
01152 
01153     //*************************************************************************
01154     /// Returns the load factor = size / bucket_count.
01155     ///\return The load factor = size / bucket_count.
01156     //*************************************************************************
01157     float load_factor() const
01158     {
01159       return static_cast<float>(size()) / static_cast<float>(bucket_count());
01160     }
01161 
01162     //*************************************************************************
01163     /// Returns the function that hashes the keys.
01164     ///\return The function that hashes the keys..
01165     //*************************************************************************
01166     hasher hash_function() const
01167     {
01168       return key_hash_function;
01169     }
01170 
01171     //*************************************************************************
01172     /// Returns the function that compares the keys.
01173     ///\return The function that compares the keys..
01174     //*************************************************************************
01175     key_equal key_eq() const
01176     {
01177       return key_equal_function;
01178     }
01179 
01180     //*************************************************************************
01181     /// Assignment operator.
01182     //*************************************************************************
01183     iunordered_map& operator = (const iunordered_map& rhs)
01184     {
01185       // Skip if doing self assignment
01186       if (this != &rhs)
01187       {
01188         assign(rhs.cbegin(), rhs.cend());
01189       }
01190 
01191       return *this;
01192     }
01193 
01194   protected:
01195 
01196     //*********************************************************************
01197     /// Constructor.
01198     //*********************************************************************
01199     iunordered_map(pool_t& node_pool_, bucket_t* pbuckets_, size_t number_of_buckets_)
01200       : pnodepool(&node_pool_),
01201         pbuckets(pbuckets_),
01202         number_of_buckets(number_of_buckets_)
01203     {
01204     }
01205 
01206     //*********************************************************************
01207     /// Initialise the unordered_map.
01208     //*********************************************************************
01209     void initialise()
01210     {
01211       if (!empty())
01212       {
01213         // For each bucket...
01214         for (size_t i = 0; i < number_of_buckets; ++i)
01215         {
01216           bucket_t& bucket = pbuckets[i];
01217 
01218           if (!bucket.empty())
01219           {
01220             // For each item in the bucket...
01221             local_iterator it = bucket.begin();
01222 
01223             while (it != bucket.end())
01224             {
01225               // Destroy the value contents.
01226               it->key_value_pair.~value_type();
01227               --construct_count;
01228 
01229               ++it;
01230             }
01231 
01232             // Now it's safe to clear the bucket.
01233             bucket.clear();
01234           }
01235         }
01236 
01237         // Now it's safe to clear the entire pool in one go.
01238         pnodepool->release_all();
01239       }
01240 
01241       first = pbuckets;
01242       last = first;
01243     }
01244 
01245   private:
01246 
01247     //*********************************************************************
01248     /// Adjust the first and last markers according to the new entry.
01249     //*********************************************************************
01250     void adjust_first_last_markers(bucket_t* pbucket)
01251     {
01252       if (pbucket < first)
01253       {
01254         first = pbucket;
01255       }
01256       else if (pbucket > last)
01257       {
01258         last = pbucket;
01259       }
01260     }
01261 
01262     // Disable copy construction.
01263     iunordered_map(const iunordered_map&);
01264 
01265     /// The pool of data nodes used in the list.
01266     pool_t* pnodepool;
01267 
01268     /// The bucket list.
01269     bucket_t* pbuckets;
01270 
01271     /// The number of buckets.
01272     const size_t number_of_buckets;
01273 
01274     /// The first and last pointers to buckets with values.
01275     bucket_t* first;
01276     bucket_t* last;
01277 
01278     /// The function that creates the hashes.
01279     hasher key_hash_function;
01280 
01281     /// The function that compares the keys for equality.
01282     key_equal key_equal_function;
01283 
01284     /// For library debugging purposes only.
01285     etl::debug_count construct_count;
01286   };
01287 
01288   //***************************************************************************
01289   /// Equal operator.
01290   ///\param lhs Reference to the first unordered_map.
01291   ///\param rhs Reference to the second unordered_map.
01292   ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b>
01293   ///\ingroup unordered_map
01294   //***************************************************************************
01295   template <typename TKey, typename TMapped, typename TKeyCompare>
01296   bool operator ==(const etl::iunordered_map<TKey, TMapped, TKeyCompare>& lhs, const etl::iunordered_map<TKey, TMapped, TKeyCompare>& rhs)
01297   {
01298     return (lhs.size() == rhs.size()) && std::equal(lhs.begin(), lhs.end(), rhs.begin());
01299   }
01300 
01301   //***************************************************************************
01302   /// Not equal operator.
01303   ///\param lhs Reference to the first unordered_map.
01304   ///\param rhs Reference to the second unordered_map.
01305   ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b>
01306   ///\ingroup unordered_map
01307   //***************************************************************************
01308   template <typename TKey, typename TMapped, typename TKeyCompare>
01309   bool operator !=(const etl::iunordered_map<TKey, TMapped, TKeyCompare>& lhs, const etl::iunordered_map<TKey, TMapped, TKeyCompare>& rhs)
01310   {
01311     return !(lhs == rhs);
01312   }
01313 
01314   //*************************************************************************
01315   /// A templated unordered_map implementation that uses a fixed size buffer.
01316   //*************************************************************************
01317   template <typename TKey, typename TValue, const size_t MAX_SIZE_, const size_t MAX_BUCKETS_ = MAX_SIZE_, typename THash = etl::hash<TKey>, typename TKeyEqual = std::equal_to<TKey> >
01318   class unordered_map : public etl::iunordered_map<TKey, TValue, THash, TKeyEqual>
01319   {
01320   private:
01321 
01322     typedef iunordered_map<TKey, TValue, THash, TKeyEqual>  base ;
01323 
01324   public:
01325 
01326     static const size_t MAX_SIZE    = MAX_SIZE_;
01327     static const size_t MAX_BUCKETS = MAX_BUCKETS_;
01328 
01329     //*************************************************************************
01330     /// Default constructor.
01331     //*************************************************************************
01332     unordered_map()
01333       : base (node_pool, buckets, MAX_BUCKETS_)
01334     {
01335       base::initialise();
01336     }
01337 
01338     //*************************************************************************
01339     /// Copy constructor.
01340     //*************************************************************************
01341     unordered_map(const unordered_map& other)
01342       : base (node_pool, buckets, MAX_BUCKETS_)
01343     {
01344       base::assign(other.cbegin(), other.cend());
01345     }
01346 
01347     //*************************************************************************
01348     /// Constructor, from an iterator range.
01349     ///\tparam TIterator The iterator type.
01350     ///\param first The iterator to the first element.
01351     ///\param last  The iterator to the last element + 1.
01352     //*************************************************************************
01353     template <typename TIterator>
01354     unordered_map(TIterator first_, TIterator last_)
01355       : base (node_pool, buckets, MAX_BUCKETS_)
01356     {
01357       base::assign(first_, last_);
01358     }
01359 
01360     //*************************************************************************
01361     /// Destructor.
01362     //*************************************************************************
01363     ~unordered_map()
01364     {
01365       base::initialise();
01366     }
01367 
01368     //*************************************************************************
01369     /// Assignment operator.
01370     //*************************************************************************
01371     unordered_map& operator = (const unordered_map& rhs)
01372     {
01373       // Skip if doing self assignment
01374       if (this != &rhs)
01375       {
01376         base::assign(rhs.cbegin(), rhs.cend());
01377       }
01378 
01379       return *this;
01380     }
01381 
01382   private:
01383 
01384     /// The pool of nodes used for the unordered_map.
01385     etl::pool<typename base::node_t, MAX_SIZE>  node_pool;
01386 
01387     /// The buckets of node lists.
01388     etl::intrusive_forward_list<typename base::node_t>  buckets[MAX_BUCKETS_];
01389   };
01390 }
01391 
01392 #undef ETL_FILE
01393 
01394 #endif
01395