emufs/indice_b.c

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