+ b_insertar_en_nodo_con_lugar(idx, clave, dato, nodo_id, nodo, hijo1, hijo2);
+ salir = 1;
+ }
+ } while (!salir);
+}
+
+void b_insertar_en_nodo_con_lugar(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo_izq, int hijo_der)
+{
+ int i = 0;
+ B_NodoHeader nodo_header;
+ B_NodoEntry* claves;
+ b_leer_header(nodo, &nodo_header);
+ claves = b_leer_claves(nodo, &nodo_header);
+ if (nodo_header.cant > 0) {
+ int j;
+ while ((i < nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
+ for(j=nodo_header.cant; j > i; j--)
+ claves[j] = claves[j-1];
+ }
+ nodo_header.cant++;
+ claves[i].clave = clave;
+ claves[i].dato = dato;
+ if (i==0) {
+ nodo_header.hijo_izquierdo = hijo_izq;
+ claves[i].hijo_derecho = hijo_der;
+ } else {
+ claves[i-1].hijo_derecho = hijo_izq;
+ claves[i].hijo_derecho = hijo_der;
+ }
+ /*b_elegir_izquierdo(idx, nodo_header.hijo_izquierdo, hijo1);*/
+
+ b_actualizar_header(nodo, &nodo_header);
+ b_grabar_nodo(idx, nodo_id, nodo);
+
+ /* Debo actualizar los punteros al padre de los hijos */
+ if (hijo_izq != -1) {
+ char* nuevo = b_leer_nodo(idx, hijo_izq);
+ if (nuevo != NULL) {
+ B_NodoHeader nuevo_header;
+ fprintf(stderr, "Actualizo padre de %d a %d\n", hijo_izq, nodo_id);
+ b_leer_header(nuevo, &nuevo_header);
+ nuevo_header.padre = nodo_id;
+ b_actualizar_header(nuevo, &nuevo_header);
+ b_grabar_nodo(idx, hijo_izq, nuevo);
+ free(nuevo);
+ } else printf("FUCK! hijo_izq=%d no existe!\n", hijo_izq);
+ }
+ if (hijo_der != -1) {
+ char* nuevo = b_leer_nodo(idx, hijo_der);
+ if (nuevo != NULL) {
+ B_NodoHeader nuevo_header;
+ fprintf(stderr, "Actualizo padre de %d a %d\n", hijo_der, nodo_id);
+ b_leer_header(nuevo, &nuevo_header);
+ nuevo_header.padre = nodo_id;
+ b_actualizar_header(nuevo, &nuevo_header);
+ b_grabar_nodo(idx, hijo_der, nuevo);
+ free(nuevo);
+ } else printf("FUCK! hijo_der=%d no existe!\n", hijo_der);
+ }
+}
+
+void b_insertar_en_nodo_con_lugar_sin_hijo_izq(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo_der)
+{
+ int i = 0;
+ B_NodoHeader nodo_header;
+ B_NodoEntry* claves;
+ b_leer_header(nodo, &nodo_header);
+ claves = b_leer_claves(nodo, &nodo_header);
+ if (nodo_header.cant > 0) {
+ int j;
+ while ((i < nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
+ for(j=nodo_header.cant; j > i; j--)
+ claves[j] = claves[j-1];
+ }
+ nodo_header.cant++;
+ claves[i].clave = clave;
+ claves[i].dato = dato;
+ claves[i].hijo_derecho = hijo_der;
+
+ b_actualizar_header(nodo, &nodo_header);
+ b_grabar_nodo(idx, nodo_id, nodo);
+
+ /* Debo actualizar el puntero al padre del hijo */
+ if (hijo_der != -1) {
+ char* nuevo = b_leer_nodo(idx, hijo_der);
+ if (nuevo != NULL) {
+ B_NodoHeader nuevo_header;
+ b_leer_header(nuevo, &nuevo_header);
+ nuevo_header.padre = nodo_id;
+ b_actualizar_header(nuevo, &nuevo_header);
+ b_grabar_nodo(idx, hijo_der, nuevo);
+ free(nuevo);
+ } else printf("FUCK! hijo_der=%d no existe!\n", hijo_der);
+ }
+}
+
+INDICE_DATO *emufs_indice_b_buscar_muchos(INDICE *idx, CLAVE clave, int *cant)
+{
+ EMUFS_REG_SIZE tam;
+ int error=0;
+ char *leido;
+ CLAVE k;
+ INDICE_DATO dato, *ret;
+
+ /* Si el indice es primario no tiene sentido hacer nada */
+ if (idx->funcion == IND_PRIMARIO) {
+ *cant = 0;
+ PERR("INDICE PRIMARIO NO SOPORTA BUSQUEDA MULTIPLE");
+ return NULL;
+ }
+
+ /* Busco la clave en el arbol */
+ dato = emufs_indice_b_buscar(idx, clave);
+
+ if (dato.id == -1) {
+ PERR("CLAvE NO ENCONTRADA EN EL ARBOL!");
+ }
+
+ /* Leo el contenido actual */
+ k.i_clave = dato.id;
+ error = 0;
+ leido = (char *)idx->emu_mult->leer_registro(idx->emu_mult, k, &tam, &error);
+
+ /* Incremento en 1 la cantidad */
+ if (leido != NULL)
+ (*cant) = *((int *)leido);
+ else
+ (*cant) = 0;
+
+ ret = malloc(sizeof(INDICE_DATO)*(*cant));
+ memcpy(ret, leido+sizeof(int), (*cant)*sizeof(INDICE_DATO));
+ free(leido);
+ return ret;
+}
+
+static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k)
+{
+ int pos, actual_id, padre_id, i, pos_padre, izquierda_id, derecha_id, p;
+ B_NodoHeader header, header_actual, header_padre, header_izq, header_der;
+ B_NodoEntry *claves, *claves_actual, *claves_padre;/*, *claves_izq, *claves_der;*/
+ char *actual, *padre, *izq, *der;
+
+ PERR("Borrando clave");
+ b_leer_header(nodo, &header);
+ claves = b_leer_claves(nodo, &header);
+
+ pos = 0;
+ /* Busco la posicion dentro de la lista de claves */
+ PERR("Buscando lugar donde se encuentra la clave");
+ while (emufs_indice_es_menor(idx, claves[pos].clave, k)) pos++;
+
+ /* Es el nodo una hoja? */
+ fprintf(stderr, "La clave esta en la pos = %d\n", pos);
+ if (header.hijo_izquierdo != -1) {
+ PERR("Nodo no es hoja, intercambio");
+/* if (pos == 0) {
+ actual = b_leer_nodo(idx, nodo_header.hijo_izquierdo);
+ else*/
+ actual = b_leer_nodo(idx, claves[pos].hijo_derecho);
+ actual_id = claves[pos].hijo_derecho;
+ p = claves[pos].hijo_derecho;
+
+ b_leer_header(actual, &header_actual);
+ while (header_actual.hijo_izquierdo != -1) {
+ actual_id = header_actual.hijo_izquierdo;
+ free(actual);
+ actual = b_leer_nodo(idx, actual_id);
+ b_leer_header(actual, &header_actual);
+ }
+ claves_actual = b_leer_claves(actual, &header_actual);
+
+ claves[pos] = claves_actual[0];
+ claves[pos].hijo_derecho = p;
+ pos = 0;
+ b_grabar_nodo(idx, nodo_id, nodo);
+ PERR("Listo");
+ } else {
+ PERR("Nodo es hoja");
+ actual = nodo;
+ header_actual = header;
+ claves_actual = claves;
+ actual_id = nodo_id;
+ }
+
+ /* Borro la clave */
+ PERR("Borrando clave");
+ for(i=pos; i < header_actual.cant-1; i++) {
+ claves_actual[i] = claves_actual[i+1];
+ }
+ PERR("Borrado completo");
+ header_actual.cant--;
+ /* Guardo los cambios */
+ b_actualizar_header(actual, &header_actual);
+ b_grabar_nodo(idx, actual_id, actual);
+
+ /* Se cumple la condicion de hijos? */
+ PERR("Dejo todo consistente");
+ fprintf(stderr, "Condicion : %d >= %d\n", header_actual.cant, MIN_HIJOS(idx));
+ if (header_actual.cant >= MIN_HIJOS(idx)) {
+ PERR("Borrar completo sin fundir");
+ return;
+ }
+
+ PERR("Node queda con menos hijos de los posibles!");
+ /* Tengo que pasar datos o fundir nodos :-( */
+ do {
+ padre_id = header.padre;
+ padre = b_leer_nodo(idx, padre_id);
+ b_leer_header(padre, &header_padre);
+ claves_padre = b_leer_claves(padre, &header_padre);
+ fprintf(stderr, "ID del padre = %d de nivel %d\n", padre_id, header_padre.nivel);
+ /* TODO Tengo el hijo_izquierdo para revisar!! XXX */
+ if (header_padre.hijo_izquierdo == actual_id) {
+ PERR("Soy el hijo izquierdo de padre");
+ izquierda_id = -1; /* No tengo hermano izquierdo */
+ /* Mi hermano derecho es el primer nodo del padre */
+ derecha_id = claves_padre[0].hijo_derecho;
+ der = b_leer_nodo(idx, derecha_id);
+ b_leer_header(der, &header_der);
+ } else {
+ PERR("Buscando que hijo soy");
+ for(pos_padre=0; (claves_padre[pos_padre].hijo_derecho != actual_id); pos_padre++) { }
+
+ if (pos_padre == header_padre.cant) {
+ PERR("ERROR GRAVE. Padre no me contiene :-(");
projects / z.facultad / 75.06 / emufs.git / blobdiff