]> git.sommitrealweird.co.uk Git - onak.git/blob - stats.c
Log total received key count.
[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 int 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 *oldkeys = NULL;
60         struct ll *sigs = NULL;
61         struct ll *nextkeys = NULL;
62         long curdegree = 0;
63         unsigned long count = 0;
64         
65         curdegree = 1;
66         keys = lladd(NULL, want);
67         oldkeys = keys;
68
69         while (keys != NULL && have->colour == 0) {
70                 sigs = cached_getkeysigs(((struct stats_key *)
71                                         keys->object)->keyid);
72                 while (sigs != NULL && have->colour == 0) {
73                         /*
74                          * Check if we've seen this key before and if not mark
75                          * it and add its sigs to the list we want to look at.
76                          */
77                         if (!((struct stats_key *)sigs->object)->disabled &&
78                             !((struct stats_key *)sigs->object)->revoked &&
79                             ((struct stats_key *)sigs->object)->colour == 0) {
80                                 count++;
81                                 ((struct stats_key *)sigs->object)->colour =
82                                         curdegree;
83                                 ((struct stats_key *)sigs->object)->parent =
84                                         ((struct stats_key *)
85                                          keys->object)->keyid;
86                                 nextkeys = lladd(nextkeys, sigs->object);
87                         }
88                         sigs = sigs->next;
89                 }
90                 keys = keys->next;
91                 if (keys == NULL) {
92                         keys = nextkeys;
93                         llfree(oldkeys, NULL);
94                         oldkeys = keys;
95                         nextkeys = NULL;
96                         curdegree++;
97                 }
98         }
99         if (oldkeys != NULL) {
100                 llfree(oldkeys, NULL);
101                 oldkeys = NULL;
102         }
103         if (nextkeys != NULL) {
104                 llfree(nextkeys, NULL);
105                 nextkeys = NULL;
106         }
107
108         return count;
109 }
110
111 /**
112  *      dofindpath - Given 2 keys displays a path between them.
113  *      @have: The key we have.
114  *      @want: The key we want to get to.
115  *      @html: Should we output in html.
116  *      @count: How many paths we should look for.
117  *
118  *      This does a breadth first search on the key tree, starting with the
119  *      key we have. It returns as soon as a path is found or when we run out
120  *      of keys; whichever comes sooner.
121  */
122 void dofindpath(uint64_t have, uint64_t want, bool html, int count)
123 {
124         struct stats_key *keyinfoa, *keyinfob, *curkey;
125         uint64_t fullhave, fullwant;
126         int rec;
127         int pathnum;
128         char *uid;
129
130         fullhave = getfullkeyid(have);
131         fullwant = getfullkeyid(want);
132
133         /*
134          * Make sure the keys we have and want are in the cache.
135          */
136         (void) cached_getkeysigs(fullhave);
137         (void) cached_getkeysigs(fullwant);
138
139         if ((keyinfoa = findinhash(fullhave)) == NULL) {
140                 printf("Couldn't find key 0x%llX.\n", have);
141                 return;
142         }
143         if ((keyinfob = findinhash(fullwant)) == NULL) {
144                 printf("Couldn't find key 0x%llX.\n", want);
145                 return;
146         }
147
148         pathnum = 0;
149         
150         while (pathnum < count) {
151                 /*
152                  * Fill the tree info up.
153                  */
154                 initcolour(true);
155                 rec = findpath(keyinfoa, keyinfob);
156                 keyinfob->parent = 0;
157
158                 printf("%s%d nodes examined. %ld elements in the hash%s\n",
159                         html ? "<HR>" : "",
160                         rec,
161                         hashelements(),
162                         html ? "<BR>" : "");
163                 if (keyinfoa->colour == 0) {
164                         if (pathnum == 0) {
165                                 printf("Can't find a link from 0x%08llX to "
166                                 "0x%08llX%s\n",
167                                 have,
168                                 want,
169                                 html ? "<BR>" : "");
170                         } else {
171                                 printf("Can't find any further paths%s\n",
172                                         html ? "<BR>" : "");
173                         }
174                         pathnum = count;
175                 } else {
176                         printf("%d steps from 0x%08llX to 0x%08llX%s\n",
177                                 keyinfoa->colour, have & 0xFFFFFFFF,
178                                 want & 0xFFFFFFFF,
179                                 html ? "<BR>" : "");
180                         curkey = keyinfoa;
181                         while (curkey != NULL && curkey->keyid != 0) {
182                                 uid = keyid2uid(curkey->keyid);
183                                 if (html && uid == NULL) {
184                                         printf("<a href=\"lookup?op=get&search="
185                                                 "0x%08llX\">0x%08llX</a> (["
186                                                 "User id not found])%s<BR>\n",
187                                                 curkey->keyid & 0xFFFFFFFF,
188                                                 curkey->keyid & 0xFFFFFFFF,
189                                                 (curkey->keyid == fullwant) ?
190                                                         "" : " signs");
191                                 } else if (html && uid != NULL) {
192                                         printf("<a href=\"lookup?op=get&search="
193                                                 "0x%08llX\">0x%08llX</a>"
194                                                 " (<a href=\"lookup?op=vindex&"
195                                                 "search=0x%08llX\">%s</a>)%s"
196                                                 "<BR>\n",
197                                                 curkey->keyid & 0xFFFFFFFF,
198                                                 curkey->keyid & 0xFFFFFFFF,
199                                                 curkey->keyid & 0xFFFFFFFF,
200                                                 txt2html(uid),
201                                                 (curkey->keyid == fullwant) ?
202                                                 "" : " signs");
203                                 } else {
204                                         printf("0x%08llX (%s)%s\n",
205                                                 curkey->keyid & 0xFFFFFFFF,
206                                                 (uid == NULL) ?
207                                                         "[User id not found]" :
208                                                         uid,
209                                                 (curkey->keyid == fullwant) ?
210                                                 "" : " signs");
211                                 }
212                                 if (uid != NULL) {
213                                         free(uid);
214                                         uid = NULL;
215                                 }
216                                 if (curkey != keyinfoa && curkey != keyinfob) {
217                                         curkey->disabled = true;
218                                 }
219                                 curkey = findinhash(curkey->parent);
220                         }
221                         if (html) {
222                                 puts("<P>List of key ids in path:</P>");
223                         } else {
224                                 puts("List of key ids in path:");
225                         }
226                         curkey = keyinfoa;
227                         while (curkey != NULL && curkey->keyid != 0) {
228                                 printf("0x%08llX ", curkey->keyid & 0xFFFFFFFF);
229                                 curkey = findinhash(curkey->parent);
230                         }
231                         putchar('\n');
232                 }
233                 pathnum++;
234         }
235 }
236
237
238
239 struct stats_key *furthestkey(struct stats_key *have)
240 {
241         unsigned long count = 0;
242         unsigned long curdegree = 0;
243         struct ll *curll, *nextll, *tmp;
244         struct ll *sigs = NULL;
245         struct stats_key *max;
246
247         if (have == NULL) {
248                 return NULL;
249         }
250
251         ++curdegree;
252
253         nextll = NULL;
254         max = have;
255         curll = lladd(NULL, have);
256
257         while (curll != NULL) {
258                 sigs = cached_getkeysigs(((struct stats_key *)
259                                 curll->object)->keyid);
260                 while (sigs != NULL) {
261                         if (((struct stats_key *) sigs->object)->colour == 0) {
262                                 /*
263                                  * We've never seen it. Count it, mark it and
264                                  * explore its subtree.
265                                  */
266                                 count++;
267                                 max = (struct stats_key *)sigs->object;
268                                 ((struct stats_key *)sigs->object)->colour = 
269                                         curdegree;
270                                 ((struct stats_key *)sigs->object)->parent = 
271                                         ((struct stats_key *)
272                                          curll->object)->keyid;
273                                 
274                                 nextll=lladd(nextll, sigs->object);
275                         }
276                         sigs=sigs->next;
277                 }
278                 tmp = curll->next;
279                 free(curll);
280                 curll = tmp;
281                 if (curll == NULL) {
282                         curll = nextll;
283                         nextll = NULL;
284                         ++curdegree;
285                 };
286         }
287
288         return max;
289 }