13804SN/A/* 212776Snikos.nikoleris@arm.com * Copyright (c) 2012, 2018 ARM Limited 39235Sandreas.hansson@arm.com * All rights reserved 49235Sandreas.hansson@arm.com * 59235Sandreas.hansson@arm.com * The license below extends only to copyright in the software and shall 69235Sandreas.hansson@arm.com * not be construed as granting a license to any other intellectual 79235Sandreas.hansson@arm.com * property including but not limited to intellectual property relating 89235Sandreas.hansson@arm.com * to a hardware implementation of the functionality of the software 99235Sandreas.hansson@arm.com * licensed hereunder. You may use the software subject to the license 109235Sandreas.hansson@arm.com * terms below provided that you ensure that this notice is replicated 119235Sandreas.hansson@arm.com * unmodified and in its entirety in all distributions of the software, 129235Sandreas.hansson@arm.com * modified or unmodified, in source code or in binary form. 139235Sandreas.hansson@arm.com * 143804SN/A * Copyright (c) 2006 The Regents of The University of Michigan 153804SN/A * All rights reserved. 163804SN/A * 173804SN/A * Redistribution and use in source and binary forms, with or without 183804SN/A * modification, are permitted provided that the following conditions are 193804SN/A * met: redistributions of source code must retain the above copyright 203804SN/A * notice, this list of conditions and the following disclaimer; 213804SN/A * redistributions in binary form must reproduce the above copyright 223804SN/A * notice, this list of conditions and the following disclaimer in the 233804SN/A * documentation and/or other materials provided with the distribution; 243804SN/A * neither the name of the copyright holders nor the names of its 253804SN/A * contributors may be used to endorse or promote products derived from 263804SN/A * this software without specific prior written permission. 273804SN/A * 283804SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 293804SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 303804SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 313804SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 323804SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 333804SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 343804SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 353804SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 363804SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 373804SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 383804SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 393804SN/A * 403804SN/A * Authors: Ali Saidi 419235Sandreas.hansson@arm.com * Andreas Hansson 423804SN/A */ 433804SN/A 449235Sandreas.hansson@arm.com#ifndef __BASE_ADDR_RANGE_MAP_HH__ 459235Sandreas.hansson@arm.com#define __BASE_ADDR_RANGE_MAP_HH__ 463804SN/A 4712783Snikos.nikoleris@arm.com#include <cstddef> 4812783Snikos.nikoleris@arm.com#include <functional> 4912783Snikos.nikoleris@arm.com#include <list> 508229SN/A#include <map> 518902SN/A#include <utility> 528229SN/A 539235Sandreas.hansson@arm.com#include "base/addr_range.hh" 5412783Snikos.nikoleris@arm.com#include "base/types.hh" 553804SN/A 568918SN/A/** 579235Sandreas.hansson@arm.com * The AddrRangeMap uses an STL map to implement an interval tree for 589235Sandreas.hansson@arm.com * address decoding. The value stored is a template type and can be 599235Sandreas.hansson@arm.com * e.g. a port identifier, or a pointer. 608918SN/A */ 6112777Sgabeblack@google.comtemplate <typename V, int max_cache_size=0> 629235Sandreas.hansson@arm.comclass AddrRangeMap 633804SN/A{ 643804SN/A private: 659235Sandreas.hansson@arm.com typedef std::map<AddrRange, V> RangeMap; 663804SN/A 673804SN/A public: 683804SN/A typedef typename RangeMap::iterator iterator; 698918SN/A typedef typename RangeMap::const_iterator const_iterator; 703804SN/A 7112776Snikos.nikoleris@arm.com /** 7212776Snikos.nikoleris@arm.com * Find entry that contains the given address range 7312776Snikos.nikoleris@arm.com * 7412776Snikos.nikoleris@arm.com * Searches through the ranges in the address map and returns an 7512776Snikos.nikoleris@arm.com * iterator to the entry which range is a superset of the input 7612776Snikos.nikoleris@arm.com * address range. Returns end() if none found. 7712776Snikos.nikoleris@arm.com * 7812776Snikos.nikoleris@arm.com * @param r An input address range 7912776Snikos.nikoleris@arm.com * @return An iterator that contains the input address range 8012776Snikos.nikoleris@arm.com */ 818918SN/A const_iterator 8212776Snikos.nikoleris@arm.com contains(const AddrRange &r) const 838918SN/A { 8412776Snikos.nikoleris@arm.com return find(r, [r](const AddrRange r1) { return r.isSubset(r1); }); 853804SN/A } 8613807Sgabeblack@google.com iterator 8713807Sgabeblack@google.com contains(const AddrRange &r) 8813807Sgabeblack@google.com { 8913807Sgabeblack@google.com return find(r, [r](const AddrRange r1) { return r.isSubset(r1); }); 9013807Sgabeblack@google.com } 913804SN/A 9212776Snikos.nikoleris@arm.com /** 9312776Snikos.nikoleris@arm.com * Find entry that contains the given address 9412776Snikos.nikoleris@arm.com * 9512776Snikos.nikoleris@arm.com * Searches through the ranges in the address map and returns an 9612776Snikos.nikoleris@arm.com * iterator to the entry which range is a superset of the input 9712776Snikos.nikoleris@arm.com * address. Returns end() if none found. 9812776Snikos.nikoleris@arm.com * 9912776Snikos.nikoleris@arm.com * @param r An input address 10012776Snikos.nikoleris@arm.com * @return An iterator that contains the input address 10112776Snikos.nikoleris@arm.com */ 1028918SN/A const_iterator 10312776Snikos.nikoleris@arm.com contains(Addr r) const 1048918SN/A { 10512776Snikos.nikoleris@arm.com return contains(RangeSize(r, 1)); 1068918SN/A } 10713807Sgabeblack@google.com iterator 10813807Sgabeblack@google.com contains(Addr r) 10913807Sgabeblack@google.com { 11013807Sgabeblack@google.com return contains(RangeSize(r, 1)); 11113807Sgabeblack@google.com } 1128918SN/A 11312776Snikos.nikoleris@arm.com /** 11412776Snikos.nikoleris@arm.com * Find entry that intersects with the given address range 11512776Snikos.nikoleris@arm.com * 11612776Snikos.nikoleris@arm.com * Searches through the ranges in the address map and returns an 11712776Snikos.nikoleris@arm.com * iterator to the first entry which range intersects with the 11812776Snikos.nikoleris@arm.com * input address. 11912776Snikos.nikoleris@arm.com * 12012776Snikos.nikoleris@arm.com * @param r An input address 12112776Snikos.nikoleris@arm.com * @return An iterator that intersects with the input address range 12212776Snikos.nikoleris@arm.com */ 12312776Snikos.nikoleris@arm.com const_iterator 12412776Snikos.nikoleris@arm.com intersects(const AddrRange &r) const 1255609SN/A { 12612776Snikos.nikoleris@arm.com return find(r, [r](const AddrRange r1) { return r.intersects(r1); }); 1275609SN/A } 12813807Sgabeblack@google.com iterator 12913807Sgabeblack@google.com intersects(const AddrRange &r) 13013807Sgabeblack@google.com { 13113807Sgabeblack@google.com return find(r, [r](const AddrRange r1) { return r.intersects(r1); }); 13213807Sgabeblack@google.com } 1335609SN/A 13413807Sgabeblack@google.com iterator 1359235Sandreas.hansson@arm.com insert(const AddrRange &r, const V& d) 1363804SN/A { 13712776Snikos.nikoleris@arm.com if (intersects(r) != end()) 1383804SN/A return tree.end(); 1393804SN/A 1408902SN/A return tree.insert(std::make_pair(r, d)).first; 1413804SN/A } 1423804SN/A 1435608SN/A void 1445608SN/A erase(iterator p) 1453804SN/A { 14612777Sgabeblack@google.com cache.remove(p); 1473804SN/A tree.erase(p); 1483804SN/A } 1493804SN/A 1505608SN/A void 1515608SN/A erase(iterator p, iterator q) 1523804SN/A { 15312777Sgabeblack@google.com for (auto it = p; it != q; it++) { 15412777Sgabeblack@google.com cache.remove(p); 15512777Sgabeblack@google.com } 1563804SN/A tree.erase(p,q); 1573804SN/A } 1583804SN/A 1595608SN/A void 1605608SN/A clear() 1613804SN/A { 16212777Sgabeblack@google.com cache.erase(cache.begin(), cache.end()); 1633804SN/A tree.erase(tree.begin(), tree.end()); 1643804SN/A } 1653804SN/A 1668918SN/A const_iterator 1678918SN/A begin() const 1688918SN/A { 1698918SN/A return tree.begin(); 1708918SN/A } 1718918SN/A 1725608SN/A iterator 1735608SN/A begin() 1743804SN/A { 1753804SN/A return tree.begin(); 1763804SN/A } 1773804SN/A 1788918SN/A const_iterator 1798918SN/A end() const 1808918SN/A { 1818918SN/A return tree.end(); 1828918SN/A } 1838918SN/A 1845608SN/A iterator 1855608SN/A end() 1863804SN/A { 1873804SN/A return tree.end(); 1883804SN/A } 1893804SN/A 1909235Sandreas.hansson@arm.com std::size_t 1918918SN/A size() const 1923804SN/A { 1933804SN/A return tree.size(); 1943804SN/A } 1953804SN/A 1965608SN/A bool 1978918SN/A empty() const 1983804SN/A { 1993804SN/A return tree.empty(); 2003804SN/A } 20112776Snikos.nikoleris@arm.com 20212776Snikos.nikoleris@arm.com private: 20312776Snikos.nikoleris@arm.com /** 20412777Sgabeblack@google.com * Add an address range map entry to the cache. 20512777Sgabeblack@google.com * 20612777Sgabeblack@google.com * @param it Iterator to the entry in the address range map 20712777Sgabeblack@google.com */ 20812777Sgabeblack@google.com void 20913807Sgabeblack@google.com addNewEntryToCache(iterator it) const 21012777Sgabeblack@google.com { 21112777Sgabeblack@google.com if (max_cache_size != 0) { 21212777Sgabeblack@google.com // If there's a cache, add this element to it. 21312777Sgabeblack@google.com if (cache.size() >= max_cache_size) { 21412777Sgabeblack@google.com // If the cache is full, move the last element to the 21512777Sgabeblack@google.com // front and overwrite it with the new value. This 21612777Sgabeblack@google.com // avoids creating or destroying elements of the list. 21712777Sgabeblack@google.com auto last = cache.end(); 21812777Sgabeblack@google.com last--; 21912777Sgabeblack@google.com *last = it; 22012777Sgabeblack@google.com if (max_cache_size > 1) 22112777Sgabeblack@google.com cache.splice(cache.begin(), cache, last); 22212777Sgabeblack@google.com } else { 22312777Sgabeblack@google.com cache.push_front(it); 22412777Sgabeblack@google.com } 22512777Sgabeblack@google.com } 22612777Sgabeblack@google.com } 22712777Sgabeblack@google.com 22812777Sgabeblack@google.com /** 22912776Snikos.nikoleris@arm.com * Find entry that satisfies a condition on an address range 23012776Snikos.nikoleris@arm.com * 23112776Snikos.nikoleris@arm.com * Searches through the ranges in the address map and returns an 23212776Snikos.nikoleris@arm.com * iterator to the entry that satisfies the input conidition on 23312776Snikos.nikoleris@arm.com * the input address range. Returns end() if none found. 23412776Snikos.nikoleris@arm.com * 23512776Snikos.nikoleris@arm.com * @param r An input address range 23612776Snikos.nikoleris@arm.com * @param f A condition on an address range 23712776Snikos.nikoleris@arm.com * @return An iterator that contains the input address range 23812776Snikos.nikoleris@arm.com */ 23913807Sgabeblack@google.com iterator 24013807Sgabeblack@google.com find(const AddrRange &r, std::function<bool(const AddrRange)> cond) 24112776Snikos.nikoleris@arm.com { 24212777Sgabeblack@google.com // Check the cache first 24312777Sgabeblack@google.com for (auto c = cache.begin(); c != cache.end(); c++) { 24412777Sgabeblack@google.com auto it = *c; 24512777Sgabeblack@google.com if (cond(it->first)) { 24612777Sgabeblack@google.com // If this entry matches, promote it to the front 24712777Sgabeblack@google.com // of the cache and return it. 24812777Sgabeblack@google.com cache.splice(cache.begin(), cache, c); 24912777Sgabeblack@google.com return it; 25012777Sgabeblack@google.com } 25112777Sgabeblack@google.com } 25212777Sgabeblack@google.com 25313807Sgabeblack@google.com iterator next = tree.upper_bound(r); 25412776Snikos.nikoleris@arm.com if (next != end() && cond(next->first)) { 25512777Sgabeblack@google.com addNewEntryToCache(next); 25612776Snikos.nikoleris@arm.com return next; 25712776Snikos.nikoleris@arm.com } 25812776Snikos.nikoleris@arm.com if (next == begin()) 25912776Snikos.nikoleris@arm.com return end(); 26012776Snikos.nikoleris@arm.com next--; 26112776Snikos.nikoleris@arm.com 26213807Sgabeblack@google.com iterator i; 26312776Snikos.nikoleris@arm.com do { 26412776Snikos.nikoleris@arm.com i = next; 26512776Snikos.nikoleris@arm.com if (cond(i->first)) { 26612777Sgabeblack@google.com addNewEntryToCache(i); 26712776Snikos.nikoleris@arm.com return i; 26812776Snikos.nikoleris@arm.com } 26912776Snikos.nikoleris@arm.com // Keep looking if the next range merges with the current one. 27012776Snikos.nikoleris@arm.com } while (next != begin() && 27112776Snikos.nikoleris@arm.com (--next)->first.mergesWith(i->first)); 27212776Snikos.nikoleris@arm.com 27312776Snikos.nikoleris@arm.com return end(); 27412776Snikos.nikoleris@arm.com } 27512776Snikos.nikoleris@arm.com 27613807Sgabeblack@google.com const_iterator 27713807Sgabeblack@google.com find(const AddrRange &r, std::function<bool(const AddrRange)> cond) const 27813807Sgabeblack@google.com { 27913807Sgabeblack@google.com return const_cast<AddrRangeMap *>(this)->find(r, cond); 28013807Sgabeblack@google.com } 28113807Sgabeblack@google.com 28212776Snikos.nikoleris@arm.com RangeMap tree; 28312777Sgabeblack@google.com 28412777Sgabeblack@google.com /** 28512777Sgabeblack@google.com * A list of iterator that correspond to the max_cache_size most 28612777Sgabeblack@google.com * recently used entries in the address range map. This mainly 28712777Sgabeblack@google.com * used to optimize lookups. The elements in the list should 28812777Sgabeblack@google.com * always be valid iterators of the tree. 28912777Sgabeblack@google.com */ 29013807Sgabeblack@google.com mutable std::list<iterator> cache; 2913804SN/A}; 2923804SN/A 2939235Sandreas.hansson@arm.com#endif //__BASE_ADDR_RANGE_MAP_HH__ 294