Allocateur de mémoire

11

Vous concevez un nouveau langage de programmation ésotérique et l'une des fonctionnalités que vous avez décidé d'ajouter est un allocateur de mémoire dynamique. Votre langue spécifie un espace d'adressage virtuel dédié spécial pour l'espace programme de l'utilisateur. Ceci est distinct de l'espace d'adressage utilisé par l'allocateur de mémoire pour tout état interne.

Pour réduire le coût de distribution de votre implémentation, la taille du code doit être aussi petite que possible.

Interface

Vous devez fournir trois fonctions: initialisation, allocation et désallocation.

Initialisation

Cette fonction prend un seul paramètre entier positif N. Cela signifie que le programme d'un utilisateur a des Noctets dans son espace d'adressage à partir desquels il y a des N-1octets pour allouer de la mémoire. L'adresse 0est réservée à "null".

Il est garanti que cette fonction sera appelée exactement une fois avant tout appel d'allocation / désallocation.

Notez que cette fonction n'a pas besoin d'allouer de mémoire physique pour l'espace d'adressage virtuel du programme utilisateur; vous créez essentiellement le "look and feel" d'un allocateur de mémoire creux.

Allouer

La fonction d'allocation doit accepter une demande du nombre d'octets de mémoire à allouer. L'entrée est garantie positive.

Votre fonction doit renvoyer une adresse entière au début du bloc alloué, ou 0pour indiquer qu'il n'y a pas de bloc contigu de la taille demandée disponible. Si un bloc contigu de la taille disponible est disponible n'importe où dans l'espace d'adressage, vous devez allouer!

Vous devez vous assurer qu'aucun deux blocs alloués ne se chevauchent.

Désallouer

La fonction de désallocation doit prendre une adresse du début d'un bloc alloué et peut également prendre la taille du bloc donné.

La mémoire qui a été désallouée est à nouveau disponible pour l'allocation. Il est supposé que l'adresse d'entrée est une adresse valide.

Exemple d'implémentation Python

Notez que vous pouvez choisir n'importe quelle méthode pour garder une trace de l'état interne; dans cet exemple, l'instance de classe en garde la trace.

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]

Notation

C'est le golf de code; le code le plus court en octets gagne. Vous n'avez pas à vous soucier de manquer de mémoire pour tout état interne requis par votre allocateur.

Des trous de boucle standard s'appliquent.

Classement

Afficher l'extrait de code

code-golf helloworld922
la source
3
Je doute que les listes Python prennent exactement un octet par élément. La "mémoire allouée" doit-elle être en octets, ou peut-elle simplement être "le type de tableau / liste générique de votre langue"?
Poignée de porte
4
Aucune allocation réelle n'est requise (sauf pour tout ce que vous voulez pour le suivi de l'état interne, qui se trouve sur son propre espace d'adressage virtuel); vous ne renvoyez que des entiers à un espace d'adressage virtuel fini et abstrait.
helloworld922
To help reduce the cost of distributing your implementation the size of the code must be as small as possibleou pourrait-il être efficace (petit et efficace ne sont pas les mêmes) que possible? : D
Le codeur
Huh, conception de la langue ?
Akangka
Bien que ce défi soit motivé par un arrière-plan de conception de langage, la conception d'un langage ne fait pas réellement partie de la tâche (plutôt implémenter des parties d'un), j'ai donc supprimé la balise.
Martin Ender

Réponses:

4

Rubis, 80

i,a,d=->n{$m=?o*n},->n{$m.sub!(/\B#{?o*n}/,?f*n);"#$`".size},->n,s{$m[n,s]=?o*s}

Comme la réponse de MegaTom, mais utilise une chaîne au lieu d'un tableau pour stocker l'état. Le caractère "o" indique une cellule ouverte, tandis qu'un "f" indique une cellule remplie. Cela nous permet d'utiliser les fonctions de manipulation de chaînes relativement succinctes de Ruby:

?o*n initialise une chaîne de n "o" s.

/\B#{?o*n}/est une expression régulière correspondant à n "o" consécutifs qui n'inclut pas le premier caractère. sub!remplace la première correspondance par n "f" s.

"#$`" donne la chaîne à gauche de la correspondance, ou une chaîne vide s'il n'y avait pas de correspondance, donc la taille est soit l'index alloué, soit 0.

La désallocation redéfinit simplement la section désignée de la chaîne sur "o".

histocrate
la source
4

JavaScript (ES6), 88

Utiliser une variable globale _(un tableau très clairsemé) pour garder une trace.

Maintenant, comment pourrais-je le tester?

I=n=>(_=[1],_[n]=0)
A=n=>_.some((x,i)=>i-p<n?(p=i+x,0):_[p]=n,p=1)?p:0
D=p=>delete _[p]
edc65
la source
3

Rubis, 135

Dispose d'un tableau global pour savoir si chaque cellule est allouée ou non.

i=->n{$a=[!0]*n;$a[0]=0}
a=->n{s=$a.each_cons(n).to_a.index{|a|a.none?};n.times{|i|$a[s+i]=0}if s;s||0}
d=->s,n{n.times{|i|$a[s+i]=!0}}
MegaTom
la source
1

Mathematica, 152

i=(n=#;l={{0,1},{#,#}};)&
a=If[#=={},0,l=l~Join~#;#[[1,1]]]&@Cases[l,{Except@n,e_}:>{e,e+#}/;Count[l,{a_,_}/;e<=a<e+#]<1,1,1]&
d=(l=l~DeleteCases~{#,_};)&

nstocker la taille totale, lstocke l'état interne. L'allocateur tentera d'allouer juste derrière une autre section de mémoire allouée.

njpipeorgan
la source