Универсальный менеджер памяти.

Автор: Валерий Мелешкин

Вступление
В процессе игры создание и уничтожение объектов происходит довольно часто.
И если для каждого объекта выделять память в хипе(куче), а затем её возвращать
системе, то во-первых эти операции будут отъедать немалую часть процессорного
времени, во-вторых образуется сильная фрагментация памяти, и выделение памяти
для каждого следующего объекта будет ещё дороже.

Выход очевиден - менеджер памяти.

Методы
Для начала перечислю известные мне методы управления памятью:
1) Самый простой и доступный - списки свободной памяти.
2) Пулы.
3) Алгоритм Пекаря и прочая экзотика со сборкой мусора и перемещением объектов
в памяти.

Позвольте сразу уволить вариант №3. Так как это непозволительная роскошь тратить
процессорное время на перемещение объектов в памяти, или, тем паче, жертвовать
половиной выделенной памяти (алгоритм пекаря требует такой жертвы).

Списки памяти оч.эффективны, но всё же если объекты необходимого размера ещё не
удалялись, то нам таки придётся потратить драгоценное время процессора. А если
их сто? тысяча?

Решение здесь публикуемое основывается на коктеле из списка и пула.

Интерфейс
Начну с конца. Что должен делать менеджер памяти в целом? Выделять память и
соответсвенно освобождать её. Ещё не плохо бы добавтиь метод, вызывающий полную
зачистку. итак:

class cMemoryMgr
{
public:
  cMemoryMgr(void) {}
  ~cMemoryMgr(void);

  void*  allocate(size_t); // вызов этого метода помещается в new
  void deallocate(void*, size_t); // а этого в delete

  void cleanup(void); // Тетя Ася :) или Мистер Проппер ;)
};

Ещё было бы странно если менеджер памяти, вдруг, стало возможным копировать.
Так защитмся же от такого срама:

memmgr = mmgrOLD;

А защищаться мы будем так:

class cMemoryMgr
{
private:
  // copy must die :)
  // эти два метода мы оставим без реализации
  // ибо нехай копировать менеджер памяти
  cMemoryMgr(const cMemoryMgr&); 
  cMemoryMgr& operator = (const cMemoryMgr&); 
public:
  cMemoryMgr(void) {}
  ~cMemoryMgr(void);

  void*  allocate(size_t); // вызов этого метода помещается в new
  void deallocate(void*, size_t); // а этого в delete

  void cleanup(void); // С Мистер Проппер веселей, память чище в два раза быстрей! ;)
};

Реализация
Итак. Теперь пришло время обсудить как это будет работать.
Так как я обещал гибрид, вот вам:
1) Мап свободной памяти (size_t -> очередь<freeCell>).
2) Список пулов
-----------------------------------------------------
процесс удаления
1) берём список свободных ячеек с нужным размером,
и, кто бы мог подумать :), добавляем в него ячейку.
-----------------------------------------------------
процесс выделения
1) ищем в карте нужный размер.
  1) берём 1-ую попавшуюся ячейку. радуемся.
2) нам не повезло - ещё никто ничё не удалил.
  1) смотрим есть ли в текущем пуле место для нас?
    1) если есть отхапыаем память. радуемся.
  2) мест нет. забиваем на тот пул. делаем себе новый.
    1) здесь места под солнцем хватает. радуемся.

Думаю надо наконец приняться за написание:

class cMemoryMgr
{
  // класс пула, блока памяти в терминах нашего менеджера
  class MemBlock
  {
  public:
    enum { defsize = 128*1024*1024 }; // размер по-умолчанию
  private:
    uchar* m_block; // соб-сно память :), вернее указатель на неё
    size_t m_remain; // сколько её ещё осталось
    size_t m_size; // сколько её всего
    size_t m_curr; // сколько мы прихватизировали
  private:
    // нехай копировать!
    MemBlock(const MemBlock& cp);
    MemBlock& operator = (const MemBlock& cp);
  public:
    // новый блок с дефолтовым размером
    MemBlock(void);
    // блок с заданным размером, только если
    // заданный больше дефолтового
    MemBlock(size_t);
    ~MemBlock(void);

    //0 == not enough memory
    void* allocate(size_t); // выделить память в этом пуле

    const size_t size(void) const;
    const size_t remaining(void) const;
  };
  // свободная ячейка
  struct MemEntry
  {
    size_t size; // сикоку
    void* ptr; // гиде
    //easy constructor
    MemEntry(void* sp, size_t sz): size(sz), ptr(sp) {}
  };
private:
  // список блоков
  std::vector<cMemoryMgr::MemBlock*> m_blocks;
  // Мап свободной памяти (size_t -> очередь<freeCell>).
  std::map<size_t, std::queue<cMemoryMgr::MemEntry> > m_freeEntrys;
private:
  void addBlock(size_t);
  //copy must die :)
  cMemoryMgr(const cMemoryMgr&);
  cMemoryMgr& operator = (const cMemoryMgr&);
public:
  cMemoryMgr(void) {}
  ~cMemoryMgr(void);

  void*  allocate(size_t);
  void deallocate(void*, size_t);

  void cleanup(void);
};

Вот и получился у нас .h
Мы уже обсуждали как оно работает, так что теперь цпп: