2 * stats.c - various routines to do stats on the key graph
4 * Jonathan McDowell <noodles@earth.li>
6 * Copyright 2000-2002 Project Purple
19 * initcolour - Clear the key graph ready for use.
20 * @parent: Do we want to clear the parent pointers too?
22 * Clears the parent and colour information on all elements in the key
25 void initcolour(bool parent)
31 * Init the colour/parent values. We get each entry list from the hash
32 * table and walk along it, zeroing the values.
34 for (loop = 0; loop < HASHSIZE; loop++) {
35 curkey = gethashtableentry(loop);
36 while (curkey != NULL) {
37 ((struct stats_key *)curkey->object)->colour = 0;
39 ((struct stats_key *)curkey->object)->parent =
42 curkey = curkey->next;
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.
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.
56 unsigned long findpath(struct stats_key *have, struct stats_key *want)
58 struct ll *keys = NULL;
59 struct ll *oldkeys = NULL;
60 struct ll *sigs = NULL;
61 struct ll *nextkeys = NULL;
63 unsigned long count = 0;
66 keys = lladd(NULL, want);
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) {
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.
77 if (!((struct stats_key *)sigs->object)->disabled &&
78 !((struct stats_key *)sigs->object)->revoked &&
79 ((struct stats_key *)sigs->object)->colour == 0) {
81 ((struct stats_key *)sigs->object)->colour =
83 ((struct stats_key *)sigs->object)->parent =
86 nextkeys = lladd(nextkeys, sigs->object);
93 llfree(oldkeys, NULL);
99 if (oldkeys != NULL) {
100 llfree(oldkeys, NULL);
103 if (nextkeys != NULL) {
104 llfree(nextkeys, NULL);
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.
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.
122 void dofindpath(uint64_t have, uint64_t want, bool html, int count)
124 struct stats_key *keyinfoa, *keyinfob, *curkey;
125 uint64_t fullhave, fullwant;
130 fullhave = getfullkeyid(have);
131 fullwant = getfullkeyid(want);
134 * Make sure the keys we have and want are in the cache.
136 (void) cached_getkeysigs(fullhave);
137 (void) cached_getkeysigs(fullwant);
139 if ((keyinfoa = findinhash(fullhave)) == NULL) {
140 printf("Couldn't find key 0x%llX.\n", have);
143 if ((keyinfob = findinhash(fullwant)) == NULL) {
144 printf("Couldn't find key 0x%llX.\n", want);
150 while (pathnum < count) {
152 * Fill the tree info up.
155 rec = findpath(keyinfoa, keyinfob);
156 keyinfob->parent = 0;
158 printf("%s%d nodes examined. %ld elements in the hash%s\n",
163 if (keyinfoa->colour == 0) {
165 printf("Can't find a link from 0x%08llX to "
171 printf("Can't find any further paths%s\n",
176 printf("%d steps from 0x%08llX to 0x%08llX%s\n",
177 keyinfoa->colour, have & 0xFFFFFFFF,
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) ?
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"
197 curkey->keyid & 0xFFFFFFFF,
198 curkey->keyid & 0xFFFFFFFF,
199 curkey->keyid & 0xFFFFFFFF,
201 (curkey->keyid == fullwant) ?
204 printf("0x%08llX (%s)%s\n",
205 curkey->keyid & 0xFFFFFFFF,
207 "[User id not found]" :
209 (curkey->keyid == fullwant) ?
216 if (curkey != keyinfoa && curkey != keyinfob) {
217 curkey->disabled = true;
219 curkey = findinhash(curkey->parent);
222 puts("<P>List of key ids in path:</P>");
224 puts("List of key ids in path:");
227 while (curkey != NULL && curkey->keyid != 0) {
228 printf("0x%08llX ", curkey->keyid & 0xFFFFFFFF);
229 curkey = findinhash(curkey->parent);
239 struct stats_key *furthestkey(struct stats_key *have)
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;
255 curll = lladd(NULL, have);
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) {
263 * We've never seen it. Count it, mark it and
264 * explore its subtree.
267 max = (struct stats_key *)sigs->object;
268 ((struct stats_key *)sigs->object)->colour =
270 ((struct stats_key *)sigs->object)->parent =
271 ((struct stats_key *)
272 curll->object)->keyid;
274 nextll=lladd(nextll, sigs->object);