Home | History | Annotate | Download | only in common 
      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),
     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_
    261