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         PERR("MAGIC");
  79         do {
  80                 if (!nodo) {
  81                         /* CREAR NODO? */
  82                         nodo = b_crear_nodo(idx, &nodo_id);
  83                 }
  84                 b_leer_header(nodo, &nodo_header);
  85                 claves = b_leer_claves(nodo, &nodo_header);
  86
  87                 padre = b_leer_nodo(idx, nodo_header.padre);
  88
  89                 if (nodo_header.cant == CANT_HIJOS(idx)) {
  90                         int total;
  91                         if (nodo_id != 0) {
  92                                 int izq_id, der_id, pos_padre, i;
  93                                 B_NodoHeader padre_header, header_der, header_izq;
  94                                 B_NodoEntry *padre_claves, nuevo_entry;
  95                                 B_NodoEntry a_pasar, *buffer;
  96
  97                                 b_leer_header(padre, &padre_header);
  98                                 padre_claves = b_leer_claves(padre, &padre_header);
  99
 100                          /* nuevo_entry = new entry(clave, dato, hijo_der) */
 101                                 PERR("Buscando que hijo soy");
 102                                 for(pos_padre=0; (padre_claves[pos_padre].hijo_derecho != nodo_id); pos_padre++)        {       }
 103
 104                                 if (pos_padre == padre_header.cant) {
 105                                         PERR("ERROR GRAVE. Padre no me contiene :-(");
 106                                 }
 107
 108                                 /* Busco mis hermanos a derecha e izquierda, si es que existen */
 109                                 PERR("Ya me encontre, busco a mis hermanos");
 110                                 if (pos_padre >= 0) {
 111                                         if (pos_padre == 0)
 112                                                 izq_id = padre_header.hijo_izquierdo;
 113                                         else
 114                                                 izq_id = padre_claves[pos_padre-1].hijo_derecho;
 115                                         izq = b_leer_nodo(idx, izq_id);
 116                                         b_leer_header(izq, &header_izq);
 117                                 } else {
 118                                         izq_id = -1;
 119                                 }
 120                                 if (pos_padre < padre_header.cant) {
 121                                         der_id = padre_claves[pos_padre+1].hijo_derecho;
 122                                         der = b_leer_nodo(idx, der_id);
 123                                         b_leer_header(der, &header_der);
 124                                 } else {
 125                                         der_id = -1;
 126                                 }
 127                                 PERR("Hermanos encontrados");
 128
 129                                 buffer = malloc((nodo_header.cant+1)*sizeof(B_NodoEntry));
 130
 131                                 nuevo_entry.clave = clave;
 132                                 nuevo_entry.dato = dato;
 133                                 nuevo_entry.hijo_derecho = hijo2;
 134
 135                                 /* Inserto ordenado */
 136                                 for(i=0; (i<nodo_header.cant) && emufs_indice_es_menor(idx, claves[i].clave, clave); i++)
 137                                         buffer[i] = claves[i];
 138                                 buffer[i] = nuevo_entry;
 139                                 while (i<nodo_header.cant) {
 140                                         buffer[i+1] = claves[i];
 141                                         i++;
 142                                 }
 143
 144                                 if ((der_id != -1) && (header_der.cant < CANT_HIJOS(idx))) {
 145                                         /* tomo la clave mas grande */
 146                                         a_pasar = buffer[nodo_header.cant];
 147
 148                                         /* la paso a la derecha */
 149                                         b_pasar_clave_a_derecha(idx, der, der_id, padre, nodo_header.padre, pos_padre, a_pasar);
 150                                         /* XXX TODO Liberar memoria y GUARDAR*/
 151                                         free(buffer);
 152
 153                                         return;
 154                                 }
 155
 156                                 if ((izq_id != -1) && (header_izq.cant < CANT_HIJOS(idx))) {
 157                                         a_pasar = buffer[0];
 158                                         b_pasar_clave_a_izquierda(idx, izq, izq_id, padre, nodo_header.padre, pos_padre, a_pasar, 0, 0);
 159                                         free(buffer);
 160                                         return;
 161                                 }
 162
 163                                 if (izq_id != -1)
 164                                         b_partir_dos_nodos_en_tres(idx, izq_id, nodo_id, nodo_header.padre, nuevo_entry);
 165                                 else // Siempre alguno tiene que existir.
 166                                         b_partir_dos_nodos_en_tres(idx, nodo_id, der_id, nodo_header.padre, nuevo_entry);
 167                                 return;
 168                         }
 169
 170                         /* Bueno, soy la raiz, tengo que tratarla como el arbol B */
 171                         /* Sigo con a fullllllllll */
 172                         nuevo = b_crear_nodo(idx, &nuevo_id);
 173                         i=0;
 174                         /* Creo una lista ordenada de los nodos a partir */
 175                         tmp_claves = (B_NodoEntry *)malloc(sizeof(B_NodoEntry)*(nodo_header.cant+1));
 176                         total = nodo_header.cant+1;
 177                         while ((i<nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) {
 178                                 tmp_claves[i] = claves[i];
 179                                 i++;
 180                         }
 181                         tmp_claves[i].clave = clave;
 182                         tmp_claves[i].dato = dato;
 183                         /*tmp_claves[i].hijo_derecho = hijo1;*/
 184                         if (i==0) {
 185                                 nodo_header.hijo_izquierdo = hijo1;
 186                                 tmp_claves[i].hijo_derecho = hijo2;
 187                         } else {
 188                                 tmp_claves[i-1].hijo_derecho = hijo1;
 189                                 tmp_claves[i].hijo_derecho = hijo2;
 190                         }
 191                         while (i < nodo_header.cant) {
 192                                 tmp_claves[i+1] = claves[i];
 193                                 i++;
 194                         }
 195
 196                         /* Asigno a cada nodo lo que corresponde */
 197                         b_leer_header(nuevo, &nuevo_header);
 198
 199                         nuevo_header.nivel = nodo_header.nivel;
 200                         nodo_header.cant = total/2;
 201                         nuevo_header.cant = (total-1) - nodo_header.cant;
 202
 203                         memset(claves, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 204                         for(j=0; j<nodo_header.cant; j++)
 205                                 claves[j] = tmp_claves[j];
 206
 207                         claves_nuevo = b_leer_claves(nuevo, &nuevo_header);
 208                         memset(claves_nuevo, '*', idx->tam_bloque-sizeof(B_NodoHeader));
 209                         for(j=0; j<nuevo_header.cant; j++)
 210                                 claves_nuevo[j] = tmp_claves[j+total/2+1];
 211
 212                         b_actualizar_header(nodo, &nodo_header);
 213                         b_actualizar_header(nuevo, &nuevo_header);
 214
 215                         if (nodo_id != 0) {
 216                                 clave = tmp_claves[total/2].clave;
 217                                 dato = tmp_claves[total/2].dato;
 218
 219                                 b_grabar_nodo(idx, nodo_id, nodo);
 220                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 221                                 free(nodo);
 222                                 free(nuevo);
 223                                 free(tmp_claves);
 224
 225                                 hijo1 = nodo_id;
 226                                 hijo2 = nuevo_id;
 227
 228                                 fprintf(stderr, "Nodos espliteados = %d %d\n", hijo1, hijo2);
 229                                 nodo = padre;
 230                                 nodo_id = nodo_header.padre;
 231                         } else {
 232                                 /* Oops, parti el raiz, y este debe quedar en 0, lo paso a otro bloque
 233                                  * y dejo el padre vacio
 234                                  */
 235                                 char *tmp_nuevo = b_crear_nodo(idx, &nodo_id);
 236                                 memcpy(tmp_nuevo, nodo, idx->tam_bloque);
 237                                 free(nodo);
 238                                 nodo = tmp_nuevo;
 239
 240                                 clave = tmp_claves[total/2].clave;
 241                                 dato = tmp_claves[total/2].dato;
 242
 243                                 b_grabar_nodo(idx, nuevo_id+1, nodo);
 244                                 b_grabar_nodo(idx, nuevo_id, nuevo);
 245
 246                                 free(nodo);
 247                                 free(nuevo);
 248                                 free(tmp_claves);
 249
 250                                 hijo1 = nuevo_id+1;
 251                                 hijo2 = nuevo_id;
 252
 253                                 fprintf(stderr, "Nodos espliteados = %d %d\n", hijo1, hijo2);
 254                                 /* Limpio al padre */
 255                                 nuevo = b_leer_nodo(idx, 0);
 256
 257                                 b_leer_header(nuevo, &nuevo_header);
 258                                 nuevo_header.cant = 0;
 259                                 nuevo_header.padre = -1;
 260                                 nuevo_header.nivel = nodo_header.nivel+1;
 261                                 nuevo_header.hijo_izquierdo = -1;
 262                                 fprintf(stderr, "root.nivel=%d\n", nuevo_header.nivel);
 263                                 memset(nuevo, -1, idx->tam_bloque);
 264                                 b_actualizar_header(nuevo, &nuevo_header);
 265                                 b_grabar_nodo(idx, 0, nuevo);
 266
 267                                 nodo_id = 0;
 268                                 nodo = nuevo;
 269                                 rompi = 1;
 270                         }
 271                 } else {
 272                         /* La clave entra en este nodo!! */
 273                         b_insertar_en_nodo_con_lugar(idx, clave, dato, nodo_id, nodo, hijo1, hijo2);
 274                         salir = 1;
 275                 }
 276         } while (!salir);
 277 }
 278