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