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 --- 40 unchanged lines hidden (view full) --- 49 50#include "base/addr_range.hh" 51 52/** 53 * The AddrRangeMap uses an STL map to implement an interval tree for 54 * address decoding. The value stored is a template type and can be 55 * e.g. a port identifier, or a pointer. 56 */ |
57template <typename V, int max_cache_size=0> |
58class AddrRangeMap 59{ 60 private: 61 typedef std::map<AddrRange, V> RangeMap; 62 63 public: 64 typedef typename RangeMap::iterator iterator; 65 typedef typename RangeMap::const_iterator const_iterator; --- 53 unchanged lines hidden (view full) --- 119 return tree.end(); 120 121 return tree.insert(std::make_pair(r, d)).first; 122 } 123 124 void 125 erase(iterator p) 126 { |
127 cache.remove(p); |
128 tree.erase(p); 129 } 130 131 void 132 erase(iterator p, iterator q) 133 { |
134 for (auto it = p; it != q; it++) { 135 cache.remove(p); 136 } |
137 tree.erase(p,q); 138 } 139 140 void 141 clear() 142 { |
143 cache.erase(cache.begin(), cache.end()); |
144 tree.erase(tree.begin(), tree.end()); 145 } 146 147 const_iterator 148 begin() const 149 { 150 return tree.begin(); 151 } --- 25 unchanged lines hidden (view full) --- 177 bool 178 empty() const 179 { 180 return tree.empty(); 181 } 182 183 private: 184 /** |
185 * Add an address range map entry to the cache. 186 * 187 * @param it Iterator to the entry in the address range map 188 */ 189 void 190 addNewEntryToCache(const_iterator it) const 191 { 192 if (max_cache_size != 0) { 193 // If there's a cache, add this element to it. 194 if (cache.size() >= max_cache_size) { 195 // If the cache is full, move the last element to the 196 // front and overwrite it with the new value. This 197 // avoids creating or destroying elements of the list. 198 auto last = cache.end(); 199 last--; 200 *last = it; 201 if (max_cache_size > 1) 202 cache.splice(cache.begin(), cache, last); 203 } else { 204 cache.push_front(it); 205 } 206 } 207 } 208 209 /** |
210 * Find entry that satisfies a condition on an address range 211 * 212 * Searches through the ranges in the address map and returns an 213 * iterator to the entry that satisfies the input conidition on 214 * the input address range. Returns end() if none found. 215 * 216 * @param r An input address range 217 * @param f A condition on an address range 218 * @return An iterator that contains the input address range 219 */ 220 const_iterator 221 find(const AddrRange &r, std::function<bool(const AddrRange)> cond) const 222 { |
223 // Check the cache first 224 for (auto c = cache.begin(); c != cache.end(); c++) { 225 auto it = *c; 226 if (cond(it->first)) { 227 // If this entry matches, promote it to the front 228 // of the cache and return it. 229 cache.splice(cache.begin(), cache, c); 230 return it; 231 } 232 } 233 |
234 const_iterator next = tree.upper_bound(r); 235 if (next != end() && cond(next->first)) { |
236 addNewEntryToCache(next); |
237 return next; 238 } 239 if (next == begin()) 240 return end(); 241 next--; 242 243 const_iterator i; 244 do { 245 i = next; 246 if (cond(i->first)) { |
247 addNewEntryToCache(i); |
248 return i; 249 } 250 // Keep looking if the next range merges with the current one. 251 } while (next != begin() && 252 (--next)->first.mergesWith(i->first)); 253 254 return end(); 255 } 256 257 RangeMap tree; |
258 259 /** 260 * A list of iterator that correspond to the max_cache_size most 261 * recently used entries in the address range map. This mainly 262 * used to optimize lookups. The elements in the list should 263 * always be valid iterators of the tree. 264 */ 265 mutable std::list<const_iterator> cache; |
266}; 267 268#endif //__BASE_ADDR_RANGE_MAP_HH__ |