5 /* Cantidad de claves por nodo */
6 #define CANT_HIJOS(x) ((x->tam_bloque-sizeof(B_NodoHeader))/sizeof(B_NodoEntry))
7 #define CANT_NODOS(x) (CANT_HIJOS(x)+1)
8 #define MIN_HIJOS(x) (CANT_HIJOS(x)/2)
11 static void b_grabar_nodo(INDICE *idx, int id, char *data);
12 static int b_ultimo_id(INDICE *idx);
13 static char *b_leer_nodo(INDICE *idx, int id);
14 static char *b_crear_nodo(INDICE *idx, int *i);
15 static void b_leer_header(char *src, B_NodoHeader *header);
16 static void b_actualizar_header(char *src, B_NodoHeader *header);
17 static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header);
18 static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2);
19 static int b_elegir_izquierdo(INDICE *idx, int a, int b);
20 static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k);
21 static void b_pasar_clave_derecha(char *, int, char *, int, char *, int, int);
22 static void b_pasar_clave_izquierda(char *, int, char *, int, char *, int, int);
23 static void b_fundir_nodo(char *, int, char *, int, char *, int, int);
25 void emufs_indice_b_crear(INDICE *idx)
34 header.hijo_izquierdo = -1;
36 fp = fopen(idx->filename, "w");
37 PERR("Creando indice");
38 fprintf(stderr, "Archivo = (%s)\n", idx->filename);
40 PERR("Error al crear el archivo");
44 /* Creo el archivo con el Nodo raiz */
45 bloque = (char *)malloc(idx->tam_bloque);
46 memset(bloque, -1, idx->tam_bloque);
48 memcpy(bloque, &header, sizeof(B_NodoHeader));
50 fwrite(bloque, idx->tam_bloque, 1, fp);
54 int emufs_indice_b_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato)
56 int i, nodo_id, padre_id;
62 nodo = b_leer_nodo(idx, 0);
63 padre_id = nodo_id = 0;
66 if (padre) free(padre);
69 b_leer_header(nodo, &header);
70 claves = b_leer_claves(nodo, &header);
72 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
73 if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, clave))) {
74 /* CLAVE DUPLICADA! */
78 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
79 nodo_id = header.hijo_izquierdo;
81 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
82 nodo_id = claves[i-1].hijo_derecho;
90 b_insertar_en_nodo(idx, clave, dato, nodo_id, nodo, -1, -1);
91 return 1; /* Agregar OK! */
94 INDICE_DATO emufs_indice_b_buscar(INDICE *idx, CLAVE clave)
103 nodo = b_leer_nodo(idx, 0);
105 b_leer_header(nodo, &header);
106 claves = b_leer_claves(nodo, &header);
108 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
109 if (emufs_indice_es_igual(idx, claves[i].clave, clave)) {
110 ret = claves[i].dato;
116 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
118 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
124 /* Nodo no encontrado */
125 ret.id = ret.bloque = -1;
129 int emufs_indice_b_borrar(INDICE *idx, CLAVE k)
131 /* Busco el nodo que contiene la clave,si es que esta existe */
138 nodo_id = 0; /* Tomo la raiz */
139 nodo = b_leer_nodo(idx, nodo_id);
140 PERR("Buscando clave a borrar");
141 while (nodo && !encontrado) {
142 /* Obtengo los datos del nodo */
143 b_leer_header(nodo, &header);
144 claves = b_leer_claves(nodo, &header);
147 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) i++;
149 if ((emufs_indice_es_igual(idx, claves[i].clave, k)) && (i<header.cant))
154 nodo_id = header.hijo_izquierdo;
155 nodo = b_leer_nodo(idx, nodo_id);
157 nodo_id = claves[i-1].hijo_derecho;
159 nodo = b_leer_nodo(idx, nodo_id);
165 PERR("Clave encontrada, borrando ...");
166 b_borrar_clave(idx, nodo, nodo_id, k);
168 PERR("Clave no encontrada");
173 static int b_ultimo_id(INDICE *idx)
177 fp = fopen(idx->filename, "r");
178 fseek(fp, 0, SEEK_END);
179 i = ftell(fp)/idx->tam_bloque;
185 static char *b_crear_nodo(INDICE *idx, int *id)
190 (*id) = b_ultimo_id(idx);
194 header.hijo_izquierdo = -1;
197 bloque = (char *)malloc(idx->tam_bloque);
198 memset(bloque, -1, idx->tam_bloque);
199 memcpy(bloque, &header, sizeof(B_NodoHeader));
201 b_grabar_nodo(idx, *id, bloque);
206 static char *b_leer_nodo(INDICE *idx, int id)
211 if (id < 0) return NULL;
213 fp = fopen(idx->filename, "r");
214 if (fp == NULL) return NULL;
216 fseek(fp, id*idx->tam_bloque, SEEK_SET);
218 out = (char *)malloc(idx->tam_bloque);
224 if (fread(out, 1, idx->tam_bloque, fp) != idx->tam_bloque) {
226 /* No se puso leer el nodo */
235 static void b_grabar_nodo(INDICE *idx, int id, char *data)
239 /* if (id > b_ultimo_id()) {
240 printf("AGREGANDO AL FINAL\n");
241 fp = fopen(FILENAME, "a");
243 _("No se pudo abrir archivo\n");
247 fp = fopen(FILENAME, "w");
249 _("No se pudo abrir archivo\n");
252 fseek(fp, id*BLOCK_SIZE, SEEK_SET);
253 printf("SOLO GUARDO DATA\n");
256 fp = fopen(idx->filename, "r+");
257 fseek(fp, id*idx->tam_bloque, SEEK_SET);
258 fwrite(data, 1, idx->tam_bloque, fp);
262 static void b_leer_header(char *src, B_NodoHeader *header)
266 memcpy(header, src, sizeof(B_NodoHeader));
269 static void b_actualizar_header(char *src, B_NodoHeader *header)
272 memcpy(src, header, sizeof(B_NodoHeader));
275 static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header)
277 return (B_NodoEntry *)(src+sizeof(B_NodoHeader));
280 static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2)
287 B_NodoHeader nodo_header, nuevo_header;
288 B_NodoEntry *claves, *tmp_claves, *claves_nuevo;
293 nodo = b_crear_nodo(idx, &nodo_id);
295 b_leer_header(nodo, &nodo_header);
296 claves = b_leer_claves(nodo, &nodo_header);
298 padre = b_leer_nodo(idx, nodo_header.padre);
300 if (nodo_header.cant == CANT_HIJOS(idx)) {
302 /* TODO: Si es B*, hay que chequear si alguno de los 2
303 * nodos hermanos pueden prestarme espacio (y
304 * desplazar si es asÃ). Si no pueden, hay que
305 * hacer un split de 2 nodos en 3.
306 * Si no es B*, hay que hacer lo que sigue:
308 nuevo = b_crear_nodo(idx, &nuevo_id);
310 /* Creo una lista ordenada de los nodos a partir */
311 tmp_claves = (B_NodoEntry *)malloc(sizeof(B_NodoEntry)*(nodo_header.cant+1));
312 total = nodo_header.cant;
313 while ((i<nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) {
314 tmp_claves[i] = claves[i];
317 tmp_claves[i].clave = clave;
318 tmp_claves[i].dato = dato;
319 tmp_claves[i].hijo_derecho = hijo1;
320 tmp_claves[i+1].hijo_derecho = hijo2;
321 while (i < nodo_header.cant) {
322 tmp_claves[i+1] = claves[i];
326 /* Asigno a cada nodo lo que corresponde */
327 b_leer_header(nuevo, &nuevo_header);
329 nuevo_header.nivel = nodo_header.nivel;
330 nodo_header.cant = total/2;
331 nuevo_header.cant = total - nodo_header.cant;
333 memset(claves, '*', idx->tam_bloque-sizeof(B_NodoHeader));
334 for(j=0; j<nodo_header.cant; j++)
335 claves[j] = tmp_claves[j];
337 claves_nuevo = b_leer_claves(nuevo, &nuevo_header);
338 memset(claves_nuevo, '*', idx->tam_bloque-sizeof(B_NodoHeader));
339 for(j=0; j<nuevo_header.cant; j++)
340 claves_nuevo[j] = tmp_claves[j+total/2+1];
342 b_actualizar_header(nodo, &nodo_header);
343 b_actualizar_header(nuevo, &nuevo_header);
346 clave = tmp_claves[total/2].clave;
347 /* XXX dato.bloque = nuevo_id; */
349 b_grabar_nodo(idx, nodo_id, nodo);
350 b_grabar_nodo(idx, nuevo_id, nuevo);
359 nodo_id = nodo_header.padre;
361 /* Oops, parti el raiz, y este debe quedar en 0, lo paso a otro bloque
362 * y dejo el padre vacio
364 char *tmp_nuevo = b_crear_nodo(idx, &nodo_id);
365 memcpy(tmp_nuevo, nodo, idx->tam_bloque);
369 clave = tmp_claves[total/2].clave;
370 /* XXX dato.bloque = nuevo_id; */
372 b_grabar_nodo(idx, nuevo_id+1, nodo);
373 b_grabar_nodo(idx, nuevo_id, nuevo);
382 /* Limpio al padre */
383 nuevo = b_leer_nodo(idx, 0);
385 b_leer_header(nuevo, &nuevo_header);
386 nuevo_header.cant = 0;
387 nuevo_header.padre = -1;
388 nuevo_header.nivel = nodo_header.nivel+1;
389 memset(nuevo, -1, idx->tam_bloque);
390 b_actualizar_header(nuevo, &nuevo_header);
391 b_grabar_nodo(idx, 0, nuevo);
398 /* La clave entra en este nodo!! */
400 if (nodo_header.cant > 0) {
401 while ((emufs_indice_es_menor(idx, claves[i].clave, clave)) && (i < nodo_header.cant)) i++;
402 for(j=nodo_header.cant; j > i; j--)
403 claves[j] = claves[j-1];
406 claves[i].clave = clave;
407 claves[i].dato = dato;
408 claves[i].hijo_derecho = hijo2;
409 nodo_header.hijo_izquierdo = b_elegir_izquierdo(idx, nodo_header.hijo_izquierdo, hijo1);
411 b_actualizar_header(nodo, &nodo_header);
412 b_grabar_nodo(idx, nodo_id, nodo);
414 /* Debo actualizar los punteros al padre de los hijos */
416 nuevo = b_leer_nodo(idx, hijo1);
418 b_leer_header(nuevo, &nuevo_header);
419 nuevo_header.padre = nodo_id;
420 b_actualizar_header(nuevo, &nuevo_header);
421 b_grabar_nodo(idx, hijo1, nuevo);
423 } else printf("FUCK! hijo1=%d no existe!\n", hijo1);
426 nuevo = b_leer_nodo(idx, hijo2);
428 b_leer_header(nuevo, &nuevo_header);
429 nuevo_header.padre = nodo_id;
430 b_actualizar_header(nuevo, &nuevo_header);
431 b_grabar_nodo(idx, hijo2, nuevo);
433 } else printf("FUCK! hijo2=%d no existe!\n", hijo2);
440 static int b_elegir_izquierdo(INDICE *idx, int a, int b)
444 B_NodoHeader header1, header2;
445 B_NodoEntry *claves1, *claves2;
450 nodo1 = b_leer_nodo(idx, a);
451 nodo2 = b_leer_nodo(idx, b);
453 b_leer_header(nodo1, &header1);
454 b_leer_header(nodo2, &header2);
456 claves1 = b_leer_claves(nodo1, &header1);
457 claves2 = b_leer_claves(nodo2, &header2);
459 if (emufs_indice_es_menor(idx, claves1[0].clave, claves2[0].clave))
469 INDICE_DATO *emufs_indice_b_buscar_muchos(INDICE *idx, CLAVE clave, int *cant)
471 /* Si el indice es primario no tiene sentido hacer nada */
472 if (idx->funcion == IND_PRIMARIO) {
477 /* TODO Implementar indices con repeticion */
481 static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k)
483 int pos, actual_id, padre_id, i, pos_padre, izquierda_id, derecha_id;
484 B_NodoHeader header, header_actual, header_padre, header_izq, header_der;
485 B_NodoEntry *claves, *claves_actual, *claves_padre;/*, *claves_izq, *claves_der;*/
486 char *actual, *padre, *izq, *der;
488 b_leer_header(nodo, &header);
489 claves = b_leer_claves(nodo, &header);
492 /* Busco la posicion dentro de la lista de claves */
493 while (emufs_indice_es_menor(idx, claves[pos].clave, k)) pos++;
495 /* Es el nodo una hoja? */
496 if (header.hijo_izquierdo != -1) {
497 /* No!, es un nodo intermedio!! */
499 actual = b_leer_nodo(idx, header.hijo_izquierdo);
501 actual = b_leer_nodo(idx, claves[pos+1].hijo_derecho);
503 b_leer_header(actual, &header_actual);
504 while (header_actual.hijo_izquierdo != -1) {
505 actual_id = header_actual.hijo_izquierdo;
507 actual = b_leer_nodo(idx, actual_id);
508 b_leer_header(actual, &header_actual);
510 claves_actual = b_leer_claves(actual, &header);
512 claves[pos] = claves_actual[0];
514 b_grabar_nodo(idx, nodo_id, nodo);
520 for(i=pos; i < header_actual.cant; i++) {
521 claves_actual[i] = claves_actual[i+1];
523 header_actual.cant--;
524 /* Guardo los cambios */
525 b_actualizar_header(actual, &header_actual);
526 b_grabar_nodo(idx, actual_id, actual);
528 /* Se cumple la condicion de hijos? */
529 if (header_actual.cant >= MIN_HIJOS(idx)) {
530 PERR("Borrar completo sin fundir");
534 /* Tengo que pasar datos o fundir nodos :-( */
536 padre_id = header.padre;
537 padre = b_leer_nodo(idx, padre_id);
538 b_leer_header(padre, &header_padre);
539 claves_padre = b_leer_claves(padre, &header_padre);
540 /* TODO Tengo el hijo_izquierdo para revisar!! XXX */
541 if (header_padre.hijo_izquierdo == actual_id) {
542 izquierda_id = -1; /* No tengo hermano izquierdo */
543 /* Mi hermano derecho es el primer nodo del padre */
544 derecha_id = claves_padre[0].hijo_derecho;
545 der = b_leer_nodo(idx, derecha_id);
546 b_leer_header(der, &header_der);
548 for(pos_padre=0; claves_padre[pos_padre].hijo_derecho != actual_id; pos_padre++) { }
550 /* Busco mis hermanos a derecha e izquierda, si es que existen */
551 if (pos_padre >= 0) {
553 izquierda_id = header_padre.hijo_izquierdo;
555 izquierda_id = claves_padre[pos_padre-1].hijo_derecho;
556 izq = b_leer_nodo(idx, izquierda_id);
557 b_leer_header(izq, &header_izq);
561 if (pos_padre < header_padre.cant) {
562 derecha_id = claves_padre[pos_padre+1].hijo_derecho;
563 der = b_leer_nodo(idx, derecha_id);
564 b_leer_header(der, &header_der);
569 /* Intendo pasar una clave desde un hermano hacia mi */
570 if ((derecha_id != -1) && (header_der.cant > MIN_HIJOS(idx))) {
571 b_pasar_clave_derecha(der, derecha_id, padre, padre_id, actual, actual_id, pos_padre);
572 } else if ((izquierda_id != -1) && (header_izq.cant > MIN_HIJOS(idx))) {
573 b_pasar_clave_izquierda(izq, izquierda_id, padre, padre_id, actual, actual_id, pos_padre-1);
575 /* No pude pasar clave, tengo que fundir :-( */
576 if (derecha_id != -1) {
577 b_fundir_nodo(actual, actual_id, padre, padre_id, der, derecha_id, pos_padre);
579 b_fundir_nodo(izq, izquierda_id, padre, padre_id, actual, actual_id, pos_padre-1);
583 /* TODO que guardo ?, todo ? */
584 b_grabar_nodo(idx, actual_id, actual);
585 b_grabar_nodo(idx, izquierda_id, izq);
586 b_grabar_nodo(idx, derecha_id, der);
587 b_grabar_nodo(idx, padre_id, padre);
588 if (actual_id != -1) free(actual);
589 /*if (padre_id != -1) free(padre);*/
590 if (derecha_id != -1) free(der);
591 if (izquierda_id != -1) free(izq);
593 actual_id = padre_id;
594 } while ((actual_id != -1) && (header_actual.cant < MIN_HIJOS(idx)));
597 static void b_pasar_clave_derecha(char *der, int der_id, char *padre, int padre_id, char *nodo, int nodo_id, int pos_clave)
600 B_NodoHeader h_der, h_padre, h_nodo;
601 B_NodoEntry *c_der, *c_padre, *c_nodo;
603 b_leer_header(nodo, &h_nodo);
604 c_nodo = b_leer_claves(nodo, &h_nodo);
605 b_leer_header(der, &h_der);
606 c_der = b_leer_claves(der, &h_der);
607 b_leer_header(padre, &h_padre);
608 c_padre = b_leer_claves(padre, &h_padre);
610 c_nodo[h_nodo.cant] = c_padre[pos_clave];
611 c_nodo[h_nodo.cant].hijo_derecho = -1; /* XXX */
613 c_padre[pos_clave] = c_der[0];
614 c_padre[pos_clave].hijo_derecho = der_id;
616 /* Muevo las claves de derecho */
617 for(i=0; i<h_der.cant; i++) {
618 c_der[i] = c_der[i+1];
623 b_actualizar_header(der, &h_der);
624 b_actualizar_header(nodo, &h_nodo);
627 static void b_pasar_clave_izquierda(char *izq, int izq_id, char *padre, int padre_id, char *nodo, int nodo_id, int pos_clave)
630 B_NodoHeader h_izq, h_padre, h_nodo;
631 B_NodoEntry *c_izq, *c_padre, *c_nodo;
633 b_leer_header(nodo, &h_nodo);
634 c_nodo = b_leer_claves(nodo, &h_nodo);
635 b_leer_header(izq, &h_izq);
636 c_izq = b_leer_claves(izq, &h_izq);
637 b_leer_header(padre, &h_padre);
638 c_padre = b_leer_claves(padre, &h_padre);
640 for(i=h_nodo.cant; i>0;i++)
641 c_nodo[i] = c_nodo[i-1];
644 c_nodo[0] = c_padre[pos_clave];
645 c_nodo[0].hijo_derecho = -1; /* XXX */
646 c_padre[pos_clave] = c_izq[h_izq.cant-1];
647 c_padre[pos_clave].hijo_derecho = izq_id;
650 b_actualizar_header(izq, &h_izq);
651 b_actualizar_header(padre, &h_padre);
652 b_actualizar_header(nodo, &h_nodo);
655 static void b_fundir_nodo(char *izq, int izq_id, char *padre, int padre_id, char *der, int der_id, int pos_clave)