Projektujesz nowy ezoteryczny język programowania, a jedną z funkcji, którą postanowiłeś dodać, jest dynamiczny alokator pamięci. Twój język określa specjalną dedykowaną wirtualną przestrzeń adresową dla przestrzeni programowej użytkownika. Jest to oddzielne od przestrzeni adresowej używanej przez alokator pamięci dla dowolnego stanu wewnętrznego.
Aby zmniejszyć koszt dystrybucji implementacji, rozmiar kodu musi być jak najmniejszy.
Berło
Musisz zapewnić trzy funkcje: inicjowanie, przydzielanie i cofanie przydziału.
Inicjalizacja
Ta funkcja przyjmuje pojedynczy dodatni parametr liczby całkowitej N. Oznacza to, że program użytkownika ma Nw swojej przestrzeni adresowej bajty, z których są N-1bajty do przydzielenia pamięci. Adres 0jest zarezerwowany dla „null”.
Zagwarantowane jest, że funkcja ta zostanie wywołana dokładnie raz przed każdym połączeniem alokacji / cofnięcia przydziału.
Należy pamiętać, że ta funkcja nie musi przydzielać pamięci fizycznej dla wirtualnej przestrzeni adresowej programu użytkownika; zasadniczo tworzysz „wygląd i styl” pustego alokatora pamięci.
Przeznaczyć
Funkcja przydzielania musi przyjąć żądanie liczby bajtów pamięci do przydzielenia. Dane wejściowe są gwarantowane jako pozytywne.
Twoja funkcja musi zwrócić adres liczby całkowitej na początek przydzielonego bloku lub 0wskazać, że nie ma dostępnego ciągłego bloku o żądanym rozmiarze. Jeśli ciągły blok o dostępnym rozmiarze jest dostępny w dowolnym miejscu w przestrzeni adresowej, musisz go przydzielić!
Musisz upewnić się, że żadne dwa przydzielone bloki się nie pokrywają.
Cofnij przydział
Funkcja dezalokacji musi przyjmować adres początku przydzielonego bloku i opcjonalnie może również przyjmować rozmiar danego bloku.
Pamięć, która została zwolniona, jest ponownie dostępna do alokacji. Zakłada się, że adres wejściowy jest prawidłowy.
Przykładowa implementacja języka Python
Pamiętaj, że możesz wybrać dowolną metodę śledzenia stanu wewnętrznego; w tym przykładzie instancja klasy śledzi to.
class myallocator:
def __init__(self, N):
# address 0 is special, it's always reserved for null
# address N is technically outside the address space, so use that as a
# marker
self.addrs = [0, N]
self.sizes = [1, 0]
def allocate(self, size):
for i,a1,s1,a2 in zip(range(len(self.addrs)),
self.addrs[:-1], self.sizes[:-1],
self.addrs[1:]):
if(a2 - (a1+s1) >= size):
# enough available space, take it
self.addrs.insert(i+1, a1+s1)
self.sizes.insert(i+1, size)
return a1+s1
# no contiguous spaces large enough to take our block
return 0
def deallocate(self, addr, size=0):
# your implementation has the option of taking in a size parameter
# in this implementation it's not used
i = self.addrs.index(addr)
del self.addrs[i]
del self.sizes[i]
Punktacja
To jest kod golfowy; najkrótszy kod w bajtach wygrywa. Nie musisz się martwić, że zabraknie pamięci dla dowolnego stanu wewnętrznego wymaganego przez twój program przydzielający.
Obowiązują standardowe otwory na pętle.
Tabela liderów
To help reduce the cost of distributing your implementation the size of the code must be as small as possibleczy może być wydajny (mały i wydajny to nie to samo), jak to możliwe? : D