nodehash.c

   1 #include "cvs.h"
   2
   3 static Node *table[4096];
   4 static int entries;
   5
   6 Node *head_node;
   7
   8 static Node *hash_number(cvs_number *n)
   9 {
  10         cvs_number key = *n;
  11         Node *p;
  12         int hash;
  13         int i;
  14
  15         if (key.c > 2 && !key.n[key.c - 2]) {
  16                 key.n[key.c - 2] = key.n[key.c - 1];
  17                 key.c--;
  18         }
  19         if (key.c & 1)
  20                 key.n[key.c] = 0;
  21         for (i = 0, hash = 0; i < key.c - 1; i++)
  22                 hash += key.n[i];
  23         hash = (hash * 256 + key.n[key.c - 1]) % 4096;
  24         for (p = table[hash]; p; p = p->hash_next) {
  25                 if (p->number.c != key.c)
  26                         continue;
  27                 for (i = 0; i < key.c && p->number.n[i] == key.n[i]; i++)
  28                         ;
  29                 if (i == key.c)
  30                         return p;
  31         }
  32         p = calloc(1, sizeof(Node));
  33         p->number = key;
  34         p->hash_next = table[hash];
  35         table[hash] = p;
  36         entries++;
  37         return p;
  38 }
  39
  40 static Node *find_parent(cvs_number *n, int depth)
  41 {
  42         cvs_number key = *n;
  43         Node *p;
  44         int hash;
  45         int i;
  46
  47         key.c -= depth;
  48         for (i = 0, hash = 0; i < key.c - 1; i++)
  49                 hash += key.n[i];
  50         hash = (hash * 256 + key.n[key.c - 1]) % 4096;
  51         for (p = table[hash]; p; p = p->hash_next) {
  52                 if (p->number.c != key.c)
  53                         continue;
  54                 for (i = 0; i < key.c && p->number.n[i] == key.n[i]; i++)
  55                         ;
  56                 if (i == key.c)
  57                         break;
  58         }
  59         return p;
  60 }
  61
  62 void hash_version(cvs_version *v)
  63 {
  64         char name[CVS_MAX_REV_LEN];
  65         v->node = hash_number(&v->number);
  66         if (v->node->v) {
  67                 fprintf(stderr, "more than one delta with number %s\n",
  68                         cvs_number_string(&v->node->number, name));
  69         } else {
  70                 v->node->v = v;
  71         }
  72         if (v->node->number.c & 1) {
  73                 fprintf(stderr, "revision with odd depth (%s)\n",
  74                         cvs_number_string(&v->node->number, name));
  75         }
  76 }
  77
  78 void hash_patch(cvs_patch *p)
  79 {
  80         char name[CVS_MAX_REV_LEN];
  81         p->node = hash_number(&p->number);
  82         if (p->node->p) {
  83                 fprintf(stderr, "more than one delta with number %s\n",
  84                         cvs_number_string(&p->node->number, name));
  85         } else {
  86                 p->node->p = p;
  87         }
  88         if (p->node->number.c & 1) {
  89                 fprintf(stderr, "patch with odd depth (%s)\n",
  90                         cvs_number_string(&p->node->number, name));
  91         }
  92 }
  93
  94 void hash_branch(cvs_branch *b)
  95 {
  96         b->node = hash_number(&b->number);
  97 }
  98
  99 void clean_hash(void)
 100 {
 101         int i;
 102         for (i = 0; i < 4096; i++) {
 103                 Node *p = table[i];
 104                 table[i] = NULL;
 105                 while (p) {
 106                         Node *q = p->hash_next;
 107                         free(p);
 108                         p = q;
 109                 }
 110         }
 111         entries = 0;
 112         head_node = NULL;
 113 }
 114
 115 static int compare(const void *a, const void *b)
 116 {
 117         Node *x = *(Node * const *)a, *y = *(Node * const *)b;
 118         int n, i;
 119         n = x->number.c;
 120         if (n < y->number.c)
 121                 return -1;
 122         if (n > y->number.c)
 123                 return 1;
 124         for (i = 0; i < n; i++) {
 125                 if (x->number.n[i] < y->number.n[i])
 126                         return -1;
 127                 if (x->number.n[i] > y->number.n[i])
 128                         return 1;
 129         }
 130         return 0;
 131 }
 132
 133 static void try_pair(Node *a, Node *b)
 134 {
 135         int n = a->number.c;
 136         int i;
 137
 138         if (n == b->number.c) {
 139                 if (n == 2) {
 140                         a->next = b;
 141                         b->to = a;
 142                         return;
 143                 }
 144                 for (i = n - 2; i >= 0; i--)
 145                         if (a->number.n[i] != b->number.n[i])
 146                                 break;
 147                 if (i < 0) {
 148                         a->next = b;
 149                         a->to = b;
 150                         return;
 151                 }
 152         } else if (n == 2) {
 153                 head_node = a;
 154         }
 155         if ((b->number.c & 1) == 0) {
 156                 b->starts = 1;
 157                 /* can the code below ever be needed? */
 158                 Node *p = find_parent(&b->number, 1);
 159                 if (p)
 160                         p->next = b;
 161         }
 162 }
 163
 164 void build_branches(void)
 165 {
 166         Node **v = malloc(sizeof(Node *) * entries), **p = v;
 167         int i;
 168
 169         for (i = 0; i < 4096; i++) {
 170                 Node *q;
 171                 for (q = table[i]; q; q = q->hash_next)
 172                         *p++ = q;
 173         }
 174         qsort(v, entries, sizeof(Node *), compare);
 175         /* only trunk? */
 176         if (v[entries-1]->number.c == 2)
 177                 head_node = v[entries-1];
 178         for (p = v + entries - 2 ; p >= v; p--)
 179                 try_pair(p[0], p[1]);
 180         for (p = v + entries - 1 ; p >= v; p--) {
 181                 Node *a = *p, *b = NULL;
 182                 if (!a->starts)
 183                         continue;
 184                 b = find_parent(&a->number, 2);
 185                 if (!b) {
 186                         char name[CVS_MAX_REV_LEN];
 187                         fprintf(stderr, "no parent for %s\n",
 188                                 cvs_number_string(&a->number, name));
 189                         continue;
 190                 }
 191                 a->sib = b->down;
 192                 b->down = a;
 193         }
 194         free(v);
 195 }