Asignador de memoria

11

Está diseñando un nuevo lenguaje de programación esotérico y una característica que ha decidido agregar es un asignador dinámico de memoria. Su idioma especifica un espacio de dirección virtual dedicado especial para el espacio del programa del usuario. Esto es independiente del espacio de direcciones utilizado por el asignador de memoria para cualquier estado interno.

Para ayudar a reducir el costo de distribuir su implementación, el tamaño del código debe ser lo más pequeño posible.

Interfaz

Debe proporcionar tres funciones: inicialización, asignación y desasignación.

Inicialización

Esta función toma un único parámetro entero positivo N. Esto significa que el programa de un usuario tiene Nbytes en su espacio de direcciones desde los cuales hay N-1bytes para asignar memoria. La dirección 0está reservada para "nulo".

Se garantiza que esta función se invocará exactamente una vez antes de cualquier llamada de asignación / desasignación.

Tenga en cuenta que esta función no necesita asignar ninguna memoria física para el espacio de direcciones virtuales del programa de usuario; básicamente está creando la "apariencia" de un asignador de memoria hueca.

Asignar

La función de asignación debe tomar una solicitud del número de bytes de memoria para asignar. La entrada está garantizada para ser positiva.

Su función debe devolver una dirección entera al comienzo del bloque asignado, o 0para indicar que no hay un bloque contiguo del tamaño solicitado disponible. ¡Si un bloque contiguo del tamaño disponible está disponible en cualquier parte del espacio de direcciones, debe asignarlo!

Debe asegurarse de que no se superpongan dos bloques asignados.

Desasignar

La función de desasignación debe tomar una dirección del inicio de un bloque asignado y, opcionalmente, también puede tomar el tamaño del bloque dado.

La memoria que se ha desasignado está disponible nuevamente para asignación. Se supone que la dirección de entrada es una dirección válida.

Ejemplo de implementación de Python

Tenga en cuenta que puede elegir cualquier método para realizar un seguimiento del estado interno; en este ejemplo, la instancia de clase lo rastrea.

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]

Puntuación

Este es el código de golf; el código más corto en bytes gana. No necesita preocuparse por quedarse sin memoria para cualquier estado interno requerido por su asignador.

Se aplican agujeros de bucle estándar.

Tabla de clasificación

Mostrar fragmento de código

code-golf helloworld922
fuente
3
Dudo que las listas de Python ocupen exactamente un byte por elemento. ¿La "memoria asignada" tiene que estar en bytes, o puede ser simplemente "el tipo genérico de matriz / lista de su idioma"?
Pomo de la puerta
44
No se requiere una asignación real (excepto lo que desee para el seguimiento interno del estado, que se encuentra en su propio espacio de dirección virtual); solo devuelve enteros a un espacio de direcciones virtual finito abstracto.
helloworld922
To help reduce the cost of distributing your implementation the size of the code must be as small as possibleo podría ser eficiente (pequeño y eficiente no son lo mismo) como sea posible? : D
El codificador
¿Eh, diseño de lenguaje ?
Akangka
Si bien este desafío está motivado con un fondo de diseño de lenguaje, el diseño de un idioma no es realmente parte de la tarea (más bien implementar partes de uno), por lo que he eliminado la etiqueta.
Martin Ender

Respuestas:

4

Rubí, 80

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

Como la respuesta de MegaTom, pero usa una cadena en lugar de una matriz para almacenar el estado. El carácter "o" denota una celda abierta, mientras que una "f" denota una llena. Esto nos permite usar las funciones de manipulación de cadenas relativamente concisas de Ruby:

?o*n inicializa una cadena de n "o" s.

/\B#{?o*n}/es una expresión regular que coincide con n "o" consecutivas que no incluye el primer carácter. sub!reemplaza el primer partido con n "f" s.

"#$`" da la cadena a la izquierda de la coincidencia, o una cadena vacía si no hubo coincidencia, por lo que el tamaño es el índice asignado o 0.

Deallocate solo establece la sección designada de la cadena de nuevo a "o" s.

histocrat
fuente
4

JavaScript (ES6), 88

Usar una variable global _(una matriz muy escasa) para realizar un seguimiento.

Ahora, ¿cómo podría probarlo?

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
fuente
3

Ruby, 135

Tiene una matriz global que realiza un seguimiento de si cada celda está asignada o no.

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
fuente
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~{#,_};)&

nalmacenar el tamaño total, lalmacena el estado interno. El asignador intentará asignar justo detrás de otra sección de memoria asignada.

njpipeorgan
fuente