addr_range_map.hh revision 5609
1/* 2 * Copyright (c) 2006 The Regents of The University of Michigan 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 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 copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Ali Saidi 29 */ 30 31#ifndef __BASE_RANGE_MAP_HH__ 32#define __BASE_RANGE_MAP_HH__ 33 34#include "base/range.hh" 35 36#include <map> 37 38template <class T,class V> 39class range_map 40{ 41 private: 42 typedef std::map<Range<T>,V> RangeMap; 43 RangeMap tree; 44 45 public: 46 typedef typename RangeMap::iterator iterator; 47 48 template <class U> 49 const iterator 50 find(const Range<U> &r) 51 { 52 iterator i; 53 54 i = tree.upper_bound(r); 55 56 if (i == tree.begin()) { 57 if (i->first.start <= r.end && i->first.end >= r.start) 58 return i; 59 else 60 // Nothing could match, so return end() 61 return tree.end(); 62 } 63 64 i--; 65 66 if (i->first.start <= r.end && i->first.end >= r.start) 67 return i; 68 69 return tree.end(); 70 } 71 72 template <class U> 73 const iterator 74 find(const U &r) 75 { 76 return find(RangeSize(r, 1)); 77 } 78 79 template <class U> 80 bool 81 intersect(const Range<U> &r) 82 { 83 iterator i; 84 i = find(r); 85 if (i != tree.end()) 86 return true; 87 return false; 88 } 89 90 91 template <class U,class W> 92 iterator 93 insert(const Range<U> &r, const W d) 94 { 95 if (intersect(r)) 96 return tree.end(); 97 98 return tree.insert(std::make_pair<Range<T>,V>(r, d)).first; 99 } 100 101 size_t 102 erase(T k) 103 { 104 return tree.erase(k); 105 } 106 107 void 108 erase(iterator p) 109 { 110 tree.erase(p); 111 } 112 113 void 114 erase(iterator p, iterator q) 115 { 116 tree.erase(p,q); 117 } 118 119 void 120 clear() 121 { 122 tree.erase(tree.begin(), tree.end()); 123 } 124 125 iterator 126 begin() 127 { 128 return tree.begin(); 129 } 130 131 iterator 132 end() 133 { 134 return tree.end(); 135 } 136 137 size_t 138 size() 139 { 140 return tree.size(); 141 } 142 143 bool 144 empty() 145 { 146 return tree.empty(); 147 } 148}; 149 150 151template <class T,class V> 152class range_multimap 153{ 154 private: 155 typedef std::multimap<Range<T>,V> RangeMap; 156 RangeMap tree; 157 158 public: 159 typedef typename RangeMap::iterator iterator; 160 161 template <class U> 162 std::pair<iterator,iterator> find(const Range<U> &r) 163 { 164 iterator i; 165 iterator j; 166 167 i = tree.lower_bound(r); 168 169 if (i == tree.begin()) { 170 if (i->first.start <= r.end && i->first.end >= r.start) 171 return std::make_pair<iterator, iterator>(i,i); 172 else 173 // Nothing could match, so return end() 174 return std::make_pair<iterator, iterator>(tree.end(), tree.end()); 175 } 176 i--; 177 178 if (i->first.start <= r.end && i->first.end >= r.start) { 179 // we have at least one match 180 j = i; 181 182 i--; 183 while (i->first.start <= r.end && i->first.end >= 184 r.start) { 185 if (i == tree.begin()) 186 break; 187 i--; 188 } 189 if (i == tree.begin() && i->first.start <= r.end && i->first.end >= 190 r.start) 191 return std::make_pair<iterator, iterator>(i,j); 192 i++; 193 return std::make_pair<iterator, iterator>(i,j); 194 195 } 196 197 return std::make_pair<iterator, iterator>(tree.end(), tree.end()); 198 } 199 200 template <class U> 201 bool 202 intersect(const Range<U> &r) 203 { 204 std::pair<iterator,iterator> p; 205 p = find(r); 206 if (p.first != tree.end()) 207 return true; 208 return false; 209 } 210 211 212 template <class U,class W> 213 iterator 214 insert(const Range<U> &r, const W d) 215 { 216 std::pair<iterator,iterator> p; 217 p = find(r); 218 if (p.first->first.start == r.start && p.first->first.end == r.end || 219 p.first == tree.end()) 220 return tree.insert(std::make_pair<Range<T>,V>(r, d)); 221 else 222 return tree.end(); 223 } 224 225 size_t 226 erase(T k) 227 { 228 return tree.erase(k); 229 } 230 231 void 232 erase(iterator p) 233 { 234 tree.erase(p); 235 } 236 237 void 238 erase(iterator p, iterator q) 239 { 240 tree.erase(p,q); 241 } 242 243 void 244 clear() 245 { 246 tree.erase(tree.begin(), tree.end()); 247 } 248 249 iterator 250 begin() 251 { 252 return tree.begin(); 253 } 254 255 iterator 256 end() 257 { 258 return tree.end(); 259 } 260 261 size_t 262 size() 263 { 264 return tree.size(); 265 } 266 267 bool 268 empty() 269 { 270 return tree.empty(); 271 } 272}; 273 274#endif //__BASE_RANGE_MAP_HH__ 275