emufs/indice_b.c

   1
   2 #include "indice_b.h"
   3
   4 #define FILENAME "b.idx"
   5 #define BLOCK_SIZE 512
   6
   7 /* Cantidad de claves por nodo */
   8 #define CANT_HIJOS ((BLOCK_SIZE-sizeof(B_NodoHeader))/sizeof(B_NodoEntry))
   9 #define CANT_NODOS (CANT_HIJOS+1)
  10 #define MIN_HIJOS (CANT_HIJOS/2)
  11
  12 /* Auxiliares */
  13 static void b_grabar_nodo(int id, char *data);
  14 static int b_ultimo_id();
  15 static char *b_leer_nodo(int id);
  16 static char *b_crear_nodo();
  17 static void b_leer_header(char *src, B_NodoHeader *header);
  18 static void b_actualizar_header(char *src, B_NodoHeader *header);
  19 static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header);
  20 static void b_insertar_en_nodo(int clave, int ubicacion, int nodo_id, char *nodo, int hijo1, int hijo2);
  21 const int b_elegir_izquierdo(int a, int b);
  22
  23 void b_crear()
  24 {
  25         FILE *fp;
  26         char *bloque;
  27         B_NodoHeader header;
  28
  29         header.cant = 0;
  30         header.nivel = 0;
  31         header.padre = -1;
  32         header.hijo_izquierdo = -1;
  33
  34         fp = fopen(FILENAME, "w");
  35
  36         /* Creo el archivo con el Nodo raiz */
  37         bloque = (char *)malloc(BLOCK_SIZE);
  38         memset(bloque, -1, BLOCK_SIZE);
  39
  40         memcpy(bloque, &header, sizeof(B_NodoHeader));
  41
  42         fwrite(bloque, BLOCK_SIZE, 1, fp);
  43         fclose(fp);
  44 }
  45
  46 int b_insertar(int clave, int ubicacion)
  47 {
  48         int i, nodo_id, padre_id;
  49         B_NodoHeader header;
  50         B_NodoEntry *claves;
  51         char *nodo, *padre;
  52
  53         /* Leo la raiz */
  54         nodo = b_leer_nodo(0);
  55         padre_id = nodo_id = 0;
  56         padre = NULL;
  57         while (nodo) {
  58                 if (padre) free(padre);
  59                 padre = nodo;
  60                 padre_id = nodo_id;
  61                 b_leer_header(nodo, &header);
  62                 claves = b_leer_claves(nodo, &header);
  63                 i=0;
  64                 while ((i<header.cant) && (claves[i].clave < clave)) i++;
  65                 if ((i<header.cant) && (claves[i].clave == clave)) {
  66                         /* CLAVE DUPLICADA! */
  67                         return 0;
  68                 } else {
  69                         if (i == 0) {
  70                                 if (header.nivel != 0) {
  71                                         nodo = b_leer_nodo(header.hijo_izquierdo);
  72                                         nodo_id = header.hijo_izquierdo;
  73                                 } else {
  74                                         nodo = NULL;
  75                                         nodo_id = -1;
  76                                 }
  77                         } else {
  78                                 if (header.nivel != 0) {
  79                                         nodo = b_leer_nodo(claves[i-1].ubicacion);
  80                                         nodo_id = claves[i-1].ubicacion;
  81                                 } else {
  82                                         nodo = NULL;
  83                                         nodo_id = -1;
  84                                 }
  85                         }
  86                 }
  87         }
  88
  89         if (nodo) free(nodo);
  90         nodo = padre;
  91         nodo_id = padre_id;
  92         b_insertar_en_nodo(clave, ubicacion, nodo_id, nodo, -1, -1);
  93         return 1; /* Agregar OK! */
  94 }
  95
  96 int b_buscar(int clave)
  97 {
  98         int i, ret;
  99         B_NodoHeader header;
 100         B_NodoEntry *claves;
 101         char *nodo, *tmp;
 102
 103         /* Leo la raiz */
 104         nodo = b_leer_nodo(0);
 105         while (nodo) {
 106                 b_leer_header(nodo, &header);
 107                 claves = b_leer_claves(nodo, &header);
 108                 i=0;
 109                 while ((i<header.cant) && (claves[i].clave < clave)) i++;
 110                 if (claves[i].clave == clave) {
 111                                 ret = claves[i].ubicacion;
 112                                 free(nodo);
 113                                 return ret;
 114                 } else {
 115                         tmp = nodo;
 116                         if (i == 0) {
 117                                 nodo = b_leer_nodo(header.hijo_izquierdo);
 118                                 printf("Me voy a izquierda = %d\n", header.hijo_izquierdo);
 119                         } else {
 120                                 nodo = b_leer_nodo(claves[i-1].ubicacion);
 121                                 printf("Me voy a hijo=%li\n", claves[i-1].ubicacion);
 122                         }
 123                         free(tmp);
 124                 }
 125         }
 126
 127         /* Nodo no encontrado */
 128         return -1;
 129 }
 130
 131 static int b_ultimo_id()
 132 {
 133         int i;
 134         FILE *fp;
 135         fp = fopen(FILENAME, "r");
 136         fseek(fp, 0, SEEK_END);
 137         i = ftell(fp)/BLOCK_SIZE;
 138         fclose(fp);
 139
 140         return i;
 141 }
 142
 143 static char *b_crear_nodo(int *id)
 144 {
 145         char *bloque;
 146         B_NodoHeader header;
 147
 148         (*id) = b_ultimo_id();
 149
 150         printf("Nuevo nodo creado : id = %d\n", *id);
 151         header.cant = 0;
 152         header.nivel = 0;
 153         header.hijo_izquierdo = -1;
 154         header.padre = -1;
 155
 156         bloque = (char *)malloc(BLOCK_SIZE);
 157         memset(bloque, -1, BLOCK_SIZE);
 158         memcpy(bloque, &header, sizeof(B_NodoHeader));
 159
 160         b_grabar_nodo(*id, bloque);
 161
 162         return bloque;
 163 }
 164
 165 static char *b_leer_nodo(int id)
 166 {
 167         FILE *fp;
 168         char *out;
 169
 170         if (id < 0) return NULL;
 171
 172         fp = fopen(FILENAME, "r");
 173         if (fp == NULL) return NULL;
 174
 175         fseek(fp, id*BLOCK_SIZE, SEEK_SET);
 176
 177         out = (char *)malloc(BLOCK_SIZE);
 178         if (out == NULL) {
 179                 fclose(fp);
 180                 return NULL;
 181         }
 182
 183         if (fread(out, 1, BLOCK_SIZE, fp) != BLOCK_SIZE) {
 184                 free(out);
 185                 /* No se puso leer el nodo */
 186                 fclose(fp);
 187                 return NULL;
 188         }
 189
 190         fclose(fp);
 191         return out;
 192 }
 193
 194 static void b_grabar_nodo(int id, char *data)
 195 {
 196         FILE *fp;
 197
 198 /*      if (id > b_ultimo_id()) {
 199                 printf("AGREGANDO AL FINAL\n");
 200                 fp = fopen(FILENAME, "a");
 201                 if (fp == NULL) {
 202                 _("No se pudo abrir archivo\n");
 203                         return;
 204                 }
 205         } else {
 206                 fp = fopen(FILENAME, "w");
 207                 if (fp == NULL) {
 208                 _("No se pudo abrir archivo\n");
 209                         return;
 210                 }
 211                 fseek(fp, id*BLOCK_SIZE, SEEK_SET);
 212                 printf("SOLO GUARDO DATA\n");
 213         }*/
 214
 215         fp = fopen(FILENAME, "r+");
 216         fseek(fp, id*BLOCK_SIZE, SEEK_SET);
 217         fwrite(data, 1, BLOCK_SIZE, fp);
 218         fclose(fp);
 219 }
 220
 221 static void b_leer_header(char *src, B_NodoHeader *header)
 222 {
 223         if (!src) return;
 224
 225         memcpy(header, src, sizeof(B_NodoHeader));
 226 }
 227
 228 static void b_actualizar_header(char *src, B_NodoHeader *header)
 229 {
 230         if (!src) return;
 231         memcpy(src, header, sizeof(B_NodoHeader));
 232 }
 233
 234 static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header)
 235 {
 236         return (B_NodoEntry *)(src+sizeof(B_NodoHeader));
 237 }
 238
 239 static void b_insertar_en_nodo(int clave, int ubicacion, int nodo_id, char *nodo, int hijo1, int hijo2)
 240 {
 241         char *padre, *nuevo;
 242         int nuevo_id;
 243         int i, j;
 244         static int rompi=0;
 245         char salir = 0;
 246         B_NodoHeader nodo_header, nuevo_header;
 247         B_NodoEntry *claves, *tmp_claves, *claves_nuevo;
 248
 249         do {
 250                 if (!nodo) {
 251                         /* CREAR NODO? */
 252                         nodo = b_crear_nodo(&nodo_id);
 253                 }
 254                 b_leer_header(nodo, &nodo_header);
 255                 claves = b_leer_claves(nodo, &nodo_header);
 256
 257                 padre = b_leer_nodo(nodo_header.padre);
 258
 259                 if (nodo_header.cant == CANT_HIJOS) {
 260                         int total;
 261                         nuevo = b_crear_nodo(&nuevo_id);
 262                         i=0;
 263                         /* Creo una lista ordenada de los nodos a partir */
 264                         tmp_claves = (B_NodoEntry *)malloc(sizeof(B_NodoEntry)*(nodo_header.cant+1));
 265                         total = nodo_header.cant;
 266                         while ((i<nodo_header.cant) && (claves[i].clave < clave)) {
 267                                 tmp_claves[i] = claves[i];
 268                                 i++;
 269                         }
 270                         tmp_claves[i].clave = clave;
 271                         tmp_claves[i].ubicacion = ubicacion;
 272                         while (i < nodo_header.cant) {
 273                                 tmp_claves[i+1] = claves[i];
 274                                 i++;
 275                         }
 276
 277                         /* Asigno a cada nodo lo que corresponde */
 278                         b_leer_header(nuevo, &nuevo_header);
 279
 280                         nuevo_header.nivel = nodo_header.nivel;
 281                         nodo_header.cant = total/2;
 282                         nuevo_header.cant = total - nodo_header.cant;
 283
 284                         memset(claves, '*', BLOCK_SIZE-sizeof(B_NodoHeader));
 285                         for(j=0; j<nodo_header.cant; j++)
 286                                 claves[j] = tmp_claves[j];
 287
 288                         claves_nuevo = b_leer_claves(nuevo, &nuevo_header);
 289                         memset(claves_nuevo, '*', BLOCK_SIZE-sizeof(B_NodoHeader));
 290                         for(j=0; j<nuevo_header.cant; j++)
 291                                 claves_nuevo[j] = tmp_claves[j+total/2+1];
 292
 293                         b_actualizar_header(nodo, &nodo_header);
 294                         b_actualizar_header(nuevo, &nuevo_header);
 295
 296                         if (nodo_id != 0) {
 297                                 clave = tmp_claves[total/2].clave;
 298                                 ubicacion = nuevo_id;
 299
 300                                 b_grabar_nodo(nodo_id, nodo);
 301                                 b_grabar_nodo(nuevo_id, nuevo);
 302                                 free(nodo);
 303                                 free(nuevo);
 304                                 free(tmp_claves);
 305
 306                                 hijo1 = nodo_id;
 307                                 hijo2 = nuevo_id;
 308
 309                                 nodo = padre;
 310                                 nodo_id = nodo_header.padre;
 311                         } else {
 312                                 /* Oops, parti el raiz, y este debe quedar en 0, lo paso a otro bloque
 313                                  * y dejo el padre vacio
 314                                  */
 315                                 char *tmp_nuevo = b_crear_nodo(&nodo_id);
 316                                 memcpy(tmp_nuevo, nodo, BLOCK_SIZE);
 317                                 free(nodo);
 318                                 nodo = tmp_nuevo;
 319
 320                                 clave = tmp_claves[total/2].clave;
 321                                 ubicacion = nuevo_id;
 322
 323                                 b_grabar_nodo(nuevo_id+1, nodo);
 324                                 b_grabar_nodo(nuevo_id, nuevo);
 325
 326                                 free(nodo);
 327                                 free(nuevo);
 328                                 free(tmp_claves);
 329
 330                                 hijo1 = nuevo_id+1;
 331                                 hijo2 = nuevo_id;
 332
 333                                 /* Limpio al padre */
 334                                 nuevo = b_leer_nodo(0);
 335
 336                                 b_leer_header(nuevo, &nuevo_header);
 337                                 nuevo_header.cant = 0;
 338                                 nuevo_header.padre = -1;
 339                                 nuevo_header.nivel = nodo_header.nivel+1;
 340                                 memset(nuevo, -1, BLOCK_SIZE);
 341                                 b_actualizar_header(nuevo, &nuevo_header);
 342                                 b_grabar_nodo(0, nuevo);
 343
 344                                 nodo_id = 0;
 345                                 nodo = nuevo;
 346                                 rompi = 1;
 347                         }
 348                 } else {
 349                         /* La clave entra en este nodo!! */
 350                         i = 0;
 351                         if (nodo_header.cant > 0) {
 352                                 while ((claves[i].clave < clave) && (i < nodo_header.cant)) i++;
 353                                 for(j=nodo_header.cant; j > i; j--)
 354                                         claves[j] = claves[j-1];
 355                         }
 356                         nodo_header.cant++;
 357                         claves[i].clave = clave;
 358                         claves[i].ubicacion = ubicacion;
 359                         nodo_header.hijo_izquierdo = b_elegir_izquierdo(nodo_header.hijo_izquierdo, hijo1);
 360
 361                         b_actualizar_header(nodo, &nodo_header);
 362                         b_grabar_nodo(nodo_id, nodo);
 363
 364                         /* Debo actualizar los punteros al padre de los hijos */
 365                         if (hijo1 != -1) {
 366                                 nuevo = b_leer_nodo(hijo1);
 367                                 if (nuevo != NULL) {
 368                                         b_leer_header(nuevo, &nuevo_header);
 369                                         nuevo_header.padre = nodo_id;
 370                                         b_actualizar_header(nuevo, &nuevo_header);
 371                                         b_grabar_nodo(hijo1, nuevo);
 372                                         free(nuevo);
 373                                 } else printf("FUCK! hijo1=%d no existe!\n", hijo1);
 374                         }
 375                         if (hijo2 != -1) {
 376                                 nuevo = b_leer_nodo(hijo2);
 377                                 if (nuevo != NULL) {
 378                                         b_leer_header(nuevo, &nuevo_header);
 379                                         nuevo_header.padre = nodo_id;
 380                                         b_actualizar_header(nuevo, &nuevo_header);
 381                                         b_grabar_nodo(hijo2, nuevo);
 382                                         free(nuevo);
 383                                 } else printf("FUCK! hijo2=%d no existe!\n", hijo2);
 384                         }
 385                         salir = 1;
 386                 }
 387         } while (!salir);
 388 }
 389
 390 const int b_elegir_izquierdo(int a, int b)
 391 {
 392         int cual;
 393         char *nodo1, *nodo2;
 394         B_NodoHeader header1, header2;
 395         B_NodoEntry *claves1, *claves2;
 396
 397         if (a==-1) return b;
 398         if (b==-1) return a;
 399
 400         nodo1 = b_leer_nodo(a);
 401         nodo2 = b_leer_nodo(b);
 402
 403         b_leer_header(nodo1, &header1);
 404         b_leer_header(nodo2, &header2);
 405
 406         claves1 = b_leer_claves(nodo1, &header1);
 407         claves2 = b_leer_claves(nodo2, &header2);
 408
 409         if (claves1[0].clave < claves2[0].clave)
 410                 cual = a;
 411         else
 412                 cual = b;
 413
 414         free(nodo1);
 415         free(nodo2);
 416         return cual;
 417 }
 418