addr_range_map.hh revision 9405:c0a0593510db 
1/*
2 * Copyright (c) 2012 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 <map>
48#include <utility>
49
50#include "base/addr_range.hh"
51
52/**
53 * The AddrRangeMap uses an STL map to implement an interval tree for
54 * address decoding. The value stored is a template type and can be
55 * e.g. a port identifier, or a pointer.
56 */
57template <typename V>
58class AddrRangeMap
59{
60  private:
61    typedef std::map<AddrRange, V> RangeMap;
62    RangeMap tree;
63
64  public:
65    typedef typename RangeMap::iterator iterator;
66    typedef typename RangeMap::const_iterator const_iterator;
67
68    const_iterator
69    find(const AddrRange &r) const
70    {
71        const_iterator i;
72
73        i = tree.upper_bound(r);
74
75        if (i == tree.begin()) {
76            if (i->first.intersects(r))
77                return i;
78            else
79                // Nothing could match, so return end()
80                return tree.end();
81        }
82
83        --i;
84
85        if (i->first.intersects(r))
86            return i;
87
88        return tree.end();
89    }
90
91    iterator
92    find(const AddrRange &r)
93    {
94        iterator i;
95
96        i = tree.upper_bound(r);
97
98        if (i == tree.begin()) {
99            if (i->first.intersects(r))
100                return i;
101            else
102                // Nothing could match, so return end()
103                return tree.end();
104        }
105
106        --i;
107
108        if (i->first.intersects(r))
109            return i;
110
111        return tree.end();
112    }
113
114    const_iterator
115    find(const Addr &r) const
116    {
117        return find(RangeSize(r, 1));
118    }
119
120    iterator
121    find(const Addr &r)
122    {
123        return find(RangeSize(r, 1));
124    }
125
126    bool
127    intersect(const AddrRange &r)
128    {
129        iterator i;
130        i = find(r);
131        if (i != tree.end())
132            return true;
133        return false;
134    }
135
136    iterator
137    insert(const AddrRange &r, const V& d)
138    {
139        if (intersect(r))
140            return tree.end();
141
142        return tree.insert(std::make_pair(r, d)).first;
143    }
144
145    std::size_t
146    erase(Addr k)
147    {
148        return tree.erase(k);
149    }
150
151    void
152    erase(iterator p)
153    {
154        tree.erase(p);
155    }
156
157    void
158    erase(iterator p, iterator q)
159    {
160        tree.erase(p,q);
161    }
162
163    void
164    clear()
165    {
166        tree.erase(tree.begin(), tree.end());
167    }
168
169    const_iterator
170    begin() const
171    {
172        return tree.begin();
173    }
174
175    iterator
176    begin()
177    {
178        return tree.begin();
179    }
180
181    const_iterator
182    end() const
183    {
184        return tree.end();
185    }
186
187    iterator
188    end()
189    {
190        return tree.end();
191    }
192
193    std::size_t
194    size() const
195    {
196        return tree.size();
197    }
198
199    bool
200    empty() const
201    {
202        return tree.empty();
203    }
204};
205
206#endif //__BASE_ADDR_RANGE_MAP_HH__
207