addr_range_map.hh revision 13807:66bd3025e9cc
111986Sandreas.sandberg@arm.com/* 211986Sandreas.sandberg@arm.com * Copyright (c) 2012, 2018 ARM Limited 311986Sandreas.sandberg@arm.com * All rights reserved 411986Sandreas.sandberg@arm.com * 511986Sandreas.sandberg@arm.com * The license below extends only to copyright in the software and shall 611986Sandreas.sandberg@arm.com * not be construed as granting a license to any other intellectual 711986Sandreas.sandberg@arm.com * property including but not limited to intellectual property relating 811986Sandreas.sandberg@arm.com * to a hardware implementation of the functionality of the software 911986Sandreas.sandberg@arm.com * licensed hereunder. You may use the software subject to the license 1011986Sandreas.sandberg@arm.com * terms below provided that you ensure that this notice is replicated 1111986Sandreas.sandberg@arm.com * unmodified and in its entirety in all distributions of the software, 1211986Sandreas.sandberg@arm.com * modified or unmodified, in source code or in binary form. 1311986Sandreas.sandberg@arm.com * 1411986Sandreas.sandberg@arm.com * Copyright (c) 2006 The Regents of The University of Michigan 1511986Sandreas.sandberg@arm.com * All rights reserved. 1611986Sandreas.sandberg@arm.com * 1711986Sandreas.sandberg@arm.com * Redistribution and use in source and binary forms, with or without 1811986Sandreas.sandberg@arm.com * modification, are permitted provided that the following conditions are 1912391Sjason@lowepower.com * met: redistributions of source code must retain the above copyright 2012391Sjason@lowepower.com * notice, this list of conditions and the following disclaimer; 2112391Sjason@lowepower.com * redistributions in binary form must reproduce the above copyright 2211986Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer in the 2312391Sjason@lowepower.com * documentation and/or other materials provided with the distribution; 2411986Sandreas.sandberg@arm.com * neither the name of the copyright holders nor the names of its 2511986Sandreas.sandberg@arm.com * contributors may be used to endorse or promote products derived from 2611986Sandreas.sandberg@arm.com * this software without specific prior written permission. 2711986Sandreas.sandberg@arm.com * 2811986Sandreas.sandberg@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2911986Sandreas.sandberg@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3011986Sandreas.sandberg@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3111986Sandreas.sandberg@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3211986Sandreas.sandberg@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3311986Sandreas.sandberg@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3411986Sandreas.sandberg@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3512391Sjason@lowepower.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3612391Sjason@lowepower.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3712391Sjason@lowepower.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3811986Sandreas.sandberg@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3912391Sjason@lowepower.com * 4012391Sjason@lowepower.com * Authors: Ali Saidi 4111986Sandreas.sandberg@arm.com * Andreas Hansson 4211986Sandreas.sandberg@arm.com */ 4311986Sandreas.sandberg@arm.com 4412037Sandreas.sandberg@arm.com#ifndef __BASE_ADDR_RANGE_MAP_HH__ 4512037Sandreas.sandberg@arm.com#define __BASE_ADDR_RANGE_MAP_HH__ 4612391Sjason@lowepower.com 4712391Sjason@lowepower.com#include <cstddef> 4812391Sjason@lowepower.com#include <functional> 4912391Sjason@lowepower.com#include <list> 5012391Sjason@lowepower.com#include <map> 5112391Sjason@lowepower.com#include <utility> 5212391Sjason@lowepower.com 5312391Sjason@lowepower.com#include "base/addr_range.hh" 5412391Sjason@lowepower.com#include "base/types.hh" 5512391Sjason@lowepower.com 5612391Sjason@lowepower.com/** 5712391Sjason@lowepower.com * The AddrRangeMap uses an STL map to implement an interval tree for 5812391Sjason@lowepower.com * address decoding. The value stored is a template type and can be 5912391Sjason@lowepower.com * e.g. a port identifier, or a pointer. 6012391Sjason@lowepower.com */ 6112391Sjason@lowepower.comtemplate <typename V, int max_cache_size=0> 6212391Sjason@lowepower.comclass AddrRangeMap 6312391Sjason@lowepower.com{ 6412391Sjason@lowepower.com private: 6512391Sjason@lowepower.com typedef std::map<AddrRange, V> RangeMap; 6612391Sjason@lowepower.com 6712391Sjason@lowepower.com public: 6812391Sjason@lowepower.com typedef typename RangeMap::iterator iterator; 6912391Sjason@lowepower.com typedef typename RangeMap::const_iterator const_iterator; 7012391Sjason@lowepower.com 7112391Sjason@lowepower.com /** 7212391Sjason@lowepower.com * Find entry that contains the given address range 7312391Sjason@lowepower.com * 7412037Sandreas.sandberg@arm.com * Searches through the ranges in the address map and returns an 7512037Sandreas.sandberg@arm.com * iterator to the entry which range is a superset of the input 7612037Sandreas.sandberg@arm.com * address range. Returns end() if none found. 7712037Sandreas.sandberg@arm.com * 7812037Sandreas.sandberg@arm.com * @param r An input address range 7912037Sandreas.sandberg@arm.com * @return An iterator that contains the input address range 8012037Sandreas.sandberg@arm.com */ 8112037Sandreas.sandberg@arm.com const_iterator 8212037Sandreas.sandberg@arm.com contains(const AddrRange &r) const 8312037Sandreas.sandberg@arm.com { 8412391Sjason@lowepower.com return find(r, [r](const AddrRange r1) { return r.isSubset(r1); }); 8512391Sjason@lowepower.com } 8612037Sandreas.sandberg@arm.com iterator 8712037Sandreas.sandberg@arm.com contains(const AddrRange &r) 8812037Sandreas.sandberg@arm.com { 8912391Sjason@lowepower.com return find(r, [r](const AddrRange r1) { return r.isSubset(r1); }); 90 } 91 92 /** 93 * Find entry that contains the given address 94 * 95 * Searches through the ranges in the address map and returns an 96 * iterator to the entry which range is a superset of the input 97 * address. Returns end() if none found. 98 * 99 * @param r An input address 100 * @return An iterator that contains the input address 101 */ 102 const_iterator 103 contains(Addr r) const 104 { 105 return contains(RangeSize(r, 1)); 106 } 107 iterator 108 contains(Addr r) 109 { 110 return contains(RangeSize(r, 1)); 111 } 112 113 /** 114 * Find entry that intersects with the given address range 115 * 116 * Searches through the ranges in the address map and returns an 117 * iterator to the first entry which range intersects with the 118 * input address. 119 * 120 * @param r An input address 121 * @return An iterator that intersects with the input address range 122 */ 123 const_iterator 124 intersects(const AddrRange &r) const 125 { 126 return find(r, [r](const AddrRange r1) { return r.intersects(r1); }); 127 } 128 iterator 129 intersects(const AddrRange &r) 130 { 131 return find(r, [r](const AddrRange r1) { return r.intersects(r1); }); 132 } 133 134 iterator 135 insert(const AddrRange &r, const V& d) 136 { 137 if (intersects(r) != end()) 138 return tree.end(); 139 140 return tree.insert(std::make_pair(r, d)).first; 141 } 142 143 void 144 erase(iterator p) 145 { 146 cache.remove(p); 147 tree.erase(p); 148 } 149 150 void 151 erase(iterator p, iterator q) 152 { 153 for (auto it = p; it != q; it++) { 154 cache.remove(p); 155 } 156 tree.erase(p,q); 157 } 158 159 void 160 clear() 161 { 162 cache.erase(cache.begin(), cache.end()); 163 tree.erase(tree.begin(), tree.end()); 164 } 165 166 const_iterator 167 begin() const 168 { 169 return tree.begin(); 170 } 171 172 iterator 173 begin() 174 { 175 return tree.begin(); 176 } 177 178 const_iterator 179 end() const 180 { 181 return tree.end(); 182 } 183 184 iterator 185 end() 186 { 187 return tree.end(); 188 } 189 190 std::size_t 191 size() const 192 { 193 return tree.size(); 194 } 195 196 bool 197 empty() const 198 { 199 return tree.empty(); 200 } 201 202 private: 203 /** 204 * Add an address range map entry to the cache. 205 * 206 * @param it Iterator to the entry in the address range map 207 */ 208 void 209 addNewEntryToCache(iterator it) const 210 { 211 if (max_cache_size != 0) { 212 // If there's a cache, add this element to it. 213 if (cache.size() >= max_cache_size) { 214 // If the cache is full, move the last element to the 215 // front and overwrite it with the new value. This 216 // avoids creating or destroying elements of the list. 217 auto last = cache.end(); 218 last--; 219 *last = it; 220 if (max_cache_size > 1) 221 cache.splice(cache.begin(), cache, last); 222 } else { 223 cache.push_front(it); 224 } 225 } 226 } 227 228 /** 229 * Find entry that satisfies a condition on an address range 230 * 231 * Searches through the ranges in the address map and returns an 232 * iterator to the entry that satisfies the input conidition on 233 * the input address range. Returns end() if none found. 234 * 235 * @param r An input address range 236 * @param f A condition on an address range 237 * @return An iterator that contains the input address range 238 */ 239 iterator 240 find(const AddrRange &r, std::function<bool(const AddrRange)> cond) 241 { 242 // Check the cache first 243 for (auto c = cache.begin(); c != cache.end(); c++) { 244 auto it = *c; 245 if (cond(it->first)) { 246 // If this entry matches, promote it to the front 247 // of the cache and return it. 248 cache.splice(cache.begin(), cache, c); 249 return it; 250 } 251 } 252 253 iterator next = tree.upper_bound(r); 254 if (next != end() && cond(next->first)) { 255 addNewEntryToCache(next); 256 return next; 257 } 258 if (next == begin()) 259 return end(); 260 next--; 261 262 iterator i; 263 do { 264 i = next; 265 if (cond(i->first)) { 266 addNewEntryToCache(i); 267 return i; 268 } 269 // Keep looking if the next range merges with the current one. 270 } while (next != begin() && 271 (--next)->first.mergesWith(i->first)); 272 273 return end(); 274 } 275 276 const_iterator 277 find(const AddrRange &r, std::function<bool(const AddrRange)> cond) const 278 { 279 return const_cast<AddrRangeMap *>(this)->find(r, cond); 280 } 281 282 RangeMap tree; 283 284 /** 285 * A list of iterator that correspond to the max_cache_size most 286 * recently used entries in the address range map. This mainly 287 * used to optimize lookups. The elements in the list should 288 * always be valid iterators of the tree. 289 */ 290 mutable std::list<iterator> cache; 291}; 292 293#endif //__BASE_ADDR_RANGE_MAP_HH__ 294