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