emufs/indice_b.c

   1
   2 #include "indice_b.h"
   3 #include "common.h"
   4
   5 /* Cantidad de claves por nodo */
   6 #define CANT_HIJOS(x) ((x->tam_bloque-sizeof(B_NodoHeader))/sizeof(B_NodoEntry))
   7 #define CANT_NODOS(x) (CANT_HIJOS(x)+1)
   8 #define MIN_HIJOS(x) (CANT_HIJOS(x)/2)
   9
  10 /* Auxiliares */
  11 static void b_grabar_nodo(INDICE *idx, int id, char *data);
  12 static int b_ultimo_id(INDICE *idx);
  13 static char *b_leer_nodo(INDICE *idx, int id);
  14 static char *b_crear_nodo(INDICE *idx, int *i);
  15 static void b_leer_header(char *src, B_NodoHeader *header);
  16 static void b_actualizar_header(char *src, B_NodoHeader *header);
  17 static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header);
  18 static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2);
  19 static int b_elegir_izquierdo(INDICE *idx, int a, int b);
  20 static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k);
  21
  22 void emufs_indice_b_crear(INDICE *idx)
  23 {
  24         FILE *fp;
  25         char *bloque;
  26         B_NodoHeader header;
  27
  28         header.cant = 0;
  29         header.nivel = 0;
  30         header.padre = -1;
  31         header.hijo_izquierdo = -1;
  32
  33         fp = fopen(idx->filename, "w");
  34         PERR("Creando indice");
  35         fprintf(stderr, "Archivo = (%s)\n", idx->filename);
  36         if (fp == NULL) {
  37                 PERR("Error al crear el archivo");
  38                 return;
  39         }
  40
  41         /* Creo el archivo con el Nodo raiz */
  42         bloque = (char *)malloc(idx->tam_bloque);
  43         memset(bloque, -1, idx->tam_bloque);
  44
  45         memcpy(bloque, &header, sizeof(B_NodoHeader));
  46
  47         fwrite(bloque, idx->tam_bloque, 1, fp);
  48         fclose(fp);
  49 }
  50
  51 int emufs_indice_b_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato)
  52 {
  53         int i, nodo_id, padre_id;
  54         B_NodoHeader header;
  55         B_NodoEntry *claves;
  56         char *nodo, *padre;
  57
  58         /* Leo la raiz */
  59         nodo = b_leer_nodo(idx, 0);
  60         padre_id = nodo_id = 0;
  61         padre = NULL;
  62         while (nodo) {
  63                 if (padre) free(padre);
  64                 padre = nodo;
  65                 padre_id = nodo_id;
  66                 b_leer_header(nodo, &header);
  67                 claves = b_leer_claves(nodo, &header);
  68                 i=0;
  69                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
  70                 if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, clave))) {
  71                         /* CLAVE DUPLICADA! */
  72                         return 0;
  73                 } else {
  74                         if (i == 0) {
  75                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
  76                                 nodo_id = header.hijo_izquierdo;
  77                         } else {
  78                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
  79                                 nodo_id = claves[i-1].hijo_derecho;
  80                         }
  81                 }
  82         }
  83
  84         if (nodo) free(nodo);
  85         nodo = padre;
  86         nodo_id = padre_id;
  87         b_insertar_en_nodo(idx, clave, dato, nodo_id, nodo, -1, -1);
  88         return 1; /* Agregar OK! */
  89 }
  90
  91 INDICE_DATO emufs_indice_b_buscar(INDICE *idx, CLAVE clave)
  92 {
  93         int i;
  94         INDICE_DATO ret;
  95         B_NodoHeader header;
  96         B_NodoEntry *claves;
  97         char *nodo, *tmp;
  98
  99         /* Leo la raiz */
 100         nodo = b_leer_nodo(idx, 0);
 101         while (nodo) {
 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 (emufs_indice_es_igual(idx, claves[i].clave, clave)) {
 107                                 ret = claves[i].dato;
 108                                 free(nodo);
 109                                 return ret;
 110                 } else {
 111                         tmp = nodo;
 112                         if (i == 0) {
 113                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
 114                         } else {
 115                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
 116                         }
 117                         free(tmp);
 118                 }
 119         }
 120
 121         /* Nodo no encontrado */
 122         ret.id = ret.bloque = -1;
 123         return ret;
 124 }
 125
 126 int emufs_indice_b_borrar(INDICE *idx, CLAVE k)
 127 {
 128         /* Busco el nodo que contiene la clave,si es que esta existe */
 129         char *nodo;
 130         int nodo_id, i;
 131         char encontrado=0;
 132         B_NodoHeader header;
 133         B_NodoEntry *claves;
 134
 135         nodo_id = 0; /* Tomo la raiz */
 136         nodo = b_leer_nodo(idx, nodo_id);
 137         PERR("Buscando clave a borrar");
 138         while (nodo && !encontrado) {
 139                 /* Obtengo los datos del nodo */
 140                 b_leer_header(nodo, &header);
 141                 claves = b_leer_claves(nodo, &header);
 142
 143                 i=0;
 144                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) i++;
 145
 146                 if ((emufs_indice_es_igual(idx, claves[i].clave, k)) && (i<header.cant))
 147                         encontrado = 1;
 148                 else {
 149                         if (i==0) {
 150                                 free(nodo);
 151                                 nodo_id = header.hijo_izquierdo;
 152                                 nodo = b_leer_nodo(idx, nodo_id);
 153                         } else {
 154                                 nodo_id = claves[i-1].hijo_derecho;
 155                                 free(nodo);
 156                                 nodo = b_leer_nodo(idx, nodo_id);
 157                         }
 158                 }
 159         }
 160
 161         if (encontrado) {
 162                 PERR("Clave encontrada, borrando ...");
 163                 b_borrar_clave(idx, nodo, nodo_id, k);
 164         } else {
 165                 PERR("Clave no encontrada");
 166         }
 167         return 0;
 168 }
 169
 170 static int b_ultimo_id(INDICE *idx)
 171 {
 172         int i;
 173         FILE *fp;
 174         fp = fopen(idx->filename, "r");
 175         fseek(fp, 0, SEEK_END);
 176         i = ftell(fp)/idx->tam_bloque;
 177         fclose(fp);
 178
 179         return i;
 180 }
 181
 182 static char *b_crear_nodo(INDICE *idx, int *id)
 183 {
 184         char *bloque;
 185         B_NodoHeader header;
 186
 187         (*id) = b_ultimo_id(idx);
 188
 189         header.cant = 0;
 190         header.nivel = 0;
 191         header.hijo_izquierdo = -1;
 192         header.padre = -1;
 193
 194         bloque = (char *)malloc(idx->tam_bloque);
 195         memset(bloque, -1, idx->tam_bloque);
 196         memcpy(bloque, &header, sizeof(B_NodoHeader));
 197
 198         b_grabar_nodo(idx, *id, bloque);
 199
 200         return bloque;
 201 }
 202
 203 static char *b_leer_nodo(INDICE *idx, int id)
 204 {
 205         FILE *fp;
 206         char *out;
 207
 208         if (id < 0) return NULL;
 209
 210         fp = fopen(idx->filename, "r");
 211         if (fp == NULL) return NULL;
 212
 213         fseek(fp, id*idx->tam_bloque, SEEK_SET);
 214
 215         out = (char *)malloc(idx->tam_bloque);
 216         if (out == NULL) {
 217                 fclose(fp);
 218                 return NULL;
 219         }
 220
 221         if (fread(out, 1, idx->tam_bloque, fp) != idx->tam_bloque) {
 222                 free(out);
 223                 /* No se puso leer el nodo */
 224                 fclose(fp);
 225                 return NULL;
 226         }
 227
 228         fclose(fp);
 229         return out;
 230 }
 231
 232 static void b_grabar_nodo(INDICE *idx, int id, char *data)
 233 {
 234         FILE *fp;
 235
 236 /*      if (id > b_ultimo_id()) {
 237                 printf("AGREGANDO AL FINAL\n");
 238                 fp = fopen(FILENAME, "a");
 239                 if (fp == NULL) {
 240                 _("No se pudo abrir archivo\n");
 241                         return;
 242                 }
 243         } else {
 244                 fp = fopen(FILENAME, "w");
 245                 if (fp == NULL) {
 246                 _("No se pudo abrir archivo\n");
 247                         return;
 248                 }
 249                 fseek(fp, id*BLOCK_SIZE, SEEK_SET);
 250                 printf("SOLO GUARDO DATA\n");
 251         }*/
 252
 253         fp = fopen(idx->filename, "r+");
 254         fseek(fp, id*idx->tam_bloque, SEEK_SET);
 255         fwrite(data, 1, idx->tam_bloque, fp);
 256         fclose(fp);
 257 }
 258
 259 static void b_leer_header(char *src, B_NodoHeader *header)
 260 {
 261         if (!src) return;
 262
 263         memcpy(header, src, sizeof(B_NodoHeader));
 264 }
 265
 266 static void b_actualizar_header(char *src, B_NodoHeader *header)
 267 {
 268         if (!src) return;
 269         memcpy(src, header, sizeof(B_NodoHeader));
 270 }
 271
 272 static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header)
 273 {
 274         return (B_NodoEntry *)(src+sizeof(B_NodoHeader));
 275 }
 276
 277 static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2)
 278 {
 279         char *padre, *nuevo;
 280         int nuevo_id;
 281         int i, j;
 282         static int rompi=0;
 283         char salir = 0;
 284         B_NodoHeader nodo_header, nuevo_header;
 285         B_NodoEntry *claves, *tmp_claves, *claves_nuevo;
 286
 287         do {
 288                 if (!nodo) {
 289                         /* CREAR NODO? */
 290                         nodo = b_crear_nodo(idx, &nodo_id);
 291                 }
 292                 b_leer_header(nodo, &nodo_header);
 293                 claves = b_leer_claves(nodo, &nodo_header);
 294
 295                 padre = b_leer_nodo(idx, nodo_header.padre);
 296
 297                 if (nodo_header.cant == CANT_HIJOS(idx)) {
 298                         int total;
 299                         nuevo = b_crear_nodo(idx, &nuevo_id);
 300                         i=0;
 301                         /* Creo una lista ordenada de los nodos a partir */
 302                         tmp_claves = (B_NodoEntry *)malloc(sizeof(B_NodoEntry)*(nodo_header.cant+1));
 303                         total = nodo_header.cant;
 304                         while ((i<nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) {
 305                                 tmp_claves[i] = claves[i];
 306                                 i++;
 307                         }
 308                         tmp_claves[i].clave = clave;
 309                         tmp_claves[i].dato = dato;
 310                         tmp_claves[i].hijo_derecho = hijo1;
 311                         tmp_claves[i+1].hijo_derecho = hijo2;
 312                         while (i < nodo_header.cant) {
 313                                 tmp_claves[i+1] = claves[i];
 314                                 i++;
 315                         }
 316
 317                         /* Asigno a cada nodo lo que corresponde */
 318                         b_leer_header(nuevo, &nuevo_header);
 319
 320                         nuevo_header.nivel = nodo_header.nivel;
 321                         nodo_header.cant = total/2;
 322                         nuevo_header.cant = total - nodo_header.cant;
 323
 324                         memset(claves, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 325                         for(j=0; j<nodo_header.cant; j++)
 326                                 claves[j] = tmp_claves[j];
 327
 328                         claves_nuevo = b_leer_claves(nuevo, &nuevo_header);
 329                         memset(claves_nuevo, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 330                         for(j=0; j<nuevo_header.cant; j++)
 331                                 claves_nuevo[j] = tmp_claves[j+total/2+1];
 332
 333                         b_actualizar_header(nodo, &nodo_header);
 334                         b_actualizar_header(nuevo, &nuevo_header);
 335
 336                         if (nodo_id != 0) {
 337                                 clave = tmp_claves[total/2].clave;
 338                                 /* XXX dato.bloque = nuevo_id; */
 339
 340                                 b_grabar_nodo(idx, nodo_id, nodo);
 341                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 342                                 free(nodo);
 343                                 free(nuevo);
 344                                 free(tmp_claves);
 345
 346                                 hijo1 = nodo_id;
 347                                 hijo2 = nuevo_id;
 348
 349                                 nodo = padre;
 350                                 nodo_id = nodo_header.padre;
 351                         } else {
 352                                 /* Oops, parti el raiz, y este debe quedar en 0, lo paso a otro bloque
 353                                  * y dejo el padre vacio
 354                                  */
 355                                 char *tmp_nuevo = b_crear_nodo(idx, &nodo_id);
 356                                 memcpy(tmp_nuevo, nodo, idx->tam_bloque);
 357                                 free(nodo);
 358                                 nodo = tmp_nuevo;
 359
 360                                 clave = tmp_claves[total/2].clave;
 361                                 /* XXX dato.bloque = nuevo_id; */
 362
 363                                 b_grabar_nodo(idx, nuevo_id+1, nodo);
 364                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 365
 366                                 free(nodo);
 367                                 free(nuevo);
 368                                 free(tmp_claves);
 369
 370                                 hijo1 = nuevo_id+1;
 371                                 hijo2 = nuevo_id;
 372
 373                                 /* Limpio al padre */
 374                                 nuevo = b_leer_nodo(idx, 0);
 375
 376                                 b_leer_header(nuevo, &nuevo_header);
 377                                 nuevo_header.cant = 0;
 378                                 nuevo_header.padre = -1;
 379                                 nuevo_header.nivel = nodo_header.nivel+1;
 380                                 memset(nuevo, -1, idx->tam_bloque);
 381                                 b_actualizar_header(nuevo, &nuevo_header);
 382                                 b_grabar_nodo(idx, 0, nuevo);
 383
 384                                 nodo_id = 0;
 385                                 nodo = nuevo;
 386                                 rompi = 1;
 387                         }
 388                 } else {
 389                         /* La clave entra en este nodo!! */
 390                         i = 0;
 391                         if (nodo_header.cant > 0) {
 392                                 while ((emufs_indice_es_menor(idx, claves[i].clave, clave)) && (i < nodo_header.cant)) i++;
 393                                 for(j=nodo_header.cant; j > i; j--)
 394                                         claves[j] = claves[j-1];
 395                         }
 396                         nodo_header.cant++;
 397                         claves[i].clave = clave;
 398                         claves[i].dato = dato;
 399                         claves[i].hijo_derecho = hijo2;
 400                         nodo_header.hijo_izquierdo = b_elegir_izquierdo(idx, nodo_header.hijo_izquierdo, hijo1);
 401
 402                         b_actualizar_header(nodo, &nodo_header);
 403                         b_grabar_nodo(idx, nodo_id, nodo);
 404
 405                         /* Debo actualizar los punteros al padre de los hijos */
 406                         if (hijo1 != -1) {
 407                                 nuevo = b_leer_nodo(idx, hijo1);
 408                                 if (nuevo != NULL) {
 409                                         b_leer_header(nuevo, &nuevo_header);
 410                                         nuevo_header.padre = nodo_id;
 411                                         b_actualizar_header(nuevo, &nuevo_header);
 412                                         b_grabar_nodo(idx, hijo1, nuevo);
 413                                         free(nuevo);
 414                                 } else printf("FUCK! hijo1=%d no existe!\n", hijo1);
 415                         }
 416                         if (hijo2 != -1) {
 417                                 nuevo = b_leer_nodo(idx, hijo2);
 418                                 if (nuevo != NULL) {
 419                                         b_leer_header(nuevo, &nuevo_header);
 420                                         nuevo_header.padre = nodo_id;
 421                                         b_actualizar_header(nuevo, &nuevo_header);
 422                                         b_grabar_nodo(idx, hijo2, nuevo);
 423                                         free(nuevo);
 424                                 } else printf("FUCK! hijo2=%d no existe!\n", hijo2);
 425                         }
 426                         salir = 1;
 427                 }
 428         } while (!salir);
 429 }
 430
 431 static int b_elegir_izquierdo(INDICE *idx, int a, int b)
 432 {
 433         int cual;
 434         char *nodo1, *nodo2;
 435         B_NodoHeader header1, header2;
 436         B_NodoEntry *claves1, *claves2;
 437
 438         if (a==-1) return b;
 439         if (b==-1) return a;
 440
 441         nodo1 = b_leer_nodo(idx, a);
 442         nodo2 = b_leer_nodo(idx, b);
 443
 444         b_leer_header(nodo1, &header1);
 445         b_leer_header(nodo2, &header2);
 446
 447         claves1 = b_leer_claves(nodo1, &header1);
 448         claves2 = b_leer_claves(nodo2, &header2);
 449
 450         if (emufs_indice_es_menor(idx, claves1[0].clave, claves2[0].clave))
 451                 cual = a;
 452         else
 453                 cual = b;
 454
 455         free(nodo1);
 456         free(nodo2);
 457         return cual;
 458 }
 459
 460 INDICE_DATO *emufs_indice_b_buscar_muchos(INDICE *idx, CLAVE clave, int *cant)
 461 {
 462         /* Si el indice es primario no tiene sentido hacer nada */
 463         if (idx->funcion == IND_PRIMARIO) {
 464                 *cant = 0;
 465                 return NULL;
 466         }
 467
 468         /* TODO Implementar indices con repeticion */
 469         return NULL;
 470 }
 471
 472 static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k)
 473 {
 474         int pos, actual_id, i;
 475         B_NodoHeader header, header_actual;
 476         B_NodoEntry *claves, *claves_actual;
 477         char *actual;
 478
 479         b_leer_header(nodo, &header);
 480         claves = b_leer_claves(nodo, &header);
 481
 482         pos = 0;
 483         /* Busco la posicion dentro de la lista de claves */
 484         while (emufs_indice_es_menor(idx, claves[pos].clave, k)) pos++;
 485
 486         /* Es el nodo una hoja? */
 487         if (header.hijo_izquierdo != -1) {
 488                 /* No!, es un nodo intermedio!! */
 489                 if (pos == 0)
 490                         actual = b_leer_nodo(idx, header.hijo_izquierdo);
 491                 else
 492                         actual = b_leer_nodo(idx, claves[pos+1].hijo_derecho);
 493
 494                 b_leer_header(actual, &header_actual);
 495                 while (header_actual.hijo_izquierdo != -1) {
 496                         actual_id = header_actual.hijo_izquierdo;
 497                         free(actual);
 498                         actual = b_leer_nodo(idx, actual_id);
 499                         b_leer_header(actual, &header_actual);
 500                 }
 501                 claves_actual = b_leer_claves(actual, &header);
 502
 503                 claves[pos] = claves_actual[0];
 504                 pos = 0;
 505                 b_grabar_nodo(idx, nodo_id, nodo);
 506         } else {
 507                 actual = nodo;
 508         }
 509
 510         /* Borro la clave */
 511         for(i=pos; i < header_actual.cant; i++) {
 512                 claves_actual[i] = claves_actual[i+1];
 513         }
 514         header_actual.cant--;
 515         /* Guardo los cambios */
 516         b_actualizar_header(actual, &header_actual);
 517         b_grabar_nodo(idx, actual_id, actual);
 518
 519         /* Se cumple la condicion de hijos? */
 520         if (header_actual.cant >= MIN_HIJOS(idx)) {
 521                 PERR("Borrar completo sin fundir");
 522                 return;
 523         }
 524
 525         /* Tengo que pasar datos o fundir nodos :-( */
 526         PERR("TODO : FUNDIR NODOS!!!!\n");
 527 }
 528