addr_range_map.hh revision 5608 
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 "base/range.hh"
35
36#include <map>
37
38template <class T,class V>
39class range_map
40{
41  private:
42    typedef std::map<Range<T>,V> RangeMap;
43    RangeMap tree;
44
45  public:
46    typedef typename RangeMap::iterator iterator;
47
48    template <class U>
49    const iterator
50    find(const Range<U> &r)
51    {
52        iterator i;
53
54        i = tree.upper_bound(r);
55
56        if (i == tree.begin()) {
57            if (i->first.start <= r.end && i->first.end >= r.start)
58                return i;
59            else
60                // Nothing could match, so return end()
61                return tree.end();
62        }
63
64        i--;
65
66        if (i->first.start <= r.end && i->first.end >= r.start)
67            return i;
68
69        return tree.end();
70    }
71
72    template <class U>
73    bool
74    intersect(const Range<U> &r)
75    {
76        iterator i;
77        i = find(r);
78        if (i != tree.end())
79            return true;
80        return false;
81    }
82
83
84    template <class U,class W>
85    iterator
86    insert(const Range<U> &r, const W d)
87    {
88        if (intersect(r))
89            return tree.end();
90
91        return tree.insert(std::make_pair<Range<T>,V>(r, d)).first;
92    }
93
94    size_t
95    erase(T k)
96    {
97        return tree.erase(k);
98    }
99
100    void
101    erase(iterator p)
102    {
103        tree.erase(p);
104    }
105
106    void
107    erase(iterator p, iterator q)
108    {
109        tree.erase(p,q);
110    }
111
112    void
113    clear()
114    {
115        tree.erase(tree.begin(), tree.end());
116    }
117
118    iterator
119    begin()
120    {
121        return tree.begin();
122    }
123
124    iterator
125    end()
126    {
127        return tree.end();
128    }
129
130    size_t
131    size()
132    {
133        return tree.size();
134    }
135
136    bool
137    empty()
138    {
139        return tree.empty();
140    }
141};
142
143
144template <class T,class V>
145class range_multimap
146{
147  private:
148    typedef std::multimap<Range<T>,V> RangeMap;
149    RangeMap tree;
150
151  public:
152    typedef typename RangeMap::iterator iterator;
153
154    template <class U>
155    std::pair<iterator,iterator> find(const Range<U> &r)
156    {
157        iterator i;
158        iterator j;
159
160        i = tree.lower_bound(r);
161
162        if (i == tree.begin()) {
163          if (i->first.start <= r.end && i->first.end >= r.start)
164                return std::make_pair<iterator, iterator>(i,i);
165          else
166            // Nothing could match, so return end()
167            return std::make_pair<iterator, iterator>(tree.end(), tree.end());
168        }
169        i--;
170
171        if (i->first.start <= r.end && i->first.end >= r.start) {
172            // we have at least one match
173            j = i;
174
175            i--;
176            while (i->first.start <= r.end && i->first.end >=
177                    r.start) {
178                if (i == tree.begin())
179                    break;
180                i--;
181            }
182            if (i == tree.begin() && i->first.start <= r.end && i->first.end >=
183                                        r.start)
184                return std::make_pair<iterator, iterator>(i,j);
185            i++;
186            return std::make_pair<iterator, iterator>(i,j);
187
188        }
189
190        return std::make_pair<iterator, iterator>(tree.end(), tree.end());
191    }
192
193    template <class U>
194    bool
195    intersect(const Range<U> &r)
196    {
197        std::pair<iterator,iterator> p;
198        p = find(r);
199        if (p.first != tree.end())
200            return true;
201        return false;
202    }
203
204
205    template <class U,class W>
206    iterator
207    insert(const Range<U> &r, const W d)
208    {
209        std::pair<iterator,iterator> p;
210        p = find(r);
211        if (p.first->first.start == r.start && p.first->first.end == r.end ||
212                p.first == tree.end())
213            return tree.insert(std::make_pair<Range<T>,V>(r, d));
214        else
215            return tree.end();
216    }
217
218    size_t
219    erase(T k)
220    {
221        return tree.erase(k);
222    }
223
224    void
225    erase(iterator p)
226    {
227        tree.erase(p);
228    }
229
230    void
231    erase(iterator p, iterator q)
232    {
233        tree.erase(p,q);
234    }
235
236    void
237    clear()
238    {
239        tree.erase(tree.begin(), tree.end());
240    }
241
242    iterator
243    begin()
244    {
245        return tree.begin();
246    }
247
248    iterator
249    end()
250    {
251        return tree.end();
252    }
253
254    size_t
255    size()
256    {
257        return tree.size();
258    }
259
260    bool
261    empty()
262    {
263        return tree.empty();
264    }
265};
266
267#endif //__BASE_RANGE_MAP_HH__
268