kernel/fiasco/src/lib/libk/mem_region.cpp

   1 INTERFACE:
   2
   3 class Mem_region
   4 {
   5 public:
   6   unsigned long start, end;
   7
   8   Mem_region() : start(0), end(0) {}
   9
  10   Mem_region(unsigned long start, unsigned long end) : start(start), end(end) {}
  11
  12   bool valid() const { return start < end; }
  13
  14   bool operator < (Mem_region const &o) const
  15   { return end < o.start; }
  16
  17   bool overlaps(Mem_region const &o) const
  18   { return !(o < *this || *this < o); }
  19
  20   bool contains(Mem_region const &o) const
  21   { return start <= o.start && end >= o.end; }
  22
  23   void merge(Mem_region const &r)
  24   {
  25     start = start < r.start ? start : r.start;
  26     end   = end > r.end     ? end   : r.end;
  27   }
  28
  29   unsigned long size() const
  30   { return end - start + 1; }
  31
  32 };
  33
  34
  35 class Mem_region_map_base
  36 {
  37 private:
  38   unsigned _s;
  39   unsigned _l;
  40   Mem_region _r[0];
  41
  42 public:
  43   Mem_region_map_base(unsigned size) : _s(size), _l(0) {}
  44 };
  45
  46 template< unsigned E >
  47 class Mem_region_map : public Mem_region_map_base
  48 {
  49 public:
  50   enum { Entries = E };
  51   Mem_region_map() : Mem_region_map_base(Entries) {}
  52
  53 private:
  54   Mem_region _r[Entries];
  55 };
  56
  57
  58 //--------------------------------------------------------------------------
  59 IMPLEMENTATION:
  60
  61 PRIVATE inline
  62 void
  63 Mem_region_map_base::del(unsigned start, unsigned end)
  64 {
  65   register unsigned delta = end - start;
  66   for (unsigned p = start; p < end; ++p)
  67     _r[p] = _r[p + delta];
  68
  69   _l -= delta;
  70 }
  71
  72 PUBLIC inline NEEDS[Mem_region_map_base::del]
  73 bool
  74 Mem_region_map_base::add(Mem_region const &r)
  75 {
  76   if (!r.valid())
  77     return true;
  78
  79   unsigned pos = 0;
  80   for (;pos < _l && _r[pos] < r; ++pos) ;
  81   if (_l > pos && !(r < _r[pos]))
  82     { // overlap -> merge
  83       _r[pos].merge(r);
  84       for (unsigned p = pos + 1; p < _l; ++p)
  85         {
  86           if (!(_r[pos] < _r[p]))
  87             _r[pos].merge(_r[p]);
  88           else
  89             {
  90               del(pos + 1, p);
  91               return true;
  92             }
  93         }
  94       _l = pos + 1;
  95       return true;
  96     }
  97
  98   if (_l >= _s)
  99     return false;
 100
 101   for (unsigned p = _l; p > pos; --p) _r[p] = _r[p-1];
 102   ++_l;
 103   _r[pos] = r;
 104   return true;
 105 }
 106
 107
 108 PUBLIC inline NEEDS[Mem_region_map_base::del]
 109 bool
 110 Mem_region_map_base::sub(Mem_region const &r)
 111 {
 112   if (!r.valid())
 113     return true;
 114
 115   unsigned pos;
 116   for (pos = 0; pos < _l; ++pos)
 117     {
 118       if (_r[pos].overlaps(r))
 119         {
 120           if (r.contains(_r[pos]))
 121             {
 122               del(pos, pos+1);
 123               --pos; // ensure we do not skip the next element
 124             }
 125           else if (r.start <= _r[pos].start)
 126             _r[pos].start = r.end + 1;
 127           else if (r.end >= _r[pos].end)
 128             _r[pos].end = r.start - 1;
 129           else
 130             {
 131               if (_l >= _s)
 132                 return false;
 133
 134               for (unsigned p = _l; p > pos; --p) _r[p] = _r[p-1];
 135               ++_l;
 136               _r[pos+1].start = r.end + 1;
 137               _r[pos+1].end = _r[pos].end;
 138               _r[pos].end = r.start - 1;
 139             }
 140         }
 141     }
 142   return true;
 143 }
 144
 145
 146 PUBLIC inline
 147 unsigned
 148 Mem_region_map_base::length() const
 149 { return _l; }
 150
 151
 152 PUBLIC inline
 153 unsigned
 154 Mem_region_map_base::capacity() const
 155 { return _s; }
 156
 157 PUBLIC inline
 158 Mem_region const &
 159 Mem_region_map_base::operator [] (unsigned idx) const
 160 { return _r[idx]; }
 161
 162 PUBLIC inline
 163 Mem_region &
 164 Mem_region_map_base::operator [] (unsigned idx)
 165 { return _r[idx]; }
 166