hphp/util/insertion-ordered-map.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #pragma once
  17
  18 #include <boost/multi_index/hashed_index.hpp>
  19 #include <boost/multi_index/member.hpp>
  20 #include <boost/multi_index/sequenced_index.hpp>
  21 #include <boost/multi_index_container.hpp>
  22
  23 namespace HPHP {
  24
  25 /*
  26  * This is an insertion-order preserving hash map. Its used to emulate
  27  * the behavior of php and hack arrays in hhbbc. Handling of int-like
  28  * string keys must be done by the user.
  29  */
  30 template <class K, class V, class Hash, class Equal>
  31 struct InsertionOrderedMap {
  32   using value_type = std::pair<K, V>;
  33 private:
  34   using extractor = boost::multi_index::member<
  35     value_type, K, &value_type::first>;
  36   struct List {};
  37   struct Unordered {};
  38   using map = boost::multi_index::multi_index_container<
  39     value_type,
  40     boost::multi_index::indexed_by<
  41       boost::multi_index::sequenced<boost::multi_index::tag<List>>,
  42       boost::multi_index::hashed_unique<boost::multi_index::tag<Unordered>,
  43                                         extractor, Hash, Equal>>>;
  44   using unordered_index = typename boost::multi_index::index<
  45     map, Unordered>::type;
  46   using list_index = typename boost::multi_index::index<map, List>::type;
  47  public:
  48   using iterator = typename list_index::iterator;
  49   using const_iterator = typename list_index::const_iterator;
  50
  51   InsertionOrderedMap() = default;
  52   InsertionOrderedMap(std::initializer_list<value_type> il) {
  53     for (auto const& kv : il) emplace_back(kv.first, kv.second);
  54   }
  55
  56   iterator find(const K& k) {
  57     return m_map.template project<0>(getUnordered().find(k));
  58   }
  59
  60   const_iterator find(const K& k) const {
  61     return m_map.template project<0>(getUnordered().find(k));
  62   }
  63
  64   template<class T>
  65   const_iterator find(T&& k) const {
  66     return m_map.template project<0>(
  67       getUnordered().find(std::forward<T>(k)));
  68   }
  69
  70   void update(iterator it, const V& v) {
  71     const_cast<V&>(it->second) = v;
  72   }
  73
  74   void update(iterator it, V&& v) {
  75     const_cast<V&>(it->second) = std::move(v);
  76   }
  77
  78   V& operator[](const K&k) {
  79     // emplace_back won't insert a new entry if the key already exists
  80     return const_cast<V&>(emplace_back(k, V{}).first->second);
  81   }
  82
  83   std::pair<iterator, bool> emplace_back(const K& k, const V& v) {
  84     return getList().push_back({k, v});
  85   }
  86
  87   std::pair<iterator, bool> emplace_front(const K& k, const V& v) {
  88     return getList().push_front({k, v});
  89   }
  90
  91   iterator begin() { return getList().begin(); }
  92   iterator end()   { return getList().end(); }
  93   const_iterator begin() const { return getList().begin(); }
  94   const_iterator end() const { return getList().end(); }
  95   friend iterator begin(InsertionOrderedMap& m) { return m.begin(); }
  96   friend iterator end(InsertionOrderedMap& m) { return m.end(); }
  97   friend const_iterator begin(const InsertionOrderedMap& m) {
  98     return m.begin();
  99   }
 100   friend const_iterator end(const InsertionOrderedMap& m) { return m.end(); }
 101   friend bool operator==(const InsertionOrderedMap& a,
 102                          const InsertionOrderedMap& b) {
 103     if (a.size() != b.size()) return false;
 104     auto it = b.begin();
 105     for (auto& kv : a) {
 106       if (!Equal{}(kv.first, it->first)) return false;
 107       if (!(kv.second == it->second)) return false;
 108       ++it;
 109     }
 110     return true;
 111   }
 112   bool empty() const { return m_map.empty(); }
 113   size_t size() const { return m_map.size(); }
 114
 115   void clear() { m_map = {}; }
 116
 117  private:
 118   unordered_index& getUnordered() { return m_map.template get<Unordered>(); }
 119   const unordered_index& getUnordered() const {
 120     return m_map.template get<Unordered>();
 121   }
 122   list_index& getList() { return m_map.template get<List>(); }
 123   const list_index& getList() const { return m_map.template get<List>(); }
 124
 125   map m_map;
 126 };
 127
 128 }