; offsets y size del struct nodo_t
; los offsets son relativos al comienzo del nodo
%define sizeof_nodo 18
%define off_id 0
%define off_nom 2
%define off_puntaje 6
%define off_izq 10
%define off_der 14
global insertar, eliminar, destruirArbol, imprimir
extern malloc, free, fopen, fprintf, fclose
section .rodata
append_mode: db 'a', 0
fprintf_format: db '[ %d %f %s ]', 0
fprintf_newline: db 10, 0
section .text
insertar:
push ebp
mov ebp, esp
push edi
push esi
push ebx
; alocamos memoria para un nodo
; XXX: lo hacemos antes de copiar cosas a los registros porque, por la
; convencion C, solo protege edi, esi y ebx
mov esi, sizeof_nodo
push esi
call malloc
add esp, 4
; si malloc devuelve 0, no tenemos nada para hacer
cmp eax, 0
je .fin
; dejamos el nuevo nodo en esi
mov esi, eax
mov ebx, [ebp + 8] ; nodo **arbol, 4bytes
%define .arbol [ebx] ; nodo *arbol, 4bytes
%define .nom [ebp + 12] ; char *nombre, 4bytes
mov dx, [ebp + 16] ; short id, 2 bytes
%define .id dx
mov edi, [ebp + 20] ; float puntaje, 4bytes
%define .punt edi
%define .nId [esi + off_id]
%define .nNom [esi + off_nom]
%define .nPuntaje [esi + off_puntaje]
%define .nIzq [esi + off_izq]
%define .nDer [esi + off_der]
; Asignamos los parametros al nodo creado
mov .nId, .id
mov .nPuntaje, .punt
mov dword .nIzq, 0
mov dword .nDer, 0
; Y copiamos el contenido del string en .nom
; XXX: el unico registro que usamos y no protege la convencion C es dx,
; pero ya lo asignamos (el id), asique no nos importa
push dword .nom
call strdup2
add esp, 4
; si fallamos al allocar memoria para el strdup, no tenemos mucho mas
; para hacer: borramos la memoria allocada para el nodo y salimos
; XXX: asignamos eax a .nNom antes de checkar porque, en caso que eax
; sea cero, nos queda NULL en .nNom y el free que se llama despues al
; borrar la memoria del nodo no deberia ser problema (free de NULL va ok)
mov .nNom, eax
cmp eax, 0
je .borrarme
; Si es el arbol vacio (apunta a NULL), entonces devolvemos el arbol que tiene solo este nodo
; Si no es el arbol vacio, insertamos el nodo
cmp dword .arbol, 0
jne .insertar
mov [ebx], esi
jmp .fin
.insertar:
push esi ; el nodo que creamos, 2º param
push ebx ; nodo **arbol, 1º param
call buscar_e_insertar
add esp, 8
jmp .fin
.borrarme:
push esi; el nodo que creamos
call borrar_nodo
add esp, 4
jmp .fin
.fin:
pop ebx
pop esi
pop edi
pop ebp
ret
; char *strdup(char *s)
strdup2:
push ebp
mov ebp, esp
push edi
push esi
push ebx
mov ebx, [ebp + 8]
; me fijo el tamaño del string
mov edi, 1
mov esi, ebx
.loop:
cmp byte [esi], 0
je .gotLargo
inc edi
inc esi
jmp .loop
; ya se el largo(edi), hago un malloc
.gotLargo:
push edi ; largo del string/cantidad de bytes
call malloc
add esp, 4
cmp eax, 0
je .fin
; ecx: longitud del string (con el \0 final)
; ebx: src
; esi: dst
mov ecx, edi
mov esi, eax
.copy:
cmp ecx, 0
je .fin
mov dl, [ebx]
mov byte [esi], dl
inc esi
inc ebx
dec ecx
jmp .copy
.fin:
; en eax ya quedo el char* que creamos
pop ebx
pop esi
pop edi
pop ebp
ret
; void buscar_e_insertar(nodo **arbol, nodo *n);
; asume que *arbol != NULL
buscar_e_insertar:
push ebp
mov ebp, esp
push edi
push esi
push ebx
mov ebx, [ebp + 8] ; nodo **arbol; 4 bytes
mov ebx, [ebx] ; nodo *arbol
mov edi, [ebp + 12]; nodo* n; 4bytes
; ponemos el id en ax
mov ax, [edi + off_id]
; invariante: en ebx guardamos el puntero a nodo que vamos iterando
; y en ecx el puntero al nodo padre del nodo actual
mov ecx, 0
.loop:
cmp dword ebx, 0
je .insertar
mov ecx, ebx
; comparamos el id del nodo a insertar con el id del actual
cmp word ax, [ebx + off_id]
; XXX: por que no andan como quiero los conditional moves ?
;cmovl ebx, [ebx + off_izq]
;cmovge ebx, [ebx + off_der]
jle .loopIz
mov ebx, [ebx + off_der]
jmp .loop
.loopIz:
mov ebx, [ebx + off_izq]
jmp .loop
.insertar:
; nos fijamos si tenemos que insertar en el subarbol izquierdo o en el subarbol derecho
; usamos ecx porque siempre salimos con ebx en NULL
cmp ax, [ecx + off_id]
jle .insertarIz
mov [ecx + off_der], edi
jmp .fin
.insertarIz:
mov [ecx + off_izq], edi
jmp .fin
.fin:
pop ebx
pop esi
pop edi
pop ebp
ret
; void eliminar(nodo **arbol, short id);
eliminar:
push ebp
mov ebp, esp
push edi
push esi
push ebx
mov ebx, [ebp + 8] ; nodo **arbol, 4bytes
%define .raiz [ebx] ; nodo *arbol, 4bytes
mov cx, [ebp + 12] ; short id, 2 bytes
%define .id cx
; si es el arbol vacio, seguro no hay nada para eliminar
cmp dword .raiz, 0
je .fin
; pusheo los registros usados que no se protegen por la C calling convention
; XX: si bien uso cx, pusheo ecx porque sino el push pushea solo dos
; bytes y desalinea la pila
push ecx
; pusheo los parametros
push ecx
push dword .raiz
call buscar_por_id
add esp, 8
; como pushe ecx (por el tema de la alineacion) pop ecx. Pero solo me
; interesa lo de cx
pop ecx
; En eax queda el puntero al nodo si existe, 0 si no existe
; Si no esta el nodo, no tenemos nada para eliminar
cmp eax, 0
je .fin
; Entonces el nodo esta. Veamos que caso de eliminacion es, segun la cantidad de hijos
; guardamos el puntero al nodo a eliminar en esi y el padre en edi
mov esi, eax
mov edi, edx
%define .nIzq [esi + off_izq]
%define .nDer [esi + off_der]
; Me fijo si tiene 0 hijos
mov edx, .nIzq
or edx, .nDer
cmp edx, 0
je .eliminar0
; Me fijo si tiene 1 hijo (alguno de los dos es 0)
mov eax, .nIzq
mul dword .nDer
or edx, eax
cmp edx, 0
je .eliminar1
; Tiene 2 hijos
jmp .eliminar2
.eliminar0:
push edi ; nodo *padre, 3º param
push esi ; nodo *nodo, 2º param
push ebx ; nodo **raiz; 1º param
call eliminar_0_hijos
add esp, 12
jmp .fin
.eliminar1:
push edi ; nodo *padre, 3º param
push esi ; nodo *nodo, 2º param
push ebx ; nodo **raiz; 1º param
call eliminar_1_hijo
add esp, 12
jmp .fin
.eliminar2:
push dword .nDer ; subarbol derecho del nodo a borrar
call buscar_min
add esp, 4
; copiarme el id y puntaje a registros
mov cx, [eax + off_id]
mov edi, [eax + off_puntaje]
; swapear los punteros de char* nombre, pues quiero quedarme con el
; nombre
push ebx
mov edx, [eax + off_nom] ; char* del min del subarbol derecho
mov ebx, [esi + off_nom] ; char* del nodo que pidieron borrar al llamar la funcion
mov [eax + off_nom], ebx
mov [esi + off_nom], edx
pop ebx
; protegemos los registros que estamos usando
push ecx
; nos llamamos recursivamente con el *minimo* del subarbol *derecho*
push ecx ; id
push ebx ; nodo **arbol
call eliminar
add esp, 8
; ponemos en esi el puntaje y id que guardamos en registros/stack
pop ecx
mov [esi + off_id], cx
mov [esi + off_puntaje], edi
jmp .fin
.fin:
pop ebx
pop esi
pop edi
pop ebp
ret
; "nodo *buscar_por_id(nodo *arbol, short id);"
; en eax devuelve el puntero al nodo buscado
; en edx devuelve el puntero al padre
buscar_por_id:
push ebp
mov ebp, esp
push edi
push esi
push ebx
mov eax, [ebp + 8] ; nodo *arbol, 4bytes
%define .nId [eax + off_id]
%define .nIzq [eax + off_izq]
%define .nDer [eax + off_der]
mov cx, [ebp + 12] ; short id, 2 bytes
%define .id, cx
; la raiz no tiene padre
mov edx, 0
.loop:
cmp eax, 0
je .fin
; comparo el id a buscar con el id del nodo
cmp cx, .nId
je .fin
; guardo en edx el padre del nodo al que voy a ir (es decir, el actual)
mov edx, eax
; el que busco es menor que el id del nodo, sigo por el subarbol izq
jl .loopIzq
; el que busco es mayor, sigo por el subarbol der
jmp .loopDer
.loopIzq:
mov eax, .nIzq
jmp .loop
.loopDer:
mov eax, .nDer
jmp .loop
.fin:
pop ebx
pop esi
pop edi
pop ebp
ret
; void borrar_nodo(nodo *n);
borrar_nodo:
push ebp
mov ebp, esp
push edi
push esi
push ebx
mov ebx, [ebp + 8]
mov esi, [ebx + off_nom]
push esi
call free
add esp, 4
push ebx
call free
add esp, 4
pop ebx
pop esi
pop edi
pop ebp
ret
; void eliminar_0_hijos(nodo **raiz, nodo *nodo, nodo *padre);
; elimina el nodo nodo (asumiendo que no tiene ningun hijo)
eliminar_0_hijos:
push ebp
mov ebp, esp
push edi
push esi
push ebx
mov eax, [ebp + 8] ; nodo **raiz
mov ebx, [ebp + 12] ; nodo *nodo, 4bytes
mov esi, [ebp + 16] ; nodo *padre, 4bytes
%define .pIzq [esi + off_izq]
%define .pDer [esi + off_der]
; si no tengo padre, yo soy la raiz. Debo borrarme
cmp esi, 0
je .borrarRaiz
; Si tengo padre, tengo que fijarme si era hijo izquiero o derecho, y
; ponerlo en NULL
; TODO: usar los cmov
cmp .pIzq, ebx
je .borrarIzq
mov dword .pDer, 0
jmp .fin
.borrarIzq:
mov dword .pIzq, 0
jmp .fin
.borrarRaiz:
; Borrar la raiz es hacer que *raiz = NULL y borrarme. Es solo eso pues
; no tengo ningun hijo
mov dword [eax], 0x0
jmp .fin
.fin:
push ebx
call borrar_nodo
add esp, 4
pop ebx
pop esi
pop edi
pop ebp
ret
; void eliminar_1_hijo(nodo **raiz, nodo *nodo, nodo *padre);
; Elimina nodo asumiendo que tiene un solo hijo. Si padre == NULL entonces el
; nodo a borrar es la raiz
eliminar_1_hijo:
push ebp
mov ebp, esp
push edi
push esi
push ebx
mov eax, [ebp + 8] ; nodo **raiz
mov ebx, [ebp + 12] ; nodo *nodo, 4bytes
%define .nIzq [ebx + off_izq]
%define .nDer [ebx + off_der]
mov esi, [ebp + 16] ; nodo *padre, 4bytes
%define .pIzq [esi + off_izq]
%define .pDer [esi + off_der]
; si no tengo padre, yo soy la raiz. Debo borrarme
cmp esi, 0
je .borrarRaiz
; si tengo padre, le dejo a cargo mi hijo
; dejo en ecx mi unico hijo
; como tengo un solo hijo, seguro que UNO (y solo uno) de .nIzq y .nDer es 0
; entonces queda el puntero que quiero en ecx
mov ecx, .nIzq
add ecx, .nDer
; me fijo si soy hijo derecho o izquierdo de mi padre, para borrarme y
; dejar a ecx en mi lugar
; me comparo con el hijo izquierdo (es lo mismo con cual, sino soy uno soy el otro)
cmp ebx, .pIzq
je .reemplazarHijoIzq
jmp .reemplazarHijoDer
.reemplazarHijoIzq:
mov .pIzq, ecx
jmp .fin
.reemplazarHijoDer:
mov .pDer, ecx
jmp .fin
.borrarRaiz:
; Tengo que eliminar la raiz, y esta tiene un hijo. Asique el hijo va a
; ser la raiz ahora
; pongo mi hijo (izq o derecho, el que sea) como raiz
mov ecx, .nIzq
add ecx, .nDer
mov [eax], ecx
; hago el free y termino
jmp .fin
.fin:
push ebx
call borrar_nodo
add esp, 4
pop ebx
pop esi
pop edi
pop ebp
ret
; nodo *buscar_min(nodo *arbol)
buscar_min:
push ebp
mov ebp, esp
push edi
push esi
push ebx
mov eax, [ebp + 8]; nodo *arbol
%define .nIzq [eax + off_izq]
; el minimo es el nodo de mas a la izquierda
.loop:
cmp dword .nIzq, 0
je .fin
mov eax, .nIzq
jmp .loop
.fin:
pop ebx
pop esi
pop edi
pop ebp
ret
; void destruirArbol(nodo * arbol);
destruirArbol:
push ebp
mov ebp, esp
push edi
push esi
push ebx
mov ebx, [ebp + 8]
%define .nIzq [ebx + off_izq]
%define .nDer [ebx + off_der]
cmp ebx, 0
je .fin
push dword .nIzq
call destruirArbol
add esp, 4
push dword .nDer
call destruirArbol
add esp, 4
push ebx
call borrar_nodo
add esp, 4
.fin:
pop ebx
pop esi
pop edi
pop ebp
ret
; void imprimir(nodo *arbol, char *archivo);
imprimir:
push ebp
mov ebp, esp
push edi
push esi
push ebx
push dword append_mode; char*, modo append, 2º param
; XXX: esto es "memoria a memoria" y anda. Por que ?
push dword [ebp + 12] ; char* path, 1º param
call fopen
add esp, 8
; si devuelve error (NULL), salimos
cmp eax, 0
je .fin
; guardo el FILE* en ebx
mov ebx, eax
push ebx; FILE*, 2º param
push dword [ebp + 8] ; nodo*, 1º param
call imprimirArbol
add esp, 8
; pongo un '\n' al final
push dword fprintf_newline
push ebx
call fprintf
add esp, 8
cmp eax, 0
jl .fin
; cerramos el FILE*
push ebx
call fclose
add esp, 4
; si devolvio error(!=0) salimos
cmp eax, 0
jne .fin
.fin:
pop ebx
pop esi
pop edi
pop ebp
ret
; void imprimir(nodo *arbol, FILE *archivo);
imprimirArbol:
push ebp
mov ebp, esp
push edi
push esi
push ebx
mov edi, [ebp + 8]; nodo* arbol
%define .nId [edi + off_id]
%define .nNom [edi + off_nom]
%define .nPun [edi + off_puntaje]
%define .nIzq [edi + off_izq]
%define .nDer [edi + off_der]
mov ebx, [ebp + 12]; file* archivo
; el nodo vacio no se imprime
; TODO: checkear como se debe imprimir el arbol vacio
cmp edi, 0
je .fin
; imprimir inorder es: imprimir el subarbol izquierdo, el nodo actual y
; luego el subarbol derecho
; Imprimo el subarbol izquierdo
push ebx ; FILE*, 2º param
push dword .nIzq ; nodo*, 1º param
call imprimirArbol
add esp, 8
; Me imprimo yo
; char* nombre, 5º param
push dword .nNom
; pongo el float, 4º param
; ocupa 8 bytes en el stack
fld dword .nPun
sub esp, 8
fstp qword [esp]
; pongo el id, 3º param
mov ax, .nId
; le pongo bien el signo
shl eax, 16
sar eax, 16
push eax
; formato, 2º param
push dword fprintf_format
; FILE*, 1º param
push ebx
call fprintf
; 8(float) + 4 * 4 (el resto) = 24
add esp, 24
; si devolvio error salimos
cmp eax, 0
jl .fin
; Imprimo el subarbol derecho
push ebx ; FILE*, 2º param
push dword .nDer ; nodo*, 1º param
call imprimirArbol
add esp, 8
.fin:
pop ebx
pop esi
pop edi
pop ebp
ret