emufs/indice_b.c

   1
   2 #include "indice_b.h"
   3 #include "common.h"
   4 #include "emufs.h"
   5 #include <curses.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 /** Lee un nodo desde el archivo */
  18 static char *b_leer_nodo(INDICE *idx, int id);
  19 /** Crea un nodo en el archivo y lo retorna. En i se pone el ID asignado */
  20 static char *b_crear_nodo(INDICE *idx, int *i);
  21 /** Lee el header de un nodo y lo guarda en header */
  22 static void b_leer_header(char *src, B_NodoHeader *header);
  23 /** Actualiza el header de un nodo desde header */
  24 static void b_actualizar_header(char *src, B_NodoHeader *header);
  25 /** Retorna el array de claves del nodo (esta data modifica directamente el bloque
  26  *  por eso no es necesario usar un actualizar_claves
  27  */
  28 static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header);
  29 /** Inserta una clave en el nodo de manera iterativa.
  30  * \param idx Índice en donde insertar la clave.
  31  * \param clave Clave a insertar.
  32  * \param dato Dato a insertar
  33  * \param nodo_id Id del nodo en el cual insertar la nueva clave.
  34  * \param nodo FIXME Nodo en donde insertar??? No entiendo por que char*.
  35  * \param hijo1 Id del nodo hijo de la izquierda del insertado.
  36  * \param hijo2 Id del nodo hijo de la derecha del insertado.
  37  */
  38 static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo_izq, int hijo_der);
  39 /** Inserta en un nodo en el que se sabe positivamente que hay lugar. */
  40 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);
  41 /** Borra una clave del arbol */
  42 static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k);
  43 /** Le pide al hermano derecho del nodo una clave cuando se eliminan claves */
  44 static void b_pedir_clave_derecha(char *, int, char *, int, char *, int, int);
  45 /** Le pide al hermano izquierdo una clave cuando se eliminan claves */
  46 static void b_pedir_clave_izquierda(char *, int, char *, int, char *, int, int);
  47 /** Le pasa al hermano derecho del nodo una clave cuando se insertan claves */
  48 static void b_pasar_clave_a_derecha(INDICE*, char*, int, char*, int, int, B_NodoEntry);
  49 /** Le pasa al hermano izquierdo una clave cuando se insertan claves */
  50 static void b_pasar_clave_a_izquierda(INDICE*, char*, int, char*, int, int, B_NodoEntry, int, int);
  51 /** Junta 2 nodos y hace uno solo */
  52 static void b_fundir_nodo(char *, int, char *, int, char *, int, int);
  53
  54 static EMUFS_REG_ID b_insertar_dup_en_pos(INDICE *idx, INDICE_DATO pos, INDICE_DATO nuevo);
  55
  56 static void abreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header);
  57 static void desabreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header);
  58
  59 void emufs_indice_b_crear(INDICE *idx)
  60 {
  61         FILE *fp;
  62         char *bloque;
  63         B_NodoHeader header;
  64
  65         header.cant = 0;
  66         header.nivel = 0;
  67         header.padre = -1;
  68         header.hijo_izquierdo = -1;
  69
  70         fp = fopen(idx->filename, "w");
  71         if (fp == NULL) {
  72                 PERR("Error al crear el archivo");
  73                 return;
  74         }
  75
  76         /* Creo el archivo con el Nodo raiz */
  77         bloque = (char *)malloc(idx->tam_bloque);
  78         memset(bloque, -1, idx->tam_bloque);
  79
  80         memcpy(bloque, &header, sizeof(B_NodoHeader));
  81
  82         fwrite(bloque, idx->tam_bloque, 1, fp);
  83         fclose(fp);
  84 }
  85
  86 int emufs_indice_b_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato)
  87 {
  88         int i, nodo_id, padre_id;
  89         B_NodoHeader header;
  90         B_NodoEntry *claves;
  91         char *nodo, *padre;
  92         INDICE_DATO dummy;
  93
  94         /* Leo la raiz */
  95         nodo = b_leer_nodo(idx, 0);
  96         padre_id = nodo_id = 0;
  97         padre = NULL;
  98         while (nodo) {
  99                 if (padre) free(padre);
 100                 padre = nodo;
 101                 padre_id = nodo_id;
 102                 b_leer_header(nodo, &header);
 103                 claves = b_leer_claves(nodo, &header);
 104                 i=0;
 105                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
 106                 if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, clave))) {
 107                         if (idx->funcion == IND_PRIMARIO) {
 108                                 PERR("Indice primario no puede contener claves duplicadas!");
 109                                 PERR(idx->nombre);
 110                                 return 0;
 111                         }
 112
 113                         /* TODO : Implementar carga de valor en clave duplicada! */
 114                         b_insertar_dup_en_pos(idx, claves[i].dato, dato);
 115
 116                         if (idx->tipo_dato == IDX_STRING) {
 117                                 /* Tengo que sacar el texto repetido del archivo de textos */
 118                                 idx->emu_string->borrar_registro(idx->emu_string, clave);
 119                         }
 120                         return 1;
 121                 } else {
 122                         if (i == 0) {
 123                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
 124                                 nodo_id = header.hijo_izquierdo;
 125                         } else {
 126                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
 127                                 nodo_id = claves[i-1].hijo_derecho;
 128                         }
 129                 }
 130         }
 131
 132         if (nodo) free(nodo);
 133         nodo = padre;
 134         nodo_id = padre_id;
 135
 136         if (idx->funcion != IND_PRIMARIO) {
 137                 /* Agrego el DATO real al archivo de claves repetiras
 138                  * y me guardo el ID para poner en el indice
 139                  */
 140                 dummy.id = -1;
 141                 dato.id = b_insertar_dup_en_pos(idx, dummy, dato);
 142         }
 143
 144         b_insertar_en_nodo(idx, clave, dato, nodo_id, nodo, -1, -1);
 145         return 1; /* Agregar OK! */
 146 }
 147
 148 INDICE_DATO emufs_indice_b_buscar(INDICE *idx, CLAVE clave)
 149 {
 150         int i;
 151         INDICE_DATO ret;
 152         B_NodoHeader header;
 153         B_NodoEntry *claves;
 154         char *nodo, *tmp;
 155         int nodo_id;
 156
 157         /* Leo la raiz */
 158         nodo = b_leer_nodo(idx, 0);
 159         nodo_id = 0;
 160         while (nodo) {
 161                 b_leer_header(nodo, &header);
 162                 claves = b_leer_claves(nodo, &header);
 163                 i=0;
 164                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
 165                 if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, clave))) {
 166                                 ret = claves[i].dato;
 167                                 b_grabar_nodo(idx, nodo_id, nodo);
 168                                 free(nodo);
 169                                 return ret;
 170                 } else {
 171                         tmp = nodo;
 172                         b_grabar_nodo(idx, nodo_id, nodo);
 173                         if (i == 0) {
 174                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
 175                                 nodo_id = header.hijo_izquierdo;
 176                         } else {
 177                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
 178                                 nodo_id = claves[i-1].hijo_derecho;
 179                         }
 180                         free(tmp);
 181                 }
 182         }
 183
 184         /* Nodo no encontrado */
 185         ret.id = ret.bloque = -1;
 186         return ret;
 187 }
 188
 189 int emufs_indice_b_borrar(INDICE *idx, CLAVE k)
 190 {
 191         /* Busco el nodo que contiene la clave,si es que esta existe */
 192         char *nodo;
 193         int nodo_id, i;
 194         char encontrado=0;
 195         B_NodoHeader header;
 196         B_NodoEntry *claves;
 197
 198         nodo_id = 0; /* Tomo la raiz */
 199         nodo = b_leer_nodo(idx, nodo_id);
 200         while (nodo && !encontrado) {
 201                 /* Obtengo los datos del nodo */
 202                 b_leer_header(nodo, &header);
 203                 claves = b_leer_claves(nodo, &header);
 204
 205                 i=0;
 206                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) i++;
 207
 208                 if ((emufs_indice_es_igual(idx, claves[i].clave, k)) && (i<header.cant))
 209                         encontrado = 1;
 210                 else {
 211                         if (i==0) {
 212                                 free(nodo);
 213                                 nodo_id = header.hijo_izquierdo;
 214                                 nodo = b_leer_nodo(idx, nodo_id);
 215                         } else {
 216                                 nodo_id = claves[i-1].hijo_derecho;
 217                                 free(nodo);
 218                                 nodo = b_leer_nodo(idx, nodo_id);
 219                         }
 220                 }
 221         }
 222
 223         if (encontrado) {
 224                 PERR("Clave encontrada, borrando ...");
 225                 b_borrar_clave(idx, nodo, nodo_id, k);
 226         } else {
 227                 PERR("Clave no encontrada");
 228         }
 229         return 0;
 230 }
 231
 232 static int b_ultimo_id(INDICE *idx)
 233 {
 234         int i;
 235         FILE *fp;
 236         fp = fopen(idx->filename, "r");
 237         fseek(fp, 0, SEEK_END);
 238         i = ftell(fp)/idx->tam_bloque;
 239         fclose(fp);
 240
 241         return i;
 242 }
 243
 244 static char *b_crear_nodo(INDICE *idx, int *id)
 245 {
 246         char *bloque;
 247         B_NodoHeader header;
 248
 249         (*id) = b_ultimo_id(idx);
 250
 251         header.cant = 0;
 252         header.nivel = 0;
 253         header.hijo_izquierdo = -1;
 254         header.padre = -1;
 255
 256         bloque = (char *)malloc(idx->tam_bloque);
 257         memset(bloque, -1, idx->tam_bloque);
 258         memcpy(bloque, &header, sizeof(B_NodoHeader));
 259
 260         b_grabar_nodo(idx, *id, bloque);
 261
 262         return bloque;
 263 }
 264
 265 static char *b_leer_nodo(INDICE *idx, int id)
 266 {
 267         FILE *fp;
 268         char *out;
 269         B_NodoHeader header;
 270         B_NodoEntry *claves;
 271
 272         if (id < 0) return NULL;
 273
 274         fp = fopen(idx->filename, "r");
 275         if (fp == NULL) return NULL;
 276
 277         fseek(fp, id*idx->tam_bloque, SEEK_SET);
 278
 279         out = (char *)malloc(idx->tam_bloque);
 280         if (out == NULL) {
 281                 fclose(fp);
 282                 return NULL;
 283         }
 284
 285         if (fread(out, 1, idx->tam_bloque, fp) != idx->tam_bloque) {
 286                 free(out);
 287                 /* No se puso leer el nodo */
 288                 fclose(fp);
 289                 return NULL;
 290         }
 291
 292         /* Si estoy manejando string tengo que sacar las abreviaturas */
 293         if (idx->tipo_dato == IDX_STRING) {
 294                 b_leer_header(out, &header);
 295                 claves = b_leer_claves(out, &header);
 296                 desabreviar_claves(idx, claves, &header);
 297         }
 298         fclose(fp);
 299         return out;
 300 }
 301
 302 static void b_grabar_nodo(INDICE *idx, int id, char *data)
 303 {
 304         FILE *fp;
 305         B_NodoHeader header;
 306         B_NodoEntry *claves;
 307
 308         /* Si las claves son de tipo string debo abreviar antes de guardar */
 309         if (idx->tipo_dato == IDX_STRING) {
 310                 b_leer_header(data, &header);
 311                 claves = b_leer_claves(data, &header);
 312                 abreviar_claves(idx, claves, &header);
 313         }
 314         fp = fopen(idx->filename, "r+");
 315         fseek(fp, id*idx->tam_bloque, SEEK_SET);
 316         fwrite(data, 1, idx->tam_bloque, fp);
 317         fclose(fp);
 318 }
 319
 320 static void b_leer_header(char *src, B_NodoHeader *header)
 321 {
 322         if (!src) return;
 323
 324         memcpy(header, src, sizeof(B_NodoHeader));
 325 }
 326
 327 static void b_actualizar_header(char *src, B_NodoHeader *header)
 328 {
 329         if (!src) return;
 330         memcpy(src, header, sizeof(B_NodoHeader));
 331 }
 332
 333 static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header)
 334 {
 335         return (B_NodoEntry *)(src+sizeof(B_NodoHeader));
 336 }
 337
 338 static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2)
 339 {
 340         char *padre, *nuevo;
 341         int nuevo_id;
 342         int i, j;
 343         static int rompi=0;
 344         char salir = 0;
 345         B_NodoHeader nodo_header, nuevo_header;
 346         B_NodoEntry *claves, *tmp_claves, *claves_nuevo;
 347
 348         do {
 349                 if (!nodo) {
 350                         /* CREAR NODO? */
 351                         nodo = b_crear_nodo(idx, &nodo_id);
 352                 }
 353                 b_leer_header(nodo, &nodo_header);
 354                 claves = b_leer_claves(nodo, &nodo_header);
 355
 356                 padre = b_leer_nodo(idx, nodo_header.padre);
 357
 358                 if (nodo_header.cant == CANT_HIJOS(idx)) {
 359                         int total;
 360                         /* TODO: Si es B*, hay que chequear si alguno de los 2
 361                          *       nodos hermanos pueden prestarme espacio (y
 362                          *       desplazar si es así). Si no pueden, hay que
 363                          *       hacer un split de 2 nodos en 3.
 364                          *       Si no es B*, hay que hacer lo que sigue:
 365                          */
 366                         nuevo = b_crear_nodo(idx, &nuevo_id);
 367                         i=0;
 368                         /* Creo una lista ordenada de los nodos a partir */
 369                         tmp_claves = (B_NodoEntry *)malloc(sizeof(B_NodoEntry)*(nodo_header.cant+1));
 370                         total = nodo_header.cant+1;
 371                         while ((i<nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) {
 372                                 tmp_claves[i] = claves[i];
 373                                 i++;
 374                         }
 375                         tmp_claves[i].clave = clave;
 376                         tmp_claves[i].dato = dato;
 377                         /*tmp_claves[i].hijo_derecho = hijo1;*/
 378                         if (i==0) {
 379                                 nodo_header.hijo_izquierdo = hijo1;
 380                                 tmp_claves[i].hijo_derecho = hijo2;
 381                         } else {
 382                                 tmp_claves[i-1].hijo_derecho = hijo1;
 383                                 tmp_claves[i].hijo_derecho = hijo2;
 384                         }
 385                         while (i < nodo_header.cant) {
 386                                 tmp_claves[i+1] = claves[i];
 387                                 i++;
 388                         }
 389
 390                         /* Asigno a cada nodo lo que corresponde */
 391                         b_leer_header(nuevo, &nuevo_header);
 392
 393                         nuevo_header.nivel = nodo_header.nivel;
 394                         nodo_header.cant = total/2;
 395                         nuevo_header.cant = (total-1) - nodo_header.cant;
 396
 397                         memset(claves, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 398                         for(j=0; j<nodo_header.cant; j++)
 399                                 claves[j] = tmp_claves[j];
 400
 401                         claves_nuevo = b_leer_claves(nuevo, &nuevo_header);
 402                         memset(claves_nuevo, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 403                         for(j=0; j<nuevo_header.cant; j++)
 404                                 claves_nuevo[j] = tmp_claves[j+total/2+1];
 405
 406                         b_actualizar_header(nodo, &nodo_header);
 407                         b_actualizar_header(nuevo, &nuevo_header);
 408
 409                         if (nodo_id != 0) {
 410                                 clave = tmp_claves[total/2].clave;
 411                                 dato = tmp_claves[total/2].dato;
 412
 413                                 b_grabar_nodo(idx, nodo_id, nodo);
 414                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 415                                 free(nodo);
 416                                 free(nuevo);
 417                                 free(tmp_claves);
 418
 419                                 hijo1 = nodo_id;
 420                                 hijo2 = nuevo_id;
 421
 422                                 fprintf(stderr, "Nodos espliteados = %d %d\n", hijo1, hijo2);
 423                                 nodo = padre;
 424                                 nodo_id = nodo_header.padre;
 425                         } else {
 426                                 /* Oops, parti el raiz, y este debe quedar en 0, lo paso a otro bloque
 427                                  * y dejo el padre vacio
 428                                  */
 429                                 char *tmp_nuevo = b_crear_nodo(idx, &nodo_id);
 430                                 memcpy(tmp_nuevo, nodo, idx->tam_bloque);
 431                                 free(nodo);
 432                                 nodo = tmp_nuevo;
 433
 434                                 clave = tmp_claves[total/2].clave;
 435                                 dato = tmp_claves[total/2].dato;
 436
 437                                 b_grabar_nodo(idx, nuevo_id+1, nodo);
 438                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 439
 440                                 free(nodo);
 441                                 free(nuevo);
 442                                 free(tmp_claves);
 443
 444                                 hijo1 = nuevo_id+1;
 445                                 hijo2 = nuevo_id;
 446
 447                                 fprintf(stderr, "Nodos espliteados = %d %d\n", hijo1, hijo2);
 448                                 /* Limpio al padre */
 449                                 nuevo = b_leer_nodo(idx, 0);
 450
 451                                 b_leer_header(nuevo, &nuevo_header);
 452                                 nuevo_header.cant = 0;
 453                                 nuevo_header.padre = -1;
 454                                 nuevo_header.nivel = nodo_header.nivel+1;
 455                                 nuevo_header.hijo_izquierdo = -1;
 456                                 fprintf(stderr, "root.nivel=%d\n", nuevo_header.nivel);
 457                                 memset(nuevo, -1, idx->tam_bloque);
 458                                 b_actualizar_header(nuevo, &nuevo_header);
 459                                 b_grabar_nodo(idx, 0, nuevo);
 460
 461                                 nodo_id = 0;
 462                                 nodo = nuevo;
 463                                 rompi = 1;
 464                         }
 465                 } else {
 466                         /* La clave entra en este nodo!! */
 467                         b_insertar_en_nodo_con_lugar(idx, clave, dato, nodo_id, nodo, hijo1, hijo2);
 468                         salir = 1;
 469                 }
 470         } while (!salir);
 471 }
 472
 473 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)
 474 {
 475         int i = 0;
 476         B_NodoHeader nodo_header;
 477         B_NodoEntry* claves;
 478         b_leer_header(nodo, &nodo_header);
 479         claves = b_leer_claves(nodo, &nodo_header);
 480         if (nodo_header.cant > 0) {
 481                 int j;
 482                 while ((i < nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
 483                 for(j=nodo_header.cant; j > i; j--)
 484                         claves[j] = claves[j-1];
 485         }
 486         nodo_header.cant++;
 487         claves[i].clave = clave;
 488         claves[i].dato = dato;
 489         if (i==0) {
 490                 nodo_header.hijo_izquierdo = hijo_izq;
 491                 claves[i].hijo_derecho = hijo_der;
 492         } else {
 493                 claves[i-1].hijo_derecho = hijo_izq;
 494                 claves[i].hijo_derecho = hijo_der;
 495         }
 496         /*b_elegir_izquierdo(idx, nodo_header.hijo_izquierdo, hijo1);*/
 497
 498         b_actualizar_header(nodo, &nodo_header);
 499         b_grabar_nodo(idx, nodo_id, nodo);
 500
 501         /* Debo actualizar los punteros al padre de los hijos */
 502         if (hijo_izq != -1) {
 503                 char* nuevo = b_leer_nodo(idx, hijo_izq);
 504                 if (nuevo != NULL) {
 505                         B_NodoHeader nuevo_header;
 506                         fprintf(stderr, "Actualizo padre de %d a %d\n", hijo_izq, nodo_id);
 507                         b_leer_header(nuevo, &nuevo_header);
 508                         nuevo_header.padre = nodo_id;
 509                         b_actualizar_header(nuevo, &nuevo_header);
 510                         b_grabar_nodo(idx, hijo_izq, nuevo);
 511                         free(nuevo);
 512                 } else printf("FUCK! hijo_izq=%d no existe!\n", hijo_izq);
 513         }
 514         if (hijo_der != -1) {
 515                 char* nuevo = b_leer_nodo(idx, hijo_der);
 516                 if (nuevo != NULL) {
 517                         B_NodoHeader nuevo_header;
 518                         fprintf(stderr, "Actualizo padre de %d a %d\n", hijo_der, nodo_id);
 519                         b_leer_header(nuevo, &nuevo_header);
 520                         nuevo_header.padre = nodo_id;
 521                         b_actualizar_header(nuevo, &nuevo_header);
 522                         b_grabar_nodo(idx, hijo_der, nuevo);
 523                         free(nuevo);
 524                 } else printf("FUCK! hijo_der=%d no existe!\n", hijo_der);
 525         }
 526 }
 527
 528 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)
 529 {
 530         int i = 0;
 531         B_NodoHeader nodo_header;
 532         B_NodoEntry* claves;
 533         b_leer_header(nodo, &nodo_header);
 534         claves = b_leer_claves(nodo, &nodo_header);
 535         if (nodo_header.cant > 0) {
 536                 int j;
 537                 while ((i < nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
 538                 for(j=nodo_header.cant; j > i; j--)
 539                         claves[j] = claves[j-1];
 540         }
 541         nodo_header.cant++;
 542         claves[i].clave = clave;
 543         claves[i].dato = dato;
 544         claves[i].hijo_derecho = hijo_der;
 545
 546         b_actualizar_header(nodo, &nodo_header);
 547         b_grabar_nodo(idx, nodo_id, nodo);
 548
 549         /* Debo actualizar el puntero al padre del hijo */
 550         if (hijo_der != -1) {
 551                 char* nuevo = b_leer_nodo(idx, hijo_der);
 552                 if (nuevo != NULL) {
 553                         B_NodoHeader nuevo_header;
 554                         b_leer_header(nuevo, &nuevo_header);
 555                         nuevo_header.padre = nodo_id;
 556                         b_actualizar_header(nuevo, &nuevo_header);
 557                         b_grabar_nodo(idx, hijo_der, nuevo);
 558                         free(nuevo);
 559                 } else printf("FUCK! hijo_der=%d no existe!\n", hijo_der);
 560         }
 561 }
 562
 563 INDICE_DATO *emufs_indice_b_buscar_muchos(INDICE *idx, CLAVE clave, int *cant)
 564 {
 565         EMUFS_REG_SIZE tam;
 566         int error=0;
 567         char *leido;
 568         CLAVE k;
 569         INDICE_DATO dato, *ret;
 570
 571         /* Si el indice es primario no tiene sentido hacer nada */
 572         if (idx->funcion == IND_PRIMARIO) {
 573                 *cant = 0;
 574                 PERR("INDICE PRIMARIO NO SOPORTA BUSQUEDA MULTIPLE");
 575                 return NULL;
 576         }
 577
 578         /* Busco la clave en el arbol */
 579         dato = emufs_indice_b_buscar(idx, clave);
 580
 581         if (dato.id == -1) {
 582                 PERR("CLAvE NO ENCONTRADA EN EL ARBOL!");
 583         }
 584
 585         /* Leo el contenido actual */
 586         k.i_clave = dato.id;
 587         error = 0;
 588         leido = (char *)idx->emu_mult->leer_registro(idx->emu_mult, k, &tam, &error);
 589
 590         /* Incremento en 1 la cantidad */
 591         if (leido != NULL)
 592                 (*cant) = *((int *)leido);
 593         else
 594                 (*cant) = 0;
 595
 596         ret = malloc(sizeof(INDICE_DATO)*(*cant));
 597         memcpy(ret, leido+sizeof(int), (*cant)*sizeof(INDICE_DATO));
 598         free(leido);
 599         return ret;
 600 }
 601
 602 static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k)
 603 {
 604         int pos, actual_id, padre_id, i, pos_padre, izquierda_id, derecha_id;
 605         B_NodoHeader header, header_actual, header_padre, header_izq, header_der;
 606         B_NodoEntry *claves, *claves_actual, *claves_padre;/*, *claves_izq, *claves_der;*/
 607         char *actual, *padre, *izq, *der;
 608
 609         PERR("Borrando clave");
 610         b_leer_header(nodo, &header);
 611         claves = b_leer_claves(nodo, &header);
 612
 613         pos = 0;
 614         /* Busco la posicion dentro de la lista de claves */
 615         PERR("Buscando lugar donde se encuentra la clave");
 616         while (emufs_indice_es_menor(idx, claves[pos].clave, k)) pos++;
 617
 618         /* Es el nodo una hoja? */
 619         if (header.hijo_izquierdo != -1) {
 620                 PERR("Nodo no es hoja, intercambio");
 621                 /* No!, es un nodo intermedio!! */
 622                 if (pos == 0)
 623                         actual = b_leer_nodo(idx, header.hijo_izquierdo);
 624                 else
 625                         actual = b_leer_nodo(idx, claves[pos+1].hijo_derecho);
 626
 627                 b_leer_header(actual, &header_actual);
 628                 while (header_actual.hijo_izquierdo != -1) {
 629                         actual_id = header_actual.hijo_izquierdo;
 630                         free(actual);
 631                         actual = b_leer_nodo(idx, actual_id);
 632                         b_leer_header(actual, &header_actual);
 633                 }
 634                 claves_actual = b_leer_claves(actual, &header);
 635
 636                 claves[pos] = claves_actual[0];
 637                 pos = 0;
 638                 b_grabar_nodo(idx, nodo_id, nodo);
 639                 PERR("Listo");
 640         } else {
 641                 PERR("Nodo es hoja");
 642                 actual = nodo;
 643         }
 644
 645         /* Borro la clave */
 646         PERR("Borrando clave");
 647         for(i=pos; i < header_actual.cant; i++) {
 648                 claves_actual[i] = claves_actual[i+1];
 649         }
 650         PERR("Borrado completo");
 651         header_actual.cant--;
 652         /* Guardo los cambios */
 653         b_actualizar_header(actual, &header_actual);
 654         b_grabar_nodo(idx, actual_id, actual);
 655
 656         /* Se cumple la condicion de hijos? */
 657         PERR("Dejo todo consistente");
 658         if (header_actual.cant >= MIN_HIJOS(idx)) {
 659                 PERR("Borrar completo sin fundir");
 660                 return;
 661         }
 662
 663         PERR("Node queda con menos hijos de los posibles!");
 664         /* Tengo que pasar datos o fundir nodos :-( */
 665         do {
 666                 padre_id = header.padre;
 667                 padre = b_leer_nodo(idx, padre_id);
 668                 b_leer_header(padre, &header_padre);
 669                 claves_padre = b_leer_claves(padre, &header_padre);
 670                 fprintf(stderr, "ID del padre = %d de nivel %d\n", padre_id, header_padre.nivel);
 671                 /* TODO Tengo el hijo_izquierdo para revisar!! XXX */
 672                 if (header_padre.hijo_izquierdo == actual_id) {
 673                         PERR("Soy el hijo izquierdo de padre");
 674                         izquierda_id = -1; /* No tengo hermano izquierdo */
 675                         /* Mi hermano derecho es el primer nodo del padre */
 676                         derecha_id = claves_padre[0].hijo_derecho;
 677                         der = b_leer_nodo(idx, derecha_id);
 678                         b_leer_header(der, &header_der);
 679                 } else {
 680                         PERR("Buscando que hijo soy");
 681                         for(pos_padre=0; (pos_padre<header_padre.cant) && (claves_padre[pos_padre].hijo_derecho != actual_id); pos_padre++)     {       }
 682
 683                         if (pos_padre == header_padre.cant) {
 684                                 PERR("ERROR GRAVE. Padre no me contiene :-(");
 685                         }
 686
 687                         /* Busco mis hermanos a derecha e izquierda, si es que existen */
 688                         PERR("Ya me encontre, busco a mis hermanos");
 689                         if (pos_padre >= 0) {
 690                                 if (pos_padre == 0)
 691                                         izquierda_id = header_padre.hijo_izquierdo;
 692                                 else
 693                                         izquierda_id = claves_padre[pos_padre-1].hijo_derecho;
 694                                 izq = b_leer_nodo(idx, izquierda_id);
 695                                 b_leer_header(izq, &header_izq);
 696                         } else {
 697                                 izquierda_id = -1;
 698                         }
 699                         if (pos_padre < header_padre.cant) {
 700                                 derecha_id = claves_padre[pos_padre+1].hijo_derecho;
 701                                 der = b_leer_nodo(idx, derecha_id);
 702                                 b_leer_header(der, &header_der);
 703                         } else {
 704                                 derecha_id = -1;
 705                         }
 706                 }
 707                 /* Intendo pasar una clave desde un hermano hacia mi */
 708                 PERR("Ta calcule lo que tengo que hacer");
 709                 if ((derecha_id != -1) && (header_der.cant > MIN_HIJOS(idx))) {
 710                         PERR("Le pido clave a derecha");
 711                         b_pedir_clave_derecha(der, derecha_id, padre, padre_id, actual, actual_id, pos_padre);
 712                         PERR("listo");
 713                 } else if ((izquierda_id != -1) && (header_izq.cant > MIN_HIJOS(idx))) {
 714                         PERR("Le pido clave a izquierda");
 715                         b_pedir_clave_izquierda(izq, izquierda_id, padre, padre_id, actual, actual_id, pos_padre-1);
 716                         PERR("Listo");
 717                 } else {
 718                         /* No pude pasar clave, tengo que fundir :-( */
 719                         PERR("Fundo nodos!");
 720                         if (derecha_id != -1) {
 721                                 b_fundir_nodo(actual, actual_id, padre, padre_id, der, derecha_id, pos_padre);
 722                         } else {
 723                                 b_fundir_nodo(izq, izquierda_id, padre, padre_id, actual, actual_id, pos_padre-1);
 724                         }
 725                 }
 726
 727                 /* TODO que guardo ?, todo ? */
 728                 b_grabar_nodo(idx, actual_id, actual);
 729                 b_grabar_nodo(idx, izquierda_id, izq);
 730                 b_grabar_nodo(idx, derecha_id, der);
 731                 b_grabar_nodo(idx, padre_id, padre);
 732                 if (actual_id != -1) free(actual);
 733                 /*if (padre_id != -1) free(padre);*/
 734                 if (derecha_id != -1) free(der);
 735                 if (izquierda_id != -1) free(izq);
 736                 actual = padre;
 737                 actual_id = padre_id;
 738         } while ((actual_id != -1) && (header_actual.cant < MIN_HIJOS(idx)));
 739 }
 740
 741 static void b_pedir_clave_derecha(char *der, int der_id, char *padre, int padre_id, char *nodo, int nodo_id, int pos_clave)
 742 {
 743         int i;
 744         B_NodoHeader h_der, h_padre, h_nodo;
 745         B_NodoEntry *c_der, *c_padre, *c_nodo;
 746
 747         b_leer_header(nodo, &h_nodo);
 748         c_nodo = b_leer_claves(nodo, &h_nodo);
 749         b_leer_header(der, &h_der);
 750         c_der = b_leer_claves(der, &h_der);
 751         b_leer_header(padre, &h_padre);
 752         c_padre = b_leer_claves(padre, &h_padre);
 753
 754         c_nodo[h_nodo.cant] = c_padre[pos_clave];
 755         c_nodo[h_nodo.cant].hijo_derecho = -1; /* XXX */
 756
 757         c_padre[pos_clave] = c_der[0];
 758         c_padre[pos_clave].hijo_derecho = der_id;
 759
 760         /* Muevo las claves de derecho */
 761         for(i=0; i<h_der.cant; i++) {
 762                 c_der[i] = c_der[i+1];
 763         }
 764         h_der.cant--;
 765         h_nodo.cant++;
 766
 767         b_actualizar_header(der, &h_der);
 768         b_actualizar_header(nodo, &h_nodo);
 769 }
 770
 771 void b_pasar_clave_a_derecha(INDICE *idx, char *der, int der_id, char *padre, int padre_id, int padre_pos, B_NodoEntry entry)
 772 {
 773         B_NodoHeader padre_h, der_h;
 774         B_NodoEntry* padre_entries;
 775         /* Leo claves y cabecera del nodo de la derecha y del padre */
 776         b_leer_header(padre, &padre_h);
 777         b_leer_header(der, &der_h);
 778         padre_entries = b_leer_claves(padre, &padre_h);
 779         /* Inserto en el hijo derecho la clave del padre */
 780         b_insertar_en_nodo_con_lugar(idx, padre_entries[padre_pos].clave, padre_entries[padre_pos].dato,
 781                         der_id, der, entry.hijo_derecho, der_h.hijo_izquierdo);
 782         /* Reemplazo clave del padre por clave nueva */
 783         entry.hijo_derecho = der_id;
 784         padre_entries[padre_pos] = entry;
 785 }
 786
 787 void b_pedir_clave_izquierda(char *izq, int izq_id, char *padre, int padre_id, char *nodo, int nodo_id, int pos_clave)
 788 {
 789         int i;
 790         B_NodoHeader h_izq, h_padre, h_nodo;
 791         B_NodoEntry *c_izq, *c_padre, *c_nodo;
 792
 793         b_leer_header(nodo, &h_nodo);
 794         c_nodo = b_leer_claves(nodo, &h_nodo);
 795         b_leer_header(izq, &h_izq);
 796         c_izq = b_leer_claves(izq, &h_izq);
 797         b_leer_header(padre, &h_padre);
 798         c_padre = b_leer_claves(padre, &h_padre);
 799
 800         for(i=h_nodo.cant; i>0;i++)
 801                 c_nodo[i] = c_nodo[i-1];
 802
 803         h_nodo.cant++;
 804         c_nodo[0] = c_padre[pos_clave];
 805         c_nodo[0].hijo_derecho = -1; /* XXX */
 806         c_padre[pos_clave] = c_izq[h_izq.cant-1];
 807         c_padre[pos_clave].hijo_derecho = izq_id;
 808         h_izq.cant--;
 809
 810         b_actualizar_header(izq, &h_izq);
 811         b_actualizar_header(padre, &h_padre);
 812         b_actualizar_header(nodo, &h_nodo);
 813 }
 814
 815 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)
 816 {
 817         B_NodoHeader padre_h;
 818         B_NodoEntry* padre_entries;
 819         /* Leo claves y cabecera del nodo de la izquierda y del padre */
 820         b_leer_header(padre, &padre_h);
 821         padre_entries = b_leer_claves(padre, &padre_h);
 822         /* Inserto en el hijo izquirdo la clave del padre */
 823         b_insertar_en_nodo_con_lugar_sin_hijo_izq(idx, padre_entries[padre_pos].clave, padre_entries[padre_pos].dato,
 824                         izq_id, izq, id_entry_hijo_izq);
 825         /* Reemplazo clave del padre por clave nueva */
 826         entry.hijo_derecho = id_entry_nodo;
 827         padre_entries[padre_pos] = entry;
 828 }
 829
 830 static void b_fundir_nodo(char *izq, int izq_id, char *padre, int padre_id, char *der, int der_id, int pos_clave)
 831 {
 832 }
 833
 834 static EMUFS_REG_ID b_insertar_dup_en_pos(INDICE *idx, INDICE_DATO pos, INDICE_DATO nuevo)
 835 {
 836         int cant;
 837         EMUFS_REG_SIZE tam;
 838         int error=0;
 839         INDICE_DATO *array;
 840         char *leido;
 841         CLAVE k;
 842
 843         /* Leo el contenido actual */
 844         k.i_clave = pos.id;
 845         error = 0;
 846         leido = (char *)idx->emu_mult->leer_registro(idx->emu_mult, k, &tam, &error);
 847
 848         /* Incremento en 1 la cantidad */
 849         if (leido != NULL)
 850                 cant = *((int *)leido);
 851         else
 852                 cant = 0;
 853         cant++;
 854
 855         /* Obtengo un nuevo lugar para el dato nuevo */
 856         /* Aca todo bien, si leido es NULL se compota como malloc */
 857         leido = realloc(leido, cant*sizeof(INDICE_DATO)+sizeof(int));
 858         array = (INDICE_DATO *)(leido+sizeof(int));
 859
 860         /* Pongo el dato nuevo */
 861         array[cant-1] = nuevo;
 862
 863         /* Actualizo la cantidad */
 864         (*((int *)leido)) = cant;
 865
 866         /* Salvo */
 867         if (k.i_clave == -1) {
 868                 /* Creo uno nuevo */
 869                 error = 0;
 870                 k.i_clave = idx->emu_mult->grabar_registro(idx->emu_mult,
 871                         leido,
 872                         cant*sizeof(INDICE_DATO)+sizeof(int),
 873                         &error
 874                 );
 875                 if (k.i_clave == -1) PERR("ALGO NO GRABO BIEN!!");
 876         } else {
 877                 /* Modifico el que ya existia! */
 878                 error = 0;
 879                 idx->emu_mult->modificar_registro(idx->emu_mult,
 880                         k,
 881                         leido,
 882                         cant*sizeof(INDICE_DATO)+sizeof(int),
 883                         &error
 884                 );
 885         }
 886         /* Clean up! */
 887         free(leido);
 888         return k.i_clave;
 889 }
 890
 891 char *abreviar(char *primera, char *actual, int *iguales)
 892 {
 893         (*iguales) = 0;
 894         while (((*primera) != '\0') && ((*actual) != '\0')) {
 895                 if ((*primera) == (*actual)) {
 896                         primera++;
 897                         actual++;
 898                         (*iguales)++;
 899                 } else {
 900                         /* No coinciden mas! */
 901                         break;
 902                 }
 903         }
 904
 905         return actual;
 906 }
 907
 908 static void abreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header)
 909 {
 910         char *primera, *actual, *resto, salvar[100];
 911         EMUFS_REG_SIZE size;
 912         int error, i;
 913         int iguales;
 914
 915         /* Agarro la primer clave entera como referencia */
 916         primera = (char *)idx->emu_string->leer_registro(idx->emu_string, array[0].clave, &size, &error);
 917         for(i=1; i<header->cant; i++) {
 918                 actual = (char *)idx->emu_string->leer_registro(idx->emu_string, array[i].clave, &size, &error);
 919                 if (*actual == '*') {
 920                         free(actual);
 921                         continue;
 922                 }
 923                 resto = abreviar(primera, actual, &iguales);
 924                 /* Para que tenga sentido abreviar tengo que tener
 925                  * mas de 2 letras iguales, si no no gano nada y complica las cosas
 926                  */
 927                 if (iguales > 1) {
 928                         sprintf(salvar, "%d|%s", iguales, resto);
 929                         free(actual);
 930                         error = 0;
 931                         idx->emu_string->modificar_registro(idx->emu_string, array[i].clave, salvar, strlen(salvar)+1, &error);
 932                 } else {
 933                         free(primera);
 934                         primera = actual;
 935                 }
 936         }
 937
 938         free(primera);
 939 }
 940
 941 static void desabreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header)
 942 {
 943         char *primera, *actual, *resto, salvar[100];
 944         EMUFS_REG_SIZE size;
 945         int error, i;
 946         int iguales;
 947
 948         /* Agarro la primer clave entera como referencia */
 949         primera = (char *)idx->emu_string->leer_registro(idx->emu_string, array[0].clave, &size, &error);
 950         for(i=1; i<header->cant; i++) {
 951                 actual = (char *)idx->emu_string->leer_registro(idx->emu_string, array[i].clave, &size, &error);
 952                 if (*actual == '*') {
 953                         free(actual);
 954                         continue;
 955                 }
 956                 iguales = strtol(actual, &resto, 10);
 957                 if ((iguales > 0) && (*resto == '|')) {
 958                         strncpy(salvar, primera, iguales);
 959                         salvar[iguales] = '\0';
 960                         strcat(salvar, resto+1); /* +1 para saltar el separador */
 961                         idx->emu_string->modificar_registro(idx->emu_string, array[i].clave, salvar, strlen(salvar)+1, &error);
 962                         free(actual);
 963                 } else {
 964                         free(primera);
 965                         primera = actual;
 966                 }
 967         }
 968
 969         free(primera);
 970 }
 971
 972 int emufs_indice_b_ver(INDICE *idx, WINDOW *win, int w, int h, int id)
 973 {
 974         int y=0;
 975         B_NodoHeader header;
 976         B_NodoEntry *claves;
 977         char *nodo;
 978         char tmp[100];
 979         int i;
 980         int proximo;
 981
 982         mvwaddstr(win, y++, 0, "Nombre : ");
 983         waddstr(win, idx->nombre);
 984
 985         /* Muestro la raiz */
 986         nodo = b_leer_nodo(idx, id);
 987         b_leer_header(nodo, &header);
 988         claves = b_leer_claves(nodo, &header);
 989
 990         mvwaddstr(win, y++, 0, "Nodo Nro ");
 991         sprintf(tmp, "%d", id);
 992         waddstr(win, tmp);
 993         mvwaddstr(win, y++, 0, "Nivel =  ");
 994         sprintf(tmp, "%d", header.nivel);
 995         waddstr(win, tmp);
 996         mvwaddstr(win, y++, 0, "Cantidad de hijo = ");
 997         sprintf(tmp, "%d", header.cant);
 998         waddstr(win, tmp);
 999         mvwaddstr(win, y++, 0, "Padre = ");
1000         sprintf(tmp, "%d", header.padre);
1001         waddstr(win, tmp);
1002
1003         /* Muestro las claves */
1004         mvwaddstr(win, y++, 0, "Claves");
1005         wmove(win, y, 0);
1006         sprintf(tmp, "%d", header.hijo_izquierdo);
1007         waddstr(win, tmp);
1008         for(i=0; i<header.cant; i++) {
1009                 sprintf(tmp, "(%d)%d",
1010                                 claves[i].clave.i_clave,
1011 /*                              claves[i].dato.id,
1012                                 claves[i].dato.bloque,*/
1013                                 claves[i].hijo_derecho
1014                 );
1015                 waddstr(win, tmp);
1016         }
1017         free(nodo);
1018         wrefresh(win);
1019         proximo = getch()-'0';
1020         werase(win);
1021         wrefresh(win);
1022         emufs_indice_b_ver(idx, win, w, h, proximo);
1023         werase(win);
1024         wrefresh(win);
1025 }
1026