addr_range_map.hh revision 5609
110037SARM gem5 Developers/* 210037SARM gem5 Developers * Copyright (c) 2006 The Regents of The University of Michigan 310037SARM gem5 Developers * All rights reserved. 410037SARM gem5 Developers * 510037SARM gem5 Developers * Redistribution and use in source and binary forms, with or without 610037SARM gem5 Developers * modification, are permitted provided that the following conditions are 710037SARM gem5 Developers * met: redistributions of source code must retain the above copyright 810037SARM gem5 Developers * notice, this list of conditions and the following disclaimer; 910037SARM gem5 Developers * redistributions in binary form must reproduce the above copyright 1010037SARM gem5 Developers * notice, this list of conditions and the following disclaimer in the 1110037SARM gem5 Developers * documentation and/or other materials provided with the distribution; 1210037SARM gem5 Developers * neither the name of the copyright holders nor the names of its 1310037SARM gem5 Developers * contributors may be used to endorse or promote products derived from 1410037SARM gem5 Developers * this software without specific prior written permission. 1510037SARM gem5 Developers * 1610037SARM gem5 Developers * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1710037SARM gem5 Developers * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1810037SARM gem5 Developers * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1910037SARM gem5 Developers * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2010037SARM gem5 Developers * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2110037SARM gem5 Developers * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2210037SARM gem5 Developers * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2310037SARM gem5 Developers * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2410037SARM gem5 Developers * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2510037SARM gem5 Developers * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2610037SARM gem5 Developers * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2710037SARM gem5 Developers * 2810037SARM gem5 Developers * Authors: Ali Saidi 2910037SARM gem5 Developers */ 3010037SARM gem5 Developers 3110037SARM gem5 Developers#ifndef __BASE_RANGE_MAP_HH__ 3210037SARM gem5 Developers#define __BASE_RANGE_MAP_HH__ 3310037SARM gem5 Developers 3410037SARM gem5 Developers#include "base/range.hh" 3510037SARM gem5 Developers 3610037SARM gem5 Developers#include <map> 3710037SARM gem5 Developers 3810037SARM gem5 Developerstemplate <class T,class V> 3910037SARM gem5 Developersclass range_map 4010037SARM gem5 Developers{ 4110037SARM gem5 Developers private: 4210037SARM gem5 Developers typedef std::map<Range<T>,V> RangeMap; 4310037SARM gem5 Developers RangeMap tree; 4410037SARM gem5 Developers 4510037SARM gem5 Developers public: 4610037SARM gem5 Developers typedef typename RangeMap::iterator iterator; 4710037SARM gem5 Developers 4810037SARM gem5 Developers template <class U> 4910037SARM gem5 Developers const iterator 5010037SARM gem5 Developers find(const Range<U> &r) 5110037SARM gem5 Developers { 5210037SARM gem5 Developers iterator i; 5310037SARM gem5 Developers 5410037SARM gem5 Developers i = tree.upper_bound(r); 5510037SARM gem5 Developers 5610037SARM gem5 Developers if (i == tree.begin()) { 5710037SARM gem5 Developers if (i->first.start <= r.end && i->first.end >= r.start) 5810037SARM gem5 Developers return i; 5910037SARM gem5 Developers else 6010037SARM gem5 Developers // Nothing could match, so return end() 6110037SARM gem5 Developers return tree.end(); 6210037SARM gem5 Developers } 6310037SARM gem5 Developers 6410037SARM gem5 Developers i--; 6510037SARM gem5 Developers 6610037SARM gem5 Developers if (i->first.start <= r.end && i->first.end >= r.start) 6710037SARM gem5 Developers return i; 6810037SARM gem5 Developers 6910037SARM gem5 Developers return tree.end(); 7010037SARM gem5 Developers } 7110037SARM gem5 Developers 7210037SARM gem5 Developers template <class U> 7310037SARM gem5 Developers const iterator 7410037SARM gem5 Developers find(const U &r) 7510037SARM gem5 Developers { 7610037SARM gem5 Developers return find(RangeSize(r, 1)); 7710037SARM gem5 Developers } 7810037SARM gem5 Developers 7910037SARM gem5 Developers template <class U> 8010037SARM gem5 Developers bool 8110037SARM gem5 Developers intersect(const Range<U> &r) 8210037SARM gem5 Developers { 8310037SARM gem5 Developers iterator i; 8410037SARM gem5 Developers i = find(r); 8510037SARM gem5 Developers if (i != tree.end()) 8610037SARM gem5 Developers return true; 8710037SARM gem5 Developers return false; 8810037SARM gem5 Developers } 8910037SARM gem5 Developers 9010037SARM gem5 Developers 9110037SARM gem5 Developers template <class U,class W> 9210037SARM gem5 Developers iterator 9310037SARM gem5 Developers insert(const Range<U> &r, const W d) 9410037SARM gem5 Developers { 9510037SARM gem5 Developers if (intersect(r)) 9610037SARM gem5 Developers return tree.end(); 9710037SARM gem5 Developers 9810037SARM gem5 Developers return tree.insert(std::make_pair<Range<T>,V>(r, d)).first; 9910037SARM gem5 Developers } 10010037SARM gem5 Developers 10110037SARM gem5 Developers size_t 10210037SARM gem5 Developers erase(T k) 10310037SARM gem5 Developers { 10410037SARM gem5 Developers return tree.erase(k); 10510037SARM gem5 Developers } 10610037SARM gem5 Developers 10710037SARM gem5 Developers void 10810037SARM gem5 Developers erase(iterator p) 10910037SARM gem5 Developers { 11010037SARM gem5 Developers tree.erase(p); 11110037SARM gem5 Developers } 11210037SARM gem5 Developers 11310037SARM gem5 Developers void 11410037SARM gem5 Developers erase(iterator p, iterator q) 11510037SARM gem5 Developers { 11610037SARM gem5 Developers tree.erase(p,q); 11710037SARM gem5 Developers } 11810037SARM gem5 Developers 11910037SARM gem5 Developers void 12010037SARM gem5 Developers clear() 12110037SARM gem5 Developers { 12210037SARM gem5 Developers tree.erase(tree.begin(), tree.end()); 12310037SARM gem5 Developers } 12410037SARM gem5 Developers 12510037SARM gem5 Developers iterator 12610037SARM gem5 Developers begin() 12710037SARM gem5 Developers { 12810037SARM gem5 Developers 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