addr_range_map.hh revision 13807
13101Sstever@eecs.umich.edu/* 23101Sstever@eecs.umich.edu * Copyright (c) 2012, 2018 ARM Limited 33101Sstever@eecs.umich.edu * All rights reserved 43101Sstever@eecs.umich.edu * 53101Sstever@eecs.umich.edu * The license below extends only to copyright in the software and shall 63101Sstever@eecs.umich.edu * not be construed as granting a license to any other intellectual 73101Sstever@eecs.umich.edu * property including but not limited to intellectual property relating 83101Sstever@eecs.umich.edu * to a hardware implementation of the functionality of the software 93101Sstever@eecs.umich.edu * licensed hereunder. You may use the software subject to the license 103101Sstever@eecs.umich.edu * terms below provided that you ensure that this notice is replicated 113101Sstever@eecs.umich.edu * unmodified and in its entirety in all distributions of the software, 123101Sstever@eecs.umich.edu * modified or unmodified, in source code or in binary form. 133101Sstever@eecs.umich.edu * 143101Sstever@eecs.umich.edu * Copyright (c) 2006 The Regents of The University of Michigan 153101Sstever@eecs.umich.edu * All rights reserved. 163101Sstever@eecs.umich.edu * 173101Sstever@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 183101Sstever@eecs.umich.edu * modification, are permitted provided that the following conditions are 193101Sstever@eecs.umich.edu * met: redistributions of source code must retain the above copyright 203101Sstever@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 213101Sstever@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 223101Sstever@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 233101Sstever@eecs.umich.edu * documentation and/or other materials provided with the distribution; 243101Sstever@eecs.umich.edu * neither the name of the copyright holders nor the names of its 253101Sstever@eecs.umich.edu * contributors may be used to endorse or promote products derived from 263101Sstever@eecs.umich.edu * this software without specific prior written permission. 273101Sstever@eecs.umich.edu * 283101Sstever@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 293101Sstever@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 303101Sstever@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 313101Sstever@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 323101Sstever@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 333101Sstever@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 343101Sstever@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 353101Sstever@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 363101Sstever@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 373101Sstever@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 383101Sstever@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 393101Sstever@eecs.umich.edu * 403101Sstever@eecs.umich.edu * Authors: Ali Saidi 413101Sstever@eecs.umich.edu * Andreas Hansson 423101Sstever@eecs.umich.edu */ 433101Sstever@eecs.umich.edu 443101Sstever@eecs.umich.edu#ifndef __BASE_ADDR_RANGE_MAP_HH__ 453101Sstever@eecs.umich.edu#define __BASE_ADDR_RANGE_MAP_HH__ 463101Sstever@eecs.umich.edu 473101Sstever@eecs.umich.edu#include <cstddef> 483101Sstever@eecs.umich.edu#include <functional> 493102Sstever@eecs.umich.edu#include <list> 503101Sstever@eecs.umich.edu#include <map> 513101Sstever@eecs.umich.edu#include <utility> 523101Sstever@eecs.umich.edu 533101Sstever@eecs.umich.edu#include "base/addr_range.hh" 543101Sstever@eecs.umich.edu#include "base/types.hh" 553101Sstever@eecs.umich.edu 563101Sstever@eecs.umich.edu/** 573101Sstever@eecs.umich.edu * The AddrRangeMap uses an STL map to implement an interval tree for 583101Sstever@eecs.umich.edu * address decoding. The value stored is a template type and can be 593101Sstever@eecs.umich.edu * e.g. a port identifier, or a pointer. 603101Sstever@eecs.umich.edu */ 613101Sstever@eecs.umich.edutemplate <typename V, int max_cache_size=0> 623101Sstever@eecs.umich.educlass AddrRangeMap 633101Sstever@eecs.umich.edu{ 643101Sstever@eecs.umich.edu private: 653101Sstever@eecs.umich.edu typedef std::map<AddrRange, V> RangeMap; 663101Sstever@eecs.umich.edu 673101Sstever@eecs.umich.edu public: 683101Sstever@eecs.umich.edu typedef typename RangeMap::iterator iterator; 693101Sstever@eecs.umich.edu typedef typename RangeMap::const_iterator const_iterator; 703101Sstever@eecs.umich.edu 713101Sstever@eecs.umich.edu /** 723101Sstever@eecs.umich.edu * Find entry that contains the given address range 733101Sstever@eecs.umich.edu * 743101Sstever@eecs.umich.edu * Searches through the ranges in the address map and returns an 753101Sstever@eecs.umich.edu * iterator to the entry which range is a superset of the input 763101Sstever@eecs.umich.edu * address range. Returns end() if none found. 773101Sstever@eecs.umich.edu * 783101Sstever@eecs.umich.edu * @param r An input address range 793101Sstever@eecs.umich.edu * @return An iterator that contains the input address range 803101Sstever@eecs.umich.edu */ 813101Sstever@eecs.umich.edu const_iterator 823101Sstever@eecs.umich.edu contains(const AddrRange &r) const 833101Sstever@eecs.umich.edu { 843101Sstever@eecs.umich.edu return find(r, [r](const AddrRange r1) { return r.isSubset(r1); }); 853101Sstever@eecs.umich.edu } 863101Sstever@eecs.umich.edu iterator 873101Sstever@eecs.umich.edu contains(const AddrRange &r) 883101Sstever@eecs.umich.edu { 893101Sstever@eecs.umich.edu return find(r, [r](const AddrRange r1) { return r.isSubset(r1); }); 903101Sstever@eecs.umich.edu } 913101Sstever@eecs.umich.edu 923101Sstever@eecs.umich.edu /** 933101Sstever@eecs.umich.edu * Find entry that contains the given address 943101Sstever@eecs.umich.edu * 953101Sstever@eecs.umich.edu * Searches through the ranges in the address map and returns an 963101Sstever@eecs.umich.edu * iterator to the entry which range is a superset of the input 973101Sstever@eecs.umich.edu * address. Returns end() if none found. 983101Sstever@eecs.umich.edu * 993101Sstever@eecs.umich.edu * @param r An input address 1003101Sstever@eecs.umich.edu * @return An iterator that contains the input address 1013101Sstever@eecs.umich.edu */ 1023101Sstever@eecs.umich.edu const_iterator 1033101Sstever@eecs.umich.edu contains(Addr r) const 1043102Sstever@eecs.umich.edu { 1053101Sstever@eecs.umich.edu return contains(RangeSize(r, 1)); 1063102Sstever@eecs.umich.edu } 1073101Sstever@eecs.umich.edu iterator 1083101Sstever@eecs.umich.edu contains(Addr r) 1093101Sstever@eecs.umich.edu { 1103102Sstever@eecs.umich.edu return contains(RangeSize(r, 1)); 1113102Sstever@eecs.umich.edu } 1123101Sstever@eecs.umich.edu 1133101Sstever@eecs.umich.edu /** 1143101Sstever@eecs.umich.edu * Find entry that intersects with the given address range 1153101Sstever@eecs.umich.edu * 1163101Sstever@eecs.umich.edu * Searches through the ranges in the address map and returns an 1173101Sstever@eecs.umich.edu * iterator to the first entry which range intersects with the 1183101Sstever@eecs.umich.edu * input address. 1193101Sstever@eecs.umich.edu * 1203101Sstever@eecs.umich.edu * @param r An input address 1213101Sstever@eecs.umich.edu * @return An iterator that intersects with the input address range 1223101Sstever@eecs.umich.edu */ 1233101Sstever@eecs.umich.edu const_iterator 1243101Sstever@eecs.umich.edu intersects(const AddrRange &r) const 1253102Sstever@eecs.umich.edu { 1263101Sstever@eecs.umich.edu return find(r, [r](const AddrRange r1) { return r.intersects(r1); }); 1273101Sstever@eecs.umich.edu } 1283101Sstever@eecs.umich.edu iterator 1293101Sstever@eecs.umich.edu intersects(const AddrRange &r) 1303101Sstever@eecs.umich.edu { 1313101Sstever@eecs.umich.edu return find(r, [r](const AddrRange r1) { return r.intersects(r1); }); 1323101Sstever@eecs.umich.edu } 1333101Sstever@eecs.umich.edu 1343101Sstever@eecs.umich.edu iterator 1353101Sstever@eecs.umich.edu insert(const AddrRange &r, const V& d) 1363101Sstever@eecs.umich.edu { 1373101Sstever@eecs.umich.edu if (intersects(r) != end()) 1383101Sstever@eecs.umich.edu return tree.end(); 1393101Sstever@eecs.umich.edu 1403101Sstever@eecs.umich.edu return tree.insert(std::make_pair(r, d)).first; 1413101Sstever@eecs.umich.edu } 1423101Sstever@eecs.umich.edu 1433101Sstever@eecs.umich.edu void 1443101Sstever@eecs.umich.edu erase(iterator p) 1453101Sstever@eecs.umich.edu { 1463101Sstever@eecs.umich.edu cache.remove(p); 1473101Sstever@eecs.umich.edu tree.erase(p); 1483101Sstever@eecs.umich.edu } 1493101Sstever@eecs.umich.edu 1503101Sstever@eecs.umich.edu void 1513101Sstever@eecs.umich.edu erase(iterator p, iterator q) 1523101Sstever@eecs.umich.edu { 1533101Sstever@eecs.umich.edu for (auto it = p; it != q; it++) { 1543101Sstever@eecs.umich.edu cache.remove(p); 1553101Sstever@eecs.umich.edu } 1563101Sstever@eecs.umich.edu tree.erase(p,q); 1573101Sstever@eecs.umich.edu } 1583101Sstever@eecs.umich.edu 1593101Sstever@eecs.umich.edu void 1603101Sstever@eecs.umich.edu clear() 1613101Sstever@eecs.umich.edu { 1623101Sstever@eecs.umich.edu cache.erase(cache.begin(), cache.end()); 1633101Sstever@eecs.umich.edu tree.erase(tree.begin(), tree.end()); 1643101Sstever@eecs.umich.edu } 1653101Sstever@eecs.umich.edu 1663101Sstever@eecs.umich.edu const_iterator 1673101Sstever@eecs.umich.edu begin() const 1683101Sstever@eecs.umich.edu { 1693101Sstever@eecs.umich.edu return tree.begin(); 1703101Sstever@eecs.umich.edu } 1713101Sstever@eecs.umich.edu 1723101Sstever@eecs.umich.edu iterator 1733101Sstever@eecs.umich.edu begin() 1743101Sstever@eecs.umich.edu { 1753101Sstever@eecs.umich.edu return tree.begin(); 1763101Sstever@eecs.umich.edu } 1773101Sstever@eecs.umich.edu 1783101Sstever@eecs.umich.edu const_iterator 1793101Sstever@eecs.umich.edu end() const 1803101Sstever@eecs.umich.edu { 1813101Sstever@eecs.umich.edu return tree.end(); 1823101Sstever@eecs.umich.edu } 1833101Sstever@eecs.umich.edu 1843101Sstever@eecs.umich.edu iterator 1853101Sstever@eecs.umich.edu end() 1863101Sstever@eecs.umich.edu { 1873101Sstever@eecs.umich.edu return tree.end(); 1883101Sstever@eecs.umich.edu } 1893101Sstever@eecs.umich.edu 1903101Sstever@eecs.umich.edu std::size_t 1913101Sstever@eecs.umich.edu size() const 1923101Sstever@eecs.umich.edu { 1933101Sstever@eecs.umich.edu return tree.size(); 1943101Sstever@eecs.umich.edu } 1953101Sstever@eecs.umich.edu 1963101Sstever@eecs.umich.edu bool 1973101Sstever@eecs.umich.edu empty() const 1983101Sstever@eecs.umich.edu { 1993101Sstever@eecs.umich.edu return tree.empty(); 2003101Sstever@eecs.umich.edu } 2013101Sstever@eecs.umich.edu 2023101Sstever@eecs.umich.edu private: 2033101Sstever@eecs.umich.edu /** 2043101Sstever@eecs.umich.edu * Add an address range map entry to the cache. 2053101Sstever@eecs.umich.edu * 2063101Sstever@eecs.umich.edu * @param it Iterator to the entry in the address range map 2073101Sstever@eecs.umich.edu */ 2083101Sstever@eecs.umich.edu void 2093101Sstever@eecs.umich.edu addNewEntryToCache(iterator it) const 2103101Sstever@eecs.umich.edu { 2113101Sstever@eecs.umich.edu if (max_cache_size != 0) { 2123101Sstever@eecs.umich.edu // If there's a cache, add this element to it. 2133101Sstever@eecs.umich.edu if (cache.size() >= max_cache_size) { 2143101Sstever@eecs.umich.edu // If the cache is full, move the last element to the 2153101Sstever@eecs.umich.edu // front and overwrite it with the new value. This 2163101Sstever@eecs.umich.edu // avoids creating or destroying elements of the list. 2173101Sstever@eecs.umich.edu auto last = cache.end(); 2183101Sstever@eecs.umich.edu last--; 2193101Sstever@eecs.umich.edu *last = it; 2203101Sstever@eecs.umich.edu if (max_cache_size > 1) 2213101Sstever@eecs.umich.edu cache.splice(cache.begin(), cache, last); 2223101Sstever@eecs.umich.edu } else { 2233101Sstever@eecs.umich.edu cache.push_front(it); 2243101Sstever@eecs.umich.edu } 2253101Sstever@eecs.umich.edu } 2263101Sstever@eecs.umich.edu } 2273101Sstever@eecs.umich.edu 2283101Sstever@eecs.umich.edu /** 2293101Sstever@eecs.umich.edu * Find entry that satisfies a condition on an address range 2303101Sstever@eecs.umich.edu * 2313101Sstever@eecs.umich.edu * Searches through the ranges in the address map and returns an 2323101Sstever@eecs.umich.edu * iterator to the entry that satisfies the input conidition on 2333101Sstever@eecs.umich.edu * the input address range. Returns end() if none found. 2343101Sstever@eecs.umich.edu * 2353101Sstever@eecs.umich.edu * @param r An input address range 2363101Sstever@eecs.umich.edu * @param f A condition on an address range 2373101Sstever@eecs.umich.edu * @return An iterator that contains the input address range 2383101Sstever@eecs.umich.edu */ 2393101Sstever@eecs.umich.edu iterator 2403101Sstever@eecs.umich.edu find(const AddrRange &r, std::function<bool(const AddrRange)> cond) 2413101Sstever@eecs.umich.edu { 2423101Sstever@eecs.umich.edu // Check the cache first 2433101Sstever@eecs.umich.edu for (auto c = cache.begin(); c != cache.end(); c++) { 2443101Sstever@eecs.umich.edu auto it = *c; 2453101Sstever@eecs.umich.edu if (cond(it->first)) { 2463101Sstever@eecs.umich.edu // If this entry matches, promote it to the front 2473101Sstever@eecs.umich.edu // of the cache and return it. 2483101Sstever@eecs.umich.edu cache.splice(cache.begin(), cache, c); 2493101Sstever@eecs.umich.edu return it; 2503101Sstever@eecs.umich.edu } 2513101Sstever@eecs.umich.edu } 2523101Sstever@eecs.umich.edu 2533101Sstever@eecs.umich.edu iterator next = tree.upper_bound(r); 2543101Sstever@eecs.umich.edu if (next != end() && cond(next->first)) { 2553101Sstever@eecs.umich.edu addNewEntryToCache(next); 2563101Sstever@eecs.umich.edu return next; 2573101Sstever@eecs.umich.edu } 2583101Sstever@eecs.umich.edu if (next == begin()) 2593101Sstever@eecs.umich.edu return end(); 2603101Sstever@eecs.umich.edu next--; 2613101Sstever@eecs.umich.edu 2623101Sstever@eecs.umich.edu iterator i; 2633101Sstever@eecs.umich.edu do { 2643101Sstever@eecs.umich.edu i = next; 2653101Sstever@eecs.umich.edu if (cond(i->first)) { 2663101Sstever@eecs.umich.edu addNewEntryToCache(i); 2673101Sstever@eecs.umich.edu return i; 2683101Sstever@eecs.umich.edu } 2693101Sstever@eecs.umich.edu // Keep looking if the next range merges with the current one. 2703101Sstever@eecs.umich.edu } while (next != begin() && 2713101Sstever@eecs.umich.edu (--next)->first.mergesWith(i->first)); 2723101Sstever@eecs.umich.edu 2733101Sstever@eecs.umich.edu return end(); 2743101Sstever@eecs.umich.edu } 2753101Sstever@eecs.umich.edu 2763101Sstever@eecs.umich.edu const_iterator 2773101Sstever@eecs.umich.edu find(const AddrRange &r, std::function<bool(const AddrRange)> cond) const 2783101Sstever@eecs.umich.edu { 2793101Sstever@eecs.umich.edu return const_cast<AddrRangeMap *>(this)->find(r, cond); 2803101Sstever@eecs.umich.edu } 2813101Sstever@eecs.umich.edu 2823101Sstever@eecs.umich.edu RangeMap tree; 2833101Sstever@eecs.umich.edu 2843101Sstever@eecs.umich.edu /** 2853101Sstever@eecs.umich.edu * A list of iterator that correspond to the max_cache_size most 2863101Sstever@eecs.umich.edu * recently used entries in the address range map. This mainly 2873101Sstever@eecs.umich.edu * used to optimize lookups. The elements in the list should 2883101Sstever@eecs.umich.edu * always be valid iterators of the tree. 2893101Sstever@eecs.umich.edu */ 2903101Sstever@eecs.umich.edu mutable std::list<iterator> cache; 2913101Sstever@eecs.umich.edu}; 2923101Sstever@eecs.umich.edu 2933101Sstever@eecs.umich.edu#endif //__BASE_ADDR_RANGE_MAP_HH__ 2943101Sstever@eecs.umich.edu