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