1/*
2 * Copyright 2015-present Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16// Copyright 2013-present Facebook. All Rights Reserved.
17// @author: Pavlo Kushnir (pavlo)
18
19#pragma once
20
21#include <initializer_list>
22#include <map>
23#include <memory>
24
25#include <folly/Range.h>
26#include <folly/experimental/StringKeyedCommon.h>
27
28namespace folly {
29
30/**
31 * Wrapper class for map<string, Value> that can
32 * perform lookup operations with StringPiece, not only string.
33 *
34 * It uses kind of hack: string pointed by StringPiece is copied when
35 * StringPiece is inserted into map
36 */
37template <
38 class Value,
39 class Compare = std::less<StringPiece>,
40 class Alloc = std::allocator<std::pair<const StringPiece, Value>>>
41class StringKeyedMap : private std::map<StringPiece, Value, Compare, Alloc> {
42 private:
43 using Base = std::map<StringPiece, Value, Compare, Alloc>;
44
45 public:
46 typedef typename Base::key_type key_type;
47 typedef typename Base::mapped_type mapped_type;
48 typedef typename Base::value_type value_type;
49 typedef typename Base::key_compare key_compare;
50 typedef typename Base::allocator_type allocator_type;
51 typedef typename Base::reference reference;
52 typedef typename Base::const_reference const_reference;
53 typedef typename Base::pointer pointer;
54 typedef typename Base::const_pointer const_pointer;
55 typedef typename Base::iterator iterator;
56 typedef typename Base::const_iterator const_iterator;
57 typedef typename Base::reverse_iterator reverse_iterator;
58 typedef typename Base::const_reverse_iterator const_reverse_iterator;
59 typedef typename Base::difference_type difference_type;
60 typedef typename Base::size_type size_type;
61
62 using Base::get_allocator;
63
64 // Ctors in the same order as
65 // http://cplusplus.com/reference/map/map/map/
66 explicit StringKeyedMap(
67 const key_compare& comp = key_compare(),
68 const allocator_type& alloc = allocator_type())
69 : Base(comp, alloc) {}
70
71 explicit StringKeyedMap(const allocator_type& alloc) : Base(alloc) {}
72
73 template <class InputIterator>
74 explicit StringKeyedMap(
75 InputIterator b,
76 InputIterator e,
77 const key_compare& comp = key_compare(),
78 const allocator_type& alloc = allocator_type())
79 : Base(comp, alloc) {
80 for (; b != e; ++b) {
81 // emplace() will carry the duplication
82 emplace(b->first, b->second);
83 }
84 }
85
86 StringKeyedMap(const StringKeyedMap& rhs)
87 : StringKeyedMap(rhs, rhs.get_allocator()) {}
88
89 StringKeyedMap(const StringKeyedMap& rhs, const allocator_type& a)
90 : StringKeyedMap(rhs.begin(), rhs.end(), rhs.key_comp(), a) {}
91
92 StringKeyedMap(StringKeyedMap&& other) noexcept : Base(std::move(other)) {}
93
94 StringKeyedMap(StringKeyedMap&& other, const allocator_type& /* a */) noexcept
95 : Base(std::move(other) /*, a*/ /* not supported by gcc */) {}
96
97 StringKeyedMap(
98 std::initializer_list<value_type> il,
99 const key_compare& comp = key_compare(),
100 const allocator_type& alloc = allocator_type())
101 : StringKeyedMap(il.begin(), il.end(), comp, alloc) {}
102
103 StringKeyedMap& operator=(const StringKeyedMap& other) & {
104 if (this == &other) {
105 return *this;
106 }
107 return *this = StringKeyedMap(other);
108 }
109
110 StringKeyedMap& operator=(StringKeyedMap&& other) & noexcept {
111 assert(this != &other);
112 clear();
113 Base::operator=(std::move(other));
114 return *this;
115 }
116
117 using Base::begin;
118 using Base::cbegin;
119 using Base::cend;
120 using Base::crbegin;
121 using Base::crend;
122 using Base::empty;
123 using Base::end;
124 using Base::max_size;
125 using Base::rbegin;
126 using Base::rend;
127 using Base::size;
128
129 bool operator==(StringKeyedMap const& other) const {
130 Base const& lhs = *this;
131 Base const& rhs = static_cast<Base const&>(other);
132 return lhs == rhs;
133 }
134
135 // no need for copy/move overload as StringPiece is small struct
136 mapped_type& operator[](StringPiece key) {
137 auto it = find(key);
138 if (it != end()) {
139 return it->second;
140 }
141 // operator[] will create new (key, value) pair
142 // we need to allocate memory for key
143 return Base::operator[](stringPieceDup(key, get_allocator()));
144 }
145
146 using Base::at;
147 using Base::count;
148 using Base::find;
149 using Base::lower_bound;
150 using Base::upper_bound;
151
152 template <class... Args>
153 std::pair<iterator, bool> emplace(StringPiece key, Args&&... args) {
154 auto it = find(key);
155 if (it != end()) {
156 return {it, false};
157 }
158 return Base::emplace(
159 stringPieceDup(key, get_allocator()), std::forward<Args>(args)...);
160 }
161
162 std::pair<iterator, bool> insert(value_type val) {
163 auto it = find(val.first);
164 if (it != end()) {
165 return {it, false};
166 }
167 return Base::insert(std::make_pair(
168 stringPieceDup(val.first, get_allocator()), std::move(val.second)));
169 }
170
171 iterator erase(const_iterator position) {
172 auto key = position->first;
173 auto result = Base::erase(position);
174 stringPieceDel(key, get_allocator());
175 return result;
176 }
177
178 size_type erase(StringPiece key) {
179 auto it = find(key);
180 if (it == end()) {
181 return 0;
182 }
183 erase(it);
184 return 1;
185 }
186
187 void clear() noexcept {
188 for (auto& it : *this) {
189 stringPieceDel(it.first, get_allocator());
190 }
191 Base::clear();
192 }
193
194 using Base::swap;
195
196 ~StringKeyedMap() {
197 // Here we assume that map doesn't use keys in destructor
198 for (auto& it : *this) {
199 stringPieceDel(it.first, get_allocator());
200 }
201 }
202};
203
204} // namespace folly
205