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