emufs/indice_bplus.c

   1 /** Arbol B+ */
   2 #include "tipo1.h"
   3 #include "tipo3.h"
   4 #include "indices.h"
   5 #include "indice_bplus.h"
   6
   7 /**#*#*#*#*#**#*#*#*#*#* Private prototypes*#*#*#*#*#**#*#*#*#*#**#*#*#*/
   8 int b_plus_grabar_nodo(INDICE *idx, NODO_B_PLUS *nodo, int num_node);
   9 NODO_B_PLUS *b_plus_leer_nodo(INDICE *idx, int num_node);
  10 NODO_B_PLUS *b_plus_crearnodo(INDICE *idx);
  11 int b_plus_destruir_nodo(NODO_B_PLUS *nodo);
  12 int b_plus_split_child(INDICE *idx, int numparent, NODO_B_PLUS *parent, int ithchild, NODO_B_PLUS *fullnode);
  13 int b_plus_insert_nonfull(INDICE *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DAT *query);
  14 int b_plus_insertar(INDICE *idx, INDEX_DAT *query);
  15 int b_plus_get_num_nodo(INDICE *idx);
  16 /**#*#*#*#*#**#*#*#*#*#*FIN PROTOTYPES*#*#*#*#*#**#*#*#*#*#**#*#*#*#*#*/
  17
  18 /** Crea un nuevo nodo y lo inicializa */
  19 NODO_B_PLUS *b_plus_crearnodo(INDICE *idx) {
  20
  21         NODO_B_PLUS *nodo = (NODO_B_PLUS*)malloc(sizeof(NODO_B_PLUS));
  22         if (nodo == NULL) return NULL;
  23         nodo->nivel = 0;
  24         nodo->cant_claves = 0;
  25
  26     /* Calculamos lo que ocupan las cadenas de bytes claves + hijos */
  27         nodo->claves = (CLAVE*)malloc(idx->size_claves);
  28         nodo->hijos = (int*)malloc(idx->size_hijos);
  29         memset(nodo->claves,-1,idx->size_claves);
  30         memset(nodo->hijos,-1,idx->size_hijos);
  31
  32     return nodo;
  33 }
  34
  35 /** Crea el archivo indice B+ */
  36 int emufs_b_plus_crear(INDICE *idx) {
  37
  38         FILE *fp;
  39         NODO_B_PLUS *raiz;
  40         int error = 0;
  41
  42         /* Creamos el archivo que contendra el indice */
  43         fp = fopen(idx->filename, "w");
  44         PERR("Creando indice con nodo raiz");
  45         if (fp == NULL) {
  46                 PERR("Error al crear el archivo");
  47                 return -1;
  48         }
  49         fclose(fp);
  50
  51         /* Creamos el nodo raiz y lo guardamos el en indice */
  52         raiz = b_plus_crearnodo(idx);
  53         error = b_plus_grabar_nodo(idx,raiz,0);
  54
  55         /* Liberamos areas de memoria reservadas */
  56         free(raiz->claves);
  57         free(raiz->hijos);
  58         free(raiz);
  59
  60         return error;
  61 }
  62
  63
  64 /** Busca el nro de bloque donde se debe guardar un reg con clave X.
  65  *  Posibilidades: return 0 - Encontro un bloque potencial
  66  *                 return -1 - No hay clave, inserto clave de nuevo bloques
  67  *                 return 1 - Hubo falla de lectura de un nodo, Abortar
  68  */
  69 int emufs_b_plus_get_bloque(INDICE *idx, INDEX_DAT *query, int num_node) {
  70
  71         int i,exitcode = 0;
  72         NODO_B_PLUS *nodo;
  73         nodo = b_plus_leer_nodo(idx,num_node);
  74         if (nodo == NULL) return 1;
  75         i = nodo->cant_claves - 1;
  76
  77         /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */
  78         if (nodo->nivel == 0) {
  79         /* Vemos en que bloque deberia ir */
  80                 while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])) i--;
  81                 if (i < 0) {
  82                         /* La clave es menor que todas, debo insertarla */
  83                         b_plus_destruir_nodo(nodo);
  84                         /*emufs_b_plus_insertar(idx,query);     */
  85                         return -1;
  86                 }
  87                 else {
  88                         /* Encontre un bloque potencial */
  89                         query->num_bloque = nodo->hijos[i];
  90                         b_plus_destruir_nodo(nodo);
  91                         return 0;
  92                 }
  93         }
  94         else {
  95                 /* Buscamos por donde descender al siguiente nivel */
  96                 while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])) i--;
  97         i++;
  98         num_node = nodo->hijos[i];
  99                 b_plus_destruir_nodo(nodo);
 100                 exitcode = emufs_b_plus_get_bloque(idx,query,num_node);
 101                 return exitcode;
 102         }
 103 }
 104
 105 NODO_B_PLUS *b_plus_leer_nodo(INDICE *idx, int num_node) {
 106
 107         /*int i = 0;*/
 108         FILE *fp;
 109         NODO_B_PLUS *memnode = b_plus_crearnodo(idx);
 110         char *disknode = (char*)malloc(idx->tam_bloque);
 111
 112         if (num_node < 0) {
 113                 PERR("Se intento leer nodo negativo!!\n");
 114                 exit(1);
 115         }
 116         if (disknode == NULL) return NULL;
 117         if (memnode == NULL) return NULL;
 118
 119     /* Open up file */
 120         fp = fopen(idx->filename, "r+");
 121         if (fp == NULL) {
 122                 free(disknode);
 123                 b_plus_destruir_nodo(memnode);
 124                 return NULL;
 125         }
 126
 127         /* Intentamos leer un nodo, sino podemos error! */
 128         fseek(fp, num_node*idx->tam_bloque, SEEK_SET);
 129         if (fread(disknode, idx->tam_bloque, 1, fp) != 1) {
 130                 free(disknode);
 131                 fclose(fp);
 132                 return NULL;
 133         }
 134         fclose(fp);
 135
 136         /* Pudimos leer un nodo de disco, ahora lo transformamos a nodo mem */
 137         memcpy(memnode,disknode,SIZE_B_PLUS_HEADER);
 138         memcpy(memnode->claves,disknode+SIZE_B_PLUS_HEADER,idx->size_claves);
 139         memcpy(memnode->hijos,disknode+SIZE_B_PLUS_HEADER+idx->size_claves,idx->size_hijos);
 140         free(disknode);
 141
 142         /*printf("Dumping Node_%i\n",num_node);
 143         printf("Nivel: %i  Cant Claves: %i\n",memnode->nivel,memnode->cant_claves);
 144         printf("Claves:");
 145         for (i = 0; i < idx->size_claves/sizeof(CLAVE); ++i) printf(" %i",memnode->claves[i].i_clave);
 146         printf("\nHijos:");
 147         for (i = 0; i < idx->size_hijos/sizeof(int); ++i) printf(" %i",memnode->hijos[i]);
 148         printf("\nEnd Dump\n"); */
 149
 150         return memnode;
 151
 152 }
 153
 154 int b_plus_grabar_nodo(INDICE *idx, NODO_B_PLUS *nodo, int num_node)
 155 {
 156         FILE *fp;
 157
 158         fp = fopen(idx->filename, "r+");
 159         if (fp == NULL) return -1;
 160
 161         fseek(fp,num_node*(SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos),SEEK_SET);
 162         fwrite(nodo,SIZE_B_PLUS_HEADER,1,fp);
 163         fwrite(nodo->claves,idx->size_claves,1,fp);
 164         fwrite(nodo->hijos,idx->size_hijos,1,fp);
 165         fclose(fp);
 166
 167         return 0;
 168 }
 169
 170 int b_plus_destruir_nodo(NODO_B_PLUS *nodo)
 171 {
 172         free(nodo->claves);
 173         free(nodo->hijos);
 174         free(nodo);
 175         return 0;
 176 }
 177
 178 int b_plus_split_child(INDICE *idx, int numparent, NODO_B_PLUS *parent, int ithchild, NODO_B_PLUS *fullnode)
 179 {
 180         /* locals */
 181         int minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1;
 182         int numbrother,j = 0;
 183         int es_interno = 1;
 184
 185         NODO_B_PLUS *brother = b_plus_crearnodo(idx);
 186         brother->nivel = fullnode->nivel; /* Idem nivel que el que se parte */
 187
 188         /* Si estoy en una hoja, la parte derecha del partido tendra minclaves+1 */
 189         /* pues el ancla se debe repetir ademas de subir */
 190         if (brother->nivel == 0) {
 191                 brother->cant_claves = minclaves+1;
 192                 es_interno = 0;
 193         }
 194         else brother->cant_claves = minclaves;
 195
 196         /* Copio las claves al brother derecho */
 197         for (j = 0; j < brother->cant_claves; ++j)
 198                 brother->claves[j] = fullnode->claves[j+minclaves+es_interno];
 199
 200         /* Copio los hijos ya sea para hoja o no hoja. */
 201         for (j = 0; j < brother->cant_claves+1; ++j)
 202                 brother->hijos[j] = fullnode->hijos[j+minclaves+es_interno];
 203
 204         /* Ahora me ocupo del nodo que se partio */
 205         fullnode->cant_claves = minclaves;
 206         /* Obtengo numero de nodo para brother y encadeno si es hoja */
 207         numbrother = b_plus_get_num_nodo(idx);
 208         if (fullnode->nivel == 0) fullnode->hijos[minclaves] = numbrother;
 209
 210         /* Ahora fixeamos el padre, apuntando al nuevo hijo */
 211         for (j = parent->cant_claves; j > ithchild; --j)
 212                 parent->hijos[j+1] = parent->hijos[j];
 213         parent->hijos[ithchild+1] = numbrother;
 214
 215         /* Idem pero subo la median key */
 216         for (j = parent->cant_claves-1; j >= ithchild; --j)
 217                 parent->claves[j+1] = parent->claves[j];
 218         parent->claves[ithchild] = fullnode->claves[minclaves];
 219         parent->cant_claves++;
 220
 221         /* Grabo los nodos en disco */
 222         b_plus_grabar_nodo(idx,fullnode,parent->hijos[ithchild]);
 223         b_plus_grabar_nodo(idx,brother,numbrother);
 224         b_plus_grabar_nodo(idx,parent,numparent);
 225
 226         b_plus_destruir_nodo(brother);
 227
 228         return 0;
 229 }
 230
 231
 232 int b_plus_insert_nonfull(INDICE *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DAT *query)
 233 {
 234     int i, num_nodo_hijo;
 235     NODO_B_PLUS *hijo;
 236
 237     i = nodo->cant_claves-1;
 238     if ( nodo->nivel == 0 ){
 239                 /* Muevo siempre el encadenamiento */
 240                 nodo->hijos[i+2] = nodo->hijos[i+1];
 241                 /* Ahora muevo las claves y sus punteros a bloques del dat */
 242         while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])){
 243             nodo->claves[i+1] = nodo->claves[i];
 244                         nodo->hijos[i+1] = nodo->hijos[i];
 245             i--;
 246         }
 247         nodo->claves[i+1] = query->clave;
 248                 nodo->hijos[i+1] = query->num_bloque;
 249         nodo->cant_claves++;
 250         b_plus_grabar_nodo(idx, nodo, num_nodo);
 251     } else {
 252         while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i]))
 253             i--;
 254         i++;
 255         num_nodo_hijo = nodo->hijos[i];
 256         hijo = b_plus_leer_nodo(idx, num_nodo_hijo);
 257         if ( hijo->cant_claves == idx->size_claves/sizeof(CLAVE) ) {
 258             b_plus_split_child(idx, num_nodo, nodo, i, hijo);
 259                         /* OjO Utilizo el menor pero con el proposito de clave > nodo->clave) */
 260             if (emufs_indice_es_menor(idx,nodo->claves[i],query->clave))
 261                 i++;
 262         }
 263                 if (hijo) b_plus_destruir_nodo(hijo);
 264                 hijo = b_plus_leer_nodo(idx, nodo->hijos[i]);
 265         b_plus_insert_nonfull(idx, hijo, nodo->hijos[i], query);
 266                 if (hijo) b_plus_destruir_nodo(hijo);
 267     }
 268
 269         return 0;
 270 }
 271
 272 int emufs_b_plus_insertar(INDICE *idx, INDEX_DAT *query)
 273 {
 274     NODO_B_PLUS *raiz;
 275
 276     raiz = b_plus_leer_nodo(idx, 0);
 277     if ( raiz->cant_claves == idx->size_claves/sizeof(CLAVE) ) {
 278         NODO_B_PLUS *new_root = b_plus_crearnodo(idx);
 279         new_root->nivel = raiz->nivel + 1;
 280         new_root->hijos[0] = b_plus_get_num_nodo(idx);
 281         b_plus_grabar_nodo(idx, raiz, new_root->hijos[0]);
 282         b_plus_grabar_nodo(idx, new_root, 0);
 283             b_plus_split_child(idx, 0, new_root, 0, raiz);
 284         b_plus_insert_nonfull(idx, new_root, 0, query);
 285                 b_plus_destruir_nodo(new_root);
 286     } else
 287         {
 288                 b_plus_insert_nonfull(idx, raiz, 0, query);
 289         }
 290
 291         b_plus_destruir_nodo(raiz);
 292
 293     return 0;
 294 }
 295
 296 /** Busca una clave dentro del arbol e indica si existe o no
 297  *  Posibilidades: return 1 - Encontro la clave
 298  *                 return 0 - No encontro la clave
 299  *                 return -1 - Hubo falla de lectura de un nodo, Abortar
 300  */
 301 int b_plus_existe_clave(INDICE *idx, INDEX_DAT *query, int num_node)
 302 {
 303         int i,exitcode = 0;
 304         NODO_B_PLUS *nodo;
 305         nodo = b_plus_leer_nodo(idx,num_node);
 306         if (nodo == NULL) return -1;
 307         i = nodo->cant_claves - 1;
 308
 309         /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */
 310         if (nodo->nivel == 0) {
 311         /* Vemos si esta la clave */
 312                 while ( i >= 0 && !emufs_indice_es_igual(idx,query->clave,nodo->claves[i])) i--;
 313                 if (i < 0)
 314                 {
 315                         b_plus_destruir_nodo(nodo);
 316                         return 0; /* No encontre la clave */
 317                 } else  {
 318                         /* Encontre la clave, guardo el nodo donde esta! */
 319                         query->num_bloque = num_node;
 320                         b_plus_destruir_nodo(nodo);
 321                         return 1;
 322                 }
 323         }
 324         else {
 325                 /* Buscamos por donde descender al siguiente nivel */
 326                 while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])) i--;
 327         i++;
 328         num_node = nodo->hijos[i];
 329                 b_plus_destruir_nodo(nodo);
 330                 exitcode = b_plus_existe_clave(idx,query,num_node);
 331                 return exitcode;
 332         }
 333 }
 334
 335 int b_plus_cant_claves_nodo(INDICE *idx, int num_node)
 336 {
 337         NODO_B_PLUS *nodo =     b_plus_leer_nodo(idx,num_node);
 338         if (nodo == NULL) return -1;
 339         return nodo->cant_claves;
 340 }
 341
 342 /* Search_Type: 0 - Predecesor, 1 - Sucesor
 343    Exitcode: 1 - Encontre lo buscado, 0 - No lo encontre, -1 Error */
 344 int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepostkey, int search_type)
 345 {
 346         int i = 0, exitcode = 0;
 347         NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node);
 348         if (nodo == NULL) return -1;
 349         i = nodo->cant_claves - 1;
 350
 351         if (nodo->nivel == 0) {
 352                 while ( i >= 0 && emufs_indice_es_menor(idx,key,nodo->claves[i])) --i;
 353                 switch (search_type) {
 354                         /* Busco predecesor en la hoja */
 355                         case 0: if (i <= 0) exitcode = 0;
 356                                         else {
 357                                                 if (emufs_indice_es_igual(idx,nodo->claves[i],key))     {
 358                                                         prepostkey->clave = nodo->claves[i-1];
 359                                                         prepostkey->num_bloque = nodo->hijos[i-1];
 360                                                 } else {
 361                                                         prepostkey->clave = nodo->claves[i];
 362                                                         prepostkey->num_bloque = nodo->hijos[i];
 363                                                 }
 364                                                 exitcode = 1;
 365                                         }
 366                                         break;
 367                         /* Busco sucesor en la hoja */
 368                         case 1: if ((nodo->claves[i].i_clave == key.i_clave) && (i == nodo->cant_claves-1)) exitcode = 0;
 369                                         else {
 370                                                 prepostkey->clave = nodo->claves[i+1];
 371                                                 prepostkey->num_bloque = nodo->hijos[i+1];
 372                                                 exitcode = 1;
 373                                         }
 374                                         break;
 375                 }
 376         } else {
 377                 /* Veo por que rama debo seguir buscando el pre o post */
 378                 while ( i >= 0 && emufs_indice_es_menor(idx,key,nodo->claves[i])) --i;
 379                 if (search_type == 0) {
 380                         if (i < 0) exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
 381                         else {
 382                                 /* Busco primero por la rama derecha, sino por la izquierda */
 383                                 exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
 384                                 if (exitcode == 0)
 385                                         exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i],prepostkey,search_type);
 386                         }
 387                         /* Handleo busqueda de clave menor o igual que todas */
 388                         if (exitcode == 0) exitcode = -1;
 389                 } else  {
 390                         /* Busco un sucesor, y funciona como getbloque... */
 391                         exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
 392                         /* Veo si tengo que devolver la clave izquierda del padre del que acabo de buscar */
 393                         if (exitcode == 0) {
 394                                 if (i < nodo->cant_claves-1) {
 395                                         prepostkey->clave = nodo->claves[i+1];
 396                                         exitcode = 1;
 397                                 } else  exitcode = -1;
 398                         }
 399                 }
 400         }
 401
 402         /* Libero y devuelvo exitcode */
 403         b_plus_destruir_nodo(nodo);
 404         return(exitcode);
 405 }
 406
 407 int emufs_b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query, int num_node)
 408 {
 409         NODO_B_PLUS *nodo;
 410         int i;
 411         INDEX_DAT auxquery;
 412         auxquery.clave = key;
 413
 414         /* Comienzo buscando la clave y obteniendo el nodo en donde esta */
 415         if (b_plus_existe_clave(idx,&auxquery,num_node) == 1) {
 416
 417                 /* Levanto el nodo y busco donde esta la clave */
 418                 /*printf("El reemplazar encontro la clave %i y en el nodo %i\n",auxquery.clave.i_clave,(int)auxquery.num_bloque);*/
 419                 nodo = b_plus_leer_nodo(idx,auxquery.num_bloque);
 420                 if (nodo == NULL) return -1;
 421                 i = nodo->cant_claves - 1;
 422
 423                 /* Busco la clave y reemplazo */
 424                 while ( i >= 0 && !emufs_indice_es_igual(idx,key,nodo->claves[i])) --i;
 425                 if (i < 0) return -1; /* Error, no esta la clave */
 426
 427                 /* Cheque por las dudas si es hoja o interno, aunque deberia ser hoja */
 428                 if (nodo->nivel > 0) {
 429                         nodo->claves[i] = query.clave;
 430                 } else {
 431                         nodo->claves[i] = query.clave;
 432                         nodo->hijos[i] = query.num_bloque;
 433                 }
 434                 b_plus_grabar_nodo(idx,nodo,auxquery.num_bloque);
 435                 b_plus_destruir_nodo(nodo);
 436                 return 0;
 437         }
 438         else return -1;
 439 }
 440
 441 int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)
 442 {
 443         INDEX_DAT prepostkey;
 444         int i = 0,j = 0,minclaves = 0, nivel_mayor1 = 0,cant_claves_child = 0;
 445         int cant_claves_rsibling = 0, cant_claves_lsibling = 0, es_hoja = 0;
 446         int leftoffset = 0;
 447         NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node);
 448         NODO_B_PLUS *node_y,*node_z,*mergenode,*siblingnode;
 449         if (nodo == NULL) { PERR("No leyo nodo bien"); return -1; }
 450         i = nodo->cant_claves - 1;
 451         minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1;
 452
 453         /* Si es hoja, borro directamente la clave. No se producira underflow
 454        pues lo asegura la recursividad del delete */
 455         if (nodo->nivel == 0) {
 456                 while ( i >= 0 && !emufs_indice_es_igual(idx,key,nodo->claves[i])) --i;
 457                 if (i < 0) return -1;
 458                 /* Encontre la clave en la pos i, la borro */
 459                 for (j = i; j < nodo->cant_claves-1; ++j) {
 460                         nodo->claves[j] = nodo->claves[j+1];
 461                         nodo->hijos[j] = nodo->hijos[j+1];
 462                 }
 463                 nodo->hijos[j] = nodo->hijos[j+1];
 464         nodo->cant_claves--;
 465
 466                 /* Grabo el nodo actualizado en disco */
 467                 b_plus_grabar_nodo(idx,nodo,num_node);
 468                 b_plus_destruir_nodo(nodo);
 469                 return 0;
 470         } else {
 471                 /* Me debo fijar si esta la clave en este nodo interno, sino busco */
 472                 while ( i >= 0 && !emufs_indice_es_igual(idx,key,nodo->claves[i])) --i;
 473                 if (i < 0) {
 474                         PERR("Entre caso 3 del eliminar");
 475                         /* No esta en este nodo interno, caso 3. Determino en que rama debe estar */
 476                         i = nodo->cant_claves - 1;
 477                         while ( i >= 0 && emufs_indice_es_menor(idx,key,nodo->claves[i])) --i;
 478                 i++;
 479                 cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]);
 480                         if (cant_claves_child > minclaves) emufs_b_plus_eliminar(idx,key,nodo->hijos[i]);
 481                         else {
 482                                 /* Vemos si estamos en caso 3a o 3b, mirando cant_claves de sus siblings */
 483                                 if (i < nodo->cant_claves) cant_claves_rsibling = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]);
 484                                 if (i > 0) cant_claves_lsibling = b_plus_cant_claves_nodo(idx,nodo->hijos[i-1]);
 485                                 printf ("El sibling derecho si existe tiene %i claves\n", cant_claves_rsibling);
 486                                 printf ("El sibling izquierdo si existe tiene %i claves\n", cant_claves_lsibling);
 487                                 if (cant_claves_rsibling > minclaves) {
 488                                         /* El sibling derecho me dara una key mediante rotacion. Caso 3a */
 489                                         PERR("Entre caso 3a right sibling del eliminar");
 490                                         node_y = b_plus_leer_nodo(idx,nodo->hijos[i]);
 491                                         node_z = b_plus_leer_nodo(idx,nodo->hijos[i+1]);
 492                                         if (node_z->nivel == 0) es_hoja = 1;
 493                                         /* Le bajo la del padre a NodeY y muevo el apropiado child de NodoZ a NodoY */
 494                                         node_y->claves[cant_claves_child] = nodo->claves[i];
 495                                         node_y->hijos[cant_claves_child+1] = node_y->hijos[cant_claves_child];
 496                                         node_y->hijos[cant_claves_child+1-es_hoja] = node_z->hijos[0];
 497                                         node_y->cant_claves++;
 498                                         /* Le subo al padre desde el NodoZ, teniendo en cuenta si es hoja o no */
 499                                         nodo->claves[i] = node_z->claves[es_hoja];
 500                                         /* Hago shifting en el sibling para quitar la que subio */
 501                                         for (j = 0; j < node_z->cant_claves-1; ++j) {
 502                                                 node_z->claves[j] = node_z->claves[j+1];
 503                                                 node_z->hijos[j] = node_z->hijos[j+1];
 504                                         }
 505                                         node_z->hijos[j] = node_z->hijos[j+1];
 506                                 node_z->cant_claves--;
 507                                         /* Grabo los cambios */
 508                                         b_plus_grabar_nodo(idx,node_z,nodo->hijos[i+1]);
 509                                         b_plus_grabar_nodo(idx,node_y,nodo->hijos[i]);
 510                                         b_plus_grabar_nodo(idx,nodo,num_node);
 511                                         b_plus_destruir_nodo(node_y);
 512                                         b_plus_destruir_nodo(node_z);
 513                                         /* Borro recursivamente KEY entrando por Child que ahora tiene minclaves+1 */
 514                                         emufs_b_plus_eliminar(idx,key,nodo->hijos[i]);
 515                                 }
 516                                 else if (cant_claves_lsibling > minclaves) {
 517                                                 /* el sibling izquierdo me dara una key mediante rotacion Caso 3a */
 518                                                 PERR("Entre caso 3a left sibling del eliminar");
 519                                                 node_z = b_plus_leer_nodo(idx,nodo->hijos[i]);
 520                                                 node_y = b_plus_leer_nodo(idx,nodo->hijos[i-1]);
 521                                                 if (node_z->nivel == 0) es_hoja = 1;
 522                                             /* Hago lugar en NodoZ para la clave que bajara desde el padre */
 523                                                 /* Muevo el ultimo y restantes claves/punteros */
 524                                                 j = node_z->cant_claves - 1;
 525                                                 node_z->hijos[j+2] = node_z->hijos[j+1];
 526                                         while (j >= 0){
 527                                         node_z->claves[j+1] = node_z->claves[j];
 528                                                         node_z->hijos[j+1] = node_z->hijos[j];
 529                                         j--;
 530                                         }
 531                                                 /* Hago la rotacion final segun sea hoja o no */
 532                                                 if (es_hoja) {
 533                                                         nodo->claves[i-1] = node_y->claves[cant_claves_lsibling-1];
 534                                                         node_z->claves[0] = node_y->claves[cant_claves_lsibling-1];
 535                                                         node_z->hijos[0] = node_y->hijos[cant_claves_lsibling-1];
 536                                                         node_y->hijos[cant_claves_lsibling-1] = node_y->hijos[cant_claves_lsibling]; /* cadena */
 537                                                         node_y->cant_claves--;
 538                                                         node_z->cant_claves++;
 539                                                 } else {
 540                                                         node_z->claves[0] = nodo->claves[i-1];
 541                                                         node_z->hijos[0] = node_y->hijos[cant_claves_lsibling];
 542                                                         nodo->claves[i-1] = node_y->claves[cant_claves_lsibling-1];
 543                                                         node_y->cant_claves--;
 544                                                         node_z->cant_claves++;
 545                                                 }
 546                                                 /* Grabo los cambios */
 547                                                 b_plus_grabar_nodo(idx,node_y,nodo->hijos[i-1]);
 548                                                 b_plus_grabar_nodo(idx,node_z,nodo->hijos[i]);
 549                                                 b_plus_grabar_nodo(idx,nodo,num_node);
 550                                                 b_plus_destruir_nodo(node_y);
 551                                                 b_plus_destruir_nodo(node_z);
 552                                                 /* Borro recursivamente KEY entrando por Child que ahora tiene minclaves+1 */
 553                                                 emufs_b_plus_eliminar(idx,key,nodo->hijos[i]);
 554                                         } else {
 555                                                 /* Caso 3b, debo bajar una clave y unificar con sibling disponible */
 556                                                 PERR("Entre caso 3b del eliminar");
 557                                                 if (cant_claves_lsibling == minclaves) {
 558                                                         PERR("Hago merge con sibling izquierdo");
 559                                                         leftoffset = 1;
 560                                                         siblingnode = b_plus_leer_nodo(idx,nodo->hijos[i]);     /* Este es el root de la rama! */
 561                                                         mergenode = b_plus_leer_nodo(idx,nodo->hijos[i-1]); /* Aca va todo */
 562                                                 } else {
 563                                                         PERR("Hago merge con sibling derecho");
 564                                                         leftoffset = 0;
 565                                                         mergenode = b_plus_leer_nodo(idx,nodo->hijos[i]);
 566                                                         siblingnode = b_plus_leer_nodo(idx,nodo->hijos[i+1]);
 567                                                 }
 568
 569                                                 /* Bajo una clave del Padre Nodo a MergeNode y muevo todo lo SiblingNode a MergeNode */
 570                                                 /* Si es nivel mayor a 1, bajo clave, otherwise no bajo pues se repetiria */
 571                                                 nivel_mayor1 = 0;
 572                                                 if (nodo->nivel > 1) {
 573                                                         nivel_mayor1 = 1;
 574                                                         mergenode->claves[minclaves] = nodo->claves[i-leftoffset];
 575                                                 }
 576                                                 for (j = 0; j < minclaves; ++j) mergenode->claves[j+minclaves+nivel_mayor1] = siblingnode->claves[j];
 577                                                 for (j = 0; j < minclaves+1; ++j) mergenode->hijos[j+minclaves+nivel_mayor1] = siblingnode->hijos[j];
 578                                                 mergenode->cant_claves = minclaves*2+nivel_mayor1;
 579
 580                                                 /* Shifteo en el nodo padre NODO, para quitar la que bajo */
 581                                                 for (j = i-leftoffset; j < nodo->cant_claves-1; ++j) {
 582                                                         nodo->claves[j] = nodo->claves[j+1];
 583                                                         nodo->hijos[j+1] = nodo->hijos[j+2];
 584                                                 }
 585                                                 nodo->cant_claves--;
 586                                                 b_plus_grabar_nodo(idx,nodo,num_node);
 587                                                 b_plus_grabar_nodo(idx,mergenode,nodo->hijos[i-leftoffset]);
 588                                                 b_plus_destruir_nodo(mergenode);
 589                                                 b_plus_destruir_nodo(siblingnode);
 590                                                 /* Elimino recursivamente Key de la rama apropiada segun el Merge que se hizo */
 591                                                 emufs_b_plus_eliminar(idx,key,nodo->hijos[i-leftoffset]);
 592                                                 /* Caso muy particular, si hize un merge de la unica clave de una raiz con sus hijos */
 593                                                 if ((nodo->nivel == 1) && (nodo->cant_claves == 0)) {
 594                                                         /* Debo establecer como nueva raiz, el NodoY */
 595                                                         mergenode = b_plus_leer_nodo(idx,nodo->hijos[i-leftoffset]);
 596                                                         b_plus_grabar_nodo(idx,mergenode,0);
 597                                                         truncate(idx->filename,SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos);
 598                                                 }
 599                                                 /* End 3b */
 600                                                 }
 601                                         }
 602                 } else {
 603                         /* Esta en el nodo interno, caso 2 */
 604                         cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]);
 605                         if (cant_claves_child > minclaves) {
 606                                 PERR("Entre caso 2a del eliminar");
 607                                 /* Caso 2a, comienzo buscando la clave previa inmediata */
 608                                 b_plus_buscar_prepost(idx,key,nodo->hijos[i],&prepostkey,0);
 609                                 /* La elimino recursivamente */
 610                                 emufs_b_plus_eliminar(idx,prepostkey.clave,nodo->hijos[i]); /* CHEAT */
 611                                 /* Remplazo mi clave key por la encontrada prekey */
 612                                 nodo->claves[i] = prepostkey.clave;
 613                                 b_plus_grabar_nodo(idx,nodo,num_node);
 614                                 /* Remplazo la otra instancia de key en una hoja seguro por prekey */
 615                                 emufs_b_plus_reemplazar_clave(idx,key,prepostkey,nodo->hijos[i+1]);
 616                         } else {
 617                                 cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]);
 618                                 if (cant_claves_child > minclaves) {
 619                                         PERR("Entre caso 2b del eliminar");
 620                                         /* Caso 2b, comienzo buscando la clave sucesor inmediata */
 621                                         b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],&prepostkey,1);
 622                                         /* La elimino recursivamente */
 623                                         emufs_b_plus_eliminar(idx,prepostkey.clave,nodo->hijos[i+1]); /* CHEAT */
 624                                         /* Remplazo mi clave key por la encontrada postkey */
 625                                         nodo->claves[i] = prepostkey.clave;
 626                                         b_plus_grabar_nodo(idx,nodo,num_node);
 627                                         /* Remplazo la otra instancia de key en una hoja seguro por postkey */
 628                                         emufs_b_plus_reemplazar_clave(idx,key,prepostkey,nodo->hijos[i+1]);
 629                                 } else {
 630                                         PERR("Entre caso 2c del eliminar");
 631                                         /* Caso 2c debo hacer un merge de la clave con hijo izq y der */
 632                                         node_y = b_plus_leer_nodo(idx,nodo->hijos[i]);
 633                                         node_z = b_plus_leer_nodo(idx,nodo->hijos[i+1]);
 634                                         /* Bajo la clave Key a NodoY y muevo todo lo de NodoZ a NodoY */
 635                                         /* Si es nivel mayor a 1, bajo clave pues no esta en NodoZ, otherwise no bajo */
 636                                         if (nodo->nivel > 1) {
 637                                                 nivel_mayor1 = 1;
 638                                                 node_y->claves[minclaves] = key;
 639                                         }
 640                                         for (j = 0; j < minclaves; ++j) node_y->claves[j+minclaves+nivel_mayor1] = node_z->claves[j];
 641                                         for (j = 0; j < minclaves+1; ++j) node_y->hijos[j+minclaves+nivel_mayor1] = node_z->hijos[j];
 642                                         node_y->cant_claves = minclaves*2+nivel_mayor1;
 643                                         /* Shifteo en el nodo padre NODO, para quitar la que bajo */
 644                                         for (j = i; j < nodo->cant_claves-1; ++j) {
 645                                                 nodo->claves[j] = nodo->claves[j+1];
 646                                                 nodo->hijos[j+1] = nodo->hijos[j+2];
 647                                         }
 648                                         nodo->cant_claves--;
 649                                         b_plus_grabar_nodo(idx,nodo,num_node);
 650                                         b_plus_grabar_nodo(idx,node_y,nodo->hijos[i]);
 651                                         b_plus_destruir_nodo(node_y);
 652                                         b_plus_destruir_nodo(node_z);
 653                                         /* Elimino recursivamente Key de NodeY, entrando por ese subtree */
 654                                         emufs_b_plus_eliminar(idx,key,nodo->hijos[i]);
 655                                         /* Caso muy particular, si hize un merge de la unica clave de una raiz con sus hijos */
 656                                         if ((nodo->nivel == 1) && (nodo->cant_claves == 0)) {
 657                                                 /* Debo establecer como nueva raiz, el NodoY */
 658                                                 node_y = b_plus_leer_nodo(idx,nodo->hijos[i]);
 659                                                 b_plus_grabar_nodo(idx,node_y,0);
 660                                                 truncate(idx->filename,SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos);
 661                                                 b_plus_destruir_nodo(node_y);
 662                                         }
 663                                 }
 664                         }
 665                 }
 666                 /* Termine caso 2 o 3, libero el nodo */
 667                 b_plus_destruir_nodo(nodo);
 668                 return 0;
 669         }
 670
 671         return -1;
 672 }
 673
 674 int b_plus_get_num_nodo(INDICE *idx)
 675 {
 676         FILE *fp;
 677         int num;
 678
 679         fp = fopen(idx->filename, "ab");
 680         if (fp == NULL) return -1;
 681
 682     num = ftell(fp)/(SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos);
 683     fclose(fp);
 684     return num;
 685 }
 686
 687 CLAVE emufs_b_plus_obtener_menor_clave(INDICE *idx) {
 688
 689         CLAVE key;
 690         NODO_B_PLUS *node;
 691         int num_child = 0;
 692         node = b_plus_leer_nodo(idx,0);
 693         if (node == NULL) {
 694                 key.i_clave = -1;
 695                 return key;
 696         }
 697
 698         while (node->nivel > 0) {
 699                 /* Deciendo por la rama de mas hacia la izquierda */
 700                 if (node->cant_claves > 0) {
 701                         num_child = node->hijos[0];
 702                         b_plus_destruir_nodo(node);
 703                         node = b_plus_leer_nodo(idx,num_child);
 704                 }
 705                 else break;
 706         }
 707
 708         /* Ahora estoy en la primer hoja del arbol, devuelvo la primer clave */
 709         key = node->claves[0];
 710         b_plus_destruir_nodo(node);
 711
 712         return key;
 713 }
 714
 715 CLAVE emufs_b_plus_obtener_mayor_clave(INDICE *idx) {
 716
 717         CLAVE key;
 718         NODO_B_PLUS *node;
 719         int num_child = 0, cant_claves = 0;
 720         node = b_plus_leer_nodo(idx,0);
 721         if (node == NULL) {
 722                 key.i_clave = -1;
 723                 return key;
 724         }
 725
 726         cant_claves = node->cant_claves;
 727         while (node->nivel > 0) {
 728                 /* Deciendo por la rama de mas hacia la derecha */
 729                 if (node->cant_claves > 0) {
 730                         num_child = node->hijos[cant_claves];
 731                         b_plus_destruir_nodo(node);
 732                         node = b_plus_leer_nodo(idx,num_child);
 733                         cant_claves = node->cant_claves;
 734                 }
 735                 else return key;
 736         }
 737
 738         /* Ahora estoy en la primer hoja del arbol, devuelvo la ultima clave */
 739         key = node->claves[cant_claves-1];
 740         b_plus_destruir_nodo(node);
 741
 742         return key;
 743 }
 744
 745 CLAVE emufs_b_plus_obtener_sig_clave(EMUFS *emu, CLAVE key) {
 746
 747         INDICE *idx = emu->indices;
 748         INDEX_DAT query;
 749         int i = 0;
 750         query.clave = key;
 751
 752         /* Si aun no tengo un array, obtengo uno */
 753         if (emu->indices->keybucket == NULL) {
 754                 /* Busco el ancla para esta key */
 755                 emufs_b_plus_get_bloque(idx,&query,0);
 756                 idx->keybucket = emufs_tipo3_obtener_claves_raw(emu,query.num_bloque);
 757                 printf ("\nLevante bloque nro: %li y obtuve un bucket con %i keys\n",query.num_bloque,idx->keybucket->cant_keys);
 758                 return (idx->keybucket->claves[0]);
 759         }
 760         else {
 761                 /* Veo si la ultima clave retornada es la ultima del array */
 762                 if (idx->keybucket->current_key == idx->keybucket->cant_keys-1) {
 763                         /* Debo obtener un nuevo bucket de claves */
 764                         if (b_plus_buscar_prepost(idx,key,0,&query,1) != -1) {
 765                                 idx->keybucket = emufs_tipo3_obtener_claves_raw(emu,query.num_bloque);
 766                                 printf ("\nLevante bloque nro: %li y obtuve un bucket con %i keys\n",query.num_bloque,idx->keybucket->cant_keys);
 767                         }
 768                         else return key;
 769                 }
 770         }
 771
 772         /* Busco la clave en el array de atras hacia adelante. */
 773         if (idx->keybucket->current_key < idx->keybucket->cant_keys-1) {
 774                 i = idx->keybucket->cant_keys - 1;
 775                 while (i >= 0 && emufs_indice_es_menor(idx,key,idx->keybucket->claves[i])) --i;
 776                 ++i;
 777                 idx->keybucket->current_key = i;
 778                 return (idx->keybucket->claves[i]);
 779         }
 780         else return key;
 781 }