sys/src/cmd/hgfs/ancestor.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <thread.h>
   4 #include "dat.h"
   5 #include "fns.h"
   6
   7 typedef struct XNode XNode;
   8 struct XNode
   9 {
  10         XNode   *next;
  11         XNode   *queue;
  12         char    mark;
  13         uchar   hash[HASHSZ];
  14 };
  15
  16 static XNode*
  17 hnode(XNode *ht[], uchar hash[])
  18 {
  19         XNode *h;
  20
  21         for(h = ht[hash[0]]; h; h = h->next)
  22                 if(memcmp(h->hash, hash, HASHSZ) == 0)
  23                         return h;
  24
  25         h = malloc(sizeof(*h));
  26         memmove(h->hash, hash, HASHSZ);
  27         h->mark = 0;
  28         h->queue = nil;
  29         h->next = ht[hash[0]];
  30         ht[hash[0]] = h;
  31         return h;
  32 }
  33
  34 /*
  35  * find common ancestor revision ahash for xhash and yhash
  36  * in the give hgfs mount point. sets ahash to nullid if
  37  * no common ancestor.
  38  */
  39 void
  40 ancestor(char *mtpt, uchar xhash[], uchar yhash[], uchar ahash[])
  41 {
  42         XNode *ht[256], *h, *q, *q1, *q2;
  43         char buf[MAXPATH], rev[6];
  44         int i;
  45
  46         if(memcmp(xhash, yhash, HASHSZ) == 0){
  47                 memmove(ahash, xhash, HASHSZ);
  48                 return;
  49         }
  50         if(memcmp(xhash, nullid, HASHSZ) == 0){
  51                 memmove(ahash, nullid, HASHSZ);
  52                 return;
  53         }
  54         if(memcmp(yhash, nullid, HASHSZ) == 0){
  55                 memmove(ahash, nullid, HASHSZ);
  56                 return;
  57         }
  58
  59         memset(ht, 0, sizeof(ht));
  60         q1 = nil;
  61
  62         h = hnode(ht, xhash);
  63         h->mark = 'x';
  64         h->queue = q1;
  65         q1 = h;
  66
  67         h = hnode(ht, yhash);
  68         h->mark = 'y';
  69         h->queue = q1;
  70         q1 = h;
  71
  72         for(;;){
  73                 q2 = nil;
  74                 while(q = q1){
  75                         q1 = q->queue;
  76                         q->queue = nil;
  77                         snprint(buf, sizeof(buf), "%s/%H", mtpt, q->hash);
  78                         for(i=1; i<=2; i++){
  79                                 sprint(rev, "rev%d", i);
  80                                 if(readhash(buf, rev, ahash) != 0)
  81                                         continue;
  82                                 if(memcmp(ahash, nullid, HASHSZ) == 0)
  83                                         continue;
  84                                 h = hnode(ht, ahash);
  85                                 if(h->mark){
  86                                         if(h->mark != q->mark)
  87                                                 goto Done;
  88                                 } else {
  89                                         h->mark = q->mark;
  90                                         h->queue = q2;
  91                                         q2 = h;
  92                                 }
  93                         }
  94                 }
  95                 if(q2 == nil){
  96                         memmove(ahash, nullid, HASHSZ);
  97                         break;
  98                 }
  99                 q1 = q2;
 100         }
 101
 102 Done:
 103         for(i=0; i<nelem(ht); i++)
 104                 while(h = ht[i]){
 105                         ht[i] = h->next;
 106                         free(h);
 107                 }
 108 }