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 *sigs = NULL;
60 struct ll *nextkeys = NULL;
65 keys = lladd(NULL, want);
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) {
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.
75 if (((struct stats_key *)sigs->object)->colour == 0) {
77 ((struct stats_key *)sigs->object)->colour =
79 ((struct stats_key *)sigs->object)->parent =
82 nextkeys = lladd(nextkeys, sigs->object);
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.
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.
107 void dofindpath(uint64_t have, uint64_t want, bool html)
109 struct stats_key *keyinfoa, *keyinfob, *curkey;
113 have = getfullkeyid(have);
114 want = getfullkeyid(want);
117 * Make sure the keys we have and want are in the cache.
119 hash_getkeysigs(have);
120 hash_getkeysigs(want);
122 if ((keyinfoa = findinhash(have)) == NULL) {
123 printf("Couldn't find key 0x%llX.\n", have);
126 if ((keyinfob = findinhash(want)) == NULL) {
127 printf("Couldn't find key 0x%llX.\n", want);
132 * Fill the tree info up.
135 rec = findpath(keyinfoa, keyinfob);
136 keyinfob->parent = 0;
138 printf("%d nodes examined. %ld elements in the hash%s\n", rec,
141 if (keyinfoa->colour == 0) {
142 printf("Can't find a link from 0x%08llX to 0x%08llX%s\n",
147 printf("%d steps from 0x%08llX to 0x%08llX%s\n",
148 keyinfoa->colour, have & 0xFFFFFFFF,
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"
158 curkey->keyid & 0xFFFFFFFF,
159 curkey->keyid & 0xFFFFFFFF,
160 (curkey->keyid == want) ? "" :
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) ? "" :
173 printf("0x%08llX (%s)%s\n",
174 curkey->keyid & 0xFFFFFFFF,
175 (uid == NULL) ? "[User id not found]" :
177 (curkey->keyid == want) ? "" :
180 curkey = findinhash(curkey->parent);
183 puts("<P>List of key ids in path:</P>");
185 puts("List of key ids in path:");
188 while (curkey != NULL && curkey->keyid != 0) {
189 printf("0x%08llX ", curkey->keyid & 0xFFFFFFFF);
190 curkey = findinhash(curkey->parent);
198 struct stats_key *furthestkey(struct stats_key *have)
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;
214 curll = lladd(NULL, have);
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) {
222 * We've never seen it. Count it, mark it and
223 * explore its subtree.
226 max = (struct stats_key *)sigs->object;
227 ((struct stats_key *)sigs->object)->colour =
229 ((struct stats_key *)sigs->object)->parent =
230 ((struct stats_key *)
231 curll->object)->keyid;
233 nextll=lladd(nextll, sigs->object);