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

Side by Side Diff: client/simple_string_dictionary.h

Issue 489993002: Add SimpleStringDictionary and its test (Closed) Base URL: https://chromium.googlesource.com/crashpad/crashpad@master
Patch Set: Breakpad version Created 6 years, 4 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 | « client/client.gyp ('k') | client/simple_string_dictionary.cc » ('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 (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_
OLDNEW
« no previous file with comments | « client/client.gyp ('k') | client/simple_string_dictionary.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698