1 /* Copyright (c) 2008-2010, 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 * * Neither the name of Google Inc. nor the names of its 11 * contributors may be used to endorse or promote products derived from 12 * this software without specific prior written permission. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 // This file is part of ThreadSanitizer, a dynamic data race detector. 28 // Author: Konstantin Serebryany. 29 #ifndef TS_DENSE_MULTIMAP_ 30 #define TS_DENSE_MULTIMAP_ 31 32 #include "ts_util.h" 33 34 // DenseMultimap is imilar to STL multimap, but optimized for memory. 35 // DenseMultimap objects are immutable after creation. 36 // All CTORs have linear complexity. 37 template<class T, int kPreallocatedElements> 38 class DenseMultimap { 39 public: 40 typedef const T *const_iterator; 41 42 enum RemoveEnum {REMOVE}; 43 44 // Create multimap {t1, t2} DenseMultimap(const T & t1,const T & t2)45 DenseMultimap(const T &t1, const T &t2) { 46 Allocate(2); 47 if (t1 < t2) { 48 ptr_[0] = t1; 49 ptr_[1] = t2; 50 } else { 51 ptr_[0] = t2; 52 ptr_[1] = t1; 53 } 54 Validate(); 55 } 56 57 // Create a copy of m. DenseMultimap(const DenseMultimap & m)58 DenseMultimap(const DenseMultimap &m) { 59 Allocate(m.size()); 60 copy(m.begin(), m.end(), ptr_); 61 Validate(); 62 } 63 64 // Create multimap m+{t} DenseMultimap(const DenseMultimap & m,const T & t)65 DenseMultimap(const DenseMultimap &m, const T &t) { 66 Allocate(m.size() + 1); 67 const_iterator it = lower_bound(m.begin(), m.end(), t); 68 copy(m.begin(), it, ptr_); 69 ptr_[it - m.begin()] = t; 70 copy(it, m.end(), ptr_ + (it - m.begin()) + 1); 71 Validate(); 72 } 73 74 // Create multimap m-{t} DenseMultimap(const DenseMultimap & m,RemoveEnum remove,const T & t)75 DenseMultimap(const DenseMultimap &m, RemoveEnum remove, const T &t) { 76 const_iterator it = lower_bound(m.begin(), m.end(), t); 77 CHECK(it < m.end() && it >= m.begin()); 78 Allocate(m.size() - 1); 79 copy(m.begin(), it, ptr_); 80 copy(it + 1, m.end(), ptr_ + (it - m.begin())); 81 Validate(); 82 } 83 ~DenseMultimap()84 ~DenseMultimap() { 85 if (size_ > kPreallocatedElements) { 86 CHECK(ptr_ != (T*)&array_); 87 delete [] ptr_; 88 } else { 89 CHECK(ptr_ == (T*)&array_); 90 } 91 } 92 size()93 size_t size() const { return size_; } 94 95 const T &operator [] (size_t i) const { 96 CHECK(i < size()); 97 return ptr_[i]; 98 } 99 begin()100 const_iterator begin() const { return ptr_; } end()101 const_iterator end() const { return ptr_ + size(); } 102 has(const T & t)103 bool has(const T&t) const { 104 return binary_search(begin(), end(), t); 105 } 106 107 bool operator < (const DenseMultimap &m) const { 108 if (size() != m.size()) return size() < m.size(); 109 for (size_t i = 0; i < size(); i++) { 110 if (ptr_[i] != m.ptr_[i]) 111 return ptr_[i] < m.ptr_[i]; 112 } 113 return false; 114 } 115 116 private: 117 Allocate(int required_size)118 void Allocate(int required_size) { 119 size_ = required_size; 120 if (size_ <= kPreallocatedElements) { 121 ptr_ = (T*)&array_; 122 } else { 123 ptr_ = new T[size_]; 124 } 125 } 126 Validate()127 void Validate() { 128 for (size_t i = 1; i < size(); i++) { 129 CHECK(ptr_[i-1] <= ptr_[i]); 130 } 131 } 132 133 T *ptr_; 134 int size_; 135 T array_[kPreallocatedElements]; 136 }; 137 138 #endif // TS_DENSE_MULTIMAP_ 139