Witam. Mam następujący problem:
Mam napisać "symulator alokatora pamięci", jak to nazwał mój prowadzący. Chodzi o to, by program na odpowiednie komendy udawał, że tworzy w pewnym obszarze pamięci o zadanej długości bloki danych. Tworzyć może tylko wtedy, gdy istnieje odpowiednio długi, ciągły obszar pusty. Ma też usuwać zadane bloki i wyświetlać ich adresy. "Alokacja" bloku następuje metodą best-fit.
#include <cstdlib>
#include <iostream>
#include <map>
#include <utility>
#include <set>
using namespace std;
struct cmp
{
bool operator()(const char* s1,const char* s2) const
{
return strcmp(s1,s2)<0;
}
};
typedef map<const char*, int, cmp> TMap;
typedef pair<int, int> TPair;
typedef set<TPair> TSet;
const char* zmienna = "A";
TMap mapPtr = (*new TMap); // Przechowuje nazwę wskaźnika i powiązany adres.
TSet setAL = (*new TSet);
TSet setLA = (*new TSet); // AL - abbr. Adress-Length, LA - abbr. Length-Adress;
TSet setBAL = (*new TSet);// BAL - abbr. Block_Adress-Length
int GetAdress(const char* PtrName)
{
// Pobieranie adresu dla zadanej nazwy zmiennej
return mapPtr[PtrName];
}
void Allocate(const char* PtrName, int size)
{
// Alokacja zmiennej PtrName o wielkości "size"
TSet::iterator it = setLA.lower_bound(TPair(size,0)); //Znajdź odpowiedni blok w zbiorze LA
if (it != setLA.end())
{
mapPtr[PtrName] = it->second; //Przypisz adres wskaźnikowi
setBAL.insert(TPair(mapPtr[PtrName], size));
if (it->first>size)
{
setLA.insert(TPair(it->first - size, it->second + size)); //Utwórz nowy wolny blok w zbiorze LA
setAL.insert(TPair(it->second + size, it->first - size)); //Utwórz nowy wolny blok w zbiorze AL
}
setAL.erase(TPair(it->second, it->first)); //Usuń odpowiedni blok z AL
setLA.erase(TPair(it->first, it->second)); //Usuń blok ze zbioru LA
}
}
void Deallocate(const char*PtrName)
{
// zwolnienie bloku PtrName
TMap::iterator it = mapPtr.find(PtrName);
if (it != mapPtr.end())
{
TSet::iterator itBAL = setBAL.lower_bound(TPair(mapPtr[PtrName], 0));
TSet::iterator itAL1 = setAL.upper_bound(TPair(mapPtr[PtrName], 0));
TSet::iterator itAL_1 = itAL1;
--itAL_1;
TSet::iterator itLA_1 = setLA.find(TPair(itAL_1->second, itAL_1->first)); //Znalezienie markera w zbiorze AL
TSet::iterator itLA1 = setLA.find(TPair(itAL1->second, itAL1->first));
if (itAL_1->first+itAL_1->second == itBAL->first)
{
if (itBAL->first+itBAL->second == itAL1->first)
{
setAL.insert(TPair(itAL_1->first, itAL_1->second+itBAL->second+itAL1->second));
setLA.insert(TPair(itAL_1->second+itBAL->second+itAL1->second, itAL_1->first));
setAL.erase(itAL1);
setLA.erase(itLA1);
}
else
{
setAL.insert(TPair(itAL_1->first, itAL_1->second+itBAL->second));
setLA.insert(TPair(itAL_1->second+itBAL->second, itAL_1->first));
}
setAL.erase(itAL_1);
setLA.erase(itLA_1);
}
else
{
if (itBAL->first+itBAL->second == itAL1->first)
{
setAL.insert(TPair(itBAL->first, itBAL->second+itAL1->second));
setLA.insert(TPair(itBAL->second+itAL1->second, itBAL->first));
setAL.erase(itAL1);
setLA.erase(itLA1);
}
else
{
setAL.insert(TPair(itBAL->first, itBAL->second));
setLA.insert(TPair(itBAL->second, itBAL->first));
}
}
setBAL.erase(itBAL);
mapPtr.erase(PtrName);
}
}
void Initiate(int Length)
{
// Inicjalizacja wszelakich potrzebnych zmiennych i kontenerów
setAL.clear();
setLA.clear();
mapPtr.clear();
setBAL.clear();
setAL.insert(TPair(0, Length));
setLA.insert(TPair(Length, 0));
}
int main()
{
int s, c, shit, size;
char order[2];
char *PtrName;
scanf("%d %d", &s, &c);
Initiate(s);
while (c)
{
scanf("%2s %s", order, PtrName);
if (order[0]=='b')
{
scanf(" %d", &size);
Allocate(PtrName, size);
}
else
if (order[0]=='p')
{
if ((mapPtr.find(PtrName)) != (mapPtr.end()))
printf("%d\n", mapPtr[PtrName]);
else
printf("%s\n", "null");
}
else
if (order[0]=='d')
{
Deallocate(PtrName);
}
//printf("%d\n", mapPtr[zmienna]);
c--;
}
return EXIT_SUCCESS;
}
Póki co mój kod wygląda tak. Niby wszystko w porządku, ale dziwnie się zachowuje. Kiedy puszczę go samopas i właduję przykładowy zestaw danych, to daje błędne wyniki. Jeżeli uruchomię debugger i ten sam zestaw będę przetwarzał "krok po kroku" (F8 w Borlandzie), to też mam złe wyniki, ale inne! Jeżeli natomiast skompiluje go pod DevC++, to program wiesza się po pierwszej komendzie.
Przykładowe wejście:
16 22
bf A 1
pr A
bf B 2
pr B
bf C 4
pr C
bf D 1
pr D
bf E 1
pr E
bf F 1
pr F
bf G 1
pr G
bf H 3
pr H
dl A
dl C
dl F
dl G
bf I 2
pr I
Wyjście:
0
1
3
7
8
9
10
11
9
polecenie: bf A 1 alokuje blok wielkości 1 i nazwie "A"
polecenie: pr A wyświetla adres bloku o nazwie "A"
polecenie: dl A usuwa blok o nazwie "A" (powstaje tam znowu obszar wolnej pamięci)
Pierwsze dwie liczby, to odpowiednio Wielkość zarządzanego obszaru i ilość poleceń