ANSI C 2

położenia w pamięci wszystkie bloki mają rozmiar będący wielokrotnością rozmiaru nagłówka, nagłówek zaś jest położony poprawnie. Efekt ten osiągnięto za pomocą unii zawierającej wymaganą strukturę nagłówka oraz obiekt o typie narzucającym najsilniejsze ograniczenia - tutaj arbitralnie przyjęliśmy, że jest nim long.

typedef long Align; /* położenie dla obiektów typu long */

union header {    /* nagłówek bloku */

struct {

union header *ptr; /* następny wolny blok */ unsigned size;    /* rozmiar tego bloku */

} s;

Align x;    /* wymuszenie położenia bloku */

};

typedef union header Header;

Składowa unii o typie Align nigdy nie będzie używana; służy jedynie do wymuszenia położenia całego nagłówka odpowiednio dla najbardziej wymagającego typu.

•

Żądany rozmiar obszaru (w znakach) będzie przez funkcję malloc zaokrąglony do właściwej liczby porcji o rozmiarze nagłówka. Przydzielony blok zawiera o jedną porcję więcej - na sam nagłówek; ta liczba porcji jest właśnie wartością zanotowaną w składowej size nagłówka. Wskaźnik zwracany przez funkcję malloc wskazuje na wolny obszar, a nie na jego nagłówek. Z przydzieloną pamięcią użytkownik może robić co chce, ale jeśli cokolwiek zostanie zapisane na zewnątrz tej pamięci, to łańcuch bloków zamieni się w śmietnik.

*-► wskazuje na następny wolny blok

rozmiar

adres zwracany użytkownikowi

Blok zwracany przez funkcję malloc

Składowa rozmiaru jest niezbędna, ponieważ bloki kontrolowane przez funkcję malloc mogą nie tworzyć ciągłej pamięci - arytmetyka na wskaźnikach nie jest w takim przypadku możliwa.

Zmienna base służy do rozpoczęcia działania dystrybutora. Jeśli wskaźnik wolnego bloku freep jest równy NULL, jak przy pierwszym wywołaniu funkcji malloc, to bu-8.7 PRZYKŁAD - DYSTRYBUTOR PAMIĘCI

duje ona zdegenerowany łańcuch wolnych bloków, który zawiera jec]_

tniarze zero ze wskaźnikiem do niego samego. Następnie - w każdym przypadku - malloc przeszukuje listę wolnych bloków. Poszukiwanie bloku o wymaganym rozmiarze rozpoczyna się od miejsca (freep), w którym ostatnio znaleziono wolny blok; strategia ta pomaga utrzymać łańcuch w jednorodnej postaci. Jeżeli znaleziony blok jest za duży, to użytkownikowi przekazuje się końcową część obszaru bloku - wystarczy wówczas jedynie uaktualnić rozmiar w oryginalnym nagłówku bloku. Przekazywany użytkownikowi wskaźnik zawsze pokazuje na wolny obszar wewnątrz bloku, rozpoczynający się tuż za nagłówkiem tego bloku.

static Header base; /* pusty łańcuch na początek */

static Header *freep = NULL; /* początek łańcucha wolnych bloków */

I* malloc: ogólny dystrybutor pamięci */ void *malloc(unsigned nbytes)

{

Header *p, *prevp;

Header *morecore(unsigned);

unsigned nunits;    /* liczba żądanych porcji */

nunits - (nbytes+ sizeof(Header)-1)/sizeof(Header) + 1; if ((prevp = freep) == NULL) {    /* pusty łańcuch */

base.s.ptr = freep = prevp = &base; base. s. size = 0;

}

for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {

if (p->s.size >= nunits) {    /* dostatecznie duży blok */

if (p->s.size == nunits ) /* dokładnie taki */ prevp->s.ptr = p->s.ptr;

else {    /* za duży: przydziel koniec */

p->s.size -= nunits; p += p->s.size; p->s.size = nunits;

}

freep = prevp; return (void *)(p+1);

}

if (p == freep) /* przeszukano cały łańcuch */ if ((p = morecore(nunits)) == NULL) return NULL; /* brak pamięci */

}

}

247