addr_range_map.hh revision 8918 
1/*
2 * Copyright (c) 2006 The Regents of The University of Michigan
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * Authors: Ali Saidi
29 */
30
31#ifndef __BASE_RANGE_MAP_HH__
32#define __BASE_RANGE_MAP_HH__
33
34#include <map>
35#include <utility>
36
37#include "base/range.hh"
38
39/**
40 * The range_map uses an STL map to implement an interval tree. The
41 * type of both the key (range) and the value are template
42 * parameters. It can, for example, be used for address decoding,
43 * using a range of addresses to map to ports.
44 */
45template <class T,class V>
46class range_map
47{
48  private:
49    typedef std::map<Range<T>,V> RangeMap;
50    RangeMap tree;
51
52  public:
53    typedef typename RangeMap::iterator iterator;
54    typedef typename RangeMap::const_iterator const_iterator;
55
56    template <class U>
57    const_iterator
58    find(const Range<U> &r) const
59    {
60        const_iterator i;
61
62        i = tree.upper_bound(r);
63
64        if (i == tree.begin()) {
65            if (i->first.start <= r.end && i->first.end >= r.start)
66                return i;
67            else
68                // Nothing could match, so return end()
69                return tree.end();
70        }
71
72        --i;
73
74        if (i->first.start <= r.end && i->first.end >= r.start)
75            return i;
76
77        return tree.end();
78    }
79
80    template <class U>
81    iterator
82    find(const Range<U> &r)
83    {
84        iterator i;
85
86        i = tree.upper_bound(r);
87
88        if (i == tree.begin()) {
89            if (i->first.start <= r.end && i->first.end >= r.start)
90                return i;
91            else
92                // Nothing could match, so return end()
93                return tree.end();
94        }
95
96        --i;
97
98        if (i->first.start <= r.end && i->first.end >= r.start)
99            return i;
100
101        return tree.end();
102    }
103
104    template <class U>
105    const_iterator
106    find(const U &r) const
107    {
108        return find(RangeSize(r, 1));
109    }
110
111    template <class U>
112    iterator
113    find(const U &r)
114    {
115        return find(RangeSize(r, 1));
116    }
117
118    template <class U>
119    bool
120    intersect(const Range<U> &r)
121    {
122        iterator i;
123        i = find(r);
124        if (i != tree.end())
125            return true;
126        return false;
127    }
128
129    template <class U,class W>
130    iterator
131    insert(const Range<U> &r, const W d)
132    {
133        if (intersect(r))
134            return tree.end();
135
136        return tree.insert(std::make_pair(r, d)).first;
137    }
138
139    size_t
140    erase(T k)
141    {
142        return tree.erase(k);
143    }
144
145    void
146    erase(iterator p)
147    {
148        tree.erase(p);
149    }
150
151    void
152    erase(iterator p, iterator q)
153    {
154        tree.erase(p,q);
155    }
156
157    void
158    clear()
159    {
160        tree.erase(tree.begin(), tree.end());
161    }
162
163    const_iterator
164    begin() const
165    {
166        return tree.begin();
167    }
168
169    iterator
170    begin()
171    {
172        return tree.begin();
173    }
174
175    const_iterator
176    end() const
177    {
178        return tree.end();
179    }
180
181    iterator
182    end()
183    {
184        return tree.end();
185    }
186
187    size_t
188    size() const
189    {
190        return tree.size();
191    }
192
193    bool
194    empty() const
195    {
196        return tree.empty();
197    }
198};
199
200
201template <class T,class V>
202class range_multimap
203{
204  private:
205    typedef std::multimap<Range<T>,V> RangeMap;
206    RangeMap tree;
207
208  public:
209    typedef typename RangeMap::iterator iterator;
210
211    template <class U>
212    std::pair<iterator,iterator> find(const Range<U> &r)
213    {
214        iterator i;
215        iterator j;
216
217        i = tree.lower_bound(r);
218
219        if (i == tree.begin()) {
220          if (i->first.start <= r.end && i->first.end >= r.start)
221                return std::make_pair<iterator, iterator>(i,i);
222          else
223            // Nothing could match, so return end()
224            return std::make_pair<iterator, iterator>(tree.end(), tree.end());
225        }
226        i--;
227
228        if (i->first.start <= r.end && i->first.end >= r.start) {
229            // we have at least one match
230            j = i;
231
232            i--;
233            while (i->first.start <= r.end && i->first.end >=
234                    r.start) {
235                if (i == tree.begin())
236                    break;
237                i--;
238            }
239            if (i == tree.begin() && i->first.start <= r.end && i->first.end >=
240                                        r.start)
241                return std::make_pair<iterator, iterator>(i,j);
242            i++;
243            return std::make_pair<iterator, iterator>(i,j);
244
245        }
246
247        return std::make_pair<iterator, iterator>(tree.end(), tree.end());
248    }
249
250    template <class U>
251    bool
252    intersect(const Range<U> &r)
253    {
254        std::pair<iterator,iterator> p;
255        p = find(r);
256        if (p.first != tree.end())
257            return true;
258        return false;
259    }
260
261
262    template <class U,class W>
263    iterator
264    insert(const Range<U> &r, const W d)
265    {
266        std::pair<iterator,iterator> p;
267        p = find(r);
268        if ((p.first->first.start == r.start && p.first->first.end == r.end) ||
269                p.first == tree.end())
270            return tree.insert(std::make_pair<Range<T>,V>(r, d));
271        else
272            return tree.end();
273    }
274
275    size_t
276    erase(T k)
277    {
278        return tree.erase(k);
279    }
280
281    void
282    erase(iterator p)
283    {
284        tree.erase(p);
285    }
286
287    void
288    erase(iterator p, iterator q)
289    {
290        tree.erase(p,q);
291    }
292
293    void
294    clear()
295    {
296        tree.erase(tree.begin(), tree.end());
297    }
298
299    iterator
300    begin()
301    {
302        return tree.begin();
303    }
304
305    iterator
306    end()
307    {
308        return tree.end();
309    }
310
311    size_t
312    size()
313    {
314        return tree.size();
315    }
316
317    bool
318    empty()
319    {
320        return tree.empty();
321    }
322};
323
324#endif //__BASE_RANGE_MAP_HH__
325