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