Added a description for my extensions (README-my-extensions.html).
[parsecvs/imz-RCS2git-use-cases.git] / nodehash.c
blobbaad8e911f98048dbdb6cc3ca67d50dc66e377ca
1 #include "cvs.h"
3 static Node *table[4096];
4 static int entries;
6 Node *head_node;
8 static Node *hash_number(cvs_number *n)
10 cvs_number key = *n;
11 Node *p;
12 int hash;
13 int i;
15 if (key.c > 2 && !key.n[key.c - 2]) {
16 key.n[key.c - 2] = key.n[key.c - 1];
17 key.c--;
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++)
29 if (i == key.c)
30 return p;
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;
40 static Node *find_parent(cvs_number *n, int depth)
42 cvs_number key = *n;
43 Node *p;
44 int hash;
45 int i;
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++)
56 if (i == key.c)
57 break;
59 return p;
62 void hash_version(cvs_version *v)
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;
72 if (v->node->number.c & 1) {
73 fprintf(stderr, "revision with odd depth (%s)\n",
74 cvs_number_string(&v->node->number, name));
78 void hash_patch(cvs_patch *p)
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;
88 if (p->node->number.c & 1) {
89 fprintf(stderr, "patch with odd depth (%s)\n",
90 cvs_number_string(&p->node->number, name));
94 void hash_branch(cvs_branch *b)
96 b->node = hash_number(&b->number);
99 void clean_hash(void)
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;
111 entries = 0;
112 head_node = NULL;
115 static int compare(const void *a, const void *b)
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;
130 return 0;
133 static void try_pair(Node *a, Node *b)
135 int n = a->number.c;
136 int i;
138 if (n == b->number.c) {
139 if (n == 2) {
140 a->next = b;
141 b->to = a;
142 return;
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;
152 } else if (n == 2) {
153 head_node = a;
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;
164 void build_branches(void)
166 Node **v = malloc(sizeof(Node *) * entries), **p = v;
167 int i;
169 for (i = 0; i < 4096; i++) {
170 Node *q;
171 for (q = table[i]; q; q = q->hash_next)
172 *p++ = q;
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;
191 a->sib = b->down;
192 b->down = a;
194 free(v);