X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/140c0b9274254d1e18c27ff2678613fd42d550f0..fe7cadabd775ddd59714749b7dfe31a578c6ecca:/emufs/indice_bplus.c?ds=sidebyside diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c index d0fdf58..aafc65b 100644 --- a/emufs/indice_bplus.c +++ b/emufs/indice_bplus.c @@ -75,11 +75,11 @@ int emufs_b_plus_get_bloque(INDICE *idx, INDEX_DAT *query, int num_node) { /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */ if (nodo->nivel == 0) { /* Vemos en que bloque deberia ir */ - while ( i >= 0 && query->clave.i_clave < nodo->claves[i].i_clave ) i--; + while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])) i--; if (i < 0) { /* La clave es menor que todas, debo insertarla */ b_plus_destruir_nodo(nodo); - /*emufs_b_plus_insertar(idx,query);*/ + /*emufs_b_plus_insertar(idx,query); */ return -1; } else { @@ -91,7 +91,7 @@ int emufs_b_plus_get_bloque(INDICE *idx, INDEX_DAT *query, int num_node) { } else { /* Buscamos por donde descender al siguiente nivel */ - while ( i >= 0 && query->clave.i_clave < nodo->claves[i].i_clave ) i--; + while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])) i--; i++; num_node = nodo->hijos[i]; b_plus_destruir_nodo(nodo); @@ -234,9 +234,11 @@ int b_plus_insert_nonfull(INDICE *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DA i = nodo->cant_claves-1; if ( nodo->nivel == 0 ){ - while ( i >= 0 && query->clave.i_clave < nodo->claves[i].i_clave ){ - nodo->claves[i+1] = nodo->claves[i]; - nodo->hijos[i+2] = nodo->hijos[i+1]; + /* Muevo siempre el encadenamiento */ + nodo->hijos[i+2] = nodo->hijos[i+1]; + /* Ahora muevo las claves y sus punteros a bloques del dat */ + while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])){ + nodo->claves[i+1] = nodo->claves[i]; nodo->hijos[i+1] = nodo->hijos[i]; i--; } @@ -245,14 +247,15 @@ int b_plus_insert_nonfull(INDICE *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DA nodo->cant_claves++; b_plus_grabar_nodo(idx, nodo, num_nodo); } else { - while ( i >= 0 && query->clave.i_clave < nodo->claves[i].i_clave ) + while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])) i--; i++; num_nodo_hijo = nodo->hijos[i]; hijo = b_plus_leer_nodo(idx, num_nodo_hijo); if ( hijo->cant_claves == idx->size_claves/sizeof(CLAVE) ) { b_plus_split_child(idx, num_nodo, nodo, i, hijo); - if ( query->clave.i_clave > nodo->claves[i].i_clave ) + /* OjO Utilizo el menor pero con el proposito de clave > nodo->clave) */ + if (emufs_indice_es_menor(idx,nodo->claves[i],query->clave)) i++; } if (hijo) b_plus_destruir_nodo(hijo); @@ -304,7 +307,7 @@ int b_plus_existe_clave(INDICE *idx, INDEX_DAT *query, int num_node) /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */ if (nodo->nivel == 0) { /* Vemos si esta la clave */ - while ( i >= 0 && query->clave.i_clave != nodo->claves[i].i_clave ) i--; + while ( i >= 0 && !emufs_indice_es_igual(idx,query->clave,nodo->claves[i])) i--; if (i < 0) { b_plus_destruir_nodo(nodo); @@ -318,7 +321,7 @@ int b_plus_existe_clave(INDICE *idx, INDEX_DAT *query, int num_node) } else { /* Buscamos por donde descender al siguiente nivel */ - while ( i >= 0 && query->clave.i_clave < nodo->claves[i].i_clave ) i--; + while ( i >= 0 && emufs_indice_es_menor(idx,query->clave,nodo->claves[i])) i--; i++; num_node = nodo->hijos[i]; b_plus_destruir_nodo(nodo); @@ -344,12 +347,12 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepo i = nodo->cant_claves - 1; if (nodo->nivel == 0) { - while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i; + while ( i >= 0 && emufs_indice_es_menor(idx,key,nodo->claves[i])) --i; switch (search_type) { /* Busco predecesor en la hoja */ case 0: if (i <= 0) exitcode = 0; else { - if (nodo->claves[i].i_clave == key.i_clave) { + if (emufs_indice_es_igual(idx,nodo->claves[i],key)) { prepostkey->clave = nodo->claves[i-1]; prepostkey->num_bloque = nodo->hijos[i-1]; } else { @@ -360,17 +363,17 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepo } break; /* Busco sucesor en la hoja */ - case 1: if ((nodo->claves[i].i_clave == key.i_clave) && (i == nodo->cant_claves-1)) exitcode = 0; - else { + case 1: if (emufs_indice_es_igual(idx,nodo->claves[i],key) && (i == nodo->cant_claves-1)) exitcode = 0; + else { prepostkey->clave = nodo->claves[i+1]; - prepostkey->num_bloque = nodo->hijos[i+i]; + prepostkey->num_bloque = nodo->hijos[i+1]; exitcode = 1; } break; } } else { /* Veo por que rama debo seguir buscando el pre o post */ - while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i; + while ( i >= 0 && emufs_indice_es_menor(idx,key,nodo->claves[i])) --i; if (search_type == 0) { if (i < 0) exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type); else { @@ -399,24 +402,24 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepo return(exitcode); } -int b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query) +int emufs_b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query, int num_node) { NODO_B_PLUS *nodo; int i; INDEX_DAT auxquery; - auxquery.clave = key; + auxquery.clave = key; /* Comienzo buscando la clave y obteniendo el nodo en donde esta */ - if (b_plus_existe_clave(idx,&auxquery,0) == 1) { + if (b_plus_existe_clave(idx,&auxquery,num_node) == 1) { /* Levanto el nodo y busco donde esta la clave */ - printf("El reemplazar encontro la clave %i y en el nodo %i\n",auxquery.clave.i_clave,(int)auxquery.num_bloque); + /*printf("El reemplazar encontro la clave %i y en el nodo %i\n",auxquery.clave.i_clave,(int)auxquery.num_bloque);*/ nodo = b_plus_leer_nodo(idx,auxquery.num_bloque); if (nodo == NULL) return -1; i = nodo->cant_claves - 1; /* Busco la clave y reemplazo */ - while ( i >= 0 && key.i_clave != nodo->claves[i].i_clave ) --i; + while ( i >= 0 && !emufs_indice_es_igual(idx,key,nodo->claves[i])) --i; if (i < 0) return -1; /* Error, no esta la clave */ /* Cheque por las dudas si es hoja o interno, aunque deberia ser hoja */ @@ -436,17 +439,19 @@ int b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query) int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) { INDEX_DAT prepostkey; - int i = 0,j = 0,minclaves = 0, cant_claves_child = 0; + int i = 0,j = 0,minclaves = 0, nivel_mayor1 = 0,cant_claves_child = 0; + int cant_claves_rsibling = 0, cant_claves_lsibling = 0, es_hoja = 0; + int leftoffset = 0; NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node); - NODO_B_PLUS *hijoder,*hijoizq; - if (nodo == NULL) return -1; + NODO_B_PLUS *node_y,*node_z,*mergenode,*siblingnode; + if (nodo == NULL) { PERR("No leyo nodo bien"); return -1; } i = nodo->cant_claves - 1; minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1; /* Si es hoja, borro directamente la clave. No se producira underflow pues lo asegura la recursividad del delete */ if (nodo->nivel == 0) { - while ( i >= 0 && key.i_clave != nodo->claves[i].i_clave ) --i; + while ( i >= 0 && !emufs_indice_es_igual(idx,key,nodo->claves[i])) --i; if (i < 0) return -1; /* Encontre la clave en la pos i, la borro */ for (j = i; j < nodo->cant_claves-1; ++j) { @@ -462,50 +467,203 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) return 0; } else { /* Me debo fijar si esta la clave en este nodo interno, sino busco */ - while ( i >= 0 && key.i_clave != nodo->claves[i].i_clave ) --i; + while ( i >= 0 && !emufs_indice_es_igual(idx,key,nodo->claves[i])) --i; if (i < 0) { - /* No esta en este nodo interno, caso 3 */ + PERR("Entre caso 3 del eliminar"); + /* No esta en este nodo interno, caso 3. Determino en que rama debe estar */ + i = nodo->cant_claves - 1; + while ( i >= 0 && emufs_indice_es_menor(idx,key,nodo->claves[i])) --i; + i++; + cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]); + if (cant_claves_child > minclaves) emufs_b_plus_eliminar(idx,key,nodo->hijos[i]); + else { + /* Vemos si estamos en caso 3a o 3b, mirando cant_claves de sus siblings */ + if (i < nodo->cant_claves) cant_claves_rsibling = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]); + if (i > 0) cant_claves_lsibling = b_plus_cant_claves_nodo(idx,nodo->hijos[i-1]); + printf ("El sibling derecho si existe tiene %i claves\n", cant_claves_rsibling); + printf ("El sibling izquierdo si existe tiene %i claves\n", cant_claves_lsibling); + if (cant_claves_rsibling > minclaves) { + /* El sibling derecho me dara una key mediante rotacion. Caso 3a */ + PERR("Entre caso 3a right sibling del eliminar"); + node_y = b_plus_leer_nodo(idx,nodo->hijos[i]); + node_z = b_plus_leer_nodo(idx,nodo->hijos[i+1]); + if (node_z->nivel == 0) es_hoja = 1; + /* Le bajo la del padre a NodeY y muevo el apropiado child de NodoZ a NodoY */ + node_y->claves[cant_claves_child] = nodo->claves[i]; + node_y->hijos[cant_claves_child+1] = node_y->hijos[cant_claves_child]; + node_y->hijos[cant_claves_child+1-es_hoja] = node_z->hijos[0]; + node_y->cant_claves++; + /* Le subo al padre desde el NodoZ, teniendo en cuenta si es hoja o no */ + nodo->claves[i] = node_z->claves[es_hoja]; + /* Hago shifting en el sibling para quitar la que subio */ + for (j = 0; j < node_z->cant_claves-1; ++j) { + node_z->claves[j] = node_z->claves[j+1]; + node_z->hijos[j] = node_z->hijos[j+1]; + } + node_z->hijos[j] = node_z->hijos[j+1]; + node_z->cant_claves--; + /* Grabo los cambios */ + b_plus_grabar_nodo(idx,node_z,nodo->hijos[i+1]); + b_plus_grabar_nodo(idx,node_y,nodo->hijos[i]); + b_plus_grabar_nodo(idx,nodo,num_node); + b_plus_destruir_nodo(node_y); + b_plus_destruir_nodo(node_z); + /* Borro recursivamente KEY entrando por Child que ahora tiene minclaves+1 */ + emufs_b_plus_eliminar(idx,key,nodo->hijos[i]); + } + else if (cant_claves_lsibling > minclaves) { + /* el sibling izquierdo me dara una key mediante rotacion Caso 3a */ + PERR("Entre caso 3a left sibling del eliminar"); + node_z = b_plus_leer_nodo(idx,nodo->hijos[i]); + node_y = b_plus_leer_nodo(idx,nodo->hijos[i-1]); + if (node_z->nivel == 0) es_hoja = 1; + /* Hago lugar en NodoZ para la clave que bajara desde el padre */ + /* Muevo el ultimo y restantes claves/punteros */ + j = node_z->cant_claves - 1; + node_z->hijos[j+2] = node_z->hijos[j+1]; + while (j >= 0){ + node_z->claves[j+1] = node_z->claves[j]; + node_z->hijos[j+1] = node_z->hijos[j]; + j--; + } + /* Hago la rotacion final segun sea hoja o no */ + if (es_hoja) { + nodo->claves[i-1] = node_y->claves[cant_claves_lsibling-1]; + node_z->claves[0] = node_y->claves[cant_claves_lsibling-1]; + node_z->hijos[0] = node_y->hijos[cant_claves_lsibling-1]; + node_y->hijos[cant_claves_lsibling-1] = node_y->hijos[cant_claves_lsibling]; /* cadena */ + node_y->cant_claves--; + node_z->cant_claves++; + } else { + node_z->claves[0] = nodo->claves[i-1]; + node_z->hijos[0] = node_y->hijos[cant_claves_lsibling]; + nodo->claves[i-1] = node_y->claves[cant_claves_lsibling-1]; + node_y->cant_claves--; + node_z->cant_claves++; + } + /* Grabo los cambios */ + b_plus_grabar_nodo(idx,node_y,nodo->hijos[i-1]); + b_plus_grabar_nodo(idx,node_z,nodo->hijos[i]); + b_plus_grabar_nodo(idx,nodo,num_node); + b_plus_destruir_nodo(node_y); + b_plus_destruir_nodo(node_z); + /* Borro recursivamente KEY entrando por Child que ahora tiene minclaves+1 */ + emufs_b_plus_eliminar(idx,key,nodo->hijos[i]); + } else { + /* Caso 3b, debo bajar una clave y unificar con sibling disponible */ + PERR("Entre caso 3b del eliminar"); + if (cant_claves_lsibling == minclaves) { + PERR("Hago merge con sibling izquierdo"); + leftoffset = 1; + siblingnode = b_plus_leer_nodo(idx,nodo->hijos[i]); /* Este es el root de la rama! */ + mergenode = b_plus_leer_nodo(idx,nodo->hijos[i-1]); /* Aca va todo */ + } else { + PERR("Hago merge con sibling derecho"); + leftoffset = 0; + mergenode = b_plus_leer_nodo(idx,nodo->hijos[i]); + siblingnode = b_plus_leer_nodo(idx,nodo->hijos[i+1]); + } + + /* Bajo una clave del Padre Nodo a MergeNode y muevo todo lo SiblingNode a MergeNode */ + /* Si es nivel mayor a 1, bajo clave, otherwise no bajo pues se repetiria */ + nivel_mayor1 = 0; + if (nodo->nivel > 1) { + nivel_mayor1 = 1; + mergenode->claves[minclaves] = nodo->claves[i-leftoffset]; + } + for (j = 0; j < minclaves; ++j) mergenode->claves[j+minclaves+nivel_mayor1] = siblingnode->claves[j]; + for (j = 0; j < minclaves+1; ++j) mergenode->hijos[j+minclaves+nivel_mayor1] = siblingnode->hijos[j]; + mergenode->cant_claves = minclaves*2+nivel_mayor1; + + /* Shifteo en el nodo padre NODO, para quitar la que bajo */ + for (j = i-leftoffset; j < nodo->cant_claves-1; ++j) { + nodo->claves[j] = nodo->claves[j+1]; + nodo->hijos[j+1] = nodo->hijos[j+2]; + } + nodo->cant_claves--; + b_plus_grabar_nodo(idx,nodo,num_node); + b_plus_grabar_nodo(idx,mergenode,nodo->hijos[i-leftoffset]); + b_plus_destruir_nodo(mergenode); + b_plus_destruir_nodo(siblingnode); + /* Elimino recursivamente Key de la rama apropiada segun el Merge que se hizo */ + emufs_b_plus_eliminar(idx,key,nodo->hijos[i-leftoffset]); + /* Caso muy particular, si hize un merge de la unica clave de una raiz con sus hijos */ + if ((nodo->nivel == 1) && (nodo->cant_claves == 0)) { + /* Debo establecer como nueva raiz, el NodoY */ + mergenode = b_plus_leer_nodo(idx,nodo->hijos[i-leftoffset]); + b_plus_grabar_nodo(idx,mergenode,0); + truncate(idx->filename,SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos); + } + /* End 3b */ + } + } } else { /* Esta en el nodo interno, caso 2 */ cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]); if (cant_claves_child > minclaves) { + PERR("Entre caso 2a del eliminar"); /* Caso 2a, comienzo buscando la clave previa inmediata */ b_plus_buscar_prepost(idx,key,nodo->hijos[i],&prepostkey,0); /* La elimino recursivamente */ - emufs_b_plus_eliminar(idx,prepostkey.clave,0); + emufs_b_plus_eliminar(idx,prepostkey.clave,nodo->hijos[i]); /* CHEAT */ /* Remplazo mi clave key por la encontrada prekey */ nodo->claves[i] = prepostkey.clave; + b_plus_grabar_nodo(idx,nodo,num_node); /* Remplazo la otra instancia de key en una hoja seguro por prekey */ - emufs_b_plus_reemplazar_clave(idx,key,prepostkey.clave); + emufs_b_plus_reemplazar_clave(idx,key,prepostkey,nodo->hijos[i+1]); } else { cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]); if (cant_claves_child > minclaves) { - /* Caso 2b, comienzo buscando la clave previa inmediata */ - b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],&prepostkey,1); + PERR("Entre caso 2b del eliminar"); + /* Caso 2b, comienzo buscando la clave sucesor inmediata */ + b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],&prepostkey,1); /* La elimino recursivamente */ - emufs_b_plus_eliminar(idx,prepostkey.clave,0); + emufs_b_plus_eliminar(idx,prepostkey.clave,nodo->hijos[i+1]); /* CHEAT */ /* Remplazo mi clave key por la encontrada postkey */ nodo->claves[i] = prepostkey.clave; + b_plus_grabar_nodo(idx,nodo,num_node); /* Remplazo la otra instancia de key en una hoja seguro por postkey */ - emufs_b_plus_reemplazar_clave(idx,key,prepostkey.clave); + emufs_b_plus_reemplazar_clave(idx,key,prepostkey,nodo->hijos[i+1]); } else { + PERR("Entre caso 2c del eliminar"); /* Caso 2c debo hacer un merge de la clave con hijo izq y der */ node_y = b_plus_leer_nodo(idx,nodo->hijos[i]); node_z = b_plus_leer_nodo(idx,nodo->hijos[i+1]); /* Bajo la clave Key a NodoY y muevo todo lo de NodoZ a NodoY */ - node_y->claves[minclaves] = nodo->claves[i]; - for (j = 0; j < minclaves; ++j) node_y->claves[j+minclaves+1] = node_z->claves[j]; - for (j = 0; j < minclaves+1; ++j) node_y->hijos[j+minclaves+1] = node_z->hijos[j]; - b_plus_destruir_nodo(z); + /* Si es nivel mayor a 1, bajo clave pues no esta en NodoZ, otherwise no bajo */ + if (nodo->nivel > 1) { + nivel_mayor1 = 1; + node_y->claves[minclaves] = key; + } + for (j = 0; j < minclaves; ++j) node_y->claves[j+minclaves+nivel_mayor1] = node_z->claves[j]; + for (j = 0; j < minclaves+1; ++j) node_y->hijos[j+minclaves+nivel_mayor1] = node_z->hijos[j]; + node_y->cant_claves = minclaves*2+nivel_mayor1; /* Shifteo en el nodo padre NODO, para quitar la que bajo */ for (j = i; j < nodo->cant_claves-1; ++j) { nodo->claves[j] = nodo->claves[j+1]; nodo->hijos[j+1] = nodo->hijos[j+2]; } - } + nodo->cant_claves--; + b_plus_grabar_nodo(idx,nodo,num_node); + b_plus_grabar_nodo(idx,node_y,nodo->hijos[i]); + b_plus_destruir_nodo(node_y); + b_plus_destruir_nodo(node_z); + /* Elimino recursivamente Key de NodeY, entrando por ese subtree */ + emufs_b_plus_eliminar(idx,key,nodo->hijos[i]); + /* Caso muy particular, si hize un merge de la unica clave de una raiz con sus hijos */ + if ((nodo->nivel == 1) && (nodo->cant_claves == 0)) { + /* Debo establecer como nueva raiz, el NodoY */ + node_y = b_plus_leer_nodo(idx,nodo->hijos[i]); + b_plus_grabar_nodo(idx,node_y,0); + truncate(idx->filename,SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos); + b_plus_destruir_nodo(node_y); + } } - } - } + } + } + /* Termine caso 2 o 3, libero el nodo */ + b_plus_destruir_nodo(nodo); + return 0; } return -1; @@ -519,8 +677,7 @@ int b_plus_get_num_nodo(INDICE *idx) fp = fopen(idx->filename, "ab"); if (fp == NULL) return -1; - num = ftell(fp)/(SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos); - printf("Num Nodo Nuevo: %i\n",num); + num = ftell(fp)/(SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos); fclose(fp); return num; }