emufs/indice_b.c

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