src/base/range_map.hh

   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  */
  45 template <class T,class V>
  46 class 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 #endif //__BASE_RANGE_MAP_HH__