addr_range_map.hh revision 12783
1/* 2 * Copyright (c) 2012, 2018 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Copyright (c) 2006 The Regents of The University of Michigan 15 * All rights reserved. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions are 19 * met: redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer; 21 * redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution; 24 * neither the name of the copyright holders nor the names of its 25 * contributors may be used to endorse or promote products derived from 26 * this software without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 39 * 40 * Authors: Ali Saidi 41 * Andreas Hansson 42 */ 43 44#ifndef __BASE_ADDR_RANGE_MAP_HH__ 45#define __BASE_ADDR_RANGE_MAP_HH__ 46 47#include <cstddef> 48#include <functional> 49#include <list> 50#include <map> 51#include <utility> 52 53#include "base/addr_range.hh" 54#include "base/types.hh" 55 56/** 57 * The AddrRangeMap uses an STL map to implement an interval tree for 58 * address decoding. The value stored is a template type and can be 59 * e.g. a port identifier, or a pointer. 60 */ 61template <typename V, int max_cache_size=0> 62class AddrRangeMap 63{ 64 private: 65 typedef std::map<AddrRange, V> RangeMap; 66 67 public: 68 typedef typename RangeMap::iterator iterator; 69 typedef typename RangeMap::const_iterator const_iterator; 70 71 /** 72 * Find entry that contains the given address range 73 * 74 * Searches through the ranges in the address map and returns an 75 * iterator to the entry which range is a superset of the input 76 * address range. Returns end() if none found. 77 * 78 * @param r An input address range 79 * @return An iterator that contains the input address range 80 */ 81 const_iterator 82 contains(const AddrRange &r) const 83 { 84 return find(r, [r](const AddrRange r1) { return r.isSubset(r1); }); 85 } 86 87 /** 88 * Find entry that contains the given address 89 * 90 * Searches through the ranges in the address map and returns an 91 * iterator to the entry which range is a superset of the input 92 * address. Returns end() if none found. 93 * 94 * @param r An input address 95 * @return An iterator that contains the input address 96 */ 97 const_iterator 98 contains(Addr r) const 99 { 100 return contains(RangeSize(r, 1)); 101 } 102 103 /** 104 * Find entry that intersects with the given address range 105 * 106 * Searches through the ranges in the address map and returns an 107 * iterator to the first entry which range intersects with the 108 * input address. 109 * 110 * @param r An input address 111 * @return An iterator that intersects with the input address range 112 */ 113 const_iterator 114 intersects(const AddrRange &r) const 115 { 116 return find(r, [r](const AddrRange r1) { return r.intersects(r1); }); 117 } 118 119 const_iterator 120 insert(const AddrRange &r, const V& d) 121 { 122 if (intersects(r) != end()) 123 return tree.end(); 124 125 return tree.insert(std::make_pair(r, d)).first; 126 } 127 128 void 129 erase(iterator p) 130 { 131 cache.remove(p); 132 tree.erase(p); 133 } 134 135 void 136 erase(iterator p, iterator q) 137 { 138 for (auto it = p; it != q; it++) { 139 cache.remove(p); 140 } 141 tree.erase(p,q); 142 } 143 144 void 145 clear() 146 { 147 cache.erase(cache.begin(), cache.end()); 148 tree.erase(tree.begin(), tree.end()); 149 } 150 151 const_iterator 152 begin() const 153 { 154 return tree.begin(); 155 } 156 157 iterator 158 begin() 159 { 160 return tree.begin(); 161 } 162 163 const_iterator 164 end() const 165 { 166 return tree.end(); 167 } 168 169 iterator 170 end() 171 { 172 return tree.end(); 173 } 174 175 std::size_t 176 size() const 177 { 178 return tree.size(); 179 } 180 181 bool 182 empty() const 183 { 184 return tree.empty(); 185 } 186 187 private: 188 /** 189 * Add an address range map entry to the cache. 190 * 191 * @param it Iterator to the entry in the address range map 192 */ 193 void 194 addNewEntryToCache(const_iterator it) const 195 { 196 if (max_cache_size != 0) { 197 // If there's a cache, add this element to it. 198 if (cache.size() >= max_cache_size) { 199 // If the cache is full, move the last element to the 200 // front and overwrite it with the new value. This 201 // avoids creating or destroying elements of the list. 202 auto last = cache.end(); 203 last--; 204 *last = it; 205 if (max_cache_size > 1) 206 cache.splice(cache.begin(), cache, last); 207 } else { 208 cache.push_front(it); 209 } 210 } 211 } 212 213 /** 214 * Find entry that satisfies a condition on an address range 215 * 216 * Searches through the ranges in the address map and returns an 217 * iterator to the entry that satisfies the input conidition on 218 * the input address range. Returns end() if none found. 219 * 220 * @param r An input address range 221 * @param f A condition on an address range 222 * @return An iterator that contains the input address range 223 */ 224 const_iterator 225 find(const AddrRange &r, std::function<bool(const AddrRange)> cond) const 226 { 227 // Check the cache first 228 for (auto c = cache.begin(); c != cache.end(); c++) { 229 auto it = *c; 230 if (cond(it->first)) { 231 // If this entry matches, promote it to the front 232 // of the cache and return it. 233 cache.splice(cache.begin(), cache, c); 234 return it; 235 } 236 } 237 238 const_iterator next = tree.upper_bound(r); 239 if (next != end() && cond(next->first)) { 240 addNewEntryToCache(next); 241 return next; 242 } 243 if (next == begin()) 244 return end(); 245 next--; 246 247 const_iterator i; 248 do { 249 i = next; 250 if (cond(i->first)) { 251 addNewEntryToCache(i); 252 return i; 253 } 254 // Keep looking if the next range merges with the current one. 255 } while (next != begin() && 256 (--next)->first.mergesWith(i->first)); 257 258 return end(); 259 } 260 261 RangeMap tree; 262 263 /** 264 * A list of iterator that correspond to the max_cache_size most 265 * recently used entries in the address range map. This mainly 266 * used to optimize lookups. The elements in the list should 267 * always be valid iterators of the tree. 268 */ 269 mutable std::list<const_iterator> cache; 270}; 271 272#endif //__BASE_ADDR_RANGE_MAP_HH__ 273