[C++] Symulator Alokatora Pamięci...

0

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ń

0

czyli masz napisac nowy alokator, ktory bazuje na fragmencie pamieci anie na calym jej obszarze:
powinno sie przydac:
http://g.oswego.edu/dl/html/malloc.html

0

Nie wiem jak bardzo ma to być skomplikowane, ale może warto zainteresować się operatorem new w wersji umiejscawiającej:

http://www.parashift.com/c++-faq-lite/dtors.html#faq-11.10
http://www.devx.com/tips/Tip/12582
zbyt długi link

lub też podejrzeć standardowe alokatory:

http://gcc.gnu.org/onlinedocs/libstdc++/20_util/allocator.html
http://www.infosys.tuwien.ac.at/Research/Component/tutorial/prw45.htm

http://www.google.pl/search?hl=pl&q=C%2B%2B+allocators&btnG=Szukaj&lr=

Mam nadzieję, że linki choć trochę pomogą :)

0

Na większość tych linków już trafiłem. Mój problem polega na tym, że ja wcale nie mam rzeczywiście alokować żadnej pamięci, tylko to zasymulować. Czyli odpowiedzieć na pytanie: Gdzie w takiej a takiej sytuacji alokator umieściłby dany blok. Z resztą ja czasem potrafię trochę zamieszać, jak usiłuję komuś coś przedstawić, więc rzucę tu pełną treść zadania. W sumie najbardziej dziwi mnie dziwne zachowanie kompilatorów na tym kodzie...

Zadanie polega na napisaniu programu, który symuluje działanie alokatora pamięci. Alokator pamięci to usługa udostępniana przez system operacyjny lub środowisko systemowe, pozwalająca na dynamiczny przydział i zwalnianie bloków danych zadanego rozmiaru w obszarze roboczym pamięci operacyjnej. W szczególności, alokator jest wykorzystywany do realizacji takich operacji, jak new i delete w języku C++.

Przy realizacji zadania projektowego należy przyjąć następujące założenia upraszczające:

* zarządzany obszar pamięci roboczej złożony jest z s komórek pamięci rozmiaru 1 bajta każda, adresowanych kolejno wartościami od 0 do s-1,
* w miarę postępu alokacji w obszarze pamięci wyróżnia się bloki wolnej pamięci, rozumiane jako najdłuższe możliwe ciągi niezaalokowanych komórek pamięci o sąsiadujących ze sobą adresach,
* początkowo cały obszar pamięci roboczej stanowi blok wolnej pamięci,
* żądanie alokacji bloku danych o rozmiarze b jest realizowane wtedy i tylko wtedy, gdy istnieje w pamięci wolny blok rozmiaru przynajmniej b,
* w przypadku, gdy alokacja następuje metodą first-fit, do realizacji żądania wykorzystywanych jest b kolejnych komórek wolnej pamięci, poczynając od komórki o możliwie jak najmniejszym adresie,
* w przypadku, gdy alokacja następuje metodą best-fit, do realizacji żądania wykorzystywanych jest b kolejnych komórek wolnej pamięci należących do bloku wolnej pamięci o możliwie jak najmniejszym rozmiarze, poczynając od komórki o możliwie jak najmniejszym adresie.
* wynikiem alokacji jest adres pierwszej komórki zaalokowanego bloku, lub wartość null, gdy alokacja się nie powiedzie,
* polecenie zwolnienia bloku pamięci przyjmuje jako parametr zmienną wskazującą na adres początkowy zaalokowanego bloku, powodując jego zwolnienie (jeśli adres jest poprawny) lub brak akcji (jeśli adres nie jest poprawny); w obydwu przypadkach wartość zmiennej wskaźnikowej jest ustawiana następnie na null.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite s c, określające odpowiednio liczbę bajtów zarządzanej pamięci i liczbę poleceń wykonywanych przez alokator w trakcie symulacji. W następnych c liniach znajduje się ciąg poleceń wydawanych alokatorowi. Każde polecenie przyjmuje jedną z czterech postaci:

* ff PTR b - polecenie alokacji bloku b bajtów metodą first-fit i zapamiętanie wyniku jako wartości zmiennej wskaźnikowej o nazwie PTR,
* bf PTR b - polecenie alokacji bloku b bajtów metodą best-fit i zapamiętanie wyniku jako wartości zmiennej wskaźnikowej o nazwie PTR,
* pr PTR - polecenie wypisania na standardowe wyjście jednej linii znakowej, zawierającej wartość adresu zapisanego w zmiennej wskaźnikowej o nazwie PTR,
* dl PTR - polecenie zwolnienia bloku pamięci począwszy od adresu wskazywanego przez zmiennę wskaźnikową o nazwie PTR.

Nazwy PTR zmiennych wskaźnikowych mogą być dowolnymi ciągami dużych liter alfabetu łacińskiego (A..Z).
Wyjście

Program powinien wypisać na standardowe wyjście w oddzielnych liniach wyniki wykonania kolejnych operacji pr, tj. liczbę całkowitą lub ciąg znaków null określający adres wskazywany przez zmienną.
Przykład 1

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

Przykład 2

Wejście:
2500000 11
bf AAA 10000
pr AAA
bf AAA 20000
pr AAA
bf BXX 20000
dl AAA
bf ABCABC 20000
pr A
pr AAA
pr BXX
pr ABCABC

Wyjście:
0
10000
null
null
30000
10000

Punktacja

Nadesłany program będzie testowany 14 razy na różnych zestawach danych testowych, z których każdy będzie warty 0.5pkt. Kolejne testy będą spełniały różne założenia dotyczące rodzaju występujących poleceń i wartości s, c, b oraz możliwych długości nazw zmiennych |PTR|.

liczba punktów występujące polecenia ograniczenia parametrów
0-2 (4 testy) bf, pr 1<=s<=1000, 1<=c<=1000, 1<=b<=1000, |PTR|=1
2-4 (4 testy) bf, pr, dl 1<=s<=1000, 1<=c<=1000, 1<=b<=1000, |PTR|=1
4-5 (2 testy) bf, pr, dl 1<=s<=1000, 1<=c<=1000, 1<=b<=1000, 1<=|PTR|<=10
5-6 (2 testy) bf, pr, dl 1<=s<=109, 1<=c<=1000, 1<=b<=109, 1<=|PTR|<=10
6-7 (2 testy) bf, pr, dl 1<=s<=109, 1<=c<=100000, 1<=b<=109, 1<=|PTR|<=10
zadanie rozszerzone ff, bf, pr, dl 1<=s<=109, 1<=c<=100000, 1<=b<=109, 1<=|PTR|<=10

Testowanie rozwiązania jest przerywane przy pierwszym nieprawidłowo rozwiązanym przypadku testowym. Punkty za kod źródłowy (0-3pkt.) przyznawane są tylko w przypadku uzyskania minimum 2pkt. za funkcjonalność.
Środowisko, wymagania

Nadsyłane programy testowane są automatycznie w środowisku SPOJ (wynik testowania funkcjonalności można poznać natychmiast). Kompilacja następuje w środowisku gcc/g++, a programy uruchamiane są w systemie Linux (osoby piszące w systemie Windows powinny skorzystać ze środowiska Dev-C++ lub Cygwin ).

Działanie programu dla każdego przypadku testowego jest ograniczone przez pewien limit czasu procesora (nie mniejszy niż 1s na Pentium III 700MHz) i pamięci (nie mniejszy niż 64MB). Przyjmuje się, że do oceny w projekcie przedkładane jest ostatnie nadesłane zgłoszenie.
Wskazówka implementacyjna

Przy realizacji programu można skorzystać z następującego podejścia:

* w pętli głownej programu przetwarzane są kolejne linie odczytywane z wejścia i na bieżąco symulowane jest działanie alokatora, poprzez modyfikację struktur danych opisujących zawartość zarządzanej pamięci i wartości zmiennych wskaźnikowych alokatora,
* używane zmienne wskaźnikowe zapamiętane są w postaci zbioru par (nazwa zmiennej, wskazywany adres),
* zawartość pamięci reprezentowana jest w postaci informacji o wszystkich wolnych blokach w pamięci, w postaci par (adres początkowy bloku, rozmiar bloku), przy czym zakłada się, że pomiędzy każdymi dwoma blokami zaalokowanymi występuje dokładnie jeden wolny blok (oznacza to w szczególności konieczność "sklejenia" bloków wolnych przy zwalnianiu zajętego bloku pomiędzy nimi, a także możliwość wystąpienia bloków wolnych o rozmiarze 0 pomiędzy dwoma sąsiednimi blokami zajętymi).

Uwaga. Zaleca się stosowanie funkcji scanf/printf do czytania wejścia i pisania na wyjście; strumienie cin/cout mogą się czasami okazać zbyt wolne.

Powyższy opis nie narzuca żadnego doboru konkretnych struktur danych dla zawartości pamięci alokatora oraz jego zmiennych wskaźnikowych. W przypadku realizacji funkcjonalności za 6pkt. wystarczy przyjąć reprezentację danych w postaci znanych z wykładu dynamicznych list dwukierunkowych.

Reprezentacja w postaci list jest jednak niewystarczająca w przypadku funkcjonalności za 7pkt. ze względu na zbyt duży czas wyszukiwania odpowiedniego elementu w liście. Celem uniknięcia nadmiaru pracy, warto zapoznać się z dostępną standardowo w C++ biblioteką STL (Standard Template Library), a w szczególności z dokumentacją kontenerów map, set i pair. Poprawnie napisany kod źródłowy realizujący pełną funkcjonalność zadania przy użyciu STL może mieć nawet poniżej 70 linii długości.

Informację o zmiennych wskaźnikowych alokatora można zapamiętać w kontenerze typu map<const char*, int, ltstr>, dla funkcji ltstr jak w przykładzie w dokumentacji kontenera map. Należy zapoznać się dokładnie ze wspomnianym przykładem.

Informację o wolnych blokach w zarządzanej pamięci można reprezentować w postaci dwóch kontenerów typu set<pair<int,int> > (oba mogą przechowywać tę samą informację, przy czym w jednym kontenerze pierwszym elementem pary jest adres początkowy bloku, drugim rozmiar bloku; w drugim kontenerze - na odwrót). Do poszukiwania elementów w kontenerze typu set można użyć np. metody lower_bound, pamiętając o sposobie porównywania danych typu pair.

Limit czasu: 1s-3s
Limit długości źródła: 50000B
Języki: C C++

Może teraz jest jasno. Wydawało mi się, że mój kod zrealizuje te założenia, ale, jak pisałem zachowuje się nieprzewidywalnie i w sumie, to nie wiem już, co on robi. Może w tej kwestii ktoś mnie może oświecić?

0

Studiujesz na pierwszym roku Politechniki Gdańskiej na kierunku Informatyka? My mieliśmy identyczne zadanko rok temu ;-)

0

Zgadza się - to nasz trzeci projekt. W sumie, mając dość dużo czasu, miałbym szansę to rozgryźć, ale obecnie szykuję się na kilka sprawdzianów, kół i zbója z fizyki (grrr).

Napisałem ten kod i byłem pewien, że zadziała przynajmniej na 2 punkty, ale zachowuje sie nieprzewidywalnie.

Skoro mieliście takie samo zadanie, to może miałbyś dla mnie jakieś wskazówki ??

0

slither, to zadanko nie jest takie straszne, jak sobie zrobie to ci pomoge ..., hehe dzieki za WARP-a

0

Heh, udało mi się na razie na 2,5 punkta (czyli cholernie mało). Póki co sprawę załatwiła zamiana typu const char* na char kosztem ograniczenia długości nazw do 1 znaku. Poprzednio coś mieszał ze wskaźnikami. Zobaczę, co teraz. Na pewno muszę przepisać funkcję usuwającą, bo mi źle pamięć scala.

0

Dobra, zrobione na 6 punktów. Ale dalej mam problem:

mam kontener STL map

struct cmp
{
       bool operator()(const char* s1,const char* s2) const
       {
            return strcmp(s1,s2)<0;
       }
};

typedef map<const char*, int, cmp> TMap;

Jednak nie działa prawidłowo. Na razie to obszedłem, ale jest mi potrzebny w takiej postaci. Wiem, w czym leży problem: Kluczami w tym kontenerze są const char*, które wprowadza użytkownik. Ja pobieram jego input do zmiennej i potem tworzę nowy wpis w map:

char zmienna[11];
int wartosc;

scanf("%s10 %d", zmienna, &wartosc);
zmienna[10]='\0';
mapPtr.insert(make_pair(zmienna, wartosc));

Wiem, że on przypisuje tam wskaźnik, który przy następnym inpucie się nie zmieni, ale zmieni się wartość pod tym adresem. Nie wiem tylko, jak to zmienić, by działało.

1 użytkowników online, w tym zalogowanych: 0, gości: 1