1  // Copyright 2010 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  // static_map.h: StaticMap.
 30  //
 31  // StaticMap provides lookup interfaces and iterators similar as stl::map's.
 32  // These lookup operations are purely Read-Only, thus memory
 33  // allocation & deallocation is mostly avoided (intentionally).
 34  //
 35  // The chunk of memory should contain data with pre-defined pattern:
 36  // **************** header ***************
 37  // uint32 (4 bytes): number of nodes
 38  // uint32 (4 bytes): address offset of node1's mapped_value
 39  // uint32 (4 bytes): address offset of node2's mapped_value
 40  // ...
 41  // uint32 (4 bytes): address offset of nodeN's mapped_value
 42  //
 43  // ************* Key array ************
 44  // (X bytes): node1's key
 45  // (X bytes): node2's key
 46  // ...
 47  // (X bytes): nodeN's key
 48  //
 49  // ************* Value array **********
 50  // (? bytes): node1's mapped_value
 51  // (? bytes): node2's mapped_value
 52  // ...
 53  // (? bytes): nodeN's mapped_value
 54  //
 55  // REQUIREMENT: Key type MUST be primitive type or pointers so that:
 56  // X = sizeof(typename Key);
 57  //
 58  // Note: since address offset is stored as uint32, user should keep in mind that
 59  // StaticMap only supports up to 4GB size of memory data.
 60  
 61  // Author: Siyang Xie (lambxsy@google.com)
 62  
 63  
 64  #ifndef PROCESSOR_STATIC_MAP_H__
 65  #define PROCESSOR_STATIC_MAP_H__
 66  
 67  #include "processor/static_map_iterator-inl.h"
 68  
 69  namespace google_breakpad {
 70  
 71  // Default functor to compare keys.
 72  template<typename Key>
 73  class DefaultCompare {
 74   public:
 75    int operator()(const Key& k1, const Key& k2) const {
 76      if (k1 < k2) return -1;
 77      if (k1 == k2) return 0;
 78      return 1;
 79    }
 80  };
 81  
 82  template<typename Key, typename Value, typename Compare = DefaultCompare<Key> >
 83  class StaticMap {
 84   public:
 85    typedef StaticMapIterator<Key, Value, Compare> iterator;
 86    typedef StaticMapIterator<Key, Value, Compare> const_iterator;
 87  
 88    StaticMap() : raw_data_(0),
 89                  num_nodes_(0),
 90                  offsets_(0),
 91                  compare_() { }
 92  
 93    explicit StaticMap(const char* raw_data);
 94  
 95    inline bool empty() const { return num_nodes_ == 0; }
 96    inline unsigned int size() const { return num_nodes_; }
 97  
 98    // Return iterators.
 99    inline iterator begin() const { return IteratorAtIndex(0); }
100    inline iterator last() const { return IteratorAtIndex(num_nodes_ - 1); }
101    inline iterator end() const { return IteratorAtIndex(num_nodes_); }
102    inline iterator IteratorAtIndex(int index) const {
103      return iterator(raw_data_, index);
104    }
105  
106    // Lookup operations.
107    iterator find(const Key& k) const;
108  
109    // lower_bound(k) searches in a sorted range for the first element that has a
110    // key not less than the argument k.
111    iterator lower_bound(const Key& k) const;
112  
113    // upper_bound(k) searches in a sorted range for the first element that has a
114    // key greater than the argument k.
115    iterator upper_bound(const Key& k) const;
116  
117    // Checks if the underlying memory data conforms to the predefined pattern:
118    // first check the number of nodes is non-negative,
119    // then check both offsets and keys are strictly increasing (sorted).
120    bool ValidateInMemoryStructure() const;
121  
122   private:
123    const Key GetKeyAtIndex(int i) const;
124  
125    // Start address of a raw memory chunk with serialized data.
126    const char* raw_data_;
127  
128    // Number of nodes in the static map.
129    int32_t num_nodes_;
130  
131    // Array of offset addresses for stored values.
132    // For example:
133    // address_of_i-th_node_value = raw_data_ + offsets_[i]
134    const uint32_t* offsets_;
135  
136    // keys_[i] = key of i_th node
137    const Key* keys_;
138  
139    Compare compare_;
140  };
141  
142  }  // namespace google_breakpad
143  
144  #endif  // PROCESSOR_STATIC_MAP_H__