Estructura de Datos : Bolsa de Almacenamiento

Definiciones

• En la literatura inglesa esta estructura de datos se conoce como storage pool.
• El significado, en inglés, de pool es : banco, bolsa y equipo.
• El storage pool contiene todos los nodos del almacenamiento que no están siendo usados.
• El almacenamiento distingue los nodos ocupados de los nodos libres. Los nodos libres se organizan en una pila enlazada. De esta manera disponemos de una estructura de datos LIFO ( Last In First Out ) lo que indica que el último nodo devuelto es el proximo a ser reusado.
• Llamaremos a la pila de nodos libres Lista de Espacio Disponible ( Available Space List ).

Diseño de Nodos

• Dependientes del problema
  • Campos Datos. Número de campos de datos.
  • Campos Datos. Tamaño de campos de datos.
  • Campos Enlaces. Número de campos de enlace.
• Dependientes de la volatilidad
  • Funciones . Se puede obviar la RETNODE().

Representaciones

Representación Gráfica ( Graphic Representation )

  +---+
  |   | AV ( Available Space List )
  +---+
    .
    .
    .
    .          1                  2                  3                             n
    .         +-------------+    +-------------+    +-------------+               +-------------+
    ........> |      |   2..|...>|      |   3..|...>|      |   4..|...> ..... ...>|      |   0  |
              +-------------+    +-------------+    +-------------+               +-------------+

Funciones

Inicialización

Este procedimiento incializa el almacenamiento con n nodos libres. La variable n es una variable de entrada. La inicialización acontece solo en el campo de enlace. La dirección de los nodos libres es de 1 a n. AV, la variable que apunta al storage pool, apunta al primer nodo libre.

• procedure INIT(n)
  • for i <---- 1 to n - 1 do
    • LINK(i) <---- i + 1
  • end
  • LINK(n) <---- 0
  • AV <---- 1
• end INIT

Obtención

Este procedimiento obtiene la dirección de un nodo libre. El nodo sale de la pila de nodos libres. Y es una variable de salida.

• procedure GETNODE(Y)
  • if AV = 0
    • then
      • call NO_MORE_NODES
    • else
      • Y <---- AV
      • AV <---- LINK(AV)
• end GETNODE

Devolución

Este procedimiento enlaza a la lista de nodos libres el nodo que se devuelve. Y es una variable de entrada con la dirección del nodo que se devuelve.

• procedure RETNODE(Y)
  • LINK(Y) <---- AV
  • AV <---- Y
• end RETNODE