#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define  nbsect 100000
#define  nbfic  1000
typedef struct element *pelement,element;
typedef struct pln *ppln,pln;
struct element { pelement next,prev; ppln tete; };
struct pln { element p; int longueur; char nom[40]; };
element fat[nbsect];
pln fic[nbfic];
// fic[0] est la liste des secteurs libres
// fic[1] est la liste des entêtes de fichiers libres
void format()
{ int i;
  for(i=0;i<nbsect;i++) fat[i]=(element){fat+i-1,fat+i+1,fic};
  *fic=(pln){{fat,fat+nbsect-1,fic},nbsect,"liste des secteurs libres"};
  fat->prev=fat[nbsect-1].next=&fic->p;
  for(i=1;i<nbfic;i++) fic[i]=(pln){{&fic[i+1].p,&fic[i-1].p,fic+1},0,""};
  fic[1]=(pln){{&fic[2].p,&fic[nbfic-1].p,fic+1},nbfic-2,"liste des entêtes de fichier vides"};
  fic[nbfic-1].p.next=&fic[1].p;
}
int nouvfic(char *nom)
{ if(!fic[1].longueur) return -1;
  pelement p=fic[1].p.next;
  ppln f=(ppln)p;
  fic[1].longueur--;
  p->prev->next=p->prev;
  p->next->prev=p->next;
  *f=(pln){{p,p,f},0,""};
  strcpy(nom,f->nom);
  return f-fic;
}
pelement tetefic(int i)
{
  return &fic[i].p;
}
pelement creenext(pelement e)
{ if(!fic->longueur) return 0;
  pelement f=fic->p.next;
  if(&e->tete->p!=e && e-fat<nbsect-1 && e[1].tete==fic) f=e+1; else // le secteur nextant e est libre
  if(&e->tete->p!=e->next && e->next>fat && e->next[-1].tete==fic) f=e->next-1;
  fic->longueur--;
  f->next->prev=f->prev;
  f->prev->next=f->next;
  e->tete->longueur++;
  *f=*e;
  f->prev=e;
  return f;
}
void libere(pelement e)
{ if(&e->tete->p==e || e->tete==fic || e->tete==fic+1) return;
  e->tete->longueur--;
  e->next->prev=e->prev;
  e->prev->next=e->next;
  int l1=e>fat && e[-1].tete==fic, l2=e<fat+nbsect-1 && e[1].tete==fic;
  pelement f=l1? e-1 :l2? e[1].prev :&fic->p;
  *e=(element){f->next,f,fic};
  e->next->prev=e;
  f->next=e;
  fic->longueur++;
}