Operaciones sobre listas (Organización del Computador II)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Archivo main.c

#include <stdio.h>
#include <stdlib.h>

/* una forma mas legible de llamar a la lista nula */
#define NULA 0

/* estructura del nodo que tiene un entero
 * y un puntero a otro nodo (o lista, que
 * terminan siendo lo mismo */
struct nodo_t {
    int dato;
    struct nodo_t *sig;
};

/* la lista es solo un puntero a nodo */
typedef struct nodo_t* lista_t;

/* funciones hechas en assembler */
extern void agregar_adelante(lista_t *, int);
extern void insertar(lista_t *, int pos, int n);
extern int longitud(lista_t);
extern int esta_en_lista(lista_t, int);
extern int posicion(lista_t, int);
extern int borrar_elem(lista_t *, int);

/* muestra los elementos de la lista recorriendola */
void mostrar_lista(lista_t li)
{
    int num = 0;
    struct nodo_t *actual = li; 

    printf("<lista>\n");
   
    while(actual != 0)
    {
        printf("(%08x) lista[%i].dato = %i\n",
            (int) actual, num, actual->dato);
        
        printf("(%08x) lista[%i].sig = %08x\n",
            (int) actual, num, (int) actual->sig);
        
        actual = actual->sig;
        num++;
    }

    printf("</lista>\n");
}

/* borra todos los nodos de la lista */
void liberar_lista(lista_t li)
{
    struct nodo_t *actual = li;

    while(actual != 0)
    {
        struct nodo_t *sig = actual->sig;
        free(actual);
        actual = sig;
    }
}

/* punto de entrada */
int main(int argc, char *argv[])
{
    lista_t mi_lista = NULA;

    /* agrega algunos elementos adelante */
    printf("Agrego '5'...");
    agregar_adelante(&mi_lista, 5);
    printf("Longitud: %i\n", longitud(mi_lista));

    printf("Agrego '2'...");    
    agregar_adelante(&mi_lista, 2);
    printf("Longitud: %i\n", longitud(mi_lista));

    printf("Agrego '1'...");
    agregar_adelante(&mi_lista, 1);
    printf("Longitud: %i\n", longitud(mi_lista));
    
    /* muestra la lista por pantalla */
    mostrar_lista(mi_lista);

    /* pregunta cosas */
    printf("Esta 2: %i\n", esta_en_lista(mi_lista, 2));
    printf("Esta 7: %i\n", esta_en_lista(mi_lista, 7));
    printf("Esta 1: %i\n", esta_en_lista(mi_lista, 1));
    printf("Esta 5: %i\n", esta_en_lista(mi_lista, 5));

    /* pregunta cosas */
    printf("Posicion 2: %i\n", posicion(mi_lista, 2));
    printf("Posicion 7: %i\n", posicion(mi_lista, 7));
    printf("Posicion 1: %i\n", posicion(mi_lista, 1));
    printf("Posicion 5: %i\n", posicion(mi_lista, 5));
    
    /* insercion aleatoria */
    insertar(&mi_lista, 1, 666);
    insertar(&mi_lista, 3, 777);
    insertar(&mi_lista, 0, 0);
    insertar(&mi_lista, 5, -1);
    insertar(&mi_lista, longitud(mi_lista), 9999);

    /* muestra la lista por pantalla */
    mostrar_lista(mi_lista);

    /* borra los elementos aleatoriamente */
    while(longitud(mi_lista) > 0)
    {
        int pos = rand() % longitud(mi_lista);
        printf("Borrando elemento: %i\n", pos);
        borrar_elem(&mi_lista, pos);
        mostrar_lista(mi_lista);
    }
    
    /* borra la lista de memoria */
    liberar_lista(mi_lista);
    
    return 0;
}

Archivo ext.asm

%ifdef WIN32
%define agregar_adelante _agregar_adelante
%define esta_en_lista _esta_en_lista
%define longitud _longitud
%define posicion _posicion
%define insertar _insertar
%define borrar_elem _borrar_elem
%define malloc _malloc
%endif

; exporto las siguientes funciones
global agregar_adelante
global esta_en_lista
global longitud
global posicion
global insertar
global borrar_elem

; requiero las siguientes funciones
extern malloc
extern free

section .text
; crea un nodo
; le pone como dato ebx
; y devuelve:
;    eax = dir del nodo
%macro crear_nodo 0
    ; pide memoria
    push 8
    call malloc
    add esp, 4

    ; setea el dato = ebx
    mov dword [eax], ebx
%endmacro

;============================================================
; void agregar_adelante(nodo**, int)
;============================================================
agregar_adelante:
    ; convencion C
    push ebp
    mov ebp, esp
    push ebx
    
    ; crea un nodo y le pone
    ; el segundo param de valor
    mov ebx, [ebp + 12]
    crear_nodo

    ; @invariante:
    ; eax = dir del nuevo nodo

    ; guarda en edx el comienzo de la lista
    mov ebx, [ebp + 8]
    mov edx, [ebx]

    ; @invariante:
    ; eax = dir del nuevo nodo
    ; ebx = dir del nodo original

    ; pone en el comienzo el nuevo nodo
    mov [ebx], eax

    ; apunta sig del nuevo nodo al comienzo anterior
    mov [eax + 4], edx

    ; concencion C   
    pop ebx
    pop ebp
    ret

;============================================================
; bool esta_en_lista(nodo*, int)
;============================================================
esta_en_lista:
    xor eax, eax
    mov ecx, [esp + 8]
    mov edx, [esp + 4]
    
    ; @invariante:
    ; eax = encontrado
    ; ecx = valor buscado
    ; edx = dir nodo actual
    
b_loop:
    test edx, edx
    jz b_fin
    
    cmp [edx], ecx
    je b_found
    
    mov edx, [edx + 4]
    jmp b_loop

b_fin:
    ret

b_found:
    mov eax, 1
    ret

;============================================================
; int longitud(nodo*)
;============================================================
longitud:
    xor eax, eax
    mov edx, [esp + 4]
    
l_loop:
    test edx, edx
    jz l_fin
    
    inc eax
    mov edx, [edx + 4]
    jmp l_loop
    
l_fin:
    ret

;============================================================
; int posicion(nodo*, int)
;============================================================
posicion:
    xor eax, eax
    mov ecx, [esp + 8]
    mov edx, [esp + 4]
    
    ; @invariante:
    ; eax = indice
    ; ecx = valor buscado
    ; edx = dir nodo actual
    
p_loop:
    test edx, edx
    jz p_fin
    
    cmp [edx], ecx
    je p_fin
    
    inc eax
    mov edx, [edx + 4]
    jmp p_loop

p_fin:
    ret
    
;============================================================
; void insertar(nodo** p_li, int pos, int n)
;============================================================
insertar:
    push ebp
    mov ebp, esp
    push ebx
    push edi
    
    mov ecx, [ebp + 12]
    mov edi, [ebp + 8]
    
    ; @invariante:
    ; ecx = posicion
    ; edi = nodo** actual

i_iterar:
    jecxz i_poner
    ; es lo mismo que:
    ; test ecx, ecx
    ; jz i_poner
    
    dec ecx
    mov edi, [edi]
    add edi, 4
    jmp i_iterar
    
    ; @invariante
    ; edi = nodo** a_insertar
    
i_poner:
    ; crea un nodo y le pone
    ; el segundo param de valor
    mov ebx, [ebp + 16]
    crear_nodo

    ; guarda en edx el comienzo de la lista
    mov edx, [edi]

    ; @invariante:
    ; eax = dir del nuevo nodo
    ; edi = dir del nodo original

    ; pone en el comienzo el nuevo nodo
    mov [edi], eax

    ; apunta sig del nuevo nodo al comienzo anterior
    mov [eax + 4], edx
    
    pop edi
    pop ebx    
    pop ebp
    ret

;============================================================
; void borrar_elem(nodo** p_li, int pos)
;============================================================
borrar_elem:
    push ebp
    mov ebp, esp
    push ebx
    push edi
    
    mov ecx, [ebp + 12]
    mov ebx, [ebp + 8]
    
    ; @invariante:
    ; ecx = posicion
    ; ebx = nodo** actual

r_iterar:
    jecxz r_borrame
    ; es lo mismo que:
    ; test ecx, ecx
    ; jz r_borrame
    
    dec ecx
    mov ebx, [ebx]
    add ebx, 4
    jmp r_iterar
    
    ; @invariante
    ; ebx = nodo** a_insertar
    
r_borrame:
    mov edx, [ebx]
    lea edi, [edx + 4]
    mov edi, [edi]
    
    push edx
    call free
    add esp, 4
    
    mov [ebx], edi
    
    pop edi
    pop ebx
    pop ebp
    ret

Archivo Makefile:

RM= rm
NASM = nasm

# optimization
#
OPT= -g -ggdb -O2

# flags for ANSI compiles
#
CFLAGS= -pedantic -ansi -Wall ${OPT}

# ANSI compiler
#
GCC= gcc

OBJ=main.o ext.o
OTHEROBJ=
INCS=
MAIN=listas

.PHONY: all win linux

all: 
	@echo Opciones: make [win/linux]

win:
	make NOPT="-fwin32 -DWIN32" ${MAIN}

linux:
	make NOPT=-felf ${MAIN}

${MAIN}: ${OBJ} ${OTHEROBJ} $(INCS)
	${GCC} ${CFLAGS} -o ${MAIN} ${OBJ} ${OTHEROBJ}

%.o: %.asm 
	${NASM} ${NOPT} -g -O1 $< -o [email protected]

%.o: %.c
	${GCC} ${CFLAGS} -c $< -o [email protected] 

clean:
	${RM} -f ${OBJ} ${OTHEROBJ} ${MAIN}

install: all
	${CAT} ${MAIN} > /dev/null

Posible salida:

Agrego '5'...Longitud: 1
Agrego '2'...Longitud: 2
Agrego '1'...Longitud: 3
<lista>
(0804a028) lista[0].dato = 1
(0804a028) lista[0].sig = 0804a018
(0804a018) lista[1].dato = 2
(0804a018) lista[1].sig = 0804a008
(0804a008) lista[2].dato = 5
(0804a008) lista[2].sig = 00000000
</lista>
Esta 2: 1
Esta 7: 0
Esta 1: 1
Esta 5: 1
Posicion 2: 1
Posicion 7: 3
Posicion 1: 0
Posicion 5: 2
<lista>
(0804a058) lista[0].dato = 0
(0804a058) lista[0].sig = 0804a028
(0804a028) lista[1].dato = 1
(0804a028) lista[1].sig = 0804a038
(0804a038) lista[2].dato = 666
(0804a038) lista[2].sig = 0804a018
(0804a018) lista[3].dato = 2
(0804a018) lista[3].sig = 0804a048
(0804a048) lista[4].dato = 777
(0804a048) lista[4].sig = 0804a068
(0804a068) lista[5].dato = -1
(0804a068) lista[5].sig = 0804a008
(0804a008) lista[6].dato = 5
(0804a008) lista[6].sig = 0804a078
(0804a078) lista[7].dato = 9999
(0804a078) lista[7].sig = 00000000
</lista>
Borrando elemento: 7
<lista>
(0804a058) lista[0].dato = 0
(0804a058) lista[0].sig = 0804a028
(0804a028) lista[1].dato = 1
(0804a028) lista[1].sig = 0804a038
(0804a038) lista[2].dato = 666
(0804a038) lista[2].sig = 0804a018
(0804a018) lista[3].dato = 2
(0804a018) lista[3].sig = 0804a048
(0804a048) lista[4].dato = 777
(0804a048) lista[4].sig = 0804a068
(0804a068) lista[5].dato = -1
(0804a068) lista[5].sig = 0804a008
(0804a008) lista[6].dato = 5
(0804a008) lista[6].sig = 00000000
</lista>
Borrando elemento: 4
<lista>
(0804a058) lista[0].dato = 0
(0804a058) lista[0].sig = 0804a028
(0804a028) lista[1].dato = 1
(0804a028) lista[1].sig = 0804a038
(0804a038) lista[2].dato = 666
(0804a038) lista[2].sig = 0804a018
(0804a018) lista[3].dato = 2
(0804a018) lista[3].sig = 0804a068
(0804a068) lista[4].dato = -1
(0804a068) lista[4].sig = 0804a008
(0804a008) lista[5].dato = 5
(0804a008) lista[5].sig = 00000000
</lista>
Borrando elemento: 3
<lista>
(0804a058) lista[0].dato = 0
(0804a058) lista[0].sig = 0804a028
(0804a028) lista[1].dato = 1
(0804a028) lista[1].sig = 0804a038
(0804a038) lista[2].dato = 666
(0804a038) lista[2].sig = 0804a068
(0804a068) lista[3].dato = -1
(0804a068) lista[3].sig = 0804a008
(0804a008) lista[4].dato = 5
(0804a008) lista[4].sig = 00000000
</lista>
Borrando elemento: 0
<lista>
(0804a028) lista[0].dato = 1
(0804a028) lista[0].sig = 0804a038
(0804a038) lista[1].dato = 666
(0804a038) lista[1].sig = 0804a068
(0804a068) lista[2].dato = -1
(0804a068) lista[2].sig = 0804a008
(0804a008) lista[3].dato = 5
(0804a008) lista[3].sig = 00000000
</lista>
Borrando elemento: 1
<lista>
(0804a028) lista[0].dato = 1
(0804a028) lista[0].sig = 0804a068
(0804a068) lista[1].dato = -1
(0804a068) lista[1].sig = 0804a008
(0804a008) lista[2].dato = 5
(0804a008) lista[2].sig = 00000000
</lista>
Borrando elemento: 1
<lista>
(0804a028) lista[0].dato = 1
(0804a028) lista[0].sig = 0804a008
(0804a008) lista[1].dato = 5
(0804a008) lista[1].sig = 00000000
</lista>
Borrando elemento: 0
<lista>
(0804a008) lista[0].dato = 5
(0804a008) lista[0].sig = 00000000
</lista>
Borrando elemento: 0
<lista>
</lista>