]> git.sommitrealweird.co.uk Git - onak.git/blob - stats.c
cscvs to tla changeset 38
[onak.git] / stats.c
1 /*
2  * stats.c - various routines to do stats on the key graph
3  *
4  * Jonathan McDowell <noodles@earth.li>
5  *
6  * Copyright 2000-2002 Project Purple
7  */
8
9 #include <stdio.h>
10 #include <stdlib.h>
11
12 #include "getcgi.h"
13 #include "hash.h"
14 #include "keydb.h"
15 #include "ll.h"
16 #include "stats.h"
17
18 /**
19  *      initcolour - Clear the key graph ready for use.
20  *      @parent: Do we want to clear the parent pointers too?
21  *
22  *      Clears the parent and colour information on all elements in the key
23  *      graph.
24  */
25 void initcolour(bool parent)
26 {
27         unsigned long loop;
28         struct ll *curkey;
29
30         /*
31          * Init the colour/parent values. We get each entry list from the hash
32          * table and walk along it, zeroing the values.
33          */
34         for (loop = 0; loop < HASHSIZE; loop++) {
35                 curkey = gethashtableentry(loop);
36                 while (curkey != NULL) {
37                         ((struct stats_key *)curkey->object)->colour = 0;
38                         if (parent) {
39                                 ((struct stats_key *)curkey->object)->parent =
40                                         0;
41                         }
42                         curkey = curkey->next;
43                 }
44         }
45 }
46
47 /**
48  *      findpath - Given 2 keys finds a path between them.
49  *      @have: The key we have.
50  *      @want: The key we want to get to.
51  *
52  *      This does a breadth first search on the key tree, starting with the
53  *      key we have. It returns as soon as a path is found or when we run out
54  *      of keys; whichever comes sooner.
55  */
56 unsigned long findpath(struct stats_key *have, struct stats_key *want)
57 {
58         struct ll *keys = NULL;
59         struct ll *sigs = NULL;
60         struct ll *nextkeys = NULL;
61         long curdegree = 0;
62         long count = 0;
63         
64         curdegree = 1;
65         keys = lladd(NULL, want);
66
67         while (keys != NULL && have->colour == 0) {
68                 sigs = hash_getkeysigs(((struct stats_key *)
69                                         keys->object)->keyid);
70                 while (sigs != NULL && have->colour == 0) {
71                         /*
72                          * Check if we've seen this key before and if not mark
73                          * it and add its sigs to the list we want to look at.
74                          */
75                         if (((struct stats_key *)sigs->object)->colour == 0) {
76                                 count++;
77                                 ((struct stats_key *)sigs->object)->colour =
78                                         curdegree;
79                                 ((struct stats_key *)sigs->object)->parent =
80                                         ((struct stats_key *)
81                                          keys->object)->keyid;
82                                 nextkeys = lladd(nextkeys, sigs->object);
83                         }
84                         sigs = sigs->next;
85                 }
86                 keys = keys->next;
87                 if (keys == NULL) {
88                         keys = nextkeys;
89                         nextkeys = NULL;
90                         curdegree++;
91                 }
92         }
93
94         return count;
95 }
96
97 /**
98  *      dofindpath - Given 2 keys displays a path between them.
99  *      @have: The key we have.
100  *      @want: The key we want to get to.
101  *      @html: Should we output in html.
102  *
103  *      This does a breadth first search on the key tree, starting with the
104  *      key we have. It returns as soon as a path is found or when we run out
105  *      of keys; whichever comes sooner.
106  */
107 void dofindpath(uint64_t have, uint64_t want, bool html)
108 {
109         struct stats_key *keyinfoa, *keyinfob, *curkey;
110         int rec;
111         char *uid;
112
113         have = getfullkeyid(have);
114         want = getfullkeyid(want);
115
116         /*
117          * Make sure the keys we have and want are in the cache.
118          */
119         hash_getkeysigs(have);
120         hash_getkeysigs(want);
121
122         if ((keyinfoa = findinhash(have)) == NULL) {
123                 printf("Couldn't find key 0x%llX.\n", have);
124                 return;
125         }
126         if ((keyinfob = findinhash(want)) == NULL) {
127                 printf("Couldn't find key 0x%llX.\n", want);
128                 return;
129         }
130         
131         /*
132          * Fill the tree info up.
133          */
134         initcolour(true);
135         rec = findpath(keyinfoa, keyinfob);
136         keyinfob->parent = 0;
137
138         printf("%d nodes examined. %ld elements in the hash%s\n", rec,
139                         hashelements(),
140                         html ? "<BR>" : "");
141         if (keyinfoa->colour == 0) {
142                 printf("Can't find a link from 0x%08llX to 0x%08llX%s\n",
143                                 have,
144                                 want,
145                                 html ? "<BR>" : "");
146         } else {
147                 printf("%d steps from 0x%08llX to 0x%08llX%s\n",
148                                 keyinfoa->colour, have & 0xFFFFFFFF,
149                                 want & 0xFFFFFFFF,
150                                 html ? "<BR>" : "");
151                 curkey = keyinfoa;
152                 while (curkey != NULL && curkey->keyid != 0) {
153                         uid = keyid2uid(curkey->keyid);
154                         if (html && uid == NULL) {
155                                 printf("<a href=\"lookup?op=get&search=%llX\">"
156                                         "0x%08llX</a> ([User id not found])%s"
157                                         "<BR>\n",
158                                         curkey->keyid & 0xFFFFFFFF,
159                                         curkey->keyid & 0xFFFFFFFF,
160                                         (curkey->keyid == want) ? "" :
161                                          " signs");
162                         } else if (html && uid != NULL) {
163                                 printf("<a href=\"lookup?op=get&search=%llX\">"
164                                         "0x%08llX</a> (<a href=\"lookup?op=vindex"
165                                         "&search=0x%llX\">%s</a>)%s<BR>\n",
166                                         curkey->keyid & 0xFFFFFFFF,
167                                         curkey->keyid & 0xFFFFFFFF,
168                                         curkey->keyid & 0xFFFFFFFF,
169                                         txt2html(keyid2uid(curkey->keyid)),
170                                         (curkey->keyid == want) ? "" :
171                                          " signs");
172                         } else {
173                                 printf("0x%08llX (%s)%s\n",
174                                         curkey->keyid & 0xFFFFFFFF,
175                                         (uid == NULL) ? "[User id not found]" :
176                                                 uid,
177                                         (curkey->keyid == want) ? "" :
178                                          " signs");
179                         }
180                         curkey = findinhash(curkey->parent);
181                 }
182                 if (html) {
183                         puts("<P>List of key ids in path:</P>");
184                 } else {
185                         puts("List of key ids in path:");
186                 }
187                 curkey = keyinfoa;
188                 while (curkey != NULL && curkey->keyid != 0) {
189                         printf("0x%08llX ", curkey->keyid & 0xFFFFFFFF);
190                         curkey = findinhash(curkey->parent);
191                 }
192                 putchar('\n');
193         }
194 }
195
196
197
198 struct stats_key *furthestkey(struct stats_key *have)
199 {
200         unsigned long count = 0;
201         unsigned long curdegree = 0;
202         struct ll *curll, *nextll, *tmp;
203         struct ll *sigs = NULL;
204         struct stats_key *max;
205
206         if (have == NULL) {
207                 return NULL;
208         }
209
210         ++curdegree;
211
212         nextll = NULL;
213         max = have;
214         curll = lladd(NULL, have);
215
216         while (curll != NULL) {
217                 sigs = hash_getkeysigs(((struct stats_key *)
218                                 curll->object)->keyid);
219                 while (sigs != NULL) {
220                         if (((struct stats_key *) sigs->object)->colour == 0) {
221                                 /*
222                                  * We've never seen it. Count it, mark it and
223                                  * explore its subtree.
224                                  */
225                                 count++;
226                                 max = (struct stats_key *)sigs->object;
227                                 ((struct stats_key *)sigs->object)->colour = 
228                                         curdegree;
229                                 ((struct stats_key *)sigs->object)->parent = 
230                                         ((struct stats_key *)
231                                          curll->object)->keyid;
232                                 
233                                 nextll=lladd(nextll, sigs->object);
234                         }
235                         sigs=sigs->next;
236                 }
237                 tmp = curll->next;
238                 free(curll);
239                 curll = tmp;
240                 if (curll == NULL) {
241                         curll = nextll;
242                         nextll = NULL;
243                         ++curdegree;
244                 };
245         }
246
247         return max;
248 }