addr_range_map.hh revision 12777
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 478229SN/A#include <map> 488902SN/A#include <utility> 498229SN/A 509235Sandreas.hansson@arm.com#include "base/addr_range.hh" 513804SN/A 528918SN/A/** 539235Sandreas.hansson@arm.com * The AddrRangeMap uses an STL map to implement an interval tree for 549235Sandreas.hansson@arm.com * address decoding. The value stored is a template type and can be 559235Sandreas.hansson@arm.com * e.g. a port identifier, or a pointer. 568918SN/A */ 5712777Sgabeblack@google.comtemplate <typename V, int max_cache_size=0> 589235Sandreas.hansson@arm.comclass AddrRangeMap 593804SN/A{ 603804SN/A private: 619235Sandreas.hansson@arm.com typedef std::map<AddrRange, V> RangeMap; 623804SN/A 633804SN/A public: 643804SN/A typedef typename RangeMap::iterator iterator; 658918SN/A typedef typename RangeMap::const_iterator const_iterator; 663804SN/A 6712776Snikos.nikoleris@arm.com /** 6812776Snikos.nikoleris@arm.com * Find entry that contains the given address range 6912776Snikos.nikoleris@arm.com * 7012776Snikos.nikoleris@arm.com * Searches through the ranges in the address map and returns an 7112776Snikos.nikoleris@arm.com * iterator to the entry which range is a superset of the input 7212776Snikos.nikoleris@arm.com * address range. Returns end() if none found. 7312776Snikos.nikoleris@arm.com * 7412776Snikos.nikoleris@arm.com * @param r An input address range 7512776Snikos.nikoleris@arm.com * @return An iterator that contains the input address range 7612776Snikos.nikoleris@arm.com */ 778918SN/A const_iterator 7812776Snikos.nikoleris@arm.com contains(const AddrRange &r) const 798918SN/A { 8012776Snikos.nikoleris@arm.com return find(r, [r](const AddrRange r1) { return r.isSubset(r1); }); 813804SN/A } 823804SN/A 8312776Snikos.nikoleris@arm.com /** 8412776Snikos.nikoleris@arm.com * Find entry that contains the given address 8512776Snikos.nikoleris@arm.com * 8612776Snikos.nikoleris@arm.com * Searches through the ranges in the address map and returns an 8712776Snikos.nikoleris@arm.com * iterator to the entry which range is a superset of the input 8812776Snikos.nikoleris@arm.com * address. Returns end() if none found. 8912776Snikos.nikoleris@arm.com * 9012776Snikos.nikoleris@arm.com * @param r An input address 9112776Snikos.nikoleris@arm.com * @return An iterator that contains the input address 9212776Snikos.nikoleris@arm.com */ 938918SN/A const_iterator 9412776Snikos.nikoleris@arm.com contains(Addr r) const 958918SN/A { 9612776Snikos.nikoleris@arm.com return contains(RangeSize(r, 1)); 978918SN/A } 988918SN/A 9912776Snikos.nikoleris@arm.com /** 10012776Snikos.nikoleris@arm.com * Find entry that intersects with the given address range 10112776Snikos.nikoleris@arm.com * 10212776Snikos.nikoleris@arm.com * Searches through the ranges in the address map and returns an 10312776Snikos.nikoleris@arm.com * iterator to the first entry which range intersects with the 10412776Snikos.nikoleris@arm.com * input address. 10512776Snikos.nikoleris@arm.com * 10612776Snikos.nikoleris@arm.com * @param r An input address 10712776Snikos.nikoleris@arm.com * @return An iterator that intersects with the input address range 10812776Snikos.nikoleris@arm.com */ 10912776Snikos.nikoleris@arm.com const_iterator 11012776Snikos.nikoleris@arm.com intersects(const AddrRange &r) const 1115609SN/A { 11212776Snikos.nikoleris@arm.com return find(r, [r](const AddrRange r1) { return r.intersects(r1); }); 1135609SN/A } 1145609SN/A 1159409Sandreas.hansson@arm.com const_iterator 1169235Sandreas.hansson@arm.com insert(const AddrRange &r, const V& d) 1173804SN/A { 11812776Snikos.nikoleris@arm.com if (intersects(r) != end()) 1193804SN/A return tree.end(); 1203804SN/A 1218902SN/A return tree.insert(std::make_pair(r, d)).first; 1223804SN/A } 1233804SN/A 1245608SN/A void 1255608SN/A erase(iterator p) 1263804SN/A { 12712777Sgabeblack@google.com cache.remove(p); 1283804SN/A tree.erase(p); 1293804SN/A } 1303804SN/A 1315608SN/A void 1325608SN/A erase(iterator p, iterator q) 1333804SN/A { 13412777Sgabeblack@google.com for (auto it = p; it != q; it++) { 13512777Sgabeblack@google.com cache.remove(p); 13612777Sgabeblack@google.com } 1373804SN/A tree.erase(p,q); 1383804SN/A } 1393804SN/A 1405608SN/A void 1415608SN/A clear() 1423804SN/A { 14312777Sgabeblack@google.com cache.erase(cache.begin(), cache.end()); 1443804SN/A tree.erase(tree.begin(), tree.end()); 1453804SN/A } 1463804SN/A 1478918SN/A const_iterator 1488918SN/A begin() const 1498918SN/A { 1508918SN/A return tree.begin(); 1518918SN/A } 1528918SN/A 1535608SN/A iterator 1545608SN/A begin() 1553804SN/A { 1563804SN/A return tree.begin(); 1573804SN/A } 1583804SN/A 1598918SN/A const_iterator 1608918SN/A end() const 1618918SN/A { 1628918SN/A return tree.end(); 1638918SN/A } 1648918SN/A 1655608SN/A iterator 1665608SN/A end() 1673804SN/A { 1683804SN/A return tree.end(); 1693804SN/A } 1703804SN/A 1719235Sandreas.hansson@arm.com std::size_t 1728918SN/A size() const 1733804SN/A { 1743804SN/A return tree.size(); 1753804SN/A } 1763804SN/A 1775608SN/A bool 1788918SN/A empty() const 1793804SN/A { 1803804SN/A return tree.empty(); 1813804SN/A } 18212776Snikos.nikoleris@arm.com 18312776Snikos.nikoleris@arm.com private: 18412776Snikos.nikoleris@arm.com /** 18512777Sgabeblack@google.com * Add an address range map entry to the cache. 18612777Sgabeblack@google.com * 18712777Sgabeblack@google.com * @param it Iterator to the entry in the address range map 18812777Sgabeblack@google.com */ 18912777Sgabeblack@google.com void 19012777Sgabeblack@google.com addNewEntryToCache(const_iterator it) const 19112777Sgabeblack@google.com { 19212777Sgabeblack@google.com if (max_cache_size != 0) { 19312777Sgabeblack@google.com // If there's a cache, add this element to it. 19412777Sgabeblack@google.com if (cache.size() >= max_cache_size) { 19512777Sgabeblack@google.com // If the cache is full, move the last element to the 19612777Sgabeblack@google.com // front and overwrite it with the new value. This 19712777Sgabeblack@google.com // avoids creating or destroying elements of the list. 19812777Sgabeblack@google.com auto last = cache.end(); 19912777Sgabeblack@google.com last--; 20012777Sgabeblack@google.com *last = it; 20112777Sgabeblack@google.com if (max_cache_size > 1) 20212777Sgabeblack@google.com cache.splice(cache.begin(), cache, last); 20312777Sgabeblack@google.com } else { 20412777Sgabeblack@google.com cache.push_front(it); 20512777Sgabeblack@google.com } 20612777Sgabeblack@google.com } 20712777Sgabeblack@google.com } 20812777Sgabeblack@google.com 20912777Sgabeblack@google.com /** 21012776Snikos.nikoleris@arm.com * Find entry that satisfies a condition on an address range 21112776Snikos.nikoleris@arm.com * 21212776Snikos.nikoleris@arm.com * Searches through the ranges in the address map and returns an 21312776Snikos.nikoleris@arm.com * iterator to the entry that satisfies the input conidition on 21412776Snikos.nikoleris@arm.com * the input address range. Returns end() if none found. 21512776Snikos.nikoleris@arm.com * 21612776Snikos.nikoleris@arm.com * @param r An input address range 21712776Snikos.nikoleris@arm.com * @param f A condition on an address range 21812776Snikos.nikoleris@arm.com * @return An iterator that contains the input address range 21912776Snikos.nikoleris@arm.com */ 22012776Snikos.nikoleris@arm.com const_iterator 22112776Snikos.nikoleris@arm.com find(const AddrRange &r, std::function<bool(const AddrRange)> cond) const 22212776Snikos.nikoleris@arm.com { 22312777Sgabeblack@google.com // Check the cache first 22412777Sgabeblack@google.com for (auto c = cache.begin(); c != cache.end(); c++) { 22512777Sgabeblack@google.com auto it = *c; 22612777Sgabeblack@google.com if (cond(it->first)) { 22712777Sgabeblack@google.com // If this entry matches, promote it to the front 22812777Sgabeblack@google.com // of the cache and return it. 22912777Sgabeblack@google.com cache.splice(cache.begin(), cache, c); 23012777Sgabeblack@google.com return it; 23112777Sgabeblack@google.com } 23212777Sgabeblack@google.com } 23312777Sgabeblack@google.com 23412776Snikos.nikoleris@arm.com const_iterator next = tree.upper_bound(r); 23512776Snikos.nikoleris@arm.com if (next != end() && cond(next->first)) { 23612777Sgabeblack@google.com addNewEntryToCache(next); 23712776Snikos.nikoleris@arm.com return next; 23812776Snikos.nikoleris@arm.com } 23912776Snikos.nikoleris@arm.com if (next == begin()) 24012776Snikos.nikoleris@arm.com return end(); 24112776Snikos.nikoleris@arm.com next--; 24212776Snikos.nikoleris@arm.com 24312776Snikos.nikoleris@arm.com const_iterator i; 24412776Snikos.nikoleris@arm.com do { 24512776Snikos.nikoleris@arm.com i = next; 24612776Snikos.nikoleris@arm.com if (cond(i->first)) { 24712777Sgabeblack@google.com addNewEntryToCache(i); 24812776Snikos.nikoleris@arm.com return i; 24912776Snikos.nikoleris@arm.com } 25012776Snikos.nikoleris@arm.com // Keep looking if the next range merges with the current one. 25112776Snikos.nikoleris@arm.com } while (next != begin() && 25212776Snikos.nikoleris@arm.com (--next)->first.mergesWith(i->first)); 25312776Snikos.nikoleris@arm.com 25412776Snikos.nikoleris@arm.com return end(); 25512776Snikos.nikoleris@arm.com } 25612776Snikos.nikoleris@arm.com 25712776Snikos.nikoleris@arm.com RangeMap tree; 25812777Sgabeblack@google.com 25912777Sgabeblack@google.com /** 26012777Sgabeblack@google.com * A list of iterator that correspond to the max_cache_size most 26112777Sgabeblack@google.com * recently used entries in the address range map. This mainly 26212777Sgabeblack@google.com * used to optimize lookups. The elements in the list should 26312777Sgabeblack@google.com * always be valid iterators of the tree. 26412777Sgabeblack@google.com */ 26512777Sgabeblack@google.com mutable std::list<const_iterator> cache; 2663804SN/A}; 2673804SN/A 2689235Sandreas.hansson@arm.com#endif //__BASE_ADDR_RANGE_MAP_HH__ 269