Нужна помощь в написании программы, Системное программирование Опции

[Yarik-Jedi]

Аллокатор памяти общего назначения

Задание на работу
~~~~~~~~~~~~~~~~~

1. Выделить блок памяти любым доступным способом. По необходимости
можно выделить ещё один блок памяти (намного меньшего размера).

2. Разработать набор функций, которые будут выполнять перечисленные
ниже действия в пределах адресов выделенного блока памяти.

3. При разработке функций использовать только арифметические операции
и операции работы с указателями. Любую память можно выделять только
внутри выделенного блока памяти.

Описание функций
~~~~~~~~~~~~~~~~

Значение аргументов:

addr -- это адрес первого байта выделенной памяти;

size -- это размер выделенной памяти в байтах.

Перечень функций и их свойств, разрешается использовать только
приведенные аргументы:

void *mem_alloc(size_t size);
выделить память заданного размера size, если памяти нет,
то вернуть NULL.

void *mem_realloc(void *addr, size_t size);
изменить размер памяти по адресу addr до size, вернуть новый
адрес памяти, если размер изменить нельзя, то оставить память
по адресу addr без изменения и вернуть NULL.

void mem_free(void *addr);
вернуть память, выделенную по адресу addr.

Адреса памяти, возвращаемые функциями mem_alloc() и mem_realloc()
должны быть выровнены на 4 байта.


Примечания
~~~~~~~~~~

В задании приведены прототипы функций на языке C, в которых (void *) это
указатель, size_t это целочисленный беззнаковый тип, void обозначает
отсутствие возвращаемого значения, NULL некоторый адрес, который
не может иметь ни один блок памяти. Работу можно выполнить на любом
языке.

В первом пункте задания говорится "выделить блок памяти любым доступным
способом", это означает, что память можно выделить любой функцией
типа malloc(), sbrk(), mmap() или задать массивом необходимого размера.

Если память выделена функциями mem_alloc() или mem_realloc(), то
то её нельзя переносить куда либо до вызова mem_free() или mem_realloc(),
если mem_realloc() вернула другой адрес.

===================================================================

Вот собствеенно такая муть. Если есть желающие помочь (и, возможно, повысить свою квалификацию :rolleyes: ) - пишите. В принципе ничего сложного тут нет. Язык С/C++ (но лучше Java или Pascal(Delphi).

P.S. Естественно не за 'спасибо'.

[Olostan]

Когда-то очень давно я делал для какого-то америкоса по заказу на РентАКодере нечто подобное, но только на чистом С (задача была - не использовать никаких ф-ций кроме выделения памяти).

Если интересует - могу _попытаться_ найти. Пиши в аську.

[Andrej]

Есть готовый самописный (в прошлом семестре на дисциплине Операционные системы писал) менеджер памяти (язык C). Все три функции в нём реализованы, отлажены и оттестированы. работают как часы
Могу выложить код прямо здесь. Или как будет удобнее по-другому?

[Yarik-Jedi]

Есть готовый самописный (в прошлом семестре на дисциплине Операционные системы писал) менеджер памяти (язык C). Все три функции в нём реализованы, отлажены и оттестированы. работают как часы
Могу выложить код прямо здесь. Или как будет удобнее по-другому?

Куда ты пропал?

[Andrej]

Куда ты пропал?

Чуть не забыл)) Я просто сообщение глянул, но так как времени отправлять не было, отложил это дело на следующий вечер. И забыл... :-[ Высылаю.

[Andrej]

На всякий случай продублирую здесь.

  
// *****************************************************************************
//! \file   My_alloc.c
//! \brief  Realizaciya menedjera pamyati
//! \author Lysenko A.A. SPb ETU gr. 3352
//! \date   08.Dec.2005 - 08.Dec.2005
// *****************************************************************************

#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>

// =============================================================================
// struktura upravleniya blokom pamyati
struct BlockInfo
{
   unsigned char bOccupied; // flag zanyatosti / svobodnosti
                            //          1            0
   size_t        nSize;     // razmer bloka
};

static void* FirstBlock;       // ukazatel' na pervy'y blok pamyati
static void* FirstFree;        // ukazatel' na pervy'y svobodny'y blok pamyati
static char  InitFlag = 0;     // flag inicializacii menedjera

const size_t MAX_MEMORY_SIZE = 0x100000; // 1 MB

// =============================================================================
// INICIALIZAROVAT'' MENEDJER PAMYATI
void MallocInit()
{
   InitFlag = 1;
   FirstFree = FirstBlock = malloc(MAX_MEMORY_SIZE);
   struct BlockInfo* pt = (struct BlockInfo*)FirstFree;
   pt->bOccupied = 0;
   pt->nSize = MAX_MEMORY_SIZE - sizeof(struct BlockInfo);
}

// =============================================================================
// OSVOBODIT'' VY'DELENNY'Y BLOK PAMYATI
void mfree(void* block)
{
   if ( (!block) || (!InitFlag) ) { return;}
   struct BlockInfo* ptCur = block - sizeof(struct BlockInfo);
   ptCur->bOccupied = 0;
   // ESLI SLEDUYUSCH'IY BLOK SVOBODEN - OB``EDENIT'' V ODIN
   struct BlockInfo* ptNext = block + ptCur->nSize;
   // ESLI PAMYATI BOLSHE NET
   if ( ptNext != (FirstBlock + MAX_MEMORY_SIZE) )
   {
      if (!ptNext->bOccupied)
      {
         ptCur->nSize += (ptNext->nSize + sizeof(struct BlockInfo));
      }
   }
   // PEREMESTIT'' UKAZATEL'' NA PERVY'Y SVOBODNY'Y BLOK, ESLI NUJNO
   if (!FirstFree)
   {
      FirstFree = ptCur;
   }
   else if ((void*)ptCur < FirstFree)
   {
      FirstFree = ptCur;
   }
}

// =============================================================================
// VY'DELIT'' BLOK PAMYATI
void* mmalloc(size_t size)
{
   // INICIALIZIROVAT'' MENEDJER
   if (!InitFlag){ MallocInit(); }
   // PROVERIT'', EST'' LI SVOBODNAYA PAMYAT''
   if (!FirstFree)
   {
      return NULL;
   }
   else
   {
      struct BlockInfo* ptBlock = (struct BlockInfo*)FirstFree;
      char allocated = 0;
      while (!allocated)
      {
         if (!ptBlock->bOccupied)
         {
            if (ptBlock->nSize >= size)
            {
               ptBlock->bOccupied = 1;
               size_t tail = ptBlock->nSize - size;
               ptBlock->nSize = size;
               // ESLI OSTAVSHEYSYA PAMYATI NE HVATAET DLYA BlockInfo - "OTDAE'M EE' POL''ZOVATELYU"
               if (tail < sizeof(struct BlockInfo))
               {
                  ptBlock->nSize += tail;
               }
               else
               {
                  struct BlockInfo* ptFree = (void*)ptBlock + ptBlock->nSize
                                             + sizeof(struct BlockInfo);
                  ptFree->bOccupied = 0;
                  ptFree->nSize = tail - sizeof(struct BlockInfo);
               }
               // SFORMIROVAT'' UKAZATEL'', KOTORY'Y VOZVRASCH'EM POL''ZOVATELYU
               ptBlock = (void*)ptBlock + sizeof(struct BlockInfo);
               allocated = 1;
            }
         }
         if (allocated)
         {
            // PEREMESTIT'' UKAZATEL'' NA PERVY'Y SVOBODNY'Y BLOK, ESLI NUJNO
            if ( ((void*)ptBlock - sizeof(struct BlockInfo)) == FirstFree )
            {
               struct BlockInfo* ptFree = (struct BlockInfo*)FirstFree;
               while (ptFree)
               {
                  if (!ptFree->bOccupied)
                  {
                     FirstFree = (void*)ptFree;
                     ptFree = NULL;
                     continue;
                  }
                  // ESLI ESCH'E' NE VSYA PAMYAT'' PROSMOTRENA, PEREYTI K SLEDUYUSCH'EMU BLOKU
                  if ( ((void*)ptFree + ptFree->nSize + sizeof(struct BlockInfo))
                     != (FirstBlock + MAX_MEMORY_SIZE) )
                  {
                     ptFree = (void*)ptFree + ptFree->nSize + sizeof(struct BlockInfo);
                  }
                  else
                  {
                     // INACHE FirstFree BUDET NULL
                     FirstFree = ptFree = NULL;
                  }
               }
            }
         }
         else
         {
            // ESLI ESCH'E' NE VSYA PAMYAT'' PROSMOTRENA, PEREYTI K SLEDUYUSCH'EMU BLOKU
            if ( ((void*)ptBlock + ptBlock->nSize + sizeof(struct BlockInfo))
                  != (FirstBlock + MAX_MEMORY_SIZE) )
            {
               ptBlock = (void*)ptBlock + ptBlock->nSize + sizeof(struct BlockInfo);
            }
            else
            {
               // INACHE VERNUT'' NULL
               ptBlock = NULL;
               allocated = 1;
            }
         }
      }
      return (void*)ptBlock;
   }
}

// =============================================================================
// PEREVY'DELIT'' BLOK PAMYATI
void* mrealloc(void* block, size_t size)
{
   // ESLI block == NULL, deystvuem, kak mmalloc()
   if ( (block == NULL) || (!InitFlag) )
   {
      return mmalloc(size);
   }

   struct BlockInfo* ptBlock = (block - sizeof(struct BlockInfo));
   // ESLI NUJNO UMEN''SHIT'' RAZMER PAMYATI
   if (ptBlock->nSize > size)
   {
      size_t tail = ptBlock->nSize - size;
      ptBlock->nSize = size;
      // ESLI OSTAVSHEYSYA PAMYATI NE HVATAET DLYA BlockInfo - "OTDAE'M EE' POL''ZOVATELYU"
      if (tail < sizeof(struct BlockInfo))
      {
         ptBlock->nSize += tail;
      }
      else
      {
         struct BlockInfo* ptFree = (void*)ptBlock + ptBlock->nSize
                                    + sizeof(struct BlockInfo);
         ptFree->bOccupied = 1;
         ptFree->nSize = tail - sizeof(struct BlockInfo);
         ptFree = (void*)ptFree + sizeof(struct BlockInfo);
         mfree(ptFree);
      }
      return block;
   }
   else if (ptBlock->nSize == size)
   {
      // KOMU-TO NECHEGO DELAT''
      return block;
   }
   else
   {
      struct BlockInfo* ptNext = (block + ptBlock->nSize);
      // ESLI PAMYATI BOLSHE NET
      if ( ptNext == (FirstBlock + MAX_MEMORY_SIZE) )
      {
         return NULL;
      }
      // RYADOM EST'' SVOBODNY'Y PODHODYASCH'IY BLOK
      if ( (!ptNext->bOccupied) &&
           ((ptBlock->nSize + ptNext->nSize + sizeof(struct BlockInfo)) >= size) )
      {
         size_t tail = ptBlock->nSize + ptNext->nSize + sizeof(struct BlockInfo)
                       - size;
         ptBlock->nSize = size;
         // ESLI OSTAVSHEYSYA PAMYATI NE HVATAET DLYA BlockInfo - "OTDAE'M EE' POL''ZOVATELYU"
         if (tail < sizeof(struct BlockInfo))
         {
            ptBlock->nSize += tail;
         }
         else
         {
            struct BlockInfo* ptFree = (void*)ptBlock + ptBlock->nSize
                                       + sizeof(struct BlockInfo);
            ptFree->bOccupied = 1;
            ptFree->nSize = tail - sizeof(struct BlockInfo);
            ptFree = (void*)ptFree + sizeof(struct BlockInfo);
            mfree(ptFree);
         }
         return block;
      }
      else
      {
         ptNext = (struct BlockInfo*)mmalloc(size);
         // ESLI UDALOS'' VY'DELIT'' NOVY'Y BLOK, UDALYAEM PEREDANNY'Y
         if (ptNext)
         {
            mfree(block);
            return ptNext;
         }
         // INACHE PEREDANNY'Y OSTAE'TSYA BEZ IZMENENIY
         else
         {
            return NULL;
         }
      }
   }
}

// =============================================================================
// O4ISTIT' VES' MASSIV PAMYATI - "UBORKA MUSORA"
void MallocUninit()
{
   InitFlag = 0;
   free(FirstBlock);
}

Если вдруг что-то в коде не ясно, спрашивай.

[Yarik-Jedi]

Большое спасибо. Попробую сдать, если получится. :rolleyes:

[Rumata]

Эх, позновато пишу, но лучше поздно, чем никогда
Вам что, на полном серьезе предлагают с использованием Java выделить вполне определенный блок памяти по заданному адресу?

[Andrej]

Большое спасибо. Попробую сдать, если получится. :rolleyes:

Пожалуйста.
Можно и в репутацию килограмчик накинуть
Должно получится - я сдал вообще без проблем

[Yarik-Jedi]

Эх, позновато пишу, но лучше поздно, чем никогда
Вам что, на полном серьезе предлагают с использованием Java выделить вполне определенный блок памяти по заданному адресу?

Нам сказали написать на любом языке программирования, но сказали, что лучше всего это на С сделать. Но поскольку я с ним очень слабо дружу, для лучшего понимания хотелось бы на Delphi/Java. :rolleyes:

[Rumata]

Нам сказали написать на любом языке программирования, но сказали, что лучше всего это на С сделать. Но поскольку я с ним очень слабо дружу, для лучшего понимания хотелось бы на Delphi/Java. :rolleyes:

В Java память для основных типов данных (boolean, char, byte, short, etc.) выделяется исключительно в стеке, а для объектов (экземпляров классов) -- в куче (при этом, как правило, единым блоком она не выделяется).
Выделение памяти -- прерогатива виртуальной машины, и у программиста нет возможности управлять этим процессом.

Сообщение отредактировал Rumata - May 11 2006, 18:38

[Andrej]

"лучше всего это на С сделать"
Это сказали правильно. Для работы с памятью (а менеджер памяти это оно и есть) C - то что доктор прописал. Delpi(Pascal) я использовал последний раз уж очень давно, так что даже и не берусь судить, как там с этим делом, но какая-то прямая работа с памятью там точно есть.

Когда искал материал для лабы, все примеры были только на C.
Вобщем, когда сдашь, напиши, как всё прошло))