Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(227)

Side by Side Diff: third_party/WebKit/Source/wtf/FlatMap.h

Issue 2396533004: Introduce a FlatMap and FlatSet into WTF (Closed)
Patch Set: Add missing ostream override Created 4 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « third_party/WebKit/Source/wtf/BUILD.gn ('k') | third_party/WebKit/Source/wtf/FlatMapTest.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright 2016 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef WTF_FlatMap_h
6 #define WTF_FlatMap_h
7
8 #include "base/macros.h"
9 #include "wtf/FlatTable.h"
10
11 namespace WTF {
12
13 template <typename Key, typename Value>
14 struct FlatMapDelegate {
15 using key_type = Key;
16 using value_type = std::pair<Key, Value>;
17
18 static inline const Key& ToKey(const value_type& v) { return v.first; }
19 };
20
21 // A FlatMap is an STL-like associative container backed by a ring buffer.
22 // Generally you should use WTF::HashMap unless you need an associative
23 // container. FlatMap is usually faster than std::map for small maps (<=128)
24 // (sometimes considerably so) and is always faster for immutable maps.
25 template <typename Key, typename Value>
26 class FlatMap : public FlatTable<FlatMapDelegate<Key, Value>> {
27 public:
28 FlatMap() {}
29
30 using BaseClass = FlatTable<FlatMapDelegate<Key, Value>>;
31 using key_type = typename BaseClass::key_type;
32 using value_type = typename BaseClass::value_type;
33 using iterator = typename BaseClass::iterator;
34 using const_iterator = typename BaseClass::const_iterator;
35 using reverse_iterator = typename BaseClass::reverse_iterator;
36 using const_reverse_iterator = typename BaseClass::const_reverse_iterator;
37
38 using BaseClass::empty;
39 using BaseClass::clear;
40 using BaseClass::insert;
41 using BaseClass::insertUnique;
42 using BaseClass::size;
43
44 iterator begin() { return BaseClass::begin(); }
45 iterator end() { return BaseClass::end(); }
46 const_iterator begin() const { return BaseClass::begin(); }
47 const_iterator end() const { return BaseClass::end(); }
48 reverse_iterator rbegin() { return BaseClass::rbegin(); }
49 const_reverse_iterator rbegin() const { return BaseClass::rbegin(); }
50
51 // Erases an entry corresponding to |key|, if any, from the map.
52 // Invalidates any iterators. O(log n + n / 2)
53 size_t erase(const Key& key) { return BaseClass::erase(key); }
54
55 // Erases |it| from the map, invalidating any iterators. O(n / 2)
56 void erase(const iterator& it) { return BaseClass::erase(it); }
57 void erase(const reverse_iterator& it) { return BaseClass::erase(it); }
58
59 // O(log n)
60 iterator find(const Key& key) { return BaseClass::find(key); }
61
62 // O(log n)
63 const_iterator find(const Key& key) const { return BaseClass::find(key); }
64
65 // O(log n + n / 2)
66 void ChangeKey(const iterator& it, const Key& new_key) {
67 size_t index;
68 if (BinarySearch(new_key, &index)) {
69 // We are overwriting an existing entry.
70 ring_buffer_[index].second = std::move(it->second);
71 erase(it);
72 return;
73 }
74
75 ChangeKeyUnique(it, new_key);
76 }
77
78 // O(n / 2)
79 void ChangeKeyUnique(const iterator& it, const Key& new_key) {
80 size_t i = IteratorPosition(it);
81 DCHECK(ValidIndex(i)) << "i = " << i;
82 if (ring_buffer_[i].first < new_key) {
83 Value tempValue = std::move(ring_buffer_[i].second);
84 for (; i != RingPrev(back_) && ring_buffer_[RingNext(i)].first < new_key;
85 i = RingNext(i)) {
86 ring_buffer_[i] = std::move(ring_buffer_[RingNext(i)]);
87 }
88 DCHECK(ValidIndex(i)) << "i = " << i;
89 ring_buffer_[i].first = new_key;
90 ring_buffer_[i].second = std::move(tempValue);
91 } else if (new_key < ring_buffer_[i].first) {
92 Value tempValue = std::move(ring_buffer_[i].second);
93 for (; i != front_ && new_key < ring_buffer_[RingPrev(i)].first;
94 i = RingPrev(i)) {
95 ring_buffer_[i] = std::move(ring_buffer_[RingPrev(i)]);
96 }
97 DCHECK(ValidIndex(i)) << "i = " << i;
98 ring_buffer_[i].first = new_key;
99 ring_buffer_[i].second = std::move(tempValue);
100 }
101 #ifndef NDEBUG
102 BaseClass::InvalidateIterators();
103 #endif
104 }
105
106 private:
107 using BaseClass::BinarySearch;
108 using BaseClass::IteratorPosition;
109 using BaseClass::RingNext;
110 using BaseClass::RingPrev;
111 using BaseClass::ValidIndex;
112 using BaseClass::back_;
113 using BaseClass::front_;
114 using BaseClass::ring_buffer_;
115 };
116
117 } // namespace WTF
118
119 #endif // WTF_FlatMap_h
OLDNEW
« no previous file with comments | « third_party/WebKit/Source/wtf/BUILD.gn ('k') | third_party/WebKit/Source/wtf/FlatMapTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698