aboutsummaryrefslogtreecommitdiff
path: root/src/common/simple_string_dictionary.h
blob: 948492053775c9a8b1748c9414aa513f7442bde8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
// Copyright (c) 2007, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef COMMON_SIMPLE_STRING_DICTIONARY_H_
#define COMMON_SIMPLE_STRING_DICTIONARY_H_

#include <assert.h>
#include <string.h>

#include "common/basictypes.h"

namespace google_breakpad {

// Opaque type for the serialized representation of a NonAllocatingMap. One is
// created in NonAllocatingMap::Serialize and can be deserialized using one of
// the constructors.
struct SerializedNonAllocatingMap;

// NonAllocatingMap is an implementation of a map/dictionary collection that
// uses a fixed amount of storage, so that it does not perform any dynamic
// allocations for its operations.
//
// The actual map storage (the Entry) is guaranteed to be POD, so that it can
// be transmitted over various IPC mechanisms.
//
// The template parameters control the amount of storage used for the key,
// value, and map. The KeySize and ValueSize are measured in bytes, not glyphs,
// and includes space for a \0 byte. This gives space for KeySize-1 and
// ValueSize-1 characters in an entry. NumEntries is the total number of
// entries that will fit in the map.
template <size_t KeySize, size_t ValueSize, size_t NumEntries>
class NonAllocatingMap {
 public:
  // Constant and publicly accessible versions of the template parameters.
  static const size_t key_size = KeySize;
  static const size_t value_size = ValueSize;
  static const size_t num_entries = NumEntries;

  // An Entry object is a single entry in the map. If the key is a 0-length
  // NUL-terminated string, the entry is empty.
  struct Entry {
    char key[KeySize];
    char value[ValueSize];

    bool is_active() const {
      return key[0] != '\0';
    }
  };

  // An Iterator can be used to iterate over all the active entries in a
  // NonAllocatingMap.
  class Iterator {
   public:
    explicit Iterator(const NonAllocatingMap& map)
        : map_(map),
          current_(0) {
    }

    // Returns the next entry in the map, or NULL if at the end of the
    // collection.
    const Entry* Next() {
      while (current_ < map_.num_entries) {
        const Entry* entry = &map_.entries_[current_++];
        if (entry->is_active()) {
          return entry;
        }
      }
      return NULL;
    }

   private:
    const NonAllocatingMap& map_;
    size_t current_;

    DISALLOW_COPY_AND_ASSIGN(Iterator);
  };

  NonAllocatingMap() : entries_() {
  }

  NonAllocatingMap(const NonAllocatingMap& other) {
    *this = other;
  }

  NonAllocatingMap& operator=(const NonAllocatingMap& other) {
    assert(other.key_size == key_size);
    assert(other.value_size == value_size);
    assert(other.num_entries == num_entries);
    if (other.key_size == key_size && other.value_size == value_size &&
        other.num_entries == num_entries) {
      memcpy(entries_, other.entries_, sizeof(entries_));
    }
    return *this;
  }

  // Constructs a map from its serialized form. |map| should be the out
  // parameter from Serialize() and |size| should be its return value.
  NonAllocatingMap(const SerializedNonAllocatingMap* map, size_t size) {
    assert(size == sizeof(entries_));
    if (size == sizeof(entries_)) {
      memcpy(entries_, map, size);
    }
  }

  // Returns the number of active key/value pairs. The upper limit for this
  // is NumEntries.
  size_t GetCount() const {
    size_t count = 0;
    for (size_t i = 0; i < num_entries; ++i) {
      if (entries_[i].is_active()) {
        ++count;
      }
    }
    return count;
  }

  // Given |key|, returns its corresponding |value|. |key| must not be NULL. If
  // the key is not found, NULL is returned.
  const char* GetValueForKey(const char* key) const {
    assert(key);
    if (!key)
      return NULL;

    size_t index = GetEntryIndexForKey(key);
    if (index == num_entries)
      return NULL;

    return entries_[index].value;
  }

  // Stores |value| into |key|, replacing the existing value if |key| is
  // already present. |key| must not be NULL. If |value| is NULL, the key is
  // removed from the map. If there is no more space in the map, then the
  // operation silently fails. Returns an index into the map that can be used
  // to quickly access the entry, or |num_entries| on failure or when clearing
  // a key with a null value.
  size_t SetKeyValue(const char* key, const char* value) {
    if (!value) {
      RemoveKey(key);
      return num_entries;
    }

    assert(key);
    if (!key)
      return num_entries;

    // Key must not be an empty string.
    assert(key[0] != '\0');
    if (key[0] == '\0')
      return num_entries;

    size_t entry_index = GetEntryIndexForKey(key);

    // If it does not yet exist, attempt to insert it.
    if (entry_index == num_entries) {
      for (size_t i = 0; i < num_entries; ++i) {
        if (!entries_[i].is_active()) {
          entry_index = i;
          Entry* entry = &entries_[i];

          strncpy(entry->key, key, key_size);
          entry->key[key_size - 1] = '\0';

          break;
        }
      }
    }

    // If the map is out of space, entry will be NULL.
    if (entry_index == num_entries)
      return num_entries;

#ifndef NDEBUG
    // Sanity check that the key only appears once.
    int count = 0;
    for (size_t i = 0; i < num_entries; ++i) {
      if (strncmp(entries_[i].key, key, key_size) == 0)
        ++count;
    }
    assert(count == 1);
#endif

    strncpy(entries_[entry_index].value, value, value_size);
    entries_[entry_index].value[value_size - 1] = '\0';

    return entry_index;
  }

  // Sets a value for a key that has already been set with SetKeyValue(), using
  // the index returned from that function.
  void SetValueAtIndex(size_t index, const char* value) {
    assert(index < num_entries);
    if (index >= num_entries)
      return;

    Entry* entry = &entries_[index];
    assert(entry->key[0] != '\0');

    strncpy(entry->value, value, value_size);
    entry->value[value_size - 1] = '\0';
  }

  // Given |key|, removes any associated value. |key| must not be NULL. If
  // the key is not found, this is a noop. This invalidates the index
  // returned by SetKeyValue().
  bool RemoveKey(const char* key) {
    assert(key);
    if (!key)
      return false;

    return RemoveAtIndex(GetEntryIndexForKey(key));
  }

  // Removes a value and key using an index that was returned from
  // SetKeyValue(). After a call to this function, the index is invalidated.
  bool RemoveAtIndex(size_t index) {
    if (index >= num_entries)
      return false;

    entries_[index].key[0] = '\0';
    entries_[index].value[0] = '\0';
    return true;
  }

  // Places a serialized version of the map into |map| and returns the size.
  // Both of these should be passed to the deserializing constructor. Note that
  // the serialized |map| is scoped to the lifetime of the non-serialized
  // instance of this class. The |map| can be copied across IPC boundaries.
  size_t Serialize(const SerializedNonAllocatingMap** map) const {
    *map = reinterpret_cast<const SerializedNonAllocatingMap*>(entries_);
    return sizeof(entries_);
  }

 private:
  size_t GetEntryIndexForKey(const char* key) const {
    for (size_t i = 0; i < num_entries; ++i) {
      if (strncmp(key, entries_[i].key, key_size) == 0) {
        return i;
      }
    }
    return num_entries;
  }

  Entry entries_[NumEntries];
};

// For historical reasons this specialized version is available with the same
// size factors as a previous implementation.
typedef NonAllocatingMap<256, 256, 64> SimpleStringDictionary;

}  // namespace google_breakpad

#endif  // COMMON_SIMPLE_STRING_DICTIONARY_H_