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         b_insertar_en_nodo_con_lugar(idx, padre_entries[padre_pos].clave, padre_entries[padre_pos].dato,
 849                         der_id, der, der_h.hijo_izquierdo, entry.hijo_derecho);
 850         /* Reemplazo clave del padre por clave nueva */
 851         entry.hijo_derecho = der_id;
 852         padre_entries[padre_pos] = entry;
 853 }
 854
 855 void b_pedir_clave_izquierda(char *izq, int izq_id, char *padre, int padre_id, char *nodo, int nodo_id, int pos_clave)
 856 {
 857         int i;
 858         B_NodoHeader h_izq, h_padre, h_nodo;
 859         B_NodoEntry *c_izq, *c_padre, *c_nodo;
 860
 861         b_leer_header(nodo, &h_nodo);
 862         c_nodo = b_leer_claves(nodo, &h_nodo);
 863         b_leer_header(izq, &h_izq);
 864         c_izq = b_leer_claves(izq, &h_izq);
 865         b_leer_header(padre, &h_padre);
 866         c_padre = b_leer_claves(padre, &h_padre);
 867
 868         PERR("Muevo las claves");
 869         for(i=h_nodo.cant; i>0;i--)
 870                 c_nodo[i] = c_nodo[i-1];
 871
 872         h_nodo.cant++;
 873         PERR("Paso clave de padre a nodo");
 874         c_nodo[0] = c_padre[pos_clave];
 875         c_nodo[0].hijo_derecho = -1; /* XXX */
 876         PERR("Paso clave de izquierda a padre");
 877         c_padre[pos_clave] = c_izq[h_izq.cant-1];
 878         c_padre[pos_clave].hijo_derecho = nodo_id;
 879         h_izq.cant--;
 880
 881         PERR("ACTUALIZO")
 882         b_actualizar_header(izq, &h_izq);
 883         b_actualizar_header(padre, &h_padre);
 884         b_actualizar_header(nodo, &h_nodo);
 885         PERR("Salgo");
 886 }
 887
 888 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)
 889 {
 890         B_NodoHeader padre_h;
 891         B_NodoEntry* padre_entries;
 892         /* Leo claves y cabecera del nodo de la izquierda y del padre */
 893         b_leer_header(padre, &padre_h);
 894         padre_entries = b_leer_claves(padre, &padre_h);
 895         /* Inserto en el hijo izquirdo la clave del padre */
 896         b_insertar_en_nodo_con_lugar_sin_hijo_izq(idx, padre_entries[padre_pos].clave, padre_entries[padre_pos].dato,
 897                         izq_id, izq, id_entry_hijo_izq);
 898         /* Reemplazo clave del padre por clave nueva */
 899         entry.hijo_derecho = id_entry_nodo;
 900         padre_entries[padre_pos] = entry;
 901 }
 902
 903 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)
 904 {
 905         int i;
 906         B_NodoHeader h_izq, h_padre, h_der;
 907         B_NodoEntry *c_izq, *c_padre, *c_der;
 908
 909         b_leer_header(der, &h_der);
 910         c_der = b_leer_claves(der, &h_der);
 911         b_leer_header(izq, &h_izq);
 912         c_izq = b_leer_claves(izq, &h_izq);
 913         b_leer_header(padre, &h_padre);
 914         c_padre = b_leer_claves(padre, &h_padre);
 915
 916         c_izq[h_izq.cant] = c_padre[pos_padre];
 917         h_padre.cant--;
 918         for(i=pos_padre; i<h_padre.cant; i++)
 919                 c_padre[i] = c_padre[i+1];
 920         h_izq.cant++;
 921         for(i=0; i<h_der.cant; i++)
 922                 c_izq[h_izq.cant+i] = c_der[i];
 923
 924         h_izq.cant += h_der.cant;
 925
 926         b_actualizar_header(izq, &h_izq);
 927         b_actualizar_header(padre, &h_padre);
 928
 929         /* TODO Aca queda libre el nodo der, ver de recuperar! */
 930         memset(der, 'X', idx->tam_bloque);
 931         b_grabar_nodo(idx, der_id, der);
 932 }
 933
 934 static EMUFS_REG_ID b_insertar_dup_en_pos(INDICE *idx, INDICE_DATO pos, INDICE_DATO nuevo)
 935 {
 936         int cant;
 937         EMUFS_REG_SIZE tam;
 938         int error=0;
 939         INDICE_DATO *array;
 940         char *leido;
 941         CLAVE k;
 942
 943         /* Leo el contenido actual */
 944         k.i_clave = pos.id;
 945         error = 0;
 946         leido = (char *)idx->emu_mult->leer_registro(idx->emu_mult, k, &tam, &error);
 947
 948         /* Incremento en 1 la cantidad */
 949         if (leido != NULL)
 950                 cant = *((int *)leido);
 951         else
 952                 cant = 0;
 953         cant++;
 954
 955         /* Obtengo un nuevo lugar para el dato nuevo */
 956         /* Aca todo bien, si leido es NULL se compota como malloc */
 957         leido = realloc(leido, cant*sizeof(INDICE_DATO)+sizeof(int));
 958         array = (INDICE_DATO *)(leido+sizeof(int));
 959
 960         /* Pongo el dato nuevo */
 961         array[cant-1] = nuevo;
 962
 963         /* Actualizo la cantidad */
 964         (*((int *)leido)) = cant;
 965
 966         /* Salvo */
 967         if (k.i_clave == -1) {
 968                 /* Creo uno nuevo */
 969                 error = 0;
 970                 k.i_clave = idx->emu_mult->grabar_registro(idx->emu_mult,
 971                         leido,
 972                         cant*sizeof(INDICE_DATO)+sizeof(int),
 973                         &error
 974                 );
 975                 if (k.i_clave == -1) PERR("ALGO NO GRABO BIEN!!");
 976         } else {
 977                 /* Modifico el que ya existia! */
 978                 INDICE_DATO dummy;
 979                 error = 0;
 980                 idx->emu_mult->modificar_registro(idx->emu_mult,
 981                         k,
 982                         leido,
 983                         cant*sizeof(INDICE_DATO)+sizeof(int),
 984                         &error,
 985                         dummy
 986                 );
 987         }
 988         /* Clean up! */
 989         free(leido);
 990         return k.i_clave;
 991 }
 992
 993 char *abreviar(char *primera, char *actual, int *iguales)
 994 {
 995         (*iguales) = 0;
 996         while (((*primera) != '\0') && ((*actual) != '\0')) {
 997                 if ((*primera) == (*actual)) {
 998                         primera++;
 999                         actual++;
1000                         (*iguales)++;
1001                 } else {
1002                         /* No coinciden mas! */
1003                         break;
1004                 }
1005         }
1006
1007         return actual;
1008 }
1009
1010 static void abreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header)
1011 {
1012         char *primera, *actual, *resto, salvar[100];
1013         EMUFS_REG_SIZE size;
1014         int error, i;
1015         int iguales;
1016
1017         /* Agarro la primer clave entera como referencia */
1018         primera = (char *)idx->emu_string->leer_registro(idx->emu_string, array[0].clave, &size, &error);
1019         for(i=1; i<header->cant; i++) {
1020                 actual = (char *)idx->emu_string->leer_registro(idx->emu_string, array[i].clave, &size, &error);
1021                 if (*actual == '*') {
1022                         free(actual);
1023                         continue;
1024                 }
1025                 resto = abreviar(primera, actual, &iguales);
1026                 /* Para que tenga sentido abreviar tengo que tener
1027                  * mas de 2 letras iguales, si no no gano nada y complica las cosas
1028                  */
1029                 if (iguales > 1) {
1030                         INDICE_DATO dummy1;
1031                         sprintf(salvar, "%d|%s", iguales, resto);
1032                         free(actual);
1033                         error = 0;
1034                         idx->emu_string->modificar_registro(idx->emu_string, array[i].clave, salvar, strlen(salvar)+1, &error, dummy1);
1035                 } else {
1036                         free(primera);
1037                         primera = actual;
1038                 }
1039         }
1040
1041         free(primera);
1042 }
1043
1044 static void desabreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header)
1045 {
1046         char *primera, *actual, *resto, salvar[100];
1047         EMUFS_REG_SIZE size;
1048         int error, i;
1049         int iguales;
1050
1051         /* Agarro la primer clave entera como referencia */
1052         primera = (char *)idx->emu_string->leer_registro(idx->emu_string, array[0].clave, &size, &error);
1053         for(i=1; i<header->cant; i++) {
1054                 actual = (char *)idx->emu_string->leer_registro(idx->emu_string, array[i].clave, &size, &error);
1055                 if (*actual == '*') {
1056                         free(actual);
1057                         continue;
1058                 }
1059                 iguales = strtol(actual, &resto, 10);
1060                 if ((iguales > 0) && (*resto == '|')) {
1061                         INDICE_DATO dummy2;
1062                         strncpy(salvar, primera, iguales);
1063                         salvar[iguales] = '\0';
1064                         strcat(salvar, resto+1); /* +1 para saltar el separador */
1065                         idx->emu_string->modificar_registro(idx->emu_string, array[i].clave, salvar, strlen(salvar)+1, &error, dummy2);
1066                         free(actual);
1067                 } else {
1068                         free(primera);
1069                         primera = actual;
1070                 }
1071         }
1072
1073         free(primera);
1074 }
1075
1076 void insertar_ordenado(INDICE *idx, B_NodoEntry *buffer, int cant, B_NodoEntry nuevo_entry)
1077 {
1078         int i, pos;
1079         for(i=0; (i<cant) && emufs_indice_es_menor(idx, buffer[i].clave, nuevo_entry.clave); i++) {}
1080         pos = i;
1081
1082         for(i=cant; i>pos; i--)
1083                 buffer[i] = buffer[i-1];
1084
1085         buffer[pos] = nuevo_entry;
1086 }
1087
1088 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)
1089 {
1090         PERR("PARTIR 2 EN 3");
1091         B_NodoEntry *buffer;
1092         char *izq, *der, *padre, *nuevo;
1093         B_NodoEntry *c_der, *c_izq, *c_nuevo, prom1, prom2;
1094         B_NodoHeader h_der, h_izq, h_nuevo;
1095         int i, j, nodo_nuevo;
1096         int cant_claves;
1097
1098         /* Leo los nodos y los datos */
1099         der = b_leer_nodo(idx, nodo_der);
1100         izq = b_leer_nodo(idx, nodo_izq);
1101
1102         b_leer_header(der, &h_der);
1103         b_leer_header(izq, &h_izq);
1104
1105         c_der = b_leer_claves(der, &h_der);
1106         c_izq = b_leer_claves(izq, &h_izq);
1107
1108         cant_claves = 2*CANT_HIJOS(idx)+2;
1109         buffer = malloc(cant_claves*sizeof(B_NodoEntry));
1110
1111         for(i=0, j=0; i<h_izq.cant; i++, j++)
1112                 buffer[j] = c_izq[i];
1113
1114         buffer[j++] = padre_entry;
1115
1116         for(i=0; i<h_der.cant; i++, j++)
1117                 buffer[j] = c_der[i];
1118
1119         insertar_ordenado(idx, buffer, cant_claves-1, nuevo_entry);
1120
1121         nuevo = b_crear_nodo(idx, &nodo_nuevo);
1122         b_leer_header(nuevo, &h_nuevo);
1123         c_nuevo = b_leer_claves(nuevo, &h_nuevo);
1124
1125         /* lleno el lado derecho e izquierdo */
1126         for(i=0, j=0; i<cant_claves/3; i++, j++)
1127                 c_izq[j] = buffer[i];
1128         prom1 = buffer[i++];
1129         h_izq.cant = j;
1130         for(j=0; i<2*cant_claves/3; i++, j++)
1131                 c_der[j] = buffer[i];
1132         h_der.cant = j;
1133         prom2 = buffer[i++];
1134         for(j=0; i<cant_claves; i++,j++)
1135                 c_nuevo[j] = buffer[i];
1136         h_nuevo.cant = j;
1137
1138         /* Actualizo headers y salvo */
1139         b_actualizar_header(der, &h_der);
1140         b_actualizar_header(izq, &h_izq);
1141         b_actualizar_header(nuevo, &h_nuevo);
1142         b_grabar_nodo(idx, nodo_izq, izq);
1143         b_grabar_nodo(idx, nodo_der, der);
1144         b_grabar_nodo(idx, nodo_nuevo, nuevo);
1145
1146         free(der);
1147         free(izq);
1148         free(nuevo);
1149         padre = b_leer_nodo(idx, id_padre);
1150         b_insertar_en_nodo(idx, prom1.clave, prom1.dato, id_padre, padre, nodo_izq, nodo_der);
1151         b_insertar_en_nodo(idx, prom2.clave, prom2.dato, id_padre, padre, nodo_der, nodo_nuevo);
1152
1153         /*
1154          * PSEUDOCODIGO    TODO FIXME XXX TODO FIXME XXX TODO FIXME XXX
1155          *
1156          * // Creo un buffer con todos los entries (las claves) de ambos nodos, mas el padre y la nueva, ordenadas
1157          * buffer_size = 2*MAX_ENTRIES+2
1158          * buffer = new entries[buffer_size]
1159          * copiar_entries(buffer, nodo_izq)
1160          * concatenar_entries(buffer, padre)
1161          * concatenar_entries(buffer, nodo_der)
1162          * insertar_ordenado(buffer, nuevo_entry)
1163          * // Borro los 2 nodos viejos para reutilizarlos y creo el tercero
1164          * borrar_entries(nodo_izq)
1165          * borrar_entries(nodo_der)
1166          * nodo_nuevo = new nodo()
1167          * // Copio de a tercios del buffer en los nuevos nodos, excluyendo las 2 claves 'limítrofes' para insertarlas luego en el padre
1168          * copiar_algunos_entries(nodo_izq, buffer, 0, (buffer_size/3)-1)
1169          * entry_promovido1 = buffer[buffer_size/3]
1170          * copiar_algunos_entries(nodo_izq, buffer, (buffer_size/3)+1, 2*(buffer_size/3))
1171          * entry_promovido2 = buffer[(2*(buffer_size/3))+1]
1172          * copiar_algunos_entries(nodo_nuevo, buffer, (2*(buffer_size/3))+2, buffer_size-1))
1173          * // Finalmente inserto (recursivamente, porque esta funcion es llamada desde b_insertar_en_nodo()) las claves promovidas en el padre
1174          * b_insertar_en_nodo(idx, entry_promovido.clave, entry_promovido.dato, entry_promovido.id, entry_promovido, nodo_izq.id, nodo_der.id)
1175          * b_insertar_en_nodo(idx, entry_promovido.clave, entry_promovido.dato, entry_promovido.id, entry_promovido, nodo_der.id, nodo_nuevo.id)
1176          *
1177          */
1178 }
1179
1180 CLAVE emufs_indice_b_obtener_menor_clave(INDICE *idx)
1181 {
1182         B_NodoHeader header;
1183         B_NodoEntry *claves;
1184         CLAVE k;
1185         char *nodo;
1186
1187         nodo = b_leer_nodo(idx, 0);
1188         b_leer_header(nodo, &header);
1189         /* Tengo que ir siempre a la izquierda hasta una hora */
1190         while (header.hijo_izquierdo != -1) {
1191                 free(nodo);
1192                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
1193                 b_leer_header(nodo, &header);
1194         }
1195
1196         /* Listo, ahora solo leo la primer clave */
1197         claves = b_leer_claves(nodo, &header);
1198         k = claves[0].clave;
1199         free(nodo);
1200         return k;
1201 }
1202
1203 CLAVE emufs_indice_b_obtener_mayor_clave(INDICE *idx)
1204 {
1205         B_NodoHeader header;
1206         B_NodoEntry *claves;
1207         CLAVE k;
1208         int i;
1209         char *nodo;
1210
1211         nodo = b_leer_nodo(idx, 0);
1212         b_leer_header(nodo, &header);
1213         claves = b_leer_claves(nodo, &header);
1214         /* Tengo que ir siempre a la izquierda hasta una hora */
1215         while (claves[header.cant-1].hijo_derecho != -1) {
1216                 i = claves[header.cant-1].hijo_derecho;
1217                 free(nodo);
1218                 nodo = b_leer_nodo(idx, i);
1219                 b_leer_header(nodo, &header);
1220                 claves = b_leer_claves(nodo, &header);
1221         }
1222
1223         /* Listo, ahora solo leo la primer clave */
1224         k = claves[header.cant-1].clave;
1225         free(nodo);
1226         return k;
1227 }
1228
1229 CLAVE emufs_indice_b_obtener_sig_clave(INDICE *idx, CLAVE k)
1230 {
1231         int i;
1232         B_NodoHeader header;
1233         B_NodoEntry *claves;
1234         char *nodo, *tmp;
1235         int nodo_id;
1236         CLAVE salida;
1237
1238         /* Primero busco la clave pasada por parametro */
1239         nodo = b_leer_nodo(idx, 0);
1240         nodo_id = 0;
1241         while (nodo) {
1242                 b_leer_header(nodo, &header);
1243                 claves = b_leer_claves(nodo, &header);
1244                 i=0;
1245                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) i++;
1246                 if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, k))) {
1247                                 /* LA ENCONTRE! , ahora busco la siguiente clave!! */
1248                                 fprintf(stderr, "Me encontre en pos %d en el padre\n", i);
1249                                 if ((i+1)<header.cant) {
1250                                         PERR("Joya, hay lugar a la derecha");
1251                                         if (claves[i].hijo_derecho == -1) {
1252                                                 PERR("Y soy hoja!!");
1253                                                 /* Joya!, fue facil, la siguiente va en camino! */
1254                                                 salida = claves[i+1].clave;
1255                                                 free(nodo);
1256                                                 return salida;
1257                                         }
1258
1259                                         PERR("No soy hoja, busco la hoja de menor");
1260                                         /* Mmmmm ... la siguiente esta en uno de mis hijo */
1261                                         /* Necesito la mas chica de las siguientes, para eso
1262                                          * me voy a mi hijo derecho y de ahi bajo siempre
1263                                          * hacia la izquierda hacia una hoja */
1264                                         i = claves[i].hijo_derecho;
1265                                         free(nodo);
1266                                         nodo = b_leer_nodo(idx, i);
1267                                         b_leer_header(nodo, &header);
1268                                         while (header.hijo_izquierdo != -1) {
1269                                                 free(nodo);
1270                                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
1271                                                 b_leer_header(nodo, &header);
1272                                         }
1273                                         claves = b_leer_claves(nodo, &header);
1274                                         salida = claves[0].clave;
1275                                         free(nodo);
1276                                         return salida;
1277                                 }
1278
1279                                 PERR("Fuck, tengo que ir otro nodo a buscar");
1280                                 /* Fuck, la siguiente clave la tengo que sacar de padre */
1281                                 /* Busco al mi padre, perdido en un maremoto hace mucho,muchos
1282                                  * años
1283                                  */
1284                                 free(nodo);
1285                                 if (header.padre == -1) {
1286                                         salida.i_clave = -1;
1287                                         return salida;
1288                                 }
1289                                 nodo = b_leer_nodo(idx, header.padre);
1290                                 b_leer_header(nodo, &header);
1291                                 claves = b_leer_claves(nodo, &header);
1292                                 i = 0;
1293                                 PERR("Busco mi siguiente en mi padre");
1294                                 fprintf(stderr, "Padre tiene %d claves\n", header.cant);
1295                                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) {
1296                                         i++;
1297                                         fprintf(stderr, "Proximo i : %d\n", i);
1298                                 }
1299                                 if (i<header.cant) {
1300                                         PERR("Siguiente clave encontrada");
1301                                         salida = claves[i].clave;
1302                                 } else {
1303                                         /* No hay mas claves! */
1304                                         PERR("Busque y busque pero no aparecio");
1305                                         salida.i_clave = -1;
1306                                 }
1307                                 return salida;
1308                 } else {
1309                         tmp = nodo;
1310                         b_grabar_nodo(idx, nodo_id, nodo);
1311                         if (i == 0) {
1312                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
1313                                 nodo_id = header.hijo_izquierdo;
1314                         } else {
1315                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
1316                                 nodo_id = claves[i-1].hijo_derecho;
1317                         }
1318                         free(tmp);
1319                 }
1320         }
1321
1322         /* No encontre la clave pasada, no existe */
1323         PERR("No encontre la clave pasada!!");
1324         salida.i_clave = -1;
1325         return salida;
1326 }
1327
1328 int b_borrar_dup_clave(INDICE *idx, INDICE_DATO k_dato, INDICE_DATO dato)
1329 {
1330         int cant, pos, i;
1331         EMUFS_REG_SIZE tam;
1332         int error=0;
1333         INDICE_DATO *array;
1334         INDICE_DATO dummy1;
1335         char *leido;
1336         CLAVE k;
1337
1338         /* Leo el contenido actual */
1339         error = 0;
1340         k.i_clave = k_dato.id;
1341         leido = (char *)idx->emu_mult->leer_registro(idx->emu_mult, k, &tam, &error);
1342
1343         if (leido == NULL) {
1344                 PERR("LEI CUALQUIER COSA, BUG?");
1345                 return 1;
1346         }
1347
1348         cant = *((int *)leido);
1349
1350         /* Obtengo un nuevo lugar para el dato nuevo */
1351         array = (INDICE_DATO *)(leido+sizeof(int));
1352
1353         /* busco pos de dato en array */
1354         for(pos=0; pos<cant; pos++) {
1355                 if (array[pos].id == dato.id) break;
1356         }
1357
1358         for(i=pos; i<cant-1; i++)
1359                 array[pos] = array[pos+1];
1360
1361         cant--;
1362
1363         if (cant == 0) {
1364                 free(leido);
1365                 /* No tengo mas cosas en esta clave, la borro */
1366                 PERR("EL REGISTRO MULTIPLE QUEDO VACIO, ELIMINANDO");
1367                 idx->emu_mult->borrar_registro(idx->emu_mult, k, dummy1);
1368                 return 0;
1369         }
1370
1371         /* Quito el elemento */
1372         leido = realloc(leido, sizeof(int)+cant*sizeof(INDICE_DATO));
1373
1374         /* Actualizo la cantidad */
1375         (*((int *)leido)) = cant;
1376
1377         error = 0;
1378         idx->emu_mult->modificar_registro(idx->emu_mult,
1379                 k,
1380                 leido,
1381                 cant*sizeof(INDICE_DATO)+sizeof(int),
1382                 &error,
1383                 dummy1
1384         );
1385
1386         free(leido);
1387
1388         return cant;
1389 }
1390
1391 #include "indice_b_asc.c"
1392