楓 software::基本テクニック

//! @file MemoryManager.h
//! メモリマネージャ
//!  ベストフィットによる実装
#ifndef __MEMORY_MANAGER_H__
#define __MEMORY_MANAGER_H__

#ifndef NULL
#define NULL 0
#endif

//! メモリの確保がコールされた時、返すメモリのアドレスの前に管理領域を付けて返す
//!
//!  +------+------+------------------+
//!  | next | size | allocated memory |
//!  +------+------+------------------+
//!                ↑ここのアドレスを返す
//!
//!
//! メモリ解放がコールされた時、渡されたアドレスから管理領域のアドレスを求めて
//! 空きメモリリストに加える
//!
//!                ↓ここのアドレスが渡される
//!  +------+------+------------------+
//!  | next | size | allocated memory |
//!  +------+------+------------------+
//!  ↑ここのアドレスを求める

//! メモリマネージャ
class CMemoryManager
{
  struct MemoryBlock {
    struct MemoryBlock* next_;
    size_t size_;
  };
  static const size_t BLOCK_SIZE = sizeof(MemoryBlock);

  MemoryBlock* free_list_;

public:
  CMemoryManager() : free_list_(NULL) {}
  void Initialize( void* memarea, size_t size );
  void* Alloc( size_t size );
  void Free( void* mem );
};

#endif // __MEMORY_MANAGER_H__

//! @file MemoryManager.cpp

#include "MemoryManager.h"

//! アドレス型 環境に応じて変える
typedef unsigned long addr_t;

//! 初期化する
//!  @param memarea : 管理するメモリ領域の先頭
//!  @param size : メモリ領域のサイズ
void CMemoryManager::Initialize( void* memarea, size_t size )
{
  free_list_ = (MemoryBlock*)memarea;
  free_list_->size_ = size - BLOCK_SIZE;
  free_list_->next_ = NULL;
}
//! メモリを確保する
//! @param size : 要求サイズ
//! @return 確保したメモリ、確保できなかったときはNULL
void* CMemoryManager::Alloc( size_t size )
{
  // 4バイトアライメント, 環境に応じてアライメントサイズは変更
  size = ((size + 3) / 4) * 4;

  MemoryBlock* bestfit = NULL;
  MemoryBlock* prev = NULL;
  MemoryBlock* cur = free_list_;
  while( cur ) {
    if( cur->size_ == size ) {
      if( prev ) {
        prev->next_ = cur->next_;
      } else {
        free_list_ = cur->next_;
      }
      // 完全に同じサイズのメモリが見つかったのでそれを返す
      return (void*)( (addr_t)cur + BLOCK_SIZE );
    } else if( cur->size_ > size ) {
      if( bestfit ) {
        if( (bestfit->size_ - size) > (cur->size_ - size) ) {
          bestfit = cur;
        }
      } else {
        bestfit = cur;
      }
    }
    prev = cur;
    cur = cur->next_;
  }

  // 最も近いサイズのメモリを分割して返す
  if( bestfit ) {
    // 分割する
    MemoryBlock* slice = (MemoryBlock*)( (addr_t)bestfit + BLOCK_SIZE + size );
    slice->size_ = bestfit->size_ - ( size + BLOCK_SIZE );
    // 空きリストの先頭につなぐ
    if( bestfit == free_list_ ) {
      slice->next_ = free_list_->next_;
      free_list_ = slice;
    } else {
      slice->next_ = free_list_;
      free_list_ = slice;
    }
    // 分割後サイズを設定し返す
    bestfit->size_ = size;
    return (void*)( (addr_t)bestfit + BLOCK_SIZE );
  }

  // 指定されたサイズ以上の空きブロックがなかった
  return NULL;
}
//! メモリを解放する
//!
//! まず、解放対象のメモリと隣接する領域がないか検索し、見つかったらそこにつなげる
//! 見つからない場合は、フリーメモリリストにつなげる
//! @param m : 解放するメモリ
void CMemoryManager::Free( void* m )
{
  MemoryBlock* del_mem = (MemoryBlock*)( (addr_t)m - BLOCK_SIZE );
  int connected = 0;

  // つなげられるメモリがなくなるまで繰り返す
  do {
    connected &= 0x01;
    MemoryBlock* cur = free_list_;
    MemoryBlock* prev = NULL;

    // 隣接するメモリがないか検索する
    while( cur ) {
      if( cur != del_mem ) {
        if( ((addr_t)del_mem + BLOCK_SIZE + del_mem->size_) == (addr_t)cur ) {
          // curメモリが自分の後と隣接しているのでくっつける
          del_mem->next_ = cur->next_;
          del_mem->size_ += BLOCK_SIZE + cur->size_;
          connected = 0x03;
          if( !prev ) {
            // 1番初めのメモリブロックとつなげた
            free_list_ = del_mem;
          } else if( prev != del_mem ) {
            prev->next_ = del_mem;
          }
          break;
        } else if( ((addr_t)cur + BLOCK_SIZE + cur->size_) == (addr_t)del_mem ) {
          // curメモリが自分の前と隣接しているのでくっつける
          cur->size_ += BLOCK_SIZE + del_mem->size_;
          del_mem = cur;
          connected = 0x03;
          break;
        }
      }
      prev = cur;
      cur = cur->next_;
    }
  } while( connected & 0x02 );

  if( connected == 0 ) {
    // 隣接するメモリがないときはフリーリストに追加する
    del_mem->next_ = free_list_;
    free_list_ = del_mem;
  }
}

//! @file ArraiedAllocator.h

#ifndef __ARRAYIED_ALLOCATOR_H__
#define __ARRAYIED_ALLOCATOR_H__

template< int TTypeSize, int TNumArray>
class ArraiedAllocator
{
  static const int MAX_SIZE = TNumArray;
  struct Item {
    union {
      char         value_[TTypeSize];
      struct Item* next_;
    };
  };
  static Item  items_[MAX_SIZE];
  static Item* first_;
  static ArraiedAllocator allocator_;
  ArraiedAllocator();

public:
  static void* Alloc() {
    Item* ret = first_;
    first_ = ret->next_;
    return reinterpret_cast<void*>(ret);
  }
  static void Free(void* item) {
    Item* rev = reinterpret_cast<Item*>(item);
    rev->next_ = first_;
    first_ = rev;
  }
  static ArraiedAllocator& GetAllocator() { return allocator_; }
  static int Max() { return MAX_SIZE; }
};

template< int TTypeSize, int TNumArray>
typename ArraiedAllocator<TTypeSize,TNumArray>::Item ArraiedAllocator<TTypeSize,TNumArray>::items_[ArraiedAllocator<TTypeSize,TNumArray>::MAX_SIZE];

template< int TTypeSize, int TNumArray>
typename ArraiedAllocator<TTypeSize, TNumArray>::Item* ArraiedAllocator<TTypeSize,TNumArray>::first_;

template< int TTypeSize, int TNumArray>
ArraiedAllocator<TTypeSize,TNumArray> ArraiedAllocator<TTypeSize,TNumArray>::allocator_;

template< int TTypeSize, int TNumArray>
ArraiedAllocator<TTypeSize,TNumArray>::ArraiedAllocator()
{
  first_ = &items_[0];
  for( int i = 0; i < TNumArray; ++i ) {
    items_[i].next_ = &items_[i+1];
  }
  items_[TNumArray-1].next_ = NULL;
}

#endif // __ARRAYIED_ALLOCATOR_H__