addr_range_map.hh revision 5608
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 bool 74 intersect(const Range<U> &r) 75 { 76 iterator i; 77 i = find(r); 78 if (i != tree.end()) 79 return true; 80 return false; 81 } 82 83 84 template <class U,class W> 85 iterator 86 insert(const Range<U> &r, const W d) 87 { 88 if (intersect(r)) 89 return tree.end(); 90 91 return tree.insert(std::make_pair<Range<T>,V>(r, d)).first; 92 } 93 94 size_t 95 erase(T k) 96 { 97 return tree.erase(k); 98 } 99 100 void 101 erase(iterator p) 102 { 103 tree.erase(p); 104 } 105 106 void 107 erase(iterator p, iterator q) 108 { 109 tree.erase(p,q); 110 } 111 112 void 113 clear() 114 { 115 tree.erase(tree.begin(), tree.end()); 116 } 117 118 iterator 119 begin() 120 { 121 return tree.begin(); 122 } 123 124 iterator 125 end() 126 { 127 return tree.end(); 128 } 129 130 size_t 131 size() 132 { 133 return tree.size(); 134 } 135 136 bool 137 empty() 138 { 139 return tree.empty(); 140 } 141}; 142 143 144template <class T,class V> 145class range_multimap 146{ 147 private: 148 typedef std::multimap<Range<T>,V> RangeMap; 149 RangeMap tree; 150 151 public: 152 typedef typename RangeMap::iterator iterator; 153 154 template <class U> 155 std::pair<iterator,iterator> find(const Range<U> &r) 156 { 157 iterator i; 158 iterator j; 159 160 i = tree.lower_bound(r); 161 162 if (i == tree.begin()) { 163 if (i->first.start <= r.end && i->first.end >= r.start) 164 return std::make_pair<iterator, iterator>(i,i); 165 else 166 // Nothing could match, so return end() 167 return std::make_pair<iterator, iterator>(tree.end(), tree.end()); 168 } 169 i--; 170 171 if (i->first.start <= r.end && i->first.end >= r.start) { 172 // we have at least one match 173 j = i; 174 175 i--; 176 while (i->first.start <= r.end && i->first.end >= 177 r.start) { 178 if (i == tree.begin()) 179 break; 180 i--; 181 } 182 if (i == tree.begin() && i->first.start <= r.end && i->first.end >= 183 r.start) 184 return std::make_pair<iterator, iterator>(i,j); 185 i++; 186 return std::make_pair<iterator, iterator>(i,j); 187 188 } 189 190 return std::make_pair<iterator, iterator>(tree.end(), tree.end()); 191 } 192 193 template <class U> 194 bool 195 intersect(const Range<U> &r) 196 { 197 std::pair<iterator,iterator> p; 198 p = find(r); 199 if (p.first != tree.end()) 200 return true; 201 return false; 202 } 203 204 205 template <class U,class W> 206 iterator 207 insert(const Range<U> &r, const W d) 208 { 209 std::pair<iterator,iterator> p; 210 p = find(r); 211 if (p.first->first.start == r.start && p.first->first.end == r.end || 212 p.first == tree.end()) 213 return tree.insert(std::make_pair<Range<T>,V>(r, d)); 214 else 215 return tree.end(); 216 } 217 218 size_t 219 erase(T k) 220 { 221 return tree.erase(k); 222 } 223 224 void 225 erase(iterator p) 226 { 227 tree.erase(p); 228 } 229 230 void 231 erase(iterator p, iterator q) 232 { 233 tree.erase(p,q); 234 } 235 236 void 237 clear() 238 { 239 tree.erase(tree.begin(), tree.end()); 240 } 241 242 iterator 243 begin() 244 { 245 return tree.begin(); 246 } 247 248 iterator 249 end() 250 { 251 return tree.end(); 252 } 253 254 size_t 255 size() 256 { 257 return tree.size(); 258 } 259 260 bool 261 empty() 262 { 263 return tree.empty(); 264 } 265}; 266 267#endif //__BASE_RANGE_MAP_HH__ 268