OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2007, Google Inc. | |
2 // All rights reserved. | |
3 // | |
4 // Redistribution and use in source and binary forms, with or without | |
5 // modification, are permitted provided that the following conditions are | |
6 // met: | |
7 // | |
8 // * Redistributions of source code must retain the above copyright | |
9 // notice, this list of conditions and the following disclaimer. | |
10 // * Redistributions in binary form must reproduce the above | |
11 // copyright notice, this list of conditions and the following disclaimer | |
12 // in the documentation and/or other materials provided with the | |
13 // distribution. | |
14 // * Neither the name of Google Inc. nor the names of its | |
15 // contributors may be used to endorse or promote products derived from | |
16 // this software without specific prior written permission. | |
17 // | |
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
29 | |
30 #ifndef COMMON_SIMPLE_STRING_DICTIONARY_H_ | |
31 #define COMMON_SIMPLE_STRING_DICTIONARY_H_ | |
32 | |
33 #include <assert.h> | |
34 #include <string.h> | |
35 | |
36 #include "common/basictypes.h" | |
37 | |
38 namespace google_breakpad { | |
39 | |
40 // Opaque type for the serialized representation of a NonAllocatingMap. One is | |
41 // created in NonAllocatingMap::Serialize and can be deserialized using one of | |
42 // the constructors. | |
43 struct SerializedNonAllocatingMap; | |
44 | |
45 // NonAllocatingMap is an implementation of a map/dictionary collection that | |
46 // uses a fixed amount of storage, so that it does not perform any dynamic | |
47 // allocations for its operations. | |
48 // | |
49 // The actual map storage (the Entry) is guaranteed to be POD, so that it can | |
50 // be transmitted over various IPC mechanisms. | |
51 // | |
52 // The template parameters control the amount of storage used for the key, | |
53 // value, and map. The KeySize and ValueSize are measured in bytes, not glyphs, | |
54 // and includes space for a \0 byte. This gives space for KeySize-1 and | |
55 // ValueSize-1 characters in an entry. NumEntries is the total number of | |
56 // entries that will fit in the map. | |
57 template <size_t KeySize, size_t ValueSize, size_t NumEntries> | |
58 class NonAllocatingMap { | |
59 public: | |
60 // Constant and publicly accessible versions of the template parameters. | |
61 static const size_t key_size = KeySize; | |
62 static const size_t value_size = ValueSize; | |
63 static const size_t num_entries = NumEntries; | |
64 | |
65 // An Entry object is a single entry in the map. If the key is a 0-length | |
66 // NUL-terminated string, the entry is empty. | |
67 struct Entry { | |
68 char key[KeySize]; | |
69 char value[ValueSize]; | |
70 | |
71 bool is_active() const { | |
72 return key[0] != '\0'; | |
73 } | |
74 }; | |
75 | |
76 // An Iterator can be used to iterate over all the active entries in a | |
77 // NonAllocatingMap. | |
78 class Iterator { | |
79 public: | |
80 explicit Iterator(const NonAllocatingMap& map) | |
81 : map_(map), | |
Robert Sesek
2014/08/21 16:55:15
I'm not sure these clang-format changes are actual
| |
82 current_(0) { | |
83 } | |
84 | |
85 // Returns the next entry in the map, or NULL if at the end of the | |
86 // collection. | |
87 const Entry* Next() { | |
88 while (current_ < map_.num_entries) { | |
89 const Entry* entry = &map_.entries_[current_++]; | |
90 if (entry->is_active()) { | |
91 return entry; | |
92 } | |
93 } | |
94 return NULL; | |
95 } | |
96 | |
97 private: | |
98 const NonAllocatingMap& map_; | |
99 size_t current_; | |
100 | |
101 DISALLOW_COPY_AND_ASSIGN(Iterator); | |
102 }; | |
103 | |
104 NonAllocatingMap() : entries_() { | |
105 } | |
106 | |
107 NonAllocatingMap(const NonAllocatingMap& other) { | |
108 *this = other; | |
109 } | |
110 | |
111 NonAllocatingMap& operator=(const NonAllocatingMap& other) { | |
112 assert(other.key_size == key_size); | |
113 assert(other.value_size == value_size); | |
114 assert(other.num_entries == num_entries); | |
115 if (other.key_size == key_size && other.value_size == value_size && | |
116 other.num_entries == num_entries) { | |
117 memcpy(entries_, other.entries_, sizeof(entries_)); | |
118 } | |
119 return *this; | |
120 } | |
121 | |
122 // Constructs a map from its serialized form. |map| should be the out | |
123 // parameter from Serialize() and |size| should be its return value. | |
124 NonAllocatingMap(const SerializedNonAllocatingMap* map, size_t size) { | |
125 assert(size == sizeof(entries_)); | |
126 if (size == sizeof(entries_)) { | |
127 memcpy(entries_, map, size); | |
128 } | |
129 } | |
130 | |
131 // Returns the number of active key/value pairs. The upper limit for this | |
132 // is NumEntries. | |
133 size_t GetCount() const { | |
134 size_t count = 0; | |
135 for (size_t i = 0; i < num_entries; ++i) { | |
136 if (entries_[i].is_active()) { | |
137 ++count; | |
138 } | |
139 } | |
140 return count; | |
141 } | |
142 | |
143 // Given |key|, returns its corresponding |value|. |key| must not be NULL. If | |
144 // the key is not found, NULL is returned. | |
145 const char* GetValueForKey(const char* key) const { | |
146 assert(key); | |
147 if (!key) | |
148 return NULL; | |
149 | |
150 const Entry* entry = GetConstEntryForKey(key); | |
151 if (!entry) | |
152 return NULL; | |
153 | |
154 return entry->value; | |
155 } | |
156 | |
157 // Stores |value| into |key|, replacing the existing value if |key| is | |
158 // already present. |key| must not be NULL. If |value| is NULL, the key is | |
159 // removed from the map. If there is no more space in the map, then the | |
160 // operation silently fails. | |
161 void SetKeyValue(const char* key, const char* value) { | |
162 if (!value) { | |
163 RemoveKey(key); | |
164 return; | |
165 } | |
166 | |
167 assert(key); | |
168 if (!key) | |
169 return; | |
170 | |
171 // Key must not be an empty string. | |
172 assert(key[0] != '\0'); | |
173 if (key[0] == '\0') | |
174 return; | |
175 | |
176 Entry* entry = GetEntryForKey(key); | |
177 | |
178 // If it does not yet exist, attempt to insert it. | |
179 if (!entry) { | |
180 for (size_t i = 0; i < num_entries; ++i) { | |
181 if (!entries_[i].is_active()) { | |
182 entry = &entries_[i]; | |
183 | |
184 strncpy(entry->key, key, key_size); | |
185 entry->key[key_size - 1] = '\0'; | |
186 | |
187 break; | |
188 } | |
189 } | |
190 } | |
191 | |
192 // If the map is out of space, entry will be NULL. | |
193 if (!entry) | |
194 return; | |
195 | |
196 #ifndef NDEBUG | |
197 // Sanity check that the key only appears once. | |
198 int count = 0; | |
199 for (size_t i = 0; i < num_entries; ++i) { | |
200 if (strncmp(entries_[i].key, key, key_size) == 0) | |
201 ++count; | |
202 } | |
203 assert(count == 1); | |
204 #endif | |
205 | |
206 strncpy(entry->value, value, value_size); | |
207 entry->value[value_size - 1] = '\0'; | |
208 } | |
209 | |
210 // Given |key|, removes any associated value. |key| must not be NULL. If | |
211 // the key is not found, this is a noop. | |
212 void RemoveKey(const char* key) { | |
213 assert(key); | |
214 if (!key) | |
215 return; | |
216 | |
217 Entry* entry = GetEntryForKey(key); | |
218 if (entry) { | |
219 entry->key[0] = '\0'; | |
220 entry->value[0] = '\0'; | |
221 } | |
222 | |
223 #ifndef NDEBUG | |
224 assert(GetEntryForKey(key) == NULL); | |
225 #endif | |
226 } | |
227 | |
228 // Places a serialized version of the map into |map| and returns the size. | |
229 // Both of these should be passed to the deserializing constructor. Note that | |
230 // the serialized |map| is scoped to the lifetime of the non-serialized | |
231 // instance of this class. The |map| can be copied across IPC boundaries. | |
232 size_t Serialize(const SerializedNonAllocatingMap** map) const { | |
233 *map = reinterpret_cast<const SerializedNonAllocatingMap*>(entries_); | |
234 return sizeof(entries_); | |
235 } | |
236 | |
237 private: | |
238 const Entry* GetConstEntryForKey(const char* key) const { | |
239 for (size_t i = 0; i < num_entries; ++i) { | |
240 if (strncmp(key, entries_[i].key, key_size) == 0) { | |
241 return &entries_[i]; | |
242 } | |
243 } | |
244 return NULL; | |
245 } | |
246 | |
247 Entry* GetEntryForKey(const char* key) { | |
248 return const_cast<Entry*>(GetConstEntryForKey(key)); | |
249 } | |
250 | |
251 Entry entries_[NumEntries]; | |
252 }; | |
253 | |
254 // For historical reasons this specialized version is available with the same | |
255 // size factors as a previous implementation. | |
256 typedef NonAllocatingMap<256, 256, 64> SimpleStringDictionary; | |
257 | |
258 } // namespace google_breakpad | |
259 | |
260 #endif // COMMON_SIMPLE_STRING_DICTIONARY_H_ | |
OLD | NEW |