src/base/addr_range_map.hh

   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  */
  61 template <typename V, int max_cache_size=0>
  62 class 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__