--- /dev/null
+
+
+static void b_asc_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2);
+
+int emufs_indice_b_asc_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato)
+{
+ int i, nodo_id, padre_id;
+ B_NodoHeader header;
+ B_NodoEntry *claves;
+ char *nodo, *padre;
+ INDICE_DATO dummy;
+
+ /* Leo la raiz */
+ nodo = b_leer_nodo(idx, 0);
+ padre_id = nodo_id = 0;
+ padre = NULL;
+ while (nodo) {
+ if (padre) free(padre);
+ padre = nodo;
+ padre_id = nodo_id;
+ b_leer_header(nodo, &header);
+ claves = b_leer_claves(nodo, &header);
+ i=0;
+ while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
+ if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, clave))) {
+ if (idx->funcion == IND_PRIMARIO) {
+ PERR("Indice primario no puede contener claves duplicadas!");
+ PERR(idx->nombre);
+ return 0;
+ }
+
+ b_insertar_dup_en_pos(idx, claves[i].dato, dato);
+
+ if (idx->tipo_dato == IDX_STRING) {
+ /* Tengo que sacar el texto repetido del archivo de textos */
+ idx->emu_string->borrar_registro(idx->emu_string, clave, dummy);
+ }
+ return 1;
+ } else {
+ if (i == 0) {
+ nodo = b_leer_nodo(idx, header.hijo_izquierdo);
+ nodo_id = header.hijo_izquierdo;
+ } else {
+ nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
+ nodo_id = claves[i-1].hijo_derecho;
+ }
+ }
+ }
+
+ if (nodo) free(nodo);
+ nodo = padre;
+ nodo_id = padre_id;
+
+ if (idx->funcion != IND_PRIMARIO) {
+ /* Agrego el DATO real al archivo de claves repetiras
+ * y me guardo el ID para poner en el indice
+ */
+ dummy.id = -1;
+ dato.id = b_insertar_dup_en_pos(idx, dummy, dato);
+ }
+
+ b_asc_insertar_en_nodo(idx, clave, dato, nodo_id, nodo, -1, -1);
+ return 1; /* Agregar OK! */
+}
+
+
+static void b_asc_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2)
+{
+ char *padre, *nuevo;
+ int nuevo_id;
+ int i, j;
+ static int rompi=0;
+ char salir = 0;
+ char *izq, *der;
+ B_NodoHeader nodo_header, nuevo_header;
+ B_NodoEntry *claves, *tmp_claves, *claves_nuevo;
+
+ do {
+ if (!nodo) {
+ /* CREAR NODO? */
+ nodo = b_crear_nodo(idx, &nodo_id);
+ }
+ b_leer_header(nodo, &nodo_header);
+ claves = b_leer_claves(nodo, &nodo_header);
+
+ padre = b_leer_nodo(idx, nodo_header.padre);
+
+ if (nodo_header.cant == CANT_HIJOS(idx)) {
+ int total;
+ if (nodo_id != 0) {
+ int izq_id, der_id, pos_padre, i;
+ B_NodoHeader padre_header, header_der, header_izq;
+ B_NodoEntry *padre_claves;
+ B_NodoEntry a_pasar, *buffer;
+
+ b_leer_header(padre, &padre_header);
+ padre_claves = b_leer_claves(padre, &padre_header);
+
+ /* nuevo_entry = new entry(clave, dato, hijo_der) */
+ PERR("Buscando que hijo soy");
+ for(pos_padre=0; (padre_claves[pos_padre].hijo_derecho != nodo_id); pos_padre++) { }
+
+ if (pos_padre == padre_header.cant) {
+ PERR("ERROR GRAVE. Padre no me contiene :-(");
+ }
+
+ /* Busco mis hermanos a derecha e izquierda, si es que existen */
+ PERR("Ya me encontre, busco a mis hermanos");
+ if (pos_padre >= 0) {
+ if (pos_padre == 0)
+ izq_id = padre_header.hijo_izquierdo;
+ else
+ izq_id = padre_claves[pos_padre-1].hijo_derecho;
+ izq = b_leer_nodo(idx, izq_id);
+ b_leer_header(izq, &header_izq);
+ } else {
+ izq_id = -1;
+ }
+ if (pos_padre < padre_header.cant) {
+ der_id = padre_claves[pos_padre+1].hijo_derecho;
+ der = b_leer_nodo(idx, der_id);
+ b_leer_header(der, &header_der);
+ } else {
+ der_id = -1;
+ }
+ PERR("Hermanos encontrados");
+
+ buffer = malloc((nodo_header.cant+1)*sizeof(B_NodoEntry));
+
+ /* Inserto ordenado */
+ for(i=0; (i<nodo_header.cant) && emufs_indice_es_menor(idx, claves[i].clave, clave); i++)
+ buffer[i] = claves[i];
+ buffer[i].clave = clave;
+ buffer[i].dato = dato;
+ buffer[i].hijo_derecho = hijo2;
+ while (i<nodo_header.cant)
+ buffer[i+1] = claves[i];
+
+ if ((der_id != -1) && (header_der.cant < CANT_HIJOS(idx))) {
+ /* tomo la clave mas grande */
+ a_pasar = buffer[nodo_header.cant];
+
+ /* la paso a la derecha */
+ b_pasar_clave_a_derecha(idx, der, der_id, padre, nodo_header.padre, pos_padre, a_pasar);
+ /* XXX TODO Liberar memoria y GUARDAR*/
+ free(buffer);
+
+ return;
+ }
+
+ if ((izq_id != -1) && (header_izq.cant < CANT_HIJOS(idx))) {
+ a_pasar = buffer[0];
+ b_pasar_clave_a_izquierda(idx, izq, izq_id, padre, nodo_header.padre, pos_padre, a_pasar, 0, 0);
+ free(buffer);
+ return;
+ }
+
+ /*
+ if (izq_id != -1)
+ b_partir_dos_nodos_en_tres(idx, hijo_izquierdo, nodo, padre, nuevo_entry)
+ else // Siempre alguno tiene que existir.
+ b_partir_dos_nodos_en_tres(idx, nodo, hijo_derecho, padre, nuevo_entry)
+ return;
+ */
+ }
+
+ /* Bueno, soy la raiz, tengo que tratarla como el arbol B */
+ /* Sigo con a fullllllllll */
+ nuevo = b_crear_nodo(idx, &nuevo_id);
+ i=0;
+ /* Creo una lista ordenada de los nodos a partir */
+ tmp_claves = (B_NodoEntry *)malloc(sizeof(B_NodoEntry)*(nodo_header.cant+1));
+ total = nodo_header.cant+1;
+ while ((i<nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) {
+ tmp_claves[i] = claves[i];
+ i++;
+ }
+ tmp_claves[i].clave = clave;
+ tmp_claves[i].dato = dato;
+ /*tmp_claves[i].hijo_derecho = hijo1;*/
+ if (i==0) {
+ nodo_header.hijo_izquierdo = hijo1;
+ tmp_claves[i].hijo_derecho = hijo2;
+ } else {
+ tmp_claves[i-1].hijo_derecho = hijo1;
+ tmp_claves[i].hijo_derecho = hijo2;
+ }
+ while (i < nodo_header.cant) {
+ tmp_claves[i+1] = claves[i];
+ i++;
+ }
+
+ /* Asigno a cada nodo lo que corresponde */
+ b_leer_header(nuevo, &nuevo_header);
+
+ nuevo_header.nivel = nodo_header.nivel;
+ nodo_header.cant = total/2;
+ nuevo_header.cant = (total-1) - nodo_header.cant;
+
+ memset(claves, '*', idx->tam_bloque-sizeof(B_NodoHeader));
+ for(j=0; j<nodo_header.cant; j++)
+ claves[j] = tmp_claves[j];
+
+ claves_nuevo = b_leer_claves(nuevo, &nuevo_header);
+ memset(claves_nuevo, '*', idx->tam_bloque-sizeof(B_NodoHeader));
+ for(j=0; j<nuevo_header.cant; j++)
+ claves_nuevo[j] = tmp_claves[j+total/2+1];
+
+ b_actualizar_header(nodo, &nodo_header);
+ b_actualizar_header(nuevo, &nuevo_header);
+
+ if (nodo_id != 0) {
+ clave = tmp_claves[total/2].clave;
+ dato = tmp_claves[total/2].dato;
+
+ b_grabar_nodo(idx, nodo_id, nodo);
+ b_grabar_nodo(idx, nuevo_id, nuevo);
+ free(nodo);
+ free(nuevo);
+ free(tmp_claves);
+
+ hijo1 = nodo_id;
+ hijo2 = nuevo_id;
+
+ fprintf(stderr, "Nodos espliteados = %d %d\n", hijo1, hijo2);
+ nodo = padre;
+ nodo_id = nodo_header.padre;
+ } else {
+ /* Oops, parti el raiz, y este debe quedar en 0, lo paso a otro bloque
+ * y dejo el padre vacio
+ */
+ char *tmp_nuevo = b_crear_nodo(idx, &nodo_id);
+ memcpy(tmp_nuevo, nodo, idx->tam_bloque);
+ free(nodo);
+ nodo = tmp_nuevo;
+
+ clave = tmp_claves[total/2].clave;
+ dato = tmp_claves[total/2].dato;
+
+ b_grabar_nodo(idx, nuevo_id+1, nodo);
+ b_grabar_nodo(idx, nuevo_id, nuevo);
+
+ free(nodo);
+ free(nuevo);
+ free(tmp_claves);
+
+ hijo1 = nuevo_id+1;
+ hijo2 = nuevo_id;
+
+ fprintf(stderr, "Nodos espliteados = %d %d\n", hijo1, hijo2);
+ /* Limpio al padre */
+ nuevo = b_leer_nodo(idx, 0);
+
+ b_leer_header(nuevo, &nuevo_header);
+ nuevo_header.cant = 0;
+ nuevo_header.padre = -1;
+ nuevo_header.nivel = nodo_header.nivel+1;
+ nuevo_header.hijo_izquierdo = -1;
+ fprintf(stderr, "root.nivel=%d\n", nuevo_header.nivel);
+ memset(nuevo, -1, idx->tam_bloque);
+ b_actualizar_header(nuevo, &nuevo_header);
+ b_grabar_nodo(idx, 0, nuevo);
+
+ nodo_id = 0;
+ nodo = nuevo;
+ rompi = 1;
+ }
+ } else {
+ /* La clave entra en este nodo!! */
+ b_insertar_en_nodo_con_lugar(idx, clave, dato, nodo_id, nodo, hijo1, hijo2);
+ salir = 1;
+ }
+ } while (!salir);
+}
+
projects / z.facultad / 75.06 / emufs.git / commitdiff