emufs/indice_b_asc.c

   1
   2
   3 static void b_asc_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2);
   4
   5 int emufs_indice_b_asc_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato)
   6 {
   7         int i, nodo_id, padre_id;
   8         B_NodoHeader header;
   9         B_NodoEntry *claves;
  10         char *nodo, *padre;
  11         INDICE_DATO dummy;
  12
  13         /* Leo la raiz */
  14         nodo = b_leer_nodo(idx, 0);
  15         padre_id = nodo_id = 0;
  16         padre = NULL;
  17         while (nodo) {
  18                 if (padre) free(padre);
  19                 padre = nodo;
  20                 padre_id = nodo_id;
  21                 b_leer_header(nodo, &header);
  22                 claves = b_leer_claves(nodo, &header);
  23                 i=0;
  24                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
  25                 if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, clave))) {
  26                         if (idx->funcion == IND_PRIMARIO) {
  27                                 PERR("Indice primario no puede contener claves duplicadas!");
  28                                 PERR(idx->nombre);
  29                                 return 0;
  30                         }
  31
  32                         b_insertar_dup_en_pos(idx, claves[i].dato, dato);
  33
  34                         if (idx->tipo_dato == IDX_STRING) {
  35                                 /* Tengo que sacar el texto repetido del archivo de textos */
  36                                 idx->emu_string->borrar_registro(idx->emu_string, clave, dummy);
  37                         }
  38                         return 1;
  39                 } else {
  40                         if (i == 0) {
  41                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
  42                                 nodo_id = header.hijo_izquierdo;
  43                         } else {
  44                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
  45                                 nodo_id = claves[i-1].hijo_derecho;
  46                         }
  47                 }
  48         }
  49
  50         if (nodo) free(nodo);
  51         nodo = padre;
  52         nodo_id = padre_id;
  53
  54         if (idx->funcion != IND_PRIMARIO) {
  55                 /* Agrego el DATO real al archivo de claves repetiras
  56                  * y me guardo el ID para poner en el indice
  57                  */
  58                 dummy.id = -1;
  59                 dato.id = b_insertar_dup_en_pos(idx, dummy, dato);
  60         }
  61
  62         b_asc_insertar_en_nodo(idx, clave, dato, nodo_id, nodo, -1, -1);
  63         return 1; /* Agregar OK! */
  64 }
  65
  66
  67 static void b_asc_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2)
  68 {
  69         char *padre, *nuevo;
  70         int nuevo_id;
  71         int i, j;
  72         static int rompi=0;
  73         char salir = 0;
  74         char *izq, *der;
  75         B_NodoHeader nodo_header, nuevo_header;
  76         B_NodoEntry *claves, *tmp_claves, *claves_nuevo;
  77
  78         do {
  79                 if (!nodo) {
  80                         /* CREAR NODO? */
  81                         nodo = b_crear_nodo(idx, &nodo_id);
  82                 }
  83                 b_leer_header(nodo, &nodo_header);
  84                 claves = b_leer_claves(nodo, &nodo_header);
  85
  86                 padre = b_leer_nodo(idx, nodo_header.padre);
  87
  88                 if (nodo_header.cant == CANT_HIJOS(idx)) {
  89                         int total;
  90                         if (nodo_id != 0) {
  91                                 int izq_id, der_id, pos_padre, i;
  92                                 B_NodoHeader padre_header, header_der, header_izq;
  93                                 B_NodoEntry *padre_claves, nuevo_entry;
  94                                 B_NodoEntry a_pasar, *buffer, clave_que_sale;
  95
  96                                 b_leer_header(padre, &padre_header);
  97                                 padre_claves = b_leer_claves(padre, &padre_header);
  98
  99                          /* nuevo_entry = new entry(clave, dato, hijo_der) */
 100                                 PERR("Buscando que hijo soy");
 101                                 for(pos_padre=0; (padre_claves[pos_padre].hijo_derecho != nodo_id); pos_padre++)        {       }
 102
 103                                 if (pos_padre == padre_header.cant) {
 104                                         PERR("ERROR GRAVE. Padre no me contiene :-(");
 105                                 }
 106
 107                                 /* Busco mis hermanos a derecha e izquierda, si es que existen */
 108                                 PERR("Ya me encontre, busco a mis hermanos");
 109                                 if (pos_padre >= 0) {
 110                                         if (pos_padre == 0)
 111                                                 izq_id = padre_header.hijo_izquierdo;
 112                                         else
 113                                                 izq_id = padre_claves[pos_padre-1].hijo_derecho;
 114                                         izq = b_leer_nodo(idx, izq_id);
 115                                         b_leer_header(izq, &header_izq);
 116                                 } else {
 117                                         izq_id = -1;
 118                                 }
 119                                 if (pos_padre < padre_header.cant) {
 120                                         der_id = padre_claves[pos_padre+1].hijo_derecho;
 121                                         der = b_leer_nodo(idx, der_id);
 122                                         b_leer_header(der, &header_der);
 123                                 } else {
 124                                         der_id = -1;
 125                                 }
 126                                 PERR("Hermanos encontrados");
 127
 128                                 buffer = malloc((nodo_header.cant+1)*sizeof(B_NodoEntry));
 129
 130                                 nuevo_entry.clave = clave;
 131                                 nuevo_entry.dato = dato;
 132                                 nuevo_entry.hijo_derecho = hijo2;
 133
 134                                 /* Inserto ordenado */
 135                                 for(i=0; (i<nodo_header.cant) && emufs_indice_es_menor(idx, claves[i].clave, clave); i++)
 136                                         buffer[i] = claves[i];
 137                                 buffer[i] = nuevo_entry;
 138                                 while (i<nodo_header.cant) {
 139                                         buffer[i+1] = claves[i];
 140                                         i++;
 141                                 }
 142
 143                                 if ((der_id != -1) && (header_der.cant < CANT_HIJOS(idx))) {
 144                                         /* tomo la clave mas grande */
 145                                         a_pasar = buffer[nodo_header.cant];
 146
 147                                         /* la paso a la derecha */
 148                                         b_pasar_clave_a_derecha(idx, der, der_id, padre, nodo_header.padre, pos_padre, a_pasar);
 149                                         /* Dejo en nodo las claves que corresponden */
 150                                         memcpy(claves, buffer, nodo_header.cant*sizeof(B_NodoEntry));
 151                                         b_grabar_nodo(idx, der_id, der);
 152                                         b_grabar_nodo(idx, nodo_header.padre, padre);
 153                                         b_grabar_nodo(idx, nodo_id, nodo);
 154                                         free(buffer);
 155                                         free(nodo);
 156                                         free(der);
 157                                         free(padre);
 158                                         return;
 159                                 }
 160
 161                                 if ((izq_id != -1) && (header_izq.cant < CANT_HIJOS(idx))) {
 162                                         PERR("ESTOY PASANDO CLAVE A IZQUIERDA");
 163                                         a_pasar = buffer[0];
 164                                         b_pasar_clave_a_izquierda(idx, izq, izq_id, padre, nodo_header.padre, pos_padre, a_pasar, hijo1, padre_claves[pos_padre].hijo_derecho);
 165                                         /* Pongo las claves que quedan en el nodo */
 166                                         memcpy(claves, buffer+1, nodo_header.cant*sizeof(B_NodoEntry));
 167                                         b_grabar_nodo(idx, izq_id, izq);
 168                                         b_grabar_nodo(idx, nodo_header.padre, padre);
 169                                         b_grabar_nodo(idx, nodo_id, nodo);
 170                                         free(buffer);
 171                                         free(nodo);
 172                                         free(izq);
 173                                         free(padre);
 174                                         return;
 175                                 }
 176
 177                                 /* Tengo que partir, tengo que sacar una clave del padre y mandarla al partir */
 178                                 clave_que_sale = padre_claves[pos_padre];
 179                                 clave_que_sale.hijo_derecho = -1;
 180                                 for(i=pos_padre; i<padre_header.cant-1; i++)
 181                                         padre_claves[i] = padre_claves[i+1];
 182                                 padre_header.cant--;
 183                                 b_actualizar_header(padre, &padre_header);
 184                                 b_grabar_nodo(idx, nodo_header.padre, padre);
 185                                 if (izq_id != -1)
 186                                         b_partir_dos_nodos_en_tres(idx, izq_id, nodo_id, clave_que_sale, nuevo_entry, nodo_header.padre);
 187                                 else // Siempre alguno tiene que existir.
 188                                         b_partir_dos_nodos_en_tres(idx, nodo_id, der_id, clave_que_sale, nuevo_entry, nodo_header.padre);
 189                                 return;
 190                         }
 191
 192                         /* Bueno, soy la raiz, tengo que tratarla como el arbol B */
 193                         /* Sigo con a fullllllllll */
 194                         nuevo = b_crear_nodo(idx, &nuevo_id);
 195                         i=0;
 196                         /* Creo una lista ordenada de los nodos a partir */
 197                         tmp_claves = (B_NodoEntry *)malloc(sizeof(B_NodoEntry)*(nodo_header.cant+1));
 198                         total = nodo_header.cant+1;
 199                         while ((i<nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) {
 200                                 tmp_claves[i] = claves[i];
 201                                 i++;
 202                         }
 203                         tmp_claves[i].clave = clave;
 204                         tmp_claves[i].dato = dato;
 205                         /*tmp_claves[i].hijo_derecho = hijo1;*/
 206                         if (i==0) {
 207                                 nodo_header.hijo_izquierdo = hijo1;
 208                                 tmp_claves[i].hijo_derecho = hijo2;
 209                         } else {
 210                                 tmp_claves[i-1].hijo_derecho = hijo1;
 211                                 tmp_claves[i].hijo_derecho = hijo2;
 212                         }
 213                         while (i < nodo_header.cant) {
 214                                 tmp_claves[i+1] = claves[i];
 215                                 i++;
 216                         }
 217
 218                         /* Asigno a cada nodo lo que corresponde */
 219                         b_leer_header(nuevo, &nuevo_header);
 220
 221                         nuevo_header.nivel = nodo_header.nivel;
 222                         nodo_header.cant = total/2;
 223                         nuevo_header.cant = (total-1) - nodo_header.cant;
 224
 225                         memset(claves, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 226                         for(j=0; j<nodo_header.cant; j++)
 227                                 claves[j] = tmp_claves[j];
 228
 229                         claves_nuevo = b_leer_claves(nuevo, &nuevo_header);
 230                         memset(claves_nuevo, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 231                         for(j=0; j<nuevo_header.cant; j++)
 232                                 claves_nuevo[j] = tmp_claves[j+total/2+1];
 233
 234                         b_actualizar_header(nodo, &nodo_header);
 235                         b_actualizar_header(nuevo, &nuevo_header);
 236
 237                         if (nodo_id != 0) {
 238                                 clave = tmp_claves[total/2].clave;
 239                                 dato = tmp_claves[total/2].dato;
 240
 241                                 b_grabar_nodo(idx, nodo_id, nodo);
 242                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 243                                 free(nodo);
 244                                 free(nuevo);
 245                                 free(tmp_claves);
 246
 247                                 hijo1 = nodo_id;
 248                                 hijo2 = nuevo_id;
 249
 250                                 nodo = padre;
 251                                 nodo_id = nodo_header.padre;
 252                         } else {
 253                                 /* Oops, parti el raiz, y este debe quedar en 0, lo paso a otro bloque
 254                                  * y dejo el padre vacio
 255                                  */
 256                                 char *tmp_nuevo = b_crear_nodo(idx, &nodo_id);
 257                                 memcpy(tmp_nuevo, nodo, idx->tam_bloque);
 258                                 free(nodo);
 259                                 nodo = tmp_nuevo;
 260
 261                                 clave = tmp_claves[total/2].clave;
 262                                 dato = tmp_claves[total/2].dato;
 263
 264                                 b_grabar_nodo(idx, nuevo_id+1, nodo);
 265                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 266
 267                                 free(nodo);
 268                                 free(nuevo);
 269                                 free(tmp_claves);
 270
 271                                 hijo1 = nuevo_id+1;
 272                                 hijo2 = nuevo_id;
 273
 274                                 /* Limpio al padre */
 275                                 nuevo = b_leer_nodo(idx, 0);
 276
 277                                 b_leer_header(nuevo, &nuevo_header);
 278                                 nuevo_header.cant = 0;
 279                                 nuevo_header.padre = -1;
 280                                 nuevo_header.nivel = nodo_header.nivel+1;
 281                                 nuevo_header.hijo_izquierdo = -1;
 282                                 memset(nuevo, -1, idx->tam_bloque);
 283                                 b_actualizar_header(nuevo, &nuevo_header);
 284                                 b_grabar_nodo(idx, 0, nuevo);
 285
 286                                 nodo_id = 0;
 287                                 nodo = nuevo;
 288                                 rompi = 1;
 289                         }
 290                 } else {
 291                         /* La clave entra en este nodo!! */
 292                         b_insertar_en_nodo_con_lugar(idx, clave, dato, nodo_id, nodo, hijo1, hijo2);
 293                         salir = 1;
 294                 }
 295         } while (!salir);
 296 }
 297