Implementación de colas ligadas en Toro

Implementación de colas ligadas en Toro :

Las colas ligadas son un método eficaz para mantener agrupados una cantidad ilimitada de elementos . En Toro son utilizadas para agrupar los procesos , los timers , los superbloques , los inodos , los buffers , etc. , se le ha dado gran cantida de uso .

Podemos clasificarlas en dos tipo : simplemente ligadas o doblemente ligadas .

Por lo general las estructuras que se encuentran en una cola simplemente ligada posee solo un campo que apunta a la siguiente estructura y la ultima de la cola posee este campo a un puntero nulo , es decir solo pueden ser recorridas en un solo sentido .
A diferencia de estas , las doblemente ligadas posee dos campos una punteando a la siguiente estructura y otra a la anterior , pudiéndose así recorrerla en ambos sentidos y de manera cíclica .

La principal diferencia es para què van a ser utilizada . Por un lado las simplemente ligadas posee un campo menos , es decir ocupan menos memoria , pero si en la cola se están agregando y quitando elementos continuamente se consume mucha cpu , porque por cada elemento que debo quitar debo recorrer toda la cola para encontrar el anterior! .
Este problema se soluciona creando un nuevo campo apuntando al elemento anterior , así surgen las doblemente ligadas .
Es por eso que las colas que mantiene a los procesos , inodos , timers ,etc. , son colas doblemente ligadas , mientras que las colas que mantiene a los buffers que deben ser escritos a disco se encuentran en colas simplemente ligadas , cada buffer es agregado al comienzo y cuando deben ser quitados por la llamada sync() , se recorre la lista desde el inicio sacando de a uno todos .

Todo muy lindo , pero el hecho de que sean tan utilizadas hace necesarios procedimiento muy rápidos y eficientes , y este es el motivo del articulo .
Lo que se trato de crear fue procedimientos generales para el tratamiento de colas ligadas , tal como lo hace linux , pero en freepascal .

Todo el código del manejo de colas ligadas se encuentra en el archivo Include/Head/list.h

Este como se ve no es una unidad sino solo un archivo que debe ser incluido en la unidad luego de IMPLEMENTATION

Para que funcione deben ser declarados en la unidad cuatro símbolos ,de la manera tradicional , {$DEFINE Use_Tail} , estos son :

Use_Tail : le indica al compilador que el código de manejo de las lista debe ser incluido

nodo_struct : Debe contener la estructura de los elementos dentro de la cola , por ejemplo para una cola ligada de procesos valdría :

{$DEFINE nodo_struct = p_tarea_struc}

Siempre se considera a nodo_struct como un puntero .



nodo_tail : Puntea al elemento cabecera de la lista , puede estar definido o no .

next_nodo y prev_nodo : Estas estructuras poseen los campo dentro de los elementos de la lista que puntean al siguiente elemento y al anterior , por ejemplo para el caso de cola de procesos , estos valdrían :

{$DEFINE next_nodo = next_tarea }
{$DEFINE prev_nodo = prev_tarea}


El procedimiento para encolar un elemento , si se ha definido nodo_tail :

procedure Push_Node(Nodo : nodo_struct) ; inline ;

o en el caso de que no se haya definido nodo_tail :

procedure Push_Node(Nodo : nodo_struct;var Nodo_Tail : nodo_struct);inline;

La diferencia de que se defina o no nodo_tail , es la capacidad de trabajar en una unidad con mas de una cola ligada , puesto que de lo contrario se definiría un único valor para el símbolo nodo_tail , con esto se especifica el nodo cabecera de la cola en cada llamada .

Siempre el elemento es agregado al comienzo de la cola .

Ojo! nodo_tail no es una estructura sino solo un puntero al primer elemento de la cola .



Para quitar un elemento sucede lo mismo :

El procedimiento para quitar un elemento , si se ha definido nodo_tail :

procedure Pop_Node(Nodo : nodo_struct );inline;

o en el caso de que no se haya definido nodo_tail :

procedure Pop_Node(Nodo : nodo_struct;var Nodo_tail : nodo_struct);inline;

Como se ve todos los procedimiento son declarados como inline para acelerar su ejecución

Para hacer un poco mas “entendible” el código suelo definir otro símbolo que oculte a estos procedimientos :

{$DEFINE push_buffer = push_node }
{$DEFINE pop_buffer = pop_node }

Lo bueno de esto que definiendo un par de símbolos ya tenes todo el código para la manipulación de listas ligadas sin importar las estructuras , campos , etc .


Para el caso de colas simplemente ligadas , se debe definir el símbolo Use_Simple_Tail
para comenzar a trabajar con ella .
Igual que en el caso de las doblemente ligadas se cuenta con los procedimientos :

para agregar un elemento :

procedure Push_Snode (Nodo , sNodo_Tail : snode_struct);inline;

y para quitar un elemento :

procedure Pop_Snode (Nodo,sNodo_Tail : snode_struct);inline;

Ahora los símbolos nodo_struct y nodo_tail pasan a llamarse snode_tail y snode_struct respectivamente


Espero que les haya servido este pequeño articulo .
Una saludo



Matias E. Vara
Toro.sourceforge.net
matiasvara@yahoo.com