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