2 +----------------------------------------------------------------------+
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 +----------------------------------------------------------------------+
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>
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.
30 template <class K
, class V
, class Hash
, class Equal
>
31 struct InsertionOrderedMap
{
32 using value_type
= std::pair
<K
, V
>;
34 using extractor
= boost::multi_index::member
<
35 value_type
, K
, &value_type::first
>;
38 using map
= boost::multi_index::multi_index_container
<
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
;
48 using iterator
= typename
list_index::iterator
;
49 using const_iterator
= typename
list_index::const_iterator
;
51 InsertionOrderedMap() = default;
52 InsertionOrderedMap(std::initializer_list
<value_type
> il
) {
53 for (auto const& kv
: il
) emplace_back(kv
.first
, kv
.second
);
56 iterator
find(const K
& k
) {
57 return m_map
.template project
<0>(getUnordered().find(k
));
60 const_iterator
find(const K
& k
) const {
61 return m_map
.template project
<0>(getUnordered().find(k
));
65 const_iterator
find(T
&& k
) const {
66 return m_map
.template project
<0>(
67 getUnordered().find(std::forward
<T
>(k
)));
70 void update(iterator it
, const V
& v
) {
71 const_cast<V
&>(it
->second
) = v
;
74 void update(iterator it
, V
&& v
) {
75 const_cast<V
&>(it
->second
) = std::move(v
);
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
);
83 std::pair
<iterator
, bool> emplace_back(const K
& k
, const V
& v
) {
84 return getList().push_back({k
, v
});
87 std::pair
<iterator
, bool> emplace_front(const K
& k
, const V
& v
) {
88 return getList().push_front({k
, v
});
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
) {
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;
106 if (!Equal
{}(kv
.first
, it
->first
)) return false;
107 if (!(kv
.second
== it
->second
)) return false;
112 bool empty() const { return m_map
.empty(); }
113 size_t size() const { return m_map
.size(); }
115 void clear() { m_map
= {}; }
118 unordered_index
& getUnordered() { return m_map
.template get
<Unordered
>(); }
119 const unordered_index
& getUnordered() const {
120 return m_map
.template get
<Unordered
>();
122 list_index
& getList() { return m_map
.template get
<List
>(); }
123 const list_index
& getList() const { return m_map
.template get
<List
>(); }