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
38namespace 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.
43struct 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.
57template <size_t KeySize, size_t ValueSize, size_t NumEntries>
58class 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),
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.
256typedef NonAllocatingMap<256, 256, 64> SimpleStringDictionary;
257
258}  // namespace google_breakpad
259
260#endif  // COMMON_SIMPLE_STRING_DICTIONARY_H_
261