- int h=0, gauche, droit, milieu, i, m;
- t_cle u;
- PAGE *pu, *b;
-
-if (a==NULL) {*v=x;*pv=NULL;h=1;}
-else {/*recherche dichotomique */
- gauche=1; droit=a->cle[0];
- do {milieu = (gauche+droit)/2;
- if (x<=a->cle[milieu]) droit=milieu-1;
- if (x>=a->cle[milieu]) gauche=milieu+1;
- } while(gauche<=droit);
- if (gauche-droit==2) /* on a trouve x - on ne fait rien */ h=0;
- else {/* x n'est pas sur cette page */
- h=insertion(x,a->fils[droit],&u,&pu);
- if (h) {/* insertion de u en position droit+1 */
- m = a->cle[0];
- if (m<2*ORDRE) {m++;h=0;
- for (i=m;i>=droit+2;i--) /*decalage */
- {a->cle[i]=a->cle[i-1];
- a->fils[i]=a->fils[i-1];
- }
- a->cle[droit+1]=u; /* insertion */
- a->fils[droit+1]=pu;
- a->cle[0]=m;
- }
- else {/* la page est pleine - on la coupe en deux */
- b=(PAGE *) malloc(sizeof(PAGE));
- if (b==NULL) {printf("Erreur allocation!\n");exit(-1);
- }
- if (droit<=ORDRE)
- {/* insertion de u dans la page de gauche ie dans a */
- if (droit==ORDRE) {*v=u;*pv=pu;}
- else {*v=a->cle[ORDRE];*pv=a->fils[ORDRE];
- for (i=ORDRE;i>=droit+2;i--) /*decalage */
- {a->cle[i]=a->cle[i-1];
- a->fils[i]=a->fils[i-1];
- }
- a->cle[droit+1]=u; /* insertion du u dans a */
- a->fils[droit+1]=pu;
- }
- for (i=1;i<=ORDRE;i++)
- {b->cle[i]=a->cle[i+ORDRE];
- b->fils[i]=a->fils[i+ORDRE];
- }
- }
- else {/* insertion dans la page droite */
- droit=droit-ORDRE;
- *v=a->cle[ORDRE+1];*pv=a->fils[ORDRE+1];
- for (i=1;i<=droit-1;i++)
- {b->cle[i]=a->cle[i+ORDRE+1];
- b->fils[i]=a->fils[i+ORDRE+1];
- }
- b->cle[droit]=u; /* insertion de u dans b */
- b->fils[droit]=pu;
- for (i=droit+1;i<=ORDRE;i++)
- {b->cle[i]=a->cle[i+ORDRE];
- b->fils[i]=a->fils[i+ORDRE];
- }
- }
- a->cle[0]=b->cle[0]=ORDRE;
- b->fils[0]=*pv;
- *pv=b;
- }
- }
- }
-}
-return h;
+ int h = 0, gauche, droit, milieu, i, m;
+ t_cle u;
+ PAGE *pu, *b;
+
+ if (a == NULL) {
+ *v = x;
+ *pv = NULL;
+ h = 1;
+ } else { /* recherche dichotomique */
+ gauche = 1;
+ droit = a->cle[0];
+ do {
+ milieu = (gauche + droit) / 2;
+ if (x <= a->cle[milieu])
+ droit = milieu - 1;
+ if (x >= a->cle[milieu])
+ gauche = milieu + 1;
+ } while (gauche <= droit);
+ if (gauche - droit == 2) /* on a trouve x - on ne fait rien */
+ h = 0;
+ else { /* x n'est pas sur cette page */
+ h = insertion(x, a->fils[droit], &u, &pu);
+ if (h) { /* insertion de u en position droit+1 */
+ m = a->cle[0];
+ if (m < 2 * ORDRE) {
+ m++;
+ h = 0;
+ for (i = m; i >= droit + 2; i--) { /* decalage */
+ a->cle[i] = a->cle[i - 1];
+ a->fils[i] = a->fils[i - 1];
+ }
+ a->cle[droit + 1] = u; /* insertion */
+ a->fils[droit + 1] = pu;
+ a->cle[0] = m;
+ } else { /* la page est pleine - on la coupe en deux */
+ b = (PAGE *) malloc(sizeof(PAGE));
+ if (b == NULL) {
+ printf("Erreur allocation!\n");
+ exit(-1);
+ }
+ if (droit <= ORDRE) { /* insertion de u dans la page de gauche ie dans a */
+ if (droit == ORDRE) {
+ *v = u;
+ *pv = pu;
+ } else {
+ *v = a->cle[ORDRE];
+ *pv = a->fils[ORDRE];
+ for (i = ORDRE; i >= droit + 2; i--) { /* decalage */
+ a->cle[i] = a->cle[i - 1];
+ a->fils[i] = a->fils[i - 1];
+ }
+ a->cle[droit + 1] = u; /* insertion du u dans a */
+ a->fils[droit + 1] = pu;
+ }
+ for (i = 1; i <= ORDRE; i++) {
+ b->cle[i] = a->cle[i + ORDRE];
+ b->fils[i] = a->fils[i + ORDRE];
+ }
+ } else { /* insertion dans la page droite */
+ droit = droit - ORDRE;
+ *v = a->cle[ORDRE + 1];
+ *pv = a->fils[ORDRE + 1];
+ for (i = 1; i <= droit - 1; i++) {
+ b->cle[i] = a->cle[i + ORDRE + 1];
+ b->fils[i] = a->fils[i + ORDRE + 1];
+ }
+ b->cle[droit] = u; /* insertion de u dans b */
+ b->fils[droit] = pu;
+ for (i = droit + 1; i <= ORDRE; i++) {
+ b->cle[i] = a->cle[i + ORDRE];
+ b->fils[i] = a->fils[i + ORDRE];
+ }
+ }
+ a->cle[0] = b->cle[0] = ORDRE;
+ b->fils[0] = *pv;
+ *pv = b;
+ }
+ }
+ }
+ }
+ return h;