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