addr_range_map.hh revision 13807 
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    iterator
87    contains(const AddrRange &r)
88    {
89        return find(r, [r](const AddrRange r1) { return r.isSubset(r1); });
90    }
91
92    /**
93     * Find entry that contains the given address
94     *
95     * Searches through the ranges in the address map and returns an
96     * iterator to the entry which range is a superset of the input
97     * address. Returns end() if none found.
98     *
99     * @param r An input address
100     * @return An iterator that contains the input address
101     */
102    const_iterator
103    contains(Addr r) const
104    {
105        return contains(RangeSize(r, 1));
106    }
107    iterator
108    contains(Addr r)
109    {
110        return contains(RangeSize(r, 1));
111    }
112
113    /**
114     * Find entry that intersects with the given address range
115     *
116     * Searches through the ranges in the address map and returns an
117     * iterator to the first entry which range intersects with the
118     * input address.
119     *
120     * @param r An input address
121     * @return An iterator that intersects with the input address range
122     */
123    const_iterator
124    intersects(const AddrRange &r) const
125    {
126        return find(r, [r](const AddrRange r1) { return r.intersects(r1); });
127    }
128    iterator
129    intersects(const AddrRange &r)
130    {
131        return find(r, [r](const AddrRange r1) { return r.intersects(r1); });
132    }
133
134    iterator
135    insert(const AddrRange &r, const V& d)
136    {
137        if (intersects(r) != end())
138            return tree.end();
139
140        return tree.insert(std::make_pair(r, d)).first;
141    }
142
143    void
144    erase(iterator p)
145    {
146        cache.remove(p);
147        tree.erase(p);
148    }
149
150    void
151    erase(iterator p, iterator q)
152    {
153        for (auto it = p; it != q; it++) {
154            cache.remove(p);
155        }
156        tree.erase(p,q);
157    }
158
159    void
160    clear()
161    {
162        cache.erase(cache.begin(), cache.end());
163        tree.erase(tree.begin(), tree.end());
164    }
165
166    const_iterator
167    begin() const
168    {
169        return tree.begin();
170    }
171
172    iterator
173    begin()
174    {
175        return tree.begin();
176    }
177
178    const_iterator
179    end() const
180    {
181        return tree.end();
182    }
183
184    iterator
185    end()
186    {
187        return tree.end();
188    }
189
190    std::size_t
191    size() const
192    {
193        return tree.size();
194    }
195
196    bool
197    empty() const
198    {
199        return tree.empty();
200    }
201
202  private:
203    /**
204     * Add an address range map entry to the cache.
205     *
206     * @param it Iterator to the entry in the address range map
207     */
208    void
209    addNewEntryToCache(iterator it) const
210    {
211        if (max_cache_size != 0) {
212            // If there's a cache, add this element to it.
213            if (cache.size() >= max_cache_size) {
214                // If the cache is full, move the last element to the
215                // front and overwrite it with the new value. This
216                // avoids creating or destroying elements of the list.
217                auto last = cache.end();
218                last--;
219                *last = it;
220                if (max_cache_size > 1)
221                    cache.splice(cache.begin(), cache, last);
222            } else {
223                cache.push_front(it);
224            }
225        }
226    }
227
228    /**
229     * Find entry that satisfies a condition on an address range
230     *
231     * Searches through the ranges in the address map and returns an
232     * iterator to the entry that satisfies the input conidition on
233     * the input address range. Returns end() if none found.
234     *
235     * @param r An input address range
236     * @param f A condition on an address range
237     * @return An iterator that contains the input address range
238     */
239    iterator
240    find(const AddrRange &r, std::function<bool(const AddrRange)> cond)
241    {
242        // Check the cache first
243        for (auto c = cache.begin(); c != cache.end(); c++) {
244            auto it = *c;
245            if (cond(it->first)) {
246                // If this entry matches, promote it to the front
247                // of the cache and return it.
248                cache.splice(cache.begin(), cache, c);
249                return it;
250            }
251        }
252
253        iterator next = tree.upper_bound(r);
254        if (next != end() && cond(next->first)) {
255            addNewEntryToCache(next);
256            return next;
257        }
258        if (next == begin())
259            return end();
260        next--;
261
262        iterator i;
263        do {
264            i = next;
265            if (cond(i->first)) {
266                addNewEntryToCache(i);
267                return i;
268            }
269            // Keep looking if the next range merges with the current one.
270        } while (next != begin() &&
271                 (--next)->first.mergesWith(i->first));
272
273        return end();
274    }
275
276    const_iterator
277    find(const AddrRange &r, std::function<bool(const AddrRange)> cond) const
278    {
279        return const_cast<AddrRangeMap *>(this)->find(r, cond);
280    }
281
282    RangeMap tree;
283
284    /**
285     * A list of iterator that correspond to the max_cache_size most
286     * recently used entries in the address range map. This mainly
287     * used to optimize lookups. The elements in the list should
288     * always be valid iterators of the tree.
289     */
290    mutable std::list<iterator> cache;
291};
292
293#endif //__BASE_ADDR_RANGE_MAP_HH__
294