#include <IntervalSet.h>

Public Member Functions
	IntervalSet (uint32_t len=0xffffffff)

void	insert (const IntervalMask &)

uint32_t	firstfit (uint32_t len) const

Detailed Description

Definition at line 44 of file IntervalSet.h.

Constructor & Destructor Documentation

◆ IntervalSet()

kuma::details::IntervalSet::IntervalSet ( uint32_t len = 0xffffffff )

Definition at line 27 of file IntervalSet.cpp.

{
  // Update _content
  _content[len] = len;
}

Member Function Documentation

◆ firstfit()

uint32_t kuma::details::IntervalSet::firstfit ( uint32_t len ) const

"firstfit(l)" returns the offset of an interval whose length is larger than "l".

When multiple intervals meet this condition, "firstfit(l)" chooses the interval with the smallest offset as its name suggests.

NOTE This method throws std::runtime_error if fails to find a proper region

Definition at line 77 of file IntervalSet.cpp.

{
  for (auto it = _content.begin(); it != _content.end(); ++it)
  {
    if (it->second >= len)
    {
      // Got it! This interval is larger than "len".
      return it->first - it->second;
    }
  }
 
  throw std::runtime_error{"infeasible"};
}

Referenced by kuma::solve().

◆ insert()

void kuma::details::IntervalSet::insert ( const IntervalMask & m )

Definition at line 33 of file IntervalSet.cpp.

{
  auto s = m.s;
  auto e = m.e;
 
  assert(s <= e);
 
  if (s == e)
  {
    // Empty region, nothing to do
    return;
  }
 
  // lower_bound() returns an iterator to the first element not less than the given key
  auto lb = _content.lower_bound(s);
 
  // NOTE 1. "lower_bound" ensures "prev_s < s <= curr_e"
  // NOTE 2. "e" points to somewhere after "s"
  auto curr_s = lb->first - lb->second;
  auto curr_e = lb->first;
 
  if (curr_s < s)
  {
    // Split the current interval
    _content[s] = s - curr_s;
    // NOTE The invariant over "_content" is temporarily broken here.
  }
 
  if (e < curr_e)
  {
    // Adjust the current interval
    _content[curr_e] = curr_e - e;
  }
  else
  {
    // Remove the current interval
    _content.erase(curr_e);
    // Check the next interval (e > curr_e)
    //
    // TODO Remove this recursive call (to prevent stack overflow issue)
    insert(mask(curr_e, e));
  }
}

References insert(), m, and kuma::details::mask().

Referenced by insert(), and kuma::solve().

The documentation for this class was generated from the following files: