emufs/indice_b.c

   1
   2 #include "indice_b.h"
   3 #include "common.h"
   4 #include "emufs.h"
   5 #include "form.h"
   6
   7 /* Cantidad de claves por nodo */
   8 #define CANT_HIJOS(x) ((x->tam_bloque-sizeof(B_NodoHeader))/sizeof(B_NodoEntry))
   9 #define CANT_NODOS(x) (CANT_HIJOS(x)+1)
  10 #define MIN_HIJOS(x) (CANT_HIJOS(x)/2)
  11
  12 /* Auxiliares */
  13 /** Graba el nodo en el archivo */
  14 static void b_grabar_nodo(INDICE *idx, int id, char *data);
  15 /** Da el ID del proximo nodo a poder ser utilizado */
  16 static int b_ultimo_id(INDICE *idx);
  17 /** Crea un nodo en el archivo y lo retorna. En i se pone el ID asignado */
  18 static char *b_crear_nodo(INDICE *idx, int *i);
  19 /** Actualiza el header de un nodo desde header */
  20 static void b_actualizar_header(char *src, B_NodoHeader *header);
  21 /** Inserta una clave en el nodo de manera iterativa.
  22  * \param idx Índice en donde insertar la clave.
  23  * \param clave Clave a insertar.
  24  * \param dato Dato a insertar
  25  * \param nodo_id Id del nodo en el cual insertar la nueva clave.
  26  * \param nodo FIXME Nodo en donde insertar??? No entiendo por que char*.
  27  * \param hijo1 Id del nodo hijo de la izquierda del insertado.
  28  * \param hijo2 Id del nodo hijo de la derecha del insertado.
  29  */
  30 static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo_izq, int hijo_der);
  31 /** Inserta en un nodo en el que se sabe positivamente que hay lugar. */
  32 static 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);
  33 /** Borra una clave del arbol */
  34 static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k);
  35 /** Le pide al hermano derecho del nodo una clave cuando se eliminan claves */
  36 static void b_pedir_clave_derecha(char *, int, char *, int, char *, int, int);
  37 /** Le pide al hermano izquierdo una clave cuando se eliminan claves */
  38 static void b_pedir_clave_izquierda(char *, int, char *, int, char *, int, int);
  39 /** Le pasa al hermano derecho del nodo una clave cuando se insertan claves */
  40 static void b_pasar_clave_a_derecha(INDICE*, char*, int, char*, int, int, B_NodoEntry);
  41 /** Le pasa al hermano izquierdo una clave cuando se insertan claves */
  42 static void b_pasar_clave_a_izquierda(INDICE*, char*, int, char*, int, int, B_NodoEntry, int, int);
  43 /** Junta 2 nodos y hace uno solo */
  44 static void b_fundir_nodo(INDICE *,char *, int, char *, int, char *, int, int);
  45 /** Crea 3 nodos a partir de 2 llenos */
  46 static void b_partir_dos_nodos_en_tres(INDICE* idx, int nodo_izq, int nodo_der, B_NodoEntry padre_entry, B_NodoEntry nuevo_entry, int id_padre);
  47
  48 static EMUFS_REG_ID b_insertar_dup_en_pos(INDICE *idx, INDICE_DATO pos, INDICE_DATO nuevo);
  49
  50 static void abreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header);
  51 static void desabreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header);
  52 int b_borrar_dup_clave(INDICE *idx, INDICE_DATO k, INDICE_DATO dato);
  53
  54 void emufs_indice_b_crear(INDICE *idx)
  55 {
  56         FILE *fp;
  57         char *bloque;
  58         B_NodoHeader header;
  59
  60         header.cant = 0;
  61         header.nivel = 0;
  62         header.padre = -1;
  63         header.hijo_izquierdo = -1;
  64
  65         fp = fopen(idx->filename, "w");
  66         if (fp == NULL) {
  67                 PERR("Error al crear el archivo");
  68                 return;
  69         }
  70
  71         /* Creo el archivo con el Nodo raiz */
  72         bloque = (char *)malloc(idx->tam_bloque);
  73         memset(bloque, -1, idx->tam_bloque);
  74
  75         memcpy(bloque, &header, sizeof(B_NodoHeader));
  76
  77         fwrite(bloque, idx->tam_bloque, 1, fp);
  78         free(bloque);
  79         fclose(fp);
  80 }
  81
  82 int emufs_indice_b_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato)
  83 {
  84         int i, nodo_id, padre_id;
  85         B_NodoHeader header;
  86         B_NodoEntry *claves;
  87         char *nodo, *padre;
  88         INDICE_DATO dummy;
  89
  90         /* Leo la raiz */
  91         nodo = b_leer_nodo(idx, 0);
  92         padre_id = nodo_id = 0;
  93         padre = NULL;
  94         while (nodo) {
  95                 if (padre) free(padre);
  96                 padre = nodo;
  97                 padre_id = nodo_id;
  98                 b_leer_header(nodo, &header);
  99                 claves = b_leer_claves(nodo, &header);
 100                 i=0;
 101                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
 102                 if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, clave))) {
 103                         if (idx->funcion == IND_PRIMARIO) {
 104                                 PERR("Indice primario no puede contener claves duplicadas!");
 105                                 PERR(idx->nombre);
 106                                 return 0;
 107                         }
 108
 109                         if ((idx->funcion == IND_SELECCION) && (!emufs_indice_es_clave_nula(idx, clave)))
 110                                 b_insertar_dup_en_pos(idx, claves[i].dato, dato);
 111
 112                         if (idx->tipo_dato == IDX_STRING) {
 113                                 /* Tengo que sacar el texto repetido del archivo de textos */
 114                                 idx->emu_string->borrar_registro(idx->emu_string, clave, dummy);
 115                         }
 116                         return 1;
 117                 } else {
 118                         if (i == 0) {
 119                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
 120                                 nodo_id = header.hijo_izquierdo;
 121                         } else {
 122                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
 123                                 nodo_id = claves[i-1].hijo_derecho;
 124                         }
 125                 }
 126         }
 127
 128         if (nodo) free(nodo);
 129         nodo = padre;
 130         nodo_id = padre_id;
 131
 132         if (idx->funcion != IND_PRIMARIO) {
 133                 /* Agrego el DATO real al archivo de claves repetiras
 134                  * y me guardo el ID para poner en el indice
 135                  */
 136                 if ((idx->funcion == IND_SELECCION) && (emufs_indice_es_clave_nula(idx, clave)))
 137                         /* UPS!, la clave que se va a insertar por primera vez es nula
 138                          * y soy un indice selectivo!, no lo puedo permitir, ciao!!
 139                          */
 140                         return 1;
 141                 dummy.id = -1;
 142                 dato.id = b_insertar_dup_en_pos(idx, dummy, dato);
 143         }
 144
 145         b_insertar_en_nodo(idx, clave, dato, nodo_id, nodo, -1, -1);
 146         return 1; /* Agregar OK! */
 147 }
 148
 149 INDICE_DATO emufs_indice_b_buscar(INDICE *idx, CLAVE clave)
 150 {
 151         int i;
 152         INDICE_DATO ret;
 153         B_NodoHeader header;
 154         B_NodoEntry *claves;
 155         char *nodo, *tmp;
 156         int nodo_id;
 157
 158         /* Leo la raiz */
 159         nodo = b_leer_nodo(idx, 0);
 160         nodo_id = 0;
 161         while (nodo) {
 162                 b_leer_header(nodo, &header);
 163                 claves = b_leer_claves(nodo, &header);
 164                 i=0;
 165                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
 166                 if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, clave))) {
 167                                 ret = claves[i].dato;
 168                                 b_grabar_nodo(idx, nodo_id, nodo);
 169                                 free(nodo);
 170                                 return ret;
 171                 } else {
 172                         tmp = nodo;
 173                         b_grabar_nodo(idx, nodo_id, nodo);
 174                         if (i == 0) {
 175                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
 176                                 nodo_id = header.hijo_izquierdo;
 177                         } else {
 178                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
 179                                 nodo_id = claves[i-1].hijo_derecho;
 180                         }
 181                         free(tmp);
 182                 }
 183         }
 184
 185         /* Nodo no encontrado */
 186         ret.id = ret.bloque = -1;
 187         return ret;
 188 }
 189
 190 int emufs_indice_b_borrar(INDICE *idx, CLAVE k, INDICE_DATO dato)
 191 {
 192         /* Busco el nodo que contiene la clave,si es que esta existe */
 193         char *nodo;
 194         int nodo_id, i;
 195         char encontrado=0;
 196         B_NodoHeader header;
 197         B_NodoEntry *claves;
 198
 199         nodo_id = 0; /* Tomo la raiz */
 200         nodo = b_leer_nodo(idx, nodo_id);
 201         while (nodo && !encontrado) {
 202                 /* Obtengo los datos del nodo */
 203                 b_leer_header(nodo, &header);
 204                 claves = b_leer_claves(nodo, &header);
 205
 206                 i=0;
 207                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) i++;
 208
 209                 if ((emufs_indice_es_igual(idx, claves[i].clave, k)) && (i<header.cant))
 210                         encontrado = 1;
 211                 else {
 212                         if (i==0) {
 213                                 free(nodo);
 214                                 nodo_id = header.hijo_izquierdo;
 215                                 nodo = b_leer_nodo(idx, nodo_id);
 216                         } else {
 217                                 nodo_id = claves[i-1].hijo_derecho;
 218                                 free(nodo);
 219                                 nodo = b_leer_nodo(idx, nodo_id);
 220                         }
 221                 }
 222         }
 223
 224         if (encontrado) {
 225                 PERR("Clave encontrada, borrando ...");
 226                 fprintf(stderr, "%s: La clave a borrar esta en el nodo %d\n", idx->nombre, nodo_id);
 227                 if (idx->funcion != IND_PRIMARIO) {
 228                         /* Debo borrar primero la clave desde el archivo de
 229                          * claves repetidas, y si recien ahi me quedo sin claves,
 230                          * borrar la clave del arbol
 231                          */
 232                         PERR("Vamos a borrar duplicados");
 233                         encontrado = b_borrar_dup_clave(idx, claves[i].dato, dato);
 234                         fprintf(stderr, "Listo, encontrado = %d\n", encontrado);
 235                 }
 236                 if (encontrado) {
 237                         b_borrar_clave(idx, nodo, nodo_id, k);
 238                 }
 239         } else {
 240                 PERR("Clave no encontrada");
 241         }
 242         return 0;
 243 }
 244
 245 static int b_ultimo_id(INDICE *idx)
 246 {
 247         int i;
 248         FILE *fp;
 249         fp = fopen(idx->filename, "r");
 250         fseek(fp, 0, SEEK_END);
 251         i = ftell(fp)/idx->tam_bloque;
 252         fclose(fp);
 253
 254         return i;
 255 }
 256
 257 static char *b_crear_nodo(INDICE *idx, int *id)
 258 {
 259         char *bloque;
 260         B_NodoHeader header;
 261
 262         (*id) = b_ultimo_id(idx);
 263
 264         header.cant = 0;
 265         header.nivel = 0;
 266         header.hijo_izquierdo = -1;
 267         header.padre = -1;
 268
 269         bloque = (char *)malloc(idx->tam_bloque);
 270         memset(bloque, -1, idx->tam_bloque);
 271         memcpy(bloque, &header, sizeof(B_NodoHeader));
 272
 273         b_grabar_nodo(idx, *id, bloque);
 274
 275         return bloque;
 276 }
 277
 278 char *b_leer_nodo(INDICE *idx, int id)
 279 {
 280         FILE *fp;
 281         char *out;
 282         /*B_NodoHeader header;
 283         B_NodoEntry *claves;*/
 284
 285         if (id < 0) return NULL;
 286
 287         fp = fopen(idx->filename, "r");
 288         if (fp == NULL) return NULL;
 289
 290         fseek(fp, id*idx->tam_bloque, SEEK_SET);
 291
 292         out = (char *)malloc(idx->tam_bloque);
 293         if (out == NULL) {
 294                 fclose(fp);
 295                 return NULL;
 296         }
 297
 298         if (fread(out, 1, idx->tam_bloque, fp) != idx->tam_bloque) {
 299                 free(out);
 300                 /* No se puso leer el nodo */
 301                 fclose(fp);
 302                 return NULL;
 303         }
 304
 305         /* Si estoy manejando string tengo que sacar las abreviaturas */
 306 /*      if (idx->tipo_dato == IDX_STRING) {
 307                 b_leer_header(out, &header);
 308                 claves = b_leer_claves(out, &header);
 309                 desabreviar_claves(idx, claves, &header);
 310         }*/
 311         fclose(fp);
 312         return out;
 313 }
 314
 315 static void b_grabar_nodo(INDICE *idx, int id, char *data)
 316 {
 317         FILE *fp;
 318         /*B_NodoHeader header;
 319         B_NodoEntry *claves;*/
 320
 321         /* Si las claves son de tipo string debo abreviar antes de guardar */
 322 /*      if (idx->tipo_dato == IDX_STRING) {
 323                 b_leer_header(data, &header);
 324                 claves = b_leer_claves(data, &header);
 325                 abreviar_claves(idx, claves, &header);
 326         }*/
 327         fp = fopen(idx->filename, "r+");
 328         fseek(fp, id*idx->tam_bloque, SEEK_SET);
 329         fwrite(data, 1, idx->tam_bloque, fp);
 330         fclose(fp);
 331 }
 332
 333 void b_leer_header(char *src, B_NodoHeader *header)
 334 {
 335         if (!src) return;
 336
 337         memcpy(header, src, sizeof(B_NodoHeader));
 338 }
 339
 340 static void b_actualizar_header(char *src, B_NodoHeader *header)
 341 {
 342         if (!src) return;
 343         memcpy(src, header, sizeof(B_NodoHeader));
 344 }
 345
 346 B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header)
 347 {
 348         return (B_NodoEntry *)(src+sizeof(B_NodoHeader));
 349 }
 350
 351 static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2)
 352 {
 353         char *padre, *nuevo;
 354         int nuevo_id;
 355         int i, j;
 356         static int rompi=0;
 357         char salir = 0;
 358         B_NodoHeader nodo_header, nuevo_header;
 359         B_NodoEntry *claves, *tmp_claves, *claves_nuevo;
 360
 361         do {
 362                 if (!nodo) {
 363                         /* CREAR NODO? */
 364                         nodo = b_crear_nodo(idx, &nodo_id);
 365                 }
 366                 b_leer_header(nodo, &nodo_header);
 367                 claves = b_leer_claves(nodo, &nodo_header);
 368
 369                 padre = b_leer_nodo(idx, nodo_header.padre);
 370
 371                 if (nodo_header.cant == CANT_HIJOS(idx)) {
 372                         int total;
 373                         /*
 374                          * TODO FIXME XXX TODO FIXME XXX TODO FIXME XXX
 375                          *
 376                          *******************************************************
 377                          * Pseudocódigo que explica que hay que hacer si es B*
 378                          *
 379                          * OJO! Si el nodo en el cual estoy insertando es el
 380                          * raíz, se maneja exactamente igual que en el B común,
 381                          * así que el if sería algo como:
 382                          * if (idx->tipo == IND_B_ASC && !es_raiz(nodo_id))
 383                          *******************************************************
 384                          *
 385                          * nuevo_entry = new entry(clave, dato, hijo_der)
 386                          * padre = get_padre(nodo)
 387                          *
 388                          * // Veo si puedo pasar a derecha
 389                          * hijo_derecho = get_hijo_derecho(padre)
 390                          * if (hijo_derecho != NULL && hijo_derecho.cantidad_entries < MAX_ENTRIES)
 391                          *      buffer = new entries[MAX_ENTRIES+1]
 392                          *      copiar_entries(buffer, nodo)
 393                          *      insertar_ordenado(buffer, nuevo_entry)
 394                          *      entry_a_pasar = get_entry_extremo_derecho(buffer)
 395                          *      b_pasar_clave_a_derecha(idx, hijo_derecho, hijo_derecho.id, padre, padre.id, padre.posicion, entry_a_pasar)
 396                          *      SALIR
 397                          *
 398                          * // Veo si puedo pasar a izquierda
 399                          * hijo_izquierdo = get_hijo_izquierdo(padre)
 400                          * if (hijo_izquierdo != NULL && hijo_izquierdo.cantidad_entries < MAX_ENTRIES)
 401                          *      buffer = new entries[MAX_ENTRIES+1]
 402                          *      copiar_entries(buffer, nodo)
 403                          *      insertar_ordenado(buffer, nuevo_entry)
 404                          *      entry_a_pasar = get_entry_extremo_izquierdo(buffer)
 405                          *      b_pasar_clave_a_izquierda(idx, hijo_izquierdo, hijo_izquierdo.id, padre, padre.id, padre.posicion, entry_a_pasar)
 406                          *      SALIR
 407                          *
 408                          * // Parto 2 nodos en 3.
 409                          * if (hijo_izquierdo != NULL)
 410                          *      b_partir_dos_nodos_en_tres(idx, hijo_izquierdo, nodo, padre, nuevo_entry)
 411                          * else // Siempre alguno tiene que existir.
 412                          *      b_partir_dos_nodos_en_tres(idx, nodo, hijo_derecho, padre, nuevo_entry)
 413                          *
 414                          * SALIR
 415                          *
 416                          **********************************************************************************
 417                          * Fin de pseudocódigo, si no es B* se sigue haciendo lo que dice a continuación. *
 418                          **********************************************************************************
 419                          */
 420                         nuevo = b_crear_nodo(idx, &nuevo_id);
 421                         i=0;
 422                         /* Creo una lista ordenada de los nodos a partir */
 423                         tmp_claves = (B_NodoEntry *)malloc(sizeof(B_NodoEntry)*(nodo_header.cant+1));
 424                         total = nodo_header.cant+1;
 425                         while ((i<nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) {
 426                                 tmp_claves[i] = claves[i];
 427                                 i++;
 428                         }
 429                         tmp_claves[i].clave = clave;
 430                         tmp_claves[i].dato = dato;
 431                         /*tmp_claves[i].hijo_derecho = hijo1;*/
 432                         if (i==0) {
 433                                 nodo_header.hijo_izquierdo = hijo1;
 434                                 tmp_claves[i].hijo_derecho = hijo2;
 435                         } else {
 436                                 tmp_claves[i-1].hijo_derecho = hijo1;
 437                                 tmp_claves[i].hijo_derecho = hijo2;
 438                         }
 439                         while (i < nodo_header.cant) {
 440                                 tmp_claves[i+1] = claves[i];
 441                                 i++;
 442                         }
 443
 444                         /* Asigno a cada nodo lo que corresponde */
 445                         b_leer_header(nuevo, &nuevo_header);
 446
 447                         nuevo_header.nivel = nodo_header.nivel;
 448                         nodo_header.cant = total/2;
 449                         nuevo_header.cant = (total-1) - nodo_header.cant;
 450
 451                         memset(claves, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 452                         for(j=0; j<nodo_header.cant; j++)
 453                                 claves[j] = tmp_claves[j];
 454
 455                         claves_nuevo = b_leer_claves(nuevo, &nuevo_header);
 456                         memset(claves_nuevo, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 457                         for(j=0; j<nuevo_header.cant; j++)
 458                                 claves_nuevo[j] = tmp_claves[j+total/2+1];
 459
 460                         b_actualizar_header(nodo, &nodo_header);
 461                         b_actualizar_header(nuevo, &nuevo_header);
 462
 463                         if (nodo_id != 0) {
 464                                 clave = tmp_claves[total/2].clave;
 465                                 dato = tmp_claves[total/2].dato;
 466
 467                                 b_grabar_nodo(idx, nodo_id, nodo);
 468                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 469                                 free(nodo);
 470                                 free(nuevo);
 471                                 free(tmp_claves);
 472
 473                                 hijo1 = nodo_id;
 474                                 hijo2 = nuevo_id;
 475
 476                                 fprintf(stderr, "Nodos espliteados = %d %d\n", hijo1, hijo2);
 477                                 nodo = padre;
 478                                 nodo_id = nodo_header.padre;
 479                         } else {
 480                                 /* Oops, parti el raiz, y este debe quedar en 0, lo paso a otro bloque
 481                                  * y dejo el padre vacio
 482                                  */
 483                                 char *tmp_nuevo = b_crear_nodo(idx, &nodo_id);
 484                                 memcpy(tmp_nuevo, nodo, idx->tam_bloque);
 485                                 free(nodo);
 486                                 nodo = tmp_nuevo;
 487
 488                                 clave = tmp_claves[total/2].clave;
 489                                 dato = tmp_claves[total/2].dato;
 490
 491                                 b_grabar_nodo(idx, nuevo_id+1, nodo);
 492                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 493
 494                                 free(nodo);
 495                                 free(nuevo);
 496                                 free(tmp_claves);
 497
 498                                 hijo1 = nuevo_id+1;
 499                                 hijo2 = nuevo_id;
 500
 501                                 fprintf(stderr, "Nodos espliteados = %d %d\n", hijo1, hijo2);
 502                                 /* Limpio al padre */
 503                                 nuevo = b_leer_nodo(idx, 0);
 504
 505                                 b_leer_header(nuevo, &nuevo_header);
 506                                 nuevo_header.cant = 0;
 507                                 nuevo_header.padre = -1;
 508                                 nuevo_header.nivel = nodo_header.nivel+1;
 509                                 nuevo_header.hijo_izquierdo = -1;
 510                                 fprintf(stderr, "root.nivel=%d\n", nuevo_header.nivel);
 511                                 memset(nuevo, -1, idx->tam_bloque);
 512                                 b_actualizar_header(nuevo, &nuevo_header);
 513                                 b_grabar_nodo(idx, 0, nuevo);
 514
 515                                 nodo_id = 0;
 516                                 nodo = nuevo;
 517                                 rompi = 1;
 518                         }
 519                 } else {
 520                         /* La clave entra en este nodo!! */
 521                         b_insertar_en_nodo_con_lugar(idx, clave, dato, nodo_id, nodo, hijo1, hijo2);
 522                         salir = 1;
 523                 }
 524         } while (!salir);
 525 }
 526
 527 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)
 528 {
 529         int i = 0;
 530         B_NodoHeader nodo_header;
 531         B_NodoEntry* claves;
 532         b_leer_header(nodo, &nodo_header);
 533         claves = b_leer_claves(nodo, &nodo_header);
 534         if (nodo_header.cant > 0) {
 535                 int j;
 536                 while ((i < nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
 537                 for(j=nodo_header.cant; j > i; j--)
 538                         claves[j] = claves[j-1];
 539         }
 540         nodo_header.cant++;
 541         claves[i].clave = clave;
 542         claves[i].dato = dato;
 543         if (i==0) {
 544                 nodo_header.hijo_izquierdo = hijo_izq;
 545                 claves[i].hijo_derecho = hijo_der;
 546         } else {
 547                 claves[i-1].hijo_derecho = hijo_izq;
 548                 claves[i].hijo_derecho = hijo_der;
 549         }
 550
 551         b_actualizar_header(nodo, &nodo_header);
 552         b_grabar_nodo(idx, nodo_id, nodo);
 553
 554         /* Debo actualizar los punteros al padre de los hijos */
 555         if (hijo_izq != -1) {
 556                 char* nuevo = b_leer_nodo(idx, hijo_izq);
 557                 if (nuevo != NULL) {
 558                         B_NodoHeader nuevo_header;
 559                         fprintf(stderr, "Actualizo padre de %d a %d\n", hijo_izq, nodo_id);
 560                         b_leer_header(nuevo, &nuevo_header);
 561                         nuevo_header.padre = nodo_id;
 562                         b_actualizar_header(nuevo, &nuevo_header);
 563                         b_grabar_nodo(idx, hijo_izq, nuevo);
 564                         free(nuevo);
 565                 } else printf("FUCK! hijo_izq=%d no existe!\n", hijo_izq);
 566         }
 567         if (hijo_der != -1) {
 568                 char* nuevo = b_leer_nodo(idx, hijo_der);
 569                 if (nuevo != NULL) {
 570                         B_NodoHeader nuevo_header;
 571                         fprintf(stderr, "Actualizo padre de %d a %d\n", hijo_der, nodo_id);
 572                         b_leer_header(nuevo, &nuevo_header);
 573                         nuevo_header.padre = nodo_id;
 574                         b_actualizar_header(nuevo, &nuevo_header);
 575                         b_grabar_nodo(idx, hijo_der, nuevo);
 576                         free(nuevo);
 577                 } else printf("FUCK! hijo_der=%d no existe!\n", hijo_der);
 578         }
 579 }
 580
 581 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)
 582 {
 583         int i = 0;
 584         B_NodoHeader nodo_header;
 585         B_NodoEntry* claves;
 586         b_leer_header(nodo, &nodo_header);
 587         claves = b_leer_claves(nodo, &nodo_header);
 588         if (nodo_header.cant > 0) {
 589                 int j;
 590                 while ((i < nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
 591                 for(j=nodo_header.cant; j > i; j--)
 592                         claves[j] = claves[j-1];
 593         }
 594         nodo_header.cant++;
 595         claves[i].clave = clave;
 596         claves[i].dato = dato;
 597         claves[i].hijo_derecho = hijo_der;
 598
 599         b_actualizar_header(nodo, &nodo_header);
 600         b_grabar_nodo(idx, nodo_id, nodo);
 601
 602         /* Debo actualizar el puntero al padre del hijo */
 603         if (hijo_der != -1) {
 604                 char* nuevo = b_leer_nodo(idx, hijo_der);
 605                 if (nuevo != NULL) {
 606                         B_NodoHeader nuevo_header;
 607                         b_leer_header(nuevo, &nuevo_header);
 608                         nuevo_header.padre = nodo_id;
 609                         b_actualizar_header(nuevo, &nuevo_header);
 610                         b_grabar_nodo(idx, hijo_der, nuevo);
 611                         free(nuevo);
 612                 } else printf("FUCK! hijo_der=%d no existe!\n", hijo_der);
 613         }
 614 }
 615
 616 INDICE_DATO *emufs_indice_b_buscar_muchos(INDICE *idx, CLAVE clave, int *cant)
 617 {
 618         EMUFS_REG_SIZE tam;
 619         int error=0;
 620         char *leido;
 621         CLAVE k;
 622         INDICE_DATO dato, *ret;
 623
 624         /* Si el indice es primario no tiene sentido hacer nada */
 625         if (idx->funcion == IND_PRIMARIO) {
 626                 *cant = 0;
 627                 PERR("INDICE PRIMARIO NO SOPORTA BUSQUEDA MULTIPLE");
 628                 return NULL;
 629         }
 630
 631         /* Busco la clave en el arbol */
 632         dato = emufs_indice_b_buscar(idx, clave);
 633
 634         if (dato.id == -1) {
 635                 PERR("CLAvE NO ENCONTRADA EN EL ARBOL!");
 636         }
 637
 638         /* Leo el contenido actual */
 639         k.i_clave = dato.id;
 640         error = 0;
 641         leido = (char *)idx->emu_mult->leer_registro(idx->emu_mult, k, &tam, &error);
 642
 643         /* Incremento en 1 la cantidad */
 644         if (leido != NULL)
 645                 (*cant) = *((int *)leido);
 646         else
 647                 (*cant) = 0;
 648
 649         ret = malloc(sizeof(INDICE_DATO)*(*cant));
 650         memcpy(ret, leido+sizeof(int), (*cant)*sizeof(INDICE_DATO));
 651         free(leido);
 652         return ret;
 653 }
 654
 655 static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k)
 656 {
 657         int pos, actual_id, padre_id, i, pos_padre, izquierda_id, derecha_id, p;
 658         B_NodoHeader header, header_actual, header_padre, header_izq, header_der;
 659         B_NodoEntry *claves, *claves_actual, *claves_padre;/*, *claves_izq, *claves_der;*/
 660         char *actual, *padre, *izq, *der;
 661
 662         PERR("Borrando clave");
 663         b_leer_header(nodo, &header);
 664         claves = b_leer_claves(nodo, &header);
 665
 666         pos = 0;
 667         /* Busco la posicion dentro de la lista de claves */
 668         PERR("Buscando lugar donde se encuentra la clave");
 669         while (emufs_indice_es_menor(idx, claves[pos].clave, k)) pos++;
 670
 671         /* Es el nodo una hoja? */
 672         fprintf(stderr, "La clave esta en la pos = %d\n", pos);
 673         if (header.hijo_izquierdo != -1) {
 674                 PERR("Nodo no es hoja, intercambio");
 675                 actual = b_leer_nodo(idx, claves[pos].hijo_derecho);
 676                 actual_id = claves[pos].hijo_derecho;
 677                 p = claves[pos].hijo_derecho;
 678
 679                 b_leer_header(actual, &header_actual);
 680                 while (header_actual.hijo_izquierdo != -1) {
 681                         actual_id = header_actual.hijo_izquierdo;
 682                         free(actual);
 683                         actual = b_leer_nodo(idx, actual_id);
 684                         b_leer_header(actual, &header_actual);
 685                 }
 686                 claves_actual = b_leer_claves(actual, &header_actual);
 687
 688                 claves[pos] = claves_actual[0];
 689                 claves[pos].hijo_derecho = p;
 690                 pos = 0;
 691                 b_grabar_nodo(idx, nodo_id, nodo);
 692                 PERR("Listo");
 693         } else {
 694                 PERR("Nodo es hoja");
 695                 actual = nodo;
 696                 header_actual = header;
 697                 claves_actual = claves;
 698                 actual_id = nodo_id;
 699         }
 700
 701         /* Borro la clave */
 702         PERR("Borrando clave");
 703         for(i=pos; i < header_actual.cant-1; i++) {
 704                 claves_actual[i] = claves_actual[i+1];
 705         }
 706         PERR("Borrado completo");
 707         header_actual.cant--;
 708         /* Guardo los cambios */
 709         b_actualizar_header(actual, &header_actual);
 710         b_grabar_nodo(idx, actual_id, actual);
 711
 712         /* Se cumple la condicion de hijos? */
 713         PERR("Dejo todo consistente");
 714         fprintf(stderr, "Condicion : %d >= %d\n", header_actual.cant, MIN_HIJOS(idx));
 715         if ((header_actual.cant >= MIN_HIJOS(idx)) || (actual_id == 0)) {
 716                 PERR("Borrar completo sin fundir");
 717                 return;
 718         }
 719
 720         PERR("Node queda con menos hijos de los posibles!");
 721         /* Tengo que pasar datos o fundir nodos :-( */
 722         do {
 723                 padre_id = header.padre;
 724                 if (padre_id == -1) continue;
 725                 padre = b_leer_nodo(idx, padre_id);
 726                 b_leer_header(padre, &header_padre);
 727                 claves_padre = b_leer_claves(padre, &header_padre);
 728                 fprintf(stderr, "ID del padre = %d de nivel %d\n", padre_id, header_padre.nivel);
 729                 /* TODO Tengo el hijo_izquierdo para revisar!! XXX */
 730                 if (header_padre.hijo_izquierdo == actual_id) {
 731                         PERR("Soy el hijo izquierdo de padre");
 732                         izquierda_id = -1; /* No tengo hermano izquierdo */
 733                         /* Mi hermano derecho es el primer nodo del padre */
 734                         derecha_id = claves_padre[0].hijo_derecho;
 735                         der = b_leer_nodo(idx, derecha_id);
 736                         b_leer_header(der, &header_der);
 737                         pos_padre = 0;
 738                 } else {
 739                         PERR("Buscando que hijo soy");
 740                         for(pos_padre=0; (claves_padre[pos_padre].hijo_derecho != actual_id); pos_padre++)      {       }
 741
 742                         if (pos_padre == header_padre.cant) {
 743                                 PERR("ERROR GRAVE. Padre no me contiene :-(");
 744                         }
 745
 746                         /* Busco mis hermanos a derecha e izquierda, si es que existen */
 747                         PERR("Ya me encontre, busco a mis hermanos");
 748                         if (pos_padre >= 0) {
 749                                 if (pos_padre == 0)
 750                                         izquierda_id = header_padre.hijo_izquierdo;
 751                                 else
 752                                         izquierda_id = claves_padre[pos_padre-1].hijo_derecho;
 753                                 izq = b_leer_nodo(idx, izquierda_id);
 754                                 b_leer_header(izq, &header_izq);
 755                         } else {
 756                                 izquierda_id = -1;
 757                         }
 758                         if (pos_padre < header_padre.cant) {
 759                                 derecha_id = claves_padre[pos_padre+1].hijo_derecho;
 760                                 der = b_leer_nodo(idx, derecha_id);
 761                                 b_leer_header(der, &header_der);
 762                         } else {
 763                                 derecha_id = -1;
 764                         }
 765                 }
 766                 /* Intendo pasar una clave desde un hermano hacia mi */
 767                 PERR("Ta calcule lo que tengo que hacer");
 768                 if ((derecha_id != -1) && (header_der.cant > MIN_HIJOS(idx))) {
 769                         PERR("Le pido clave a derecha");
 770                         fprintf(stderr, "ANTES DE PEDIR DERECHA TENGO %d claves\n", header_actual.cant);
 771                         fprintf(stderr, "PEDIR DERECHA DATOS : yo=%d, padre=%d, der=%d, pos_clave=%d\n", actual_id, padre_id, derecha_id, pos_padre);
 772                         b_pedir_clave_derecha(der, derecha_id, padre, padre_id, actual, actual_id, pos_padre);
 773                         PERR("listo");
 774                         b_leer_header(der, &header_der);
 775                         b_leer_header(padre, &header_padre);
 776                         b_leer_header(actual, &header_actual);
 777                         fprintf(stderr, "DESPUES DE PEDIR DERECHA TENGO %d claves\n", header_actual.cant);
 778                 } else if ((izquierda_id != -1) && (header_izq.cant > MIN_HIJOS(idx))) {
 779                         PERR("Le pido clave a izquierda");
 780                         b_pedir_clave_izquierda(izq, izquierda_id, padre, padre_id, actual, actual_id, pos_padre);
 781                         /* como se modificaron cosas, leo de nuevo los headers */
 782                         b_leer_header(izq, &header_izq);
 783                         b_leer_header(padre, &header_padre);
 784                         b_leer_header(actual, &header_actual);
 785                         PERR("Listo");
 786                 } else {
 787                         /* No pude pasar clave, tengo que fundir :-( */
 788                         PERR("Fundo nodos!");
 789                         if (derecha_id != -1) {
 790                                 b_fundir_nodo(idx, actual, actual_id, padre, padre_id, der, derecha_id, pos_padre);
 791                         } else {
 792                                 b_fundir_nodo(idx, izq, izquierda_id, padre, padre_id, actual, actual_id, pos_padre);
 793                         }
 794                 }
 795
 796                 /* TODO que guardo ?, todo ? */
 797                 b_grabar_nodo(idx, actual_id, actual);
 798                 if (izquierda_id != -1) b_grabar_nodo(idx, izquierda_id, izq);
 799                 if (derecha_id != -1) b_grabar_nodo(idx, derecha_id, der);
 800                 if (padre_id != -1) b_grabar_nodo(idx, padre_id, padre);
 801                 if (actual_id != -1) free(actual);
 802                 if (derecha_id != -1) free(der);
 803                 if (izquierda_id != -1) free(izq);
 804                 actual = padre;
 805                 actual_id = padre_id;
 806                 b_leer_header(actual, &header_actual);
 807                 claves_actual = b_leer_claves(actual, &header_actual);
 808         } while ((actual_id != -1) && (actual_id != 0) && (header_actual.cant < MIN_HIJOS(idx)));
 809 }
 810
 811 static void b_pedir_clave_derecha(char *der, int der_id, char *padre, int padre_id, char *nodo, int nodo_id, int pos_clave)
 812 {
 813         int i;
 814         B_NodoHeader h_der, h_padre, h_nodo;
 815         B_NodoEntry *c_der, *c_padre, *c_nodo;
 816
 817         PERR("Derecha 1");
 818         b_leer_header(nodo, &h_nodo);
 819         c_nodo = b_leer_claves(nodo, &h_nodo);
 820         b_leer_header(der, &h_der);
 821         c_der = b_leer_claves(der, &h_der);
 822         b_leer_header(padre, &h_padre);
 823         c_padre = b_leer_claves(padre, &h_padre);
 824
 825         PERR("Derecha 2");
 826         c_nodo[h_nodo.cant] = c_padre[pos_clave+1];
 827         c_nodo[h_nodo.cant].hijo_derecho = -1; /* XXX */
 828
 829         PERR("Derecha 3");
 830         c_padre[pos_clave+1] = c_der[0];
 831         c_padre[pos_clave+1].hijo_derecho = der_id;
 832
 833         /* Muevo las claves de derecho */
 834         PERR("Derecha 4");
 835         for(i=0; i<h_der.cant-1; i++) {
 836                 c_der[i] = c_der[i+1];
 837         }
 838         h_der.cant--;
 839         h_nodo.cant++;
 840
 841         b_actualizar_header(der, &h_der);
 842         b_actualizar_header(nodo, &h_nodo);
 843         PERR("Derecha 5");
 844 }
 845
 846 void b_pasar_clave_a_derecha(INDICE *idx, char *der, int der_id, char *padre, int padre_id, int padre_pos, B_NodoEntry entry)
 847 {
 848         B_NodoHeader padre_h, der_h;
 849         B_NodoEntry* padre_entries;
 850         /* Leo claves y cabecera del nodo de la derecha y del padre */
 851         b_leer_header(padre, &padre_h);
 852         b_leer_header(der, &der_h);
 853         padre_entries = b_leer_claves(padre, &padre_h);
 854         /* Inserto en el hijo derecho la clave del padre */
 855         PERR("PASAR CLAVE DERECHA");
 856         b_insertar_en_nodo_con_lugar(idx, padre_entries[padre_pos].clave, padre_entries[padre_pos].dato,
 857                         der_id, der, der_h.hijo_izquierdo, entry.hijo_derecho);
 858         /* Reemplazo clave del padre por clave nueva */
 859         entry.hijo_derecho = der_id;
 860         padre_entries[padre_pos] = entry;
 861 }
 862
 863 void b_pedir_clave_izquierda(char *izq, int izq_id, char *padre, int padre_id, char *nodo, int nodo_id, int pos_clave)
 864 {
 865         int i;
 866         B_NodoHeader h_izq, h_padre, h_nodo;
 867         B_NodoEntry *c_izq, *c_padre, *c_nodo;
 868
 869         b_leer_header(nodo, &h_nodo);
 870         c_nodo = b_leer_claves(nodo, &h_nodo);
 871         b_leer_header(izq, &h_izq);
 872         c_izq = b_leer_claves(izq, &h_izq);
 873         b_leer_header(padre, &h_padre);
 874         c_padre = b_leer_claves(padre, &h_padre);
 875
 876         PERR("Muevo las claves");
 877         for(i=h_nodo.cant; i>0;i--)
 878                 c_nodo[i] = c_nodo[i-1];
 879
 880         h_nodo.cant++;
 881         PERR("Paso clave de padre a nodo");
 882         c_nodo[0] = c_padre[pos_clave];
 883         c_nodo[0].hijo_derecho = -1; /* XXX */
 884         PERR("Paso clave de izquierda a padre");
 885         c_padre[pos_clave] = c_izq[h_izq.cant-1];
 886         c_padre[pos_clave].hijo_derecho = nodo_id;
 887         h_izq.cant--;
 888
 889         PERR("ACTUALIZO")
 890         b_actualizar_header(izq, &h_izq);
 891         b_actualizar_header(padre, &h_padre);
 892         b_actualizar_header(nodo, &h_nodo);
 893         PERR("Salgo");
 894 }
 895
 896 void b_pasar_clave_a_izquierda(INDICE* idx, char *izq, int izq_id, char *padre, int padre_id, int padre_pos, B_NodoEntry entry, int id_entry_hijo_izq, int id_entry_nodo)
 897 {
 898         B_NodoHeader padre_h;
 899         B_NodoEntry* padre_entries;
 900         /* Leo claves y cabecera del nodo de la izquierda y del padre */
 901         b_leer_header(padre, &padre_h);
 902         padre_entries = b_leer_claves(padre, &padre_h);
 903         /* Inserto en el hijo izquirdo la clave del padre */
 904         b_insertar_en_nodo_con_lugar_sin_hijo_izq(idx, padre_entries[padre_pos].clave, padre_entries[padre_pos].dato,
 905                         izq_id, izq, id_entry_hijo_izq);
 906         /* Reemplazo clave del padre por clave nueva */
 907         entry.hijo_derecho = id_entry_nodo;
 908         padre_entries[padre_pos] = entry;
 909 }
 910
 911 static void b_fundir_nodo(INDICE *idx, char *izq, int izq_id, char *padre, int padre_id, char *der, int der_id, int pos_padre)
 912 {
 913         int i;
 914         B_NodoHeader h_izq, h_padre, h_der;
 915         B_NodoEntry *c_izq, *c_padre, *c_der;
 916
 917         b_leer_header(der, &h_der);
 918         c_der = b_leer_claves(der, &h_der);
 919         b_leer_header(izq, &h_izq);
 920         c_izq = b_leer_claves(izq, &h_izq);
 921         b_leer_header(padre, &h_padre);
 922         c_padre = b_leer_claves(padre, &h_padre);
 923
 924         c_izq[h_izq.cant] = c_padre[pos_padre];
 925         h_padre.cant--;
 926         for(i=pos_padre; i<h_padre.cant; i++)
 927                 c_padre[i] = c_padre[i+1];
 928         h_izq.cant++;
 929         for(i=0; i<h_der.cant; i++)
 930                 c_izq[h_izq.cant+i] = c_der[i];
 931
 932         h_izq.cant += h_der.cant;
 933
 934         b_actualizar_header(izq, &h_izq);
 935         b_actualizar_header(padre, &h_padre);
 936
 937         /* TODO Aca queda libre el nodo der, ver de recuperar! */
 938         memset(der, 'X', idx->tam_bloque);
 939         b_grabar_nodo(idx, der_id, der);
 940 }
 941
 942 static EMUFS_REG_ID b_insertar_dup_en_pos(INDICE *idx, INDICE_DATO pos, INDICE_DATO nuevo)
 943 {
 944         int cant;
 945         EMUFS_REG_SIZE tam;
 946         int error=0;
 947         INDICE_DATO *array;
 948         char *leido;
 949         CLAVE k;
 950
 951         /* Leo el contenido actual */
 952         k.i_clave = pos.id;
 953         error = 0;
 954         leido = (char *)idx->emu_mult->leer_registro(idx->emu_mult, k, &tam, &error);
 955
 956         /* Incremento en 1 la cantidad */
 957         if (leido != NULL)
 958                 cant = *((int *)leido);
 959         else
 960                 cant = 0;
 961         cant++;
 962
 963         /* Obtengo un nuevo lugar para el dato nuevo */
 964         /* Aca todo bien, si leido es NULL se compota como malloc */
 965         leido = realloc(leido, cant*sizeof(INDICE_DATO)+sizeof(int));
 966         array = (INDICE_DATO *)(leido+sizeof(int));
 967
 968         /* Pongo el dato nuevo */
 969         array[cant-1] = nuevo;
 970
 971         /* Actualizo la cantidad */
 972         (*((int *)leido)) = cant;
 973
 974         /* Salvo */
 975         if (k.i_clave == -1) {
 976                 /* Creo uno nuevo */
 977                 error = 0;
 978                 k.i_clave = idx->emu_mult->grabar_registro(idx->emu_mult,
 979                         leido,
 980                         cant*sizeof(INDICE_DATO)+sizeof(int),
 981                         &error
 982                 );
 983                 if (k.i_clave == -1) PERR("ALGO NO GRABO BIEN!!");
 984         } else {
 985                 /* Modifico el que ya existia! */
 986                 INDICE_DATO dummy;
 987                 error = 0;
 988                 idx->emu_mult->modificar_registro(idx->emu_mult,
 989                         k,
 990                         leido,
 991                         cant*sizeof(INDICE_DATO)+sizeof(int),
 992                         &error,
 993                         dummy
 994                 );
 995         }
 996         /* Clean up! */
 997         free(leido);
 998         return k.i_clave;
 999 }
1000
1001 char *abreviar(char *primera, char *actual, int *iguales)
1002 {
1003         (*iguales) = 0;
1004         while (((*primera) != '\0') && ((*actual) != '\0')) {
1005                 if ((*primera) == (*actual)) {
1006                         primera++;
1007                         actual++;
1008                         (*iguales)++;
1009                 } else {
1010                         /* No coinciden mas! */
1011                         break;
1012                 }
1013         }
1014
1015         return actual;
1016 }
1017
1018 static void abreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header)
1019 {
1020         char *primera, *actual, *resto, salvar[100];
1021         EMUFS_REG_SIZE size;
1022         int error, i;
1023         int iguales;
1024
1025         /* Agarro la primer clave entera como referencia */
1026         primera = (char *)idx->emu_string->leer_registro(idx->emu_string, array[0].clave, &size, &error);
1027         for(i=1; i<header->cant; i++) {
1028                 actual = (char *)idx->emu_string->leer_registro(idx->emu_string, array[i].clave, &size, &error);
1029                 if (*actual == '*') {
1030                         free(actual);
1031                         continue;
1032                 }
1033                 resto = abreviar(primera, actual, &iguales);
1034                 /* Para que tenga sentido abreviar tengo que tener
1035                  * mas de 2 letras iguales, si no no gano nada y complica las cosas
1036                  */
1037                 if (iguales > 1) {
1038                         INDICE_DATO dummy1;
1039                         sprintf(salvar, "%d|%s", iguales, resto);
1040                         free(actual);
1041                         error = 0;
1042                         idx->emu_string->modificar_registro(idx->emu_string, array[i].clave, salvar, strlen(salvar)+1, &error, dummy1);
1043                 } else {
1044                         free(primera);
1045                         primera = actual;
1046                 }
1047         }
1048
1049         free(primera);
1050 }
1051
1052 static void desabreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header)
1053 {
1054         char *primera, *actual, *resto, salvar[100];
1055         EMUFS_REG_SIZE size;
1056         int error, i;
1057         int iguales;
1058
1059         /* Agarro la primer clave entera como referencia */
1060         primera = (char *)idx->emu_string->leer_registro(idx->emu_string, array[0].clave, &size, &error);
1061         for(i=1; i<header->cant; i++) {
1062                 actual = (char *)idx->emu_string->leer_registro(idx->emu_string, array[i].clave, &size, &error);
1063                 if (*actual == '*') {
1064                         free(actual);
1065                         continue;
1066                 }
1067                 iguales = strtol(actual, &resto, 10);
1068                 if ((iguales > 0) && (*resto == '|')) {
1069                         INDICE_DATO dummy2;
1070                         strncpy(salvar, primera, iguales);
1071                         salvar[iguales] = '\0';
1072                         strcat(salvar, resto+1); /* +1 para saltar el separador */
1073                         idx->emu_string->modificar_registro(idx->emu_string, array[i].clave, salvar, strlen(salvar)+1, &error, dummy2);
1074                         free(actual);
1075                 } else {
1076                         free(primera);
1077                         primera = actual;
1078                 }
1079         }
1080
1081         free(primera);
1082 }
1083
1084 void insertar_ordenado(INDICE *idx, B_NodoEntry *buffer, int cant, B_NodoEntry nuevo_entry)
1085 {
1086         int i, pos;
1087         for(i=0; (i<cant) && emufs_indice_es_menor(idx, buffer[i].clave, nuevo_entry.clave); i++) {}
1088         pos = i;
1089
1090         for(i=cant; i>pos; i--)
1091                 buffer[i] = buffer[i-1];
1092
1093         buffer[pos] = nuevo_entry;
1094 }
1095
1096 static void b_partir_dos_nodos_en_tres(INDICE* idx, int nodo_izq, int nodo_der, B_NodoEntry padre_entry, B_NodoEntry nuevo_entry, int id_padre)
1097 {
1098         PERR("PARTIR 2 EN 3");
1099         B_NodoEntry *buffer;
1100         char *izq, *der, *padre, *nuevo;
1101         B_NodoEntry *c_der, *c_izq, *c_nuevo, prom1, prom2;
1102         B_NodoHeader h_der, h_izq, h_nuevo;
1103         int i, j, nodo_nuevo;
1104         int cant_claves;
1105
1106         /* Leo los nodos y los datos */
1107         der = b_leer_nodo(idx, nodo_der);
1108         izq = b_leer_nodo(idx, nodo_izq);
1109
1110         b_leer_header(der, &h_der);
1111         b_leer_header(izq, &h_izq);
1112
1113         c_der = b_leer_claves(der, &h_der);
1114         c_izq = b_leer_claves(izq, &h_izq);
1115
1116         cant_claves = 2*CANT_HIJOS(idx)+2;
1117         buffer = malloc(cant_claves*sizeof(B_NodoEntry));
1118
1119         for(i=0, j=0; i<h_izq.cant; i++, j++)
1120                 buffer[j] = c_izq[i];
1121
1122         buffer[j++] = padre_entry;
1123
1124         for(i=0; i<h_der.cant; i++, j++)
1125                 buffer[j] = c_der[i];
1126
1127         insertar_ordenado(idx, buffer, cant_claves-1, nuevo_entry);
1128
1129         nuevo = b_crear_nodo(idx, &nodo_nuevo);
1130         b_leer_header(nuevo, &h_nuevo);
1131         c_nuevo = b_leer_claves(nuevo, &h_nuevo);
1132
1133         /* lleno el lado derecho e izquierdo */
1134         for(i=0, j=0; i<cant_claves/3; i++, j++)
1135                 c_izq[j] = buffer[i];
1136         prom1 = buffer[i++];
1137         h_izq.cant = j;
1138         for(j=0; i<2*cant_claves/3; i++, j++)
1139                 c_der[j] = buffer[i];
1140         h_der.cant = j;
1141         prom2 = buffer[i++];
1142         for(j=0; i<cant_claves; i++,j++)
1143                 c_nuevo[j] = buffer[i];
1144         h_nuevo.cant = j;
1145
1146         /* Actualizo headers y salvo */
1147         b_actualizar_header(der, &h_der);
1148         b_actualizar_header(izq, &h_izq);
1149         b_actualizar_header(nuevo, &h_nuevo);
1150         b_grabar_nodo(idx, nodo_izq, izq);
1151         b_grabar_nodo(idx, nodo_der, der);
1152         b_grabar_nodo(idx, nodo_nuevo, nuevo);
1153
1154         free(der);
1155         free(izq);
1156         free(nuevo);
1157         padre = b_leer_nodo(idx, id_padre);
1158         b_insertar_en_nodo(idx, prom1.clave, prom1.dato, id_padre, padre, nodo_izq, nodo_der);
1159         b_insertar_en_nodo(idx, prom2.clave, prom2.dato, id_padre, padre, nodo_der, nodo_nuevo);
1160
1161         /*
1162          * PSEUDOCODIGO    TODO FIXME XXX TODO FIXME XXX TODO FIXME XXX
1163          *
1164          * // Creo un buffer con todos los entries (las claves) de ambos nodos, mas el padre y la nueva, ordenadas
1165          * buffer_size = 2*MAX_ENTRIES+2
1166          * buffer = new entries[buffer_size]
1167          * copiar_entries(buffer, nodo_izq)
1168          * concatenar_entries(buffer, padre)
1169          * concatenar_entries(buffer, nodo_der)
1170          * insertar_ordenado(buffer, nuevo_entry)
1171          * // Borro los 2 nodos viejos para reutilizarlos y creo el tercero
1172          * borrar_entries(nodo_izq)
1173          * borrar_entries(nodo_der)
1174          * nodo_nuevo = new nodo()
1175          * // Copio de a tercios del buffer en los nuevos nodos, excluyendo las 2 claves 'limítrofes' para insertarlas luego en el padre
1176          * copiar_algunos_entries(nodo_izq, buffer, 0, (buffer_size/3)-1)
1177          * entry_promovido1 = buffer[buffer_size/3]
1178          * copiar_algunos_entries(nodo_izq, buffer, (buffer_size/3)+1, 2*(buffer_size/3))
1179          * entry_promovido2 = buffer[(2*(buffer_size/3))+1]
1180          * copiar_algunos_entries(nodo_nuevo, buffer, (2*(buffer_size/3))+2, buffer_size-1))
1181          * // Finalmente inserto (recursivamente, porque esta funcion es llamada desde b_insertar_en_nodo()) las claves promovidas en el padre
1182          * b_insertar_en_nodo(idx, entry_promovido.clave, entry_promovido.dato, entry_promovido.id, entry_promovido, nodo_izq.id, nodo_der.id)
1183          * b_insertar_en_nodo(idx, entry_promovido.clave, entry_promovido.dato, entry_promovido.id, entry_promovido, nodo_der.id, nodo_nuevo.id)
1184          *
1185          */
1186 }
1187
1188 CLAVE emufs_indice_b_obtener_menor_clave(INDICE *idx)
1189 {
1190         B_NodoHeader header;
1191         B_NodoEntry *claves;
1192         CLAVE k;
1193         char *nodo;
1194
1195         nodo = b_leer_nodo(idx, 0);
1196         b_leer_header(nodo, &header);
1197         /* Tengo que ir siempre a la izquierda hasta una hora */
1198         while (header.hijo_izquierdo != -1) {
1199                 free(nodo);
1200                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
1201                 b_leer_header(nodo, &header);
1202         }
1203
1204         /* Listo, ahora solo leo la primer clave */
1205         claves = b_leer_claves(nodo, &header);
1206         k = claves[0].clave;
1207         free(nodo);
1208         return k;
1209 }
1210
1211 CLAVE emufs_indice_b_obtener_mayor_clave(INDICE *idx)
1212 {
1213         B_NodoHeader header;
1214         B_NodoEntry *claves;
1215         CLAVE k;
1216         int i;
1217         char *nodo;
1218
1219         nodo = b_leer_nodo(idx, 0);
1220         b_leer_header(nodo, &header);
1221         claves = b_leer_claves(nodo, &header);
1222         /* Tengo que ir siempre a la izquierda hasta una hora */
1223         while (claves[header.cant-1].hijo_derecho != -1) {
1224                 i = claves[header.cant-1].hijo_derecho;
1225                 free(nodo);
1226                 nodo = b_leer_nodo(idx, i);
1227                 b_leer_header(nodo, &header);
1228                 claves = b_leer_claves(nodo, &header);
1229         }
1230
1231         /* Listo, ahora solo leo la primer clave */
1232         k = claves[header.cant-1].clave;
1233         free(nodo);
1234         return k;
1235 }
1236
1237 CLAVE emufs_indice_b_obtener_sig_clave(INDICE *idx, CLAVE k)
1238 {
1239         int i;
1240         B_NodoHeader header;
1241         B_NodoEntry *claves;
1242         char *nodo, *tmp;
1243         int nodo_id;
1244         CLAVE salida;
1245
1246         /* Primero busco la clave pasada por parametro */
1247         nodo = b_leer_nodo(idx, 0);
1248         nodo_id = 0;
1249         while (nodo) {
1250                 b_leer_header(nodo, &header);
1251                 claves = b_leer_claves(nodo, &header);
1252                 i=0;
1253                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) i++;
1254                 if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, k))) {
1255                                 /* LA ENCONTRE! , ahora busco la siguiente clave!! */
1256                                 fprintf(stderr, "Me encontre en pos %d en el padre\n", i);
1257                                 if ((i+1)<header.cant) {
1258                                         PERR("Joya, hay lugar a la derecha");
1259                                         if (claves[i].hijo_derecho == -1) {
1260                                                 PERR("Y soy hoja!!");
1261                                                 /* Joya!, fue facil, la siguiente va en camino! */
1262                                                 salida = claves[i+1].clave;
1263                                                 free(nodo);
1264                                                 return salida;
1265                                         }
1266
1267                                         PERR("No soy hoja, busco la hoja de menor");
1268                                         /* Mmmmm ... la siguiente esta en uno de mis hijo */
1269                                         /* Necesito la mas chica de las siguientes, para eso
1270                                          * me voy a mi hijo derecho y de ahi bajo siempre
1271                                          * hacia la izquierda hacia una hoja */
1272                                         i = claves[i].hijo_derecho;
1273                                         free(nodo);
1274                                         nodo = b_leer_nodo(idx, i);
1275                                         b_leer_header(nodo, &header);
1276                                         while (header.hijo_izquierdo != -1) {
1277                                                 free(nodo);
1278                                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
1279                                                 b_leer_header(nodo, &header);
1280                                         }
1281                                         claves = b_leer_claves(nodo, &header);
1282                                         salida = claves[0].clave;
1283                                         free(nodo);
1284                                         return salida;
1285                                 }
1286
1287                                 PERR("Fuck, tengo que ir otro nodo a buscar");
1288                                 /* Fuck, la siguiente clave la tengo que sacar de padre */
1289                                 /* Busco al mi padre, perdido en un maremoto hace mucho,muchos
1290                                  * años
1291                                  */
1292                                 tmp = nodo;
1293                                 if (header.padre == -1) {
1294                                         if (nodo_id == 0) {
1295                                                 /* Bien, son el nodo raiz y aca tendria que ir hacia mi hijo
1296                                                  * derecho
1297                                                  */
1298                                                 nodo = b_leer_nodo(idx, claves[header.cant-1].hijo_derecho);
1299                                                 free(tmp);
1300                                                 b_leer_header(nodo, &header);
1301                                                 claves = b_leer_claves(nodo, &header);
1302
1303                                                 salida = claves[0].clave;
1304                                         }
1305                                         return salida;
1306                                 }
1307                                 free(nodo);
1308                                 nodo = b_leer_nodo(idx, header.padre);
1309                                 b_leer_header(nodo, &header);
1310                                 claves = b_leer_claves(nodo, &header);
1311                                 i = 0;
1312                                 PERR("Busco mi siguiente en mi padre");
1313                                 fprintf(stderr, "Padre tiene %d claves\n", header.cant);
1314                                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) {
1315                                         i++;
1316                                         fprintf(stderr, "Proximo i : %d\n", i);
1317                                 }
1318                                 if (i<header.cant) {
1319                                         PERR("Siguiente clave encontrada");
1320                                         salida = claves[i].clave;
1321                                 } else {
1322                                         /* No hay mas claves! */
1323                                         PERR("Busque y busque pero no aparecio");
1324                                         salida.i_clave = -1;
1325                                 }
1326                                 return salida;
1327                 } else {
1328                         tmp = nodo;
1329                         b_grabar_nodo(idx, nodo_id, nodo);
1330                         if (i == 0) {
1331                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
1332                                 nodo_id = header.hijo_izquierdo;
1333                         } else {
1334                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
1335                                 nodo_id = claves[i-1].hijo_derecho;
1336                         }
1337                         free(tmp);
1338                 }
1339         }
1340
1341         /* No encontre la clave pasada, no existe */
1342         PERR("No encontre la clave pasada!!");
1343         salida.i_clave = -1;
1344         return salida;
1345 }
1346
1347 int b_borrar_dup_clave(INDICE *idx, INDICE_DATO k_dato, INDICE_DATO dato)
1348 {
1349         int cant, pos, i;
1350         EMUFS_REG_SIZE tam;
1351         int error=0;
1352         INDICE_DATO *array;
1353         INDICE_DATO dummy1;
1354         char *leido;
1355         CLAVE k;
1356
1357         /* Leo el contenido actual */
1358         error = 0;
1359         k.i_clave = k_dato.id;
1360         leido = (char *)idx->emu_mult->leer_registro(idx->emu_mult, k, &tam, &error);
1361
1362         if (leido == NULL) {
1363                 PERR("LEI CUALQUIER COSA, BUG?");
1364                 return 1;
1365         }
1366
1367         cant = *((int *)leido);
1368
1369         /* Obtengo un nuevo lugar para el dato nuevo */
1370         array = (INDICE_DATO *)(leido+sizeof(int));
1371
1372         /* busco pos de dato en array */
1373         for(pos=0; pos<cant; pos++) {
1374                 if (array[pos].id == dato.id) break;
1375         }
1376
1377         for(i=pos; i<cant-1; i++)
1378                 array[pos] = array[pos+1];
1379
1380         cant--;
1381
1382         if (cant == 0) {
1383                 free(leido);
1384                 /* No tengo mas cosas en esta clave, la borro */
1385                 PERR("EL REGISTRO MULTIPLE QUEDO VACIO, ELIMINANDO");
1386                 idx->emu_mult->borrar_registro(idx->emu_mult, k, dummy1);
1387                 return 0;
1388         }
1389
1390         /* Quito el elemento */
1391         leido = realloc(leido, sizeof(int)+cant*sizeof(INDICE_DATO));
1392
1393         /* Actualizo la cantidad */
1394         (*((int *)leido)) = cant;
1395
1396         error = 0;
1397         idx->emu_mult->modificar_registro(idx->emu_mult,
1398                 k,
1399                 leido,
1400                 cant*sizeof(INDICE_DATO)+sizeof(int),
1401                 &error,
1402                 dummy1
1403         );
1404
1405         free(leido);
1406
1407         return cant;
1408 }
1409
1410 #ifdef NO_TERMINAOD
1411 EMUFS_Estadisticas emufs_indice_b_obtener_estadisticas(INDICE *idx)
1412 {
1413         EMUFS_Estadisticas stats, st_string, st_multiples;
1414
1415         stats.tam_archivo = emufs_common_get_file_size(idx->filename);
1416         stats.cant_bloques = stats.tam_archivo/idx->tam_bloque;
1417
1418 }
1419 #endif
1420
1421 #include "indice_b_asc.c"