git » orga2-tp1.git » commit 2cc92ee

Implementar 2 casos de eliminar

author Rodrigo Campos
2011-04-09 22:41:33 UTC
committer Rodrigo Campos
2011-04-09 23:32:23 UTC
parent 9eb0992884b3437ba8c7397e068aa69248a82513
Implementar 2 casos de eliminar

Solo implementamos el caso de eliminar un nodo sin hijos o con 1 solo
hijo. Pero NO implementamos el de eliminar un nodo con dos hijos todavia
(es e mas tricky, pero se reduce a uno de los ya implementados)
bintree.asm +274 -1
test.c +38 -13 
diff --git a/bintree.asm b/bintree.asm
index 6cafbf9..d229a99 100644
--- a/bintree.asm
+++ b/bintree.asm
@@ -8,7 +8,7 @@
 %define off_izq 10
 %define off_der 14
 
-extern malloc
+extern malloc, free
 
 section .data
 msg: db 'hola', 0
@@ -153,11 +153,284 @@ buscar_e_insertar:
 	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 nos quedamos con el puntero al nodo si existe, 0 si no existe
+	; Si no esta el nodo, no tenemos nada para hacer tampoco
+	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
+	add edx, .nDer
+	cmp edx, 0
+	je .eliminar0
+
+	; Me fijo si tiene 1 hijo
+	mov eax, .nIzq
+	mul dword .nDer
+	cmp edx, 0
+	je .eliminar1
+
+	; Tiene 2 hijos
+
+
+
+	jmp .fin
+
+.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
+
 .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 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 free
+	add esp, 4
+
+	pop ebx
+	pop esi
+	pop edi
+	pop ebp
+	ret
+
+; void eliminar_1_hijo(nodo **raiz, nodo *nodo, nodo *padre);
+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
+
+
+	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 ; XXX: este add funciona siempre bien, no ?
+	mov [eax], ecx
+
+	; hago el free y termino
+	jmp .fin
+
+.fin:
+	push ebx
+	call free
+	add esp, 4
+
+	pop ebx
+	pop esi
+	pop edi
+	pop ebp
+	ret
+
+destruirArbol:
+	push ebp
+	mov ebp, esp
+	push edi
+	push esi
+	push ebx
+
+
+	pop ebx
+	pop esi
+	pop edi
+	pop ebp
+	ret
+
+imprimir:
+	push ebp
+	mov ebp, esp
+	push edi
+	push esi
+	push ebx
+
+
+	pop ebx
+	pop esi
+	pop edi
+	pop ebp
+	ret
diff --git a/test.c b/test.c
index 6b14d87..037a400 100644
--- a/test.c
+++ b/test.c
@@ -8,19 +8,44 @@ void test_write2(nodo *n);
 int main()
 {
 
-	printf("el tamaño del nodo es: %d\n", sizeof(nodo));
-	nodo *n2 = NULL;
-	insertar(&n2, "rata capo", 33, 7.5);
-	//nodo n3 = { 34, "nodo 3", 5, NULL, NULL };
-	insertar(&n2, "nodo2", 32, 7.5);
-	insertar(&n2, "nodo3", 31, 7.5);
-	//buscar_e_insertar(&n2, &n3);
-	printf("nodo.id es: %d\n", n2->id);
-	printf("nodo.puntaje es: %f\n", n2->puntaje);
-	printf("nodo.nombre es: %s\n", n2->nombre);
-	//printf("nodo2.nombre es: %s\n", n2->der->nombre);
-	printf("nodo2.nombre es: %s\n", n2->izq->nombre);
-	printf("nodo3.nombre es: %s\n", n2->izq->izq->nombre);
+//	printf("el tamaño del nodo es: %d\n", sizeof(nodo));
+//	nodo *n2 = NULL;
+//	insertar(&n2, "rata capo", 33, 7.5);
+//	//nodo n3 = { 34, "nodo 3", 5, NULL, NULL };
+//	insertar(&n2, "nodo2", 32, 7.5);
+//	insertar(&n2, "nodo3", 31, 7.5);
+//
+//	//buscar_e_insertar(&n2, &n3);
+//	printf("nodo.id es: %d\n", n2->id);
+//	printf("nodo.puntaje es: %f\n", n2->puntaje);
+//	printf("nodo.nombre es: %s\n", n2->nombre);
+//	//printf("nodo2.nombre es: %s\n", n2->der->nombre);
+//	printf("nodo2.nombre es: %s\n", n2->izq->nombre);
+//	printf("nodo3.nombre es: %s\n", n2->izq->izq->nombre);
+
+
+	nodo *e = NULL;
+	insertar(&e, "nodoe", 32, 7.5);
+	insertar(&e, "nodoe", 30, 7.5);
+
+	if (e->izq->izq == NULL)
+		printf("hijo iz es NULL\n");
+	else
+		printf("hijo iz es NO es NULL\n");
+
+	insertar(&e, "nodoe", 31, 7.5);
+
+	if (e->izq->izq == NULL)
+		printf("hijo iz es NULL\n");
+	else
+		printf("hijo iz es NO es NULL\n");
+
+	printf("31 == %d\n", e->izq->der->id);
+
+	printf("Hola puto\n");
+	eliminar(&e, 30);
+	eliminar(&e, 31);
+	eliminar(&e, 32);
 
 	return 0;
 }