addr_range_map.hh revision 12783:a610dc4b5778 
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 */
61template <typename V, int max_cache_size=0>
62class 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__
273