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()) {
| 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.start <= r.end && i->first.end >= r.start)
| 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
| 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.start <= r.end && i->first.end >= r.start)
| 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()) {
| 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.start <= r.end && i->first.end >= r.start)
| 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
| 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.start <= r.end && i->first.end >= r.start)
| 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__
| 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__
|