patch_depends.c

   1
   2 /*
   3  * Given a list of files containing patches, we determine any dependancy
   4  * relationship between them.
   5  * If a chunk in one file overlaps a chunk in a previous file then the one
   6  * depends on the other.
   7  *
   8  * Each patch contains a list of chunks that apply to a file. Each
   9  * chunk has an original start/end and a new start/end.
  10  *
  11  * Each target file links to  a list of chunks, each of which points to it's
  12  * patch file. The chunks are sorted by new start
  13  *
  14  * When we add a chunk which changes size, we update the new start/end of all
  15  * previous chunks in that file which end after this one starts.
  16  *
  17  */
  18
  19 struct chunk {
  20         struct patch *patch;    /* the patch this chunk is from */
  21         struct file *file;      /* the file this chunk patches */
  22         int old_start, old_end;
  23         int new_start, new_end;
  24         struct chunk *next;     /* next chunk for this file */
  25 };
  26
  27 struct file {
  28         char * name;            /* name of the file */
  29         struct chunk *chunks;   /* chunks which patch this file */
  30 };
  31
  32 struct patch {
  33         char * name;            /* name of file containing this patch */
  34         int cnt;                /* number of patches we depend on (so far) */
  35         struct patch *depends;  /* array of patches we depend on */
  36         struct patch *next;     /* previous patch that was loaded */
  37 } *patches = NULL;
  38
  39 void report(void)
  40 {
  41         struct patch *p;
  42         int c;
  43
  44         for (p= patches; p ; p=p->next) {
  45                 printf("%s :", p->name);
  46                 for (c=0 ; c < p->cnt ; c++)
  47                         printf(" %s", p->depends[c]);
  48                 printf("\n");
  49         }
  50 }
  51
  52 int check_depends(struct patch *new, struct patch *old)
  53 {
  54         /* see if new already depends on old */
  55         int i;
  56         if (new == old) return 1;
  57         for (i=0; i<new->cnt ; i++)
  58                 if (check_depends(new->depends[i], old))
  59                         return 1;
  60         return 0;
  61 }
  62
  63 void add_depends(struct patch *new, struct patch *old)
  64 {
  65         /* patch new depends on patch old, but this hasn't
  66          * been recorded yet
  67          */
  68         int size = InitDepends;
  69         while (size < new->cnt) size<<= 1;
  70
  71         new->cnt++;
  72         if (new->cnt > size)
  73                 new->depends = realloc(new->depends, size*sizeof(struct patch *));
  74         new->depends[new->cnt-1] = old;
  75 }
  76
  77 void add_chunk(struct patch *p, struct file *f, int os, int oe, int ns, int ne)
  78 {
  79         struct chunk *c = xmalloc(sizeof(struct chunk));
  80         c->patch = p;
  81         c->file = f;
  82         c->old_start = os;
  83         c->old_end = oe;
  84         c->new_start = ns;
  85         c->new_end = ne;
  86
  87         for (c1 = f->chunks ; c1 ; c1=c1->next) {
  88                 if (ns < c1->new_end && ne > c1->new_start) {
  89                         /* goody, found a dependancy */
  90                         if (!check_depends(c->patch, c1->patch))
  91                                 add_depends(c->patch, c1->patch);
  92                 }