emufs/indice_b.c

   1
   2 #include "indice_b.h"
   3 #include "common.h"
   4
   5 /* Cantidad de claves por nodo */
   6 #define CANT_HIJOS(x) ((x->tam_bloque-sizeof(B_NodoHeader))/sizeof(B_NodoEntry))
   7 #define CANT_NODOS(x) (CANT_HIJOS(x)+1)
   8 #define MIN_HIJOS(x) (CANT_HIJOS(x)/2)
   9
  10 /* Auxiliares */
  11 /* Graba el nodo en el archivo */
  12 static void b_grabar_nodo(INDICE *idx, int id, char *data);
  13 /* Da el ID del proximo nodo a poder ser utilizado */
  14 static int b_ultimo_id(INDICE *idx);
  15 /* Lee un nodo desde el archivo */
  16 static char *b_leer_nodo(INDICE *idx, int id);
  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 /* Lee el header de un nodo y lo guarda en header */
  20 static void b_leer_header(char *src, B_NodoHeader *header);
  21 /* Actualiza el header de un nodo desde header */
  22 static void b_actualizar_header(char *src, B_NodoHeader *header);
  23 /* Retorna el array de claves del nodo (esta data modifica directamente el bloque
  24  * por eso no es necesario usar un actualizar_claves
  25  */
  26 static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header);
  27 /* Inserta una clave en el nodo de manera iterativa */
  28 static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2);
  29 /* Esto es para asegurar el orden de los hijos luego de partir, en el caso de que
  30  * lo que se parta sea la raiz
  31  */
  32 static int b_elegir_izquierdo(INDICE *idx, int a, int b);
  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_pasar_clave_derecha(char *, int, char *, int, char *, int, int);
  37 /* Le pide al hermano izquierdo una clavfe cuando se eliminan claves */
  38 static void b_pasar_clave_izquierda(char *, int, char *, int, char *, int, int);
  39 /* Junta 2 nodos y hace uno solo */
  40 static void b_fundir_nodo(char *, int, char *, int, char *, int, int);
  41
  42 void emufs_indice_b_crear(INDICE *idx)
  43 {
  44         FILE *fp;
  45         char *bloque;
  46         B_NodoHeader header;
  47
  48         header.cant = 0;
  49         header.nivel = 0;
  50         header.padre = -1;
  51         header.hijo_izquierdo = -1;
  52
  53         fp = fopen(idx->filename, "w");
  54         PERR("Creando indice");
  55         fprintf(stderr, "Archivo = (%s)\n", idx->filename);
  56         if (fp == NULL) {
  57                 PERR("Error al crear el archivo");
  58                 return;
  59         }
  60
  61         /* Creo el archivo con el Nodo raiz */
  62         bloque = (char *)malloc(idx->tam_bloque);
  63         memset(bloque, -1, idx->tam_bloque);
  64
  65         memcpy(bloque, &header, sizeof(B_NodoHeader));
  66
  67         fwrite(bloque, idx->tam_bloque, 1, fp);
  68         fclose(fp);
  69 }
  70
  71 int emufs_indice_b_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato)
  72 {
  73         int i, nodo_id, padre_id;
  74         B_NodoHeader header;
  75         B_NodoEntry *claves;
  76         char *nodo, *padre;
  77
  78         /* Leo la raiz */
  79         nodo = b_leer_nodo(idx, 0);
  80         padre_id = nodo_id = 0;
  81         padre = NULL;
  82         while (nodo) {
  83                 if (padre) free(padre);
  84                 padre = nodo;
  85                 padre_id = nodo_id;
  86                 b_leer_header(nodo, &header);
  87                 claves = b_leer_claves(nodo, &header);
  88                 i=0;
  89                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
  90                 if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, clave))) {
  91                         /* CLAVE DUPLICADA! */
  92                         return 0;
  93                 } else {
  94                         if (i == 0) {
  95                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
  96                                 nodo_id = header.hijo_izquierdo;
  97                         } else {
  98                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
  99                                 nodo_id = claves[i-1].hijo_derecho;
 100                         }
 101                 }
 102         }
 103
 104         if (nodo) free(nodo);
 105         nodo = padre;
 106         nodo_id = padre_id;
 107         b_insertar_en_nodo(idx, clave, dato, nodo_id, nodo, -1, -1);
 108         return 1; /* Agregar OK! */
 109 }
 110
 111 INDICE_DATO emufs_indice_b_buscar(INDICE *idx, CLAVE clave)
 112 {
 113         int i;
 114         INDICE_DATO ret;
 115         B_NodoHeader header;
 116         B_NodoEntry *claves;
 117         char *nodo, *tmp;
 118
 119         /* Leo la raiz */
 120         nodo = b_leer_nodo(idx, 0);
 121         while (nodo) {
 122                 b_leer_header(nodo, &header);
 123                 claves = b_leer_claves(nodo, &header);
 124                 i=0;
 125                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
 126                 if (emufs_indice_es_igual(idx, claves[i].clave, clave)) {
 127                                 ret = claves[i].dato;
 128                                 free(nodo);
 129                                 return ret;
 130                 } else {
 131                         tmp = nodo;
 132                         if (i == 0) {
 133                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
 134                         } else {
 135                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
 136                         }
 137                         free(tmp);
 138                 }
 139         }
 140
 141         /* Nodo no encontrado */
 142         ret.id = ret.bloque = -1;
 143         return ret;
 144 }
 145
 146 int emufs_indice_b_borrar(INDICE *idx, CLAVE k)
 147 {
 148         /* Busco el nodo que contiene la clave,si es que esta existe */
 149         char *nodo;
 150         int nodo_id, i;
 151         char encontrado=0;
 152         B_NodoHeader header;
 153         B_NodoEntry *claves;
 154
 155         nodo_id = 0; /* Tomo la raiz */
 156         nodo = b_leer_nodo(idx, nodo_id);
 157         PERR("Buscando clave a borrar");
 158         while (nodo && !encontrado) {
 159                 /* Obtengo los datos del nodo */
 160                 b_leer_header(nodo, &header);
 161                 claves = b_leer_claves(nodo, &header);
 162
 163                 i=0;
 164                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) i++;
 165
 166                 if ((emufs_indice_es_igual(idx, claves[i].clave, k)) && (i<header.cant))
 167                         encontrado = 1;
 168                 else {
 169                         if (i==0) {
 170                                 free(nodo);
 171                                 nodo_id = header.hijo_izquierdo;
 172                                 nodo = b_leer_nodo(idx, nodo_id);
 173                         } else {
 174                                 nodo_id = claves[i-1].hijo_derecho;
 175                                 free(nodo);
 176                                 nodo = b_leer_nodo(idx, nodo_id);
 177                         }
 178                 }
 179         }
 180
 181         if (encontrado) {
 182                 PERR("Clave encontrada, borrando ...");
 183                 b_borrar_clave(idx, nodo, nodo_id, k);
 184         } else {
 185                 PERR("Clave no encontrada");
 186         }
 187         return 0;
 188 }
 189
 190 static int b_ultimo_id(INDICE *idx)
 191 {
 192         int i;
 193         FILE *fp;
 194         fp = fopen(idx->filename, "r");
 195         fseek(fp, 0, SEEK_END);
 196         i = ftell(fp)/idx->tam_bloque;
 197         fclose(fp);
 198
 199         return i;
 200 }
 201
 202 static char *b_crear_nodo(INDICE *idx, int *id)
 203 {
 204         char *bloque;
 205         B_NodoHeader header;
 206
 207         (*id) = b_ultimo_id(idx);
 208
 209         header.cant = 0;
 210         header.nivel = 0;
 211         header.hijo_izquierdo = -1;
 212         header.padre = -1;
 213
 214         bloque = (char *)malloc(idx->tam_bloque);
 215         memset(bloque, -1, idx->tam_bloque);
 216         memcpy(bloque, &header, sizeof(B_NodoHeader));
 217
 218         b_grabar_nodo(idx, *id, bloque);
 219
 220         return bloque;
 221 }
 222
 223 static char *b_leer_nodo(INDICE *idx, int id)
 224 {
 225         FILE *fp;
 226         char *out;
 227
 228         if (id < 0) return NULL;
 229
 230         fp = fopen(idx->filename, "r");
 231         if (fp == NULL) return NULL;
 232
 233         fseek(fp, id*idx->tam_bloque, SEEK_SET);
 234
 235         out = (char *)malloc(idx->tam_bloque);
 236         if (out == NULL) {
 237                 fclose(fp);
 238                 return NULL;
 239         }
 240
 241         if (fread(out, 1, idx->tam_bloque, fp) != idx->tam_bloque) {
 242                 free(out);
 243                 /* No se puso leer el nodo */
 244                 fclose(fp);
 245                 return NULL;
 246         }
 247
 248         fclose(fp);
 249         return out;
 250 }
 251
 252 static void b_grabar_nodo(INDICE *idx, int id, char *data)
 253 {
 254         FILE *fp;
 255
 256 /*      if (id > b_ultimo_id()) {
 257                 printf("AGREGANDO AL FINAL\n");
 258                 fp = fopen(FILENAME, "a");
 259                 if (fp == NULL) {
 260                 _("No se pudo abrir archivo\n");
 261                         return;
 262                 }
 263         } else {
 264                 fp = fopen(FILENAME, "w");
 265                 if (fp == NULL) {
 266                 _("No se pudo abrir archivo\n");
 267                         return;
 268                 }
 269                 fseek(fp, id*BLOCK_SIZE, SEEK_SET);
 270                 printf("SOLO GUARDO DATA\n");
 271         }*/
 272
 273         fp = fopen(idx->filename, "r+");
 274         fseek(fp, id*idx->tam_bloque, SEEK_SET);
 275         fwrite(data, 1, idx->tam_bloque, fp);
 276         fclose(fp);
 277 }
 278
 279 static void b_leer_header(char *src, B_NodoHeader *header)
 280 {
 281         if (!src) return;
 282
 283         memcpy(header, src, sizeof(B_NodoHeader));
 284 }
 285
 286 static void b_actualizar_header(char *src, B_NodoHeader *header)
 287 {
 288         if (!src) return;
 289         memcpy(src, header, sizeof(B_NodoHeader));
 290 }
 291
 292 static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header)
 293 {
 294         return (B_NodoEntry *)(src+sizeof(B_NodoHeader));
 295 }
 296
 297 static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2)
 298 {
 299         char *padre, *nuevo;
 300         int nuevo_id;
 301         int i, j;
 302         static int rompi=0;
 303         char salir = 0;
 304         B_NodoHeader nodo_header, nuevo_header;
 305         B_NodoEntry *claves, *tmp_claves, *claves_nuevo;
 306
 307         do {
 308                 if (!nodo) {
 309                         /* CREAR NODO? */
 310                         nodo = b_crear_nodo(idx, &nodo_id);
 311                 }
 312                 b_leer_header(nodo, &nodo_header);
 313                 claves = b_leer_claves(nodo, &nodo_header);
 314
 315                 padre = b_leer_nodo(idx, nodo_header.padre);
 316
 317                 if (nodo_header.cant == CANT_HIJOS(idx)) {
 318                         int total;
 319                         /* TODO: Si es B*, hay que chequear si alguno de los 2
 320                          *       nodos hermanos pueden prestarme espacio (y
 321                          *       desplazar si es así). Si no pueden, hay que
 322                          *       hacer un split de 2 nodos en 3.
 323                          *       Si no es B*, hay que hacer lo que sigue:
 324                          */
 325                         nuevo = b_crear_nodo(idx, &nuevo_id);
 326                         i=0;
 327                         /* Creo una lista ordenada de los nodos a partir */
 328                         tmp_claves = (B_NodoEntry *)malloc(sizeof(B_NodoEntry)*(nodo_header.cant+1));
 329                         total = nodo_header.cant;
 330                         while ((i<nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) {
 331                                 tmp_claves[i] = claves[i];
 332                                 i++;
 333                         }
 334                         tmp_claves[i].clave = clave;
 335                         tmp_claves[i].dato = dato;
 336                         tmp_claves[i].hijo_derecho = hijo1;
 337                         tmp_claves[i+1].hijo_derecho = hijo2;
 338                         while (i < nodo_header.cant) {
 339                                 tmp_claves[i+1] = claves[i];
 340                                 i++;
 341                         }
 342
 343                         /* Asigno a cada nodo lo que corresponde */
 344                         b_leer_header(nuevo, &nuevo_header);
 345
 346                         nuevo_header.nivel = nodo_header.nivel;
 347                         nodo_header.cant = total/2;
 348                         nuevo_header.cant = total - nodo_header.cant;
 349
 350                         memset(claves, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 351                         for(j=0; j<nodo_header.cant; j++)
 352                                 claves[j] = tmp_claves[j];
 353
 354                         claves_nuevo = b_leer_claves(nuevo, &nuevo_header);
 355                         memset(claves_nuevo, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 356                         for(j=0; j<nuevo_header.cant; j++)
 357                                 claves_nuevo[j] = tmp_claves[j+total/2+1];
 358
 359                         b_actualizar_header(nodo, &nodo_header);
 360                         b_actualizar_header(nuevo, &nuevo_header);
 361
 362                         if (nodo_id != 0) {
 363                                 clave = tmp_claves[total/2].clave;
 364                                 /* XXX dato.bloque = nuevo_id; */
 365
 366                                 b_grabar_nodo(idx, nodo_id, nodo);
 367                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 368                                 free(nodo);
 369                                 free(nuevo);
 370                                 free(tmp_claves);
 371
 372                                 hijo1 = nodo_id;
 373                                 hijo2 = nuevo_id;
 374
 375                                 nodo = padre;
 376                                 nodo_id = nodo_header.padre;
 377                         } else {
 378                                 /* Oops, parti el raiz, y este debe quedar en 0, lo paso a otro bloque
 379                                  * y dejo el padre vacio
 380                                  */
 381                                 char *tmp_nuevo = b_crear_nodo(idx, &nodo_id);
 382                                 memcpy(tmp_nuevo, nodo, idx->tam_bloque);
 383                                 free(nodo);
 384                                 nodo = tmp_nuevo;
 385
 386                                 clave = tmp_claves[total/2].clave;
 387                                 /* XXX dato.bloque = nuevo_id; */
 388
 389                                 b_grabar_nodo(idx, nuevo_id+1, nodo);
 390                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 391
 392                                 free(nodo);
 393                                 free(nuevo);
 394                                 free(tmp_claves);
 395
 396                                 hijo1 = nuevo_id+1;
 397                                 hijo2 = nuevo_id;
 398
 399                                 /* Limpio al padre */
 400                                 nuevo = b_leer_nodo(idx, 0);
 401
 402                                 b_leer_header(nuevo, &nuevo_header);
 403                                 nuevo_header.cant = 0;
 404                                 nuevo_header.padre = -1;
 405                                 nuevo_header.nivel = nodo_header.nivel+1;
 406                                 memset(nuevo, -1, idx->tam_bloque);
 407                                 b_actualizar_header(nuevo, &nuevo_header);
 408                                 b_grabar_nodo(idx, 0, nuevo);
 409
 410                                 nodo_id = 0;
 411                                 nodo = nuevo;
 412                                 rompi = 1;
 413                         }
 414                 } else {
 415                         /* La clave entra en este nodo!! */
 416                         i = 0;
 417                         if (nodo_header.cant > 0) {
 418                                 while ((emufs_indice_es_menor(idx, claves[i].clave, clave)) && (i < nodo_header.cant)) i++;
 419                                 for(j=nodo_header.cant; j > i; j--)
 420                                         claves[j] = claves[j-1];
 421                         }
 422                         nodo_header.cant++;
 423                         claves[i].clave = clave;
 424                         claves[i].dato = dato;
 425                         claves[i].hijo_derecho = hijo2;
 426                         nodo_header.hijo_izquierdo = b_elegir_izquierdo(idx, nodo_header.hijo_izquierdo, hijo1);
 427
 428                         b_actualizar_header(nodo, &nodo_header);
 429                         b_grabar_nodo(idx, nodo_id, nodo);
 430
 431                         /* Debo actualizar los punteros al padre de los hijos */
 432                         if (hijo1 != -1) {
 433                                 nuevo = b_leer_nodo(idx, hijo1);
 434                                 if (nuevo != NULL) {
 435                                         b_leer_header(nuevo, &nuevo_header);
 436                                         nuevo_header.padre = nodo_id;
 437                                         b_actualizar_header(nuevo, &nuevo_header);
 438                                         b_grabar_nodo(idx, hijo1, nuevo);
 439                                         free(nuevo);
 440                                 } else printf("FUCK! hijo1=%d no existe!\n", hijo1);
 441                         }
 442                         if (hijo2 != -1) {
 443                                 nuevo = b_leer_nodo(idx, hijo2);
 444                                 if (nuevo != NULL) {
 445                                         b_leer_header(nuevo, &nuevo_header);
 446                                         nuevo_header.padre = nodo_id;
 447                                         b_actualizar_header(nuevo, &nuevo_header);
 448                                         b_grabar_nodo(idx, hijo2, nuevo);
 449                                         free(nuevo);
 450                                 } else printf("FUCK! hijo2=%d no existe!\n", hijo2);
 451                         }
 452                         salir = 1;
 453                 }
 454         } while (!salir);
 455 }
 456
 457 static int b_elegir_izquierdo(INDICE *idx, int a, int b)
 458 {
 459         int cual;
 460         char *nodo1, *nodo2;
 461         B_NodoHeader header1, header2;
 462         B_NodoEntry *claves1, *claves2;
 463
 464         if (a==-1) return b;
 465         if (b==-1) return a;
 466
 467         nodo1 = b_leer_nodo(idx, a);
 468         nodo2 = b_leer_nodo(idx, b);
 469
 470         b_leer_header(nodo1, &header1);
 471         b_leer_header(nodo2, &header2);
 472
 473         claves1 = b_leer_claves(nodo1, &header1);
 474         claves2 = b_leer_claves(nodo2, &header2);
 475
 476         if (emufs_indice_es_menor(idx, claves1[0].clave, claves2[0].clave))
 477                 cual = a;
 478         else
 479                 cual = b;
 480
 481         free(nodo1);
 482         free(nodo2);
 483         return cual;
 484 }
 485
 486 INDICE_DATO *emufs_indice_b_buscar_muchos(INDICE *idx, CLAVE clave, int *cant)
 487 {
 488         /* Si el indice es primario no tiene sentido hacer nada */
 489         if (idx->funcion == IND_PRIMARIO) {
 490                 *cant = 0;
 491                 return NULL;
 492         }
 493
 494         /* TODO Implementar indices con repeticion */
 495         return NULL;
 496 }
 497
 498 static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k)
 499 {
 500         int pos, actual_id, padre_id, i, pos_padre, izquierda_id, derecha_id;
 501         B_NodoHeader header, header_actual, header_padre, header_izq, header_der;
 502         B_NodoEntry *claves, *claves_actual, *claves_padre;/*, *claves_izq, *claves_der;*/
 503         char *actual, *padre, *izq, *der;
 504
 505         b_leer_header(nodo, &header);
 506         claves = b_leer_claves(nodo, &header);
 507
 508         pos = 0;
 509         /* Busco la posicion dentro de la lista de claves */
 510         while (emufs_indice_es_menor(idx, claves[pos].clave, k)) pos++;
 511
 512         /* Es el nodo una hoja? */
 513         if (header.hijo_izquierdo != -1) {
 514                 /* No!, es un nodo intermedio!! */
 515                 if (pos == 0)
 516                         actual = b_leer_nodo(idx, header.hijo_izquierdo);
 517                 else
 518                         actual = b_leer_nodo(idx, claves[pos+1].hijo_derecho);
 519
 520                 b_leer_header(actual, &header_actual);
 521                 while (header_actual.hijo_izquierdo != -1) {
 522                         actual_id = header_actual.hijo_izquierdo;
 523                         free(actual);
 524                         actual = b_leer_nodo(idx, actual_id);
 525                         b_leer_header(actual, &header_actual);
 526                 }
 527                 claves_actual = b_leer_claves(actual, &header);
 528
 529                 claves[pos] = claves_actual[0];
 530                 pos = 0;
 531                 b_grabar_nodo(idx, nodo_id, nodo);
 532         } else {
 533                 actual = nodo;
 534         }
 535
 536         /* Borro la clave */
 537         for(i=pos; i < header_actual.cant; i++) {
 538                 claves_actual[i] = claves_actual[i+1];
 539         }
 540         header_actual.cant--;
 541         /* Guardo los cambios */
 542         b_actualizar_header(actual, &header_actual);
 543         b_grabar_nodo(idx, actual_id, actual);
 544
 545         /* Se cumple la condicion de hijos? */
 546         if (header_actual.cant >= MIN_HIJOS(idx)) {
 547                 PERR("Borrar completo sin fundir");
 548                 return;
 549         }
 550
 551         /* Tengo que pasar datos o fundir nodos :-( */
 552         do {
 553                 padre_id = header.padre;
 554                 padre = b_leer_nodo(idx, padre_id);
 555                 b_leer_header(padre, &header_padre);
 556                 claves_padre = b_leer_claves(padre, &header_padre);
 557                 /* TODO Tengo el hijo_izquierdo para revisar!! XXX */
 558                 if (header_padre.hijo_izquierdo == actual_id) {
 559                         izquierda_id = -1; /* No tengo hermano izquierdo */
 560                         /* Mi hermano derecho es el primer nodo del padre */
 561                         derecha_id = claves_padre[0].hijo_derecho;
 562                         der = b_leer_nodo(idx, derecha_id);
 563                         b_leer_header(der, &header_der);
 564                 } else {
 565                         for(pos_padre=0; claves_padre[pos_padre].hijo_derecho != actual_id; pos_padre++)        {       }
 566
 567                         /* Busco mis hermanos a derecha e izquierda, si es que existen */
 568                         if (pos_padre >= 0) {
 569                                 if (pos_padre == 0)
 570                                         izquierda_id = header_padre.hijo_izquierdo;
 571                                 else
 572                                         izquierda_id = claves_padre[pos_padre-1].hijo_derecho;
 573                                 izq = b_leer_nodo(idx, izquierda_id);
 574                                 b_leer_header(izq, &header_izq);
 575                         } else {
 576                                 izquierda_id = -1;
 577                         }
 578                         if (pos_padre < header_padre.cant) {
 579                                 derecha_id = claves_padre[pos_padre+1].hijo_derecho;
 580                                 der = b_leer_nodo(idx, derecha_id);
 581                                 b_leer_header(der, &header_der);
 582                         } else {
 583                                 derecha_id = -1;
 584                         }
 585                 }
 586                 /* Intendo pasar una clave desde un hermano hacia mi */
 587                 if ((derecha_id != -1) && (header_der.cant > MIN_HIJOS(idx))) {
 588                         b_pasar_clave_derecha(der, derecha_id, padre, padre_id, actual, actual_id, pos_padre);
 589                 } else if ((izquierda_id != -1) && (header_izq.cant > MIN_HIJOS(idx))) {
 590                         b_pasar_clave_izquierda(izq, izquierda_id, padre, padre_id, actual, actual_id, pos_padre-1);
 591                 } else {
 592                         /* No pude pasar clave, tengo que fundir :-( */
 593                         if (derecha_id != -1) {
 594                                 b_fundir_nodo(actual, actual_id, padre, padre_id, der, derecha_id, pos_padre);
 595                         } else {
 596                                 b_fundir_nodo(izq, izquierda_id, padre, padre_id, actual, actual_id, pos_padre-1);
 597                         }
 598                 }
 599
 600                 /* TODO que guardo ?, todo ? */
 601                 b_grabar_nodo(idx, actual_id, actual);
 602                 b_grabar_nodo(idx, izquierda_id, izq);
 603                 b_grabar_nodo(idx, derecha_id, der);
 604                 b_grabar_nodo(idx, padre_id, padre);
 605                 if (actual_id != -1) free(actual);
 606                 /*if (padre_id != -1) free(padre);*/
 607                 if (derecha_id != -1) free(der);
 608                 if (izquierda_id != -1) free(izq);
 609                 actual = padre;
 610                 actual_id = padre_id;
 611         } while ((actual_id != -1) && (header_actual.cant < MIN_HIJOS(idx)));
 612 }
 613
 614 static void b_pasar_clave_derecha(char *der, int der_id, char *padre, int padre_id, char *nodo, int nodo_id, int pos_clave)
 615 {
 616         int i;
 617         B_NodoHeader h_der, h_padre, h_nodo;
 618         B_NodoEntry *c_der, *c_padre, *c_nodo;
 619
 620         b_leer_header(nodo, &h_nodo);
 621         c_nodo = b_leer_claves(nodo, &h_nodo);
 622         b_leer_header(der, &h_der);
 623         c_der = b_leer_claves(der, &h_der);
 624         b_leer_header(padre, &h_padre);
 625         c_padre = b_leer_claves(padre, &h_padre);
 626
 627         c_nodo[h_nodo.cant] = c_padre[pos_clave];
 628         c_nodo[h_nodo.cant].hijo_derecho = -1; /* XXX */
 629
 630         c_padre[pos_clave] = c_der[0];
 631         c_padre[pos_clave].hijo_derecho = der_id;
 632
 633         /* Muevo las claves de derecho */
 634         for(i=0; i<h_der.cant; i++) {
 635                 c_der[i] = c_der[i+1];
 636         }
 637         h_der.cant--;
 638         h_nodo.cant++;
 639
 640         b_actualizar_header(der, &h_der);
 641         b_actualizar_header(nodo, &h_nodo);
 642 }
 643
 644 static void b_pasar_clave_izquierda(char *izq, int izq_id, char *padre, int padre_id, char *nodo, int nodo_id, int pos_clave)
 645 {
 646         int i;
 647         B_NodoHeader h_izq, h_padre, h_nodo;
 648         B_NodoEntry *c_izq, *c_padre, *c_nodo;
 649
 650         b_leer_header(nodo, &h_nodo);
 651         c_nodo = b_leer_claves(nodo, &h_nodo);
 652         b_leer_header(izq, &h_izq);
 653         c_izq = b_leer_claves(izq, &h_izq);
 654         b_leer_header(padre, &h_padre);
 655         c_padre = b_leer_claves(padre, &h_padre);
 656
 657         for(i=h_nodo.cant; i>0;i++)
 658                 c_nodo[i] = c_nodo[i-1];
 659
 660         h_nodo.cant++;
 661         c_nodo[0] = c_padre[pos_clave];
 662         c_nodo[0].hijo_derecho = -1; /* XXX */
 663         c_padre[pos_clave] = c_izq[h_izq.cant-1];
 664         c_padre[pos_clave].hijo_derecho = izq_id;
 665         h_izq.cant--;
 666
 667         b_actualizar_header(izq, &h_izq);
 668         b_actualizar_header(padre, &h_padre);
 669         b_actualizar_header(nodo, &h_nodo);
 670 }
 671
 672 static void b_fundir_nodo(char *izq, int izq_id, char *padre, int padre_id, char *der, int der_id, int pos_clave)
 673 {
 674 }
 675