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