]> git.llucax.com Git - z.facultad/75.06/emufs.git/blob - emufs/indice_b.c
0e99b7e5e71c8bb5ba21aad8a25cb046fde33ee9
[z.facultad/75.06/emufs.git] / emufs / indice_b.c
1
2 #include "indice_b.h"
3 #include "common.h"
4
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)
9
10 /* Auxiliares */
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);
24
25 void emufs_indice_b_crear(INDICE *idx)
26 {
27         FILE *fp;
28         char *bloque;
29         B_NodoHeader header;
30
31         header.cant = 0;
32         header.nivel = 0;
33         header.padre = -1;
34         header.hijo_izquierdo = -1;
35
36         fp = fopen(idx->filename, "w");
37         PERR("Creando indice");
38         fprintf(stderr, "Archivo = (%s)\n", idx->filename);
39         if (fp == NULL) {
40                 PERR("Error al crear el archivo");
41                 return;
42         }
43         
44         /* Creo el archivo con el Nodo raiz */
45         bloque = (char *)malloc(idx->tam_bloque);
46         memset(bloque, -1, idx->tam_bloque);
47
48         memcpy(bloque, &header, sizeof(B_NodoHeader));
49
50         fwrite(bloque, idx->tam_bloque, 1, fp);
51         fclose(fp);
52 }
53
54 int emufs_indice_b_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato)
55 {
56         int i, nodo_id, padre_id;
57         B_NodoHeader header;
58         B_NodoEntry *claves;
59         char *nodo, *padre;
60         
61         /* Leo la raiz */
62         nodo = b_leer_nodo(idx, 0);
63         padre_id = nodo_id = 0;
64         padre = NULL;
65         while (nodo) {
66                 if (padre) free(padre);
67                 padre = nodo;
68                 padre_id = nodo_id;
69                 b_leer_header(nodo, &header);
70                 claves = b_leer_claves(nodo, &header);
71                 i=0;
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! */
75                         return 0;
76                 } else {
77                         if (i == 0) {
78                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
79                                 nodo_id = header.hijo_izquierdo;
80                         } else {
81                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
82                                 nodo_id = claves[i-1].hijo_derecho;
83                         }
84                 }
85         }
86
87         if (nodo) free(nodo);
88         nodo = padre;
89         nodo_id = padre_id;
90         b_insertar_en_nodo(idx, clave, dato, nodo_id, nodo, -1, -1);
91         return 1; /* Agregar OK! */
92 }
93
94 INDICE_DATO emufs_indice_b_buscar(INDICE *idx, CLAVE clave)
95 {
96         int i;
97         INDICE_DATO ret;
98         B_NodoHeader header;
99         B_NodoEntry *claves;
100         char *nodo, *tmp;
101         
102         /* Leo la raiz */
103         nodo = b_leer_nodo(idx, 0);
104         while (nodo) {
105                 b_leer_header(nodo, &header);
106                 claves = b_leer_claves(nodo, &header);
107                 i=0;
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;
111                                 free(nodo);
112                                 return ret;
113                 } else {
114                         tmp = nodo;
115                         if (i == 0) {
116                                 nodo = b_leer_nodo(idx, header.hijo_izquierdo);
117                         } else {
118                                 nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
119                         }
120                         free(tmp);
121                 }
122         }
123
124         /* Nodo no encontrado */
125         ret.id = ret.bloque = -1;
126         return ret;
127 }
128
129 int emufs_indice_b_borrar(INDICE *idx, CLAVE k)
130 {
131         /* Busco el nodo que contiene la clave,si es que esta existe */
132         char *nodo;
133         int nodo_id, i;
134         char encontrado=0;
135         B_NodoHeader header;
136         B_NodoEntry *claves;
137
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);
145
146                 i=0;
147                 while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) i++;
148
149                 if ((emufs_indice_es_igual(idx, claves[i].clave, k)) && (i<header.cant))
150                         encontrado = 1;
151                 else {
152                         if (i==0) {
153                                 free(nodo);
154                                 nodo_id = header.hijo_izquierdo;
155                                 nodo = b_leer_nodo(idx, nodo_id);
156                         } else {
157                                 nodo_id = claves[i-1].hijo_derecho;
158                                 free(nodo);
159                                 nodo = b_leer_nodo(idx, nodo_id);
160                         }
161                 }
162         }
163
164         if (encontrado) {
165                 PERR("Clave encontrada, borrando ...");
166                 b_borrar_clave(idx, nodo, nodo_id, k);
167         } else {
168                 PERR("Clave no encontrada");
169         }
170         return 0;
171 }
172
173 static int b_ultimo_id(INDICE *idx)
174 {
175         int i;
176         FILE *fp;
177         fp = fopen(idx->filename, "r");
178         fseek(fp, 0, SEEK_END);
179         i = ftell(fp)/idx->tam_bloque;
180         fclose(fp);
181
182         return i;
183 }
184
185 static char *b_crear_nodo(INDICE *idx, int *id)
186 {
187         char *bloque;
188         B_NodoHeader header;
189
190         (*id) = b_ultimo_id(idx);
191
192         header.cant = 0;
193         header.nivel = 0;
194         header.hijo_izquierdo = -1;
195         header.padre = -1;
196
197         bloque = (char *)malloc(idx->tam_bloque);
198         memset(bloque, -1, idx->tam_bloque);
199         memcpy(bloque, &header, sizeof(B_NodoHeader));
200
201         b_grabar_nodo(idx, *id, bloque);
202
203         return bloque;
204 }
205
206 static char *b_leer_nodo(INDICE *idx, int id)
207 {
208         FILE *fp;
209         char *out;
210
211         if (id < 0) return NULL;
212
213         fp = fopen(idx->filename, "r");
214         if (fp == NULL) return NULL;
215
216         fseek(fp, id*idx->tam_bloque, SEEK_SET);
217
218         out = (char *)malloc(idx->tam_bloque);
219         if (out == NULL) {
220                 fclose(fp);
221                 return NULL;
222         }
223
224         if (fread(out, 1, idx->tam_bloque, fp) != idx->tam_bloque) {
225                 free(out);
226                 /* No se puso leer el nodo */
227                 fclose(fp);
228                 return NULL;
229         }
230
231         fclose(fp);
232         return out;
233 }
234
235 static void b_grabar_nodo(INDICE *idx, int id, char *data)
236 {
237         FILE *fp;
238
239 /*      if (id > b_ultimo_id()) {
240                 printf("AGREGANDO AL FINAL\n");
241                 fp = fopen(FILENAME, "a");
242                 if (fp == NULL) {
243                 _("No se pudo abrir archivo\n");
244                         return;
245                 }
246         } else {
247                 fp = fopen(FILENAME, "w");
248                 if (fp == NULL) {
249                 _("No se pudo abrir archivo\n");
250                         return;
251                 }
252                 fseek(fp, id*BLOCK_SIZE, SEEK_SET);
253                 printf("SOLO GUARDO DATA\n");
254         }*/
255
256         fp = fopen(idx->filename, "r+");
257         fseek(fp, id*idx->tam_bloque, SEEK_SET);
258         fwrite(data, 1, idx->tam_bloque, fp);
259         fclose(fp);
260 }
261
262 static void b_leer_header(char *src, B_NodoHeader *header)
263 {
264         if (!src) return;
265
266         memcpy(header, src, sizeof(B_NodoHeader));
267 }
268
269 static void b_actualizar_header(char *src, B_NodoHeader *header)
270 {
271         if (!src) return;
272         memcpy(src, header, sizeof(B_NodoHeader));
273 }
274
275 static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header)
276 {
277         return (B_NodoEntry *)(src+sizeof(B_NodoHeader));
278 }
279
280 static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2)
281 {
282         char *padre, *nuevo;
283         int nuevo_id;
284         int i, j;
285         static int rompi=0;
286         char salir = 0;
287         B_NodoHeader nodo_header, nuevo_header;
288         B_NodoEntry *claves, *tmp_claves, *claves_nuevo;
289
290         do {
291                 if (!nodo) {
292                         /* CREAR NODO? */
293                         nodo = b_crear_nodo(idx, &nodo_id);
294                 }
295                 b_leer_header(nodo, &nodo_header);
296                 claves = b_leer_claves(nodo, &nodo_header);
297
298                 padre = b_leer_nodo(idx, nodo_header.padre);
299
300                 if (nodo_header.cant == CANT_HIJOS(idx)) {
301                         int total;
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:
307                          */
308                         nuevo = b_crear_nodo(idx, &nuevo_id);
309                         i=0;
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];
315                                 i++;
316                         }
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];
323                                 i++;
324                         }
325                         
326                         /* Asigno a cada nodo lo que corresponde */
327                         b_leer_header(nuevo, &nuevo_header);
328
329                         nuevo_header.nivel = nodo_header.nivel;
330                         nodo_header.cant = total/2;
331                         nuevo_header.cant = total - nodo_header.cant;
332
333                         memset(claves, '*', idx->tam_bloque-sizeof(B_NodoHeader));
334                         for(j=0; j<nodo_header.cant; j++)
335                                 claves[j] = tmp_claves[j];
336
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];
341
342                         b_actualizar_header(nodo, &nodo_header);
343                         b_actualizar_header(nuevo, &nuevo_header);
344
345                         if (nodo_id != 0) {
346                                 clave = tmp_claves[total/2].clave;
347                                 /* XXX dato.bloque = nuevo_id; */
348
349                                 b_grabar_nodo(idx, nodo_id, nodo);
350                                 b_grabar_nodo(idx, nuevo_id, nuevo);
351                                 free(nodo);
352                                 free(nuevo);
353                                 free(tmp_claves);
354
355                                 hijo1 = nodo_id;
356                                 hijo2 = nuevo_id;
357
358                                 nodo = padre;
359                                 nodo_id = nodo_header.padre;
360                         } else {
361                                 /* Oops, parti el raiz, y este debe quedar en 0, lo paso a otro bloque
362                                  * y dejo el padre vacio
363                                  */
364                                 char *tmp_nuevo = b_crear_nodo(idx, &nodo_id);
365                                 memcpy(tmp_nuevo, nodo, idx->tam_bloque);
366                                 free(nodo);
367                                 nodo = tmp_nuevo;
368         
369                                 clave = tmp_claves[total/2].clave;
370                                 /* XXX dato.bloque = nuevo_id; */
371
372                                 b_grabar_nodo(idx, nuevo_id+1, nodo);
373                                 b_grabar_nodo(idx, nuevo_id, nuevo);
374                 
375                                 free(nodo);
376                                 free(nuevo);
377                                 free(tmp_claves);
378
379                                 hijo1 = nuevo_id+1;
380                                 hijo2 = nuevo_id;
381
382                                 /* Limpio al padre */
383                                 nuevo = b_leer_nodo(idx, 0);
384
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);
392
393                                 nodo_id = 0;
394                                 nodo = nuevo;
395                                 rompi = 1;
396                         }
397                 } else {
398                         /* La clave entra en este nodo!! */
399                         i = 0;
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];
404                         }
405                         nodo_header.cant++;
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);
410
411                         b_actualizar_header(nodo, &nodo_header);
412                         b_grabar_nodo(idx, nodo_id, nodo);
413
414                         /* Debo actualizar los punteros al padre de los hijos */
415                         if (hijo1 != -1) {
416                                 nuevo = b_leer_nodo(idx, hijo1);
417                                 if (nuevo != NULL) {
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);
422                                         free(nuevo);
423                                 } else printf("FUCK! hijo1=%d no existe!\n", hijo1);
424                         }
425                         if (hijo2 != -1) {
426                                 nuevo = b_leer_nodo(idx, hijo2);
427                                 if (nuevo != NULL) {
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);
432                                         free(nuevo);
433                                 } else printf("FUCK! hijo2=%d no existe!\n", hijo2);
434                         }
435                         salir = 1;
436                 }
437         } while (!salir);
438 }
439
440 static int b_elegir_izquierdo(INDICE *idx, int a, int b)
441 {
442         int cual;
443         char *nodo1, *nodo2;
444         B_NodoHeader header1, header2;
445         B_NodoEntry *claves1, *claves2;
446
447         if (a==-1) return b;
448         if (b==-1) return a;
449
450         nodo1 = b_leer_nodo(idx, a);
451         nodo2 = b_leer_nodo(idx, b);
452
453         b_leer_header(nodo1, &header1);
454         b_leer_header(nodo2, &header2);
455
456         claves1 = b_leer_claves(nodo1, &header1);
457         claves2 = b_leer_claves(nodo2, &header2);
458
459         if (emufs_indice_es_menor(idx, claves1[0].clave, claves2[0].clave))
460                 cual = a;
461         else
462                 cual = b;
463
464         free(nodo1);
465         free(nodo2);
466         return cual;
467 }
468
469 INDICE_DATO *emufs_indice_b_buscar_muchos(INDICE *idx, CLAVE clave, int *cant)
470 {
471         /* Si el indice es primario no tiene sentido hacer nada */
472         if (idx->funcion == IND_PRIMARIO) {
473                 *cant = 0;
474                 return NULL;
475         }
476
477         /* TODO Implementar indices con repeticion */
478         return NULL;
479 }
480
481 static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k)
482 {
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;
487
488         b_leer_header(nodo, &header);
489         claves = b_leer_claves(nodo, &header);
490
491         pos = 0;
492         /* Busco la posicion dentro de la lista de claves */
493         while (emufs_indice_es_menor(idx, claves[pos].clave, k)) pos++;
494
495         /* Es el nodo una hoja? */
496         if (header.hijo_izquierdo != -1) {
497                 /* No!, es un nodo intermedio!! */
498                 if (pos == 0)
499                         actual = b_leer_nodo(idx, header.hijo_izquierdo);
500                 else
501                         actual = b_leer_nodo(idx, claves[pos+1].hijo_derecho);
502
503                 b_leer_header(actual, &header_actual);
504                 while (header_actual.hijo_izquierdo != -1) {
505                         actual_id = header_actual.hijo_izquierdo;
506                         free(actual);
507                         actual = b_leer_nodo(idx, actual_id);
508                         b_leer_header(actual, &header_actual);
509                 }
510                 claves_actual = b_leer_claves(actual, &header);
511
512                 claves[pos] = claves_actual[0];
513                 pos = 0;
514                 b_grabar_nodo(idx, nodo_id, nodo);
515         } else {
516                 actual = nodo;
517         }
518
519         /* Borro la clave */
520         for(i=pos; i < header_actual.cant; i++) {
521                 claves_actual[i] = claves_actual[i+1];
522         }
523         header_actual.cant--;
524         /* Guardo los cambios */
525         b_actualizar_header(actual, &header_actual);
526         b_grabar_nodo(idx, actual_id, actual);
527
528         /* Se cumple la condicion de hijos? */
529         if (header_actual.cant >= MIN_HIJOS(idx)) {
530                 PERR("Borrar completo sin fundir");
531                 return;
532         }
533
534         /* Tengo que pasar datos o fundir nodos :-( */
535         do {
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);
547                 } else {
548                         for(pos_padre=0; claves_padre[pos_padre].hijo_derecho != actual_id; pos_padre++)        {       }
549
550                         /* Busco mis hermanos a derecha e izquierda, si es que existen */
551                         if (pos_padre >= 0) {
552                                 if (pos_padre == 0)
553                                         izquierda_id = header_padre.hijo_izquierdo;
554                                 else
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);
558                         } else {
559                                 izquierda_id = -1;
560                         }
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);
565                         } else {
566                                 derecha_id = -1;
567                         }
568                 }
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);
574                 } else {
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);
578                         } else {
579                                 b_fundir_nodo(izq, izquierda_id, padre, padre_id, actual, actual_id, pos_padre-1);
580                         }
581                 }
582
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);
592                 actual = padre;
593                 actual_id = padre_id;
594         } while ((actual_id != -1) && (header_actual.cant < MIN_HIJOS(idx)));
595 }
596
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)
598 {
599         int i;
600         B_NodoHeader h_der, h_padre, h_nodo;
601         B_NodoEntry *c_der, *c_padre, *c_nodo;
602
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);
609
610         c_nodo[h_nodo.cant] = c_padre[pos_clave];
611         c_nodo[h_nodo.cant].hijo_derecho = -1; /* XXX */
612
613         c_padre[pos_clave] = c_der[0];
614         c_padre[pos_clave].hijo_derecho = der_id;
615         
616         /* Muevo las claves de derecho */
617         for(i=0; i<h_der.cant; i++) {
618                 c_der[i] = c_der[i+1];
619         }
620         h_der.cant--;
621         h_nodo.cant++;
622
623         b_actualizar_header(der, &h_der);
624         b_actualizar_header(nodo, &h_nodo);
625 }
626
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)
628 {
629         int i;
630         B_NodoHeader h_izq, h_padre, h_nodo;
631         B_NodoEntry *c_izq, *c_padre, *c_nodo;
632
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);
639
640         for(i=h_nodo.cant; i>0;i++)
641                 c_nodo[i] = c_nodo[i-1];
642
643         h_nodo.cant++;
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;
648         h_izq.cant--;
649
650         b_actualizar_header(izq, &h_izq);
651         b_actualizar_header(padre, &h_padre);
652         b_actualizar_header(nodo, &h_nodo);
653 }
654
655 static void b_fundir_nodo(char *izq, int izq_id, char *padre, int padre_id, char *der, int der_id, int pos_clave)
656 {
657 }
658