kuma Namespace Reference

Namespaces
namespace	details

Data Structures
class	Context
class	Context< Algorithm::Greedy >
class	Context< Algorithm::LinearScanFirstFit >

Typedefs
using	ItemID = uint32_t
using	ItemSize = uint32_t
using	MemoryOffset = uint32_t
using	MemorySize = uint32_t

Enumerations
enum	Algorithm { Greedy , LinearScanFirstFit }

Functions
void	solve (Context< Greedy > *)
void	solve (Context< Algorithm::LinearScanFirstFit > *)
void	solve (Context< Algorithm::Greedy > *ctx)

Typedef Documentation

ItemID

using kuma::ItemID = typedef uint32_t

Definition at line 39 of file kuma.h.

ItemSize

using kuma::ItemSize = typedef uint32_t

Definition at line 40 of file kuma.h.

MemoryOffset

using kuma::MemoryOffset = typedef uint32_t

Definition at line 42 of file kuma.h.

MemorySize

using kuma::MemorySize = typedef uint32_t

Definition at line 43 of file kuma.h.

Enumeration Type Documentation

Algorithm

enum kuma::Algorithm

Enumerator
Greedy
LinearScanFirstFit

Definition at line 27 of file kuma.h.

{
  // No reuse
  Greedy,
  LinearScanFirstFit,
};

Function Documentation

solve() [1/3]

void kuma::solve

(

Context< Algorithm::Greedy > *

ctx

)

Definition at line 25 of file kuma.cpp.

{
  uint32_t next = 0;
 
  for (uint32_t n = 0; n < ctx->item_count(); ++n)
  {
    ctx->mem_offset(n, next);
    next += ctx->item_size(n);
  }
 
  ctx->mem_total(next);
};

solve() [2/3]

void kuma::solve

(

Context< Algorithm::LinearScanFirstFit > *

ctx

)

Definition at line 48 of file kuma.cpp.

{
  using namespace kuma::details;
 
  uint32_t upper_bound = 0;
  std::map<ItemID, std::pair<uint32_t /* BEGIN */, uint32_t /* END */>> committed_items;
 
  // Allocate items in linear order (from item 0, item 1, ...)
  //
  // The implementor of Context is responsible for item ordering.
  for (uint32_t n = 0; n < ctx->item_count(); ++n)
  {
    IntervalSet intervals;
 
    for (auto item_in_conflict : ctx->conflict_with(n))
    {
      auto it = committed_items.find(item_in_conflict);
 
      // Skip if item_in_conflict is not committed yet
      if (it == committed_items.end())
      {
        continue;
      }
 
      auto const alloc_s = it->second.first;
      auto const alloc_e = it->second.second;
      intervals.insert(mask(alloc_s, alloc_e));
    }
 
    uint32_t const item_size = ctx->item_size(n);
    uint32_t const item_alloc_s = intervals.firstfit(item_size);
    uint32_t const item_alloc_e = item_alloc_s + item_size;
 
    // Notify "mem_offset"
    ctx->mem_offset(n, item_alloc_s);
 
    // Update "upper bound" and commit allocation
    upper_bound = std::max(upper_bound, item_alloc_e);
    committed_items[n] = std::make_pair(item_alloc_s, item_alloc_e);
  }
 
  // Notify "mem_total"
  ctx->mem_total(upper_bound);
}

References kuma::details::IntervalSet::firstfit(), and kuma::details::IntervalSet::insert().

solve() [3/3]

void kuma::solve

(

Context< Greedy > *

)