gpgstats-0.0.2/graphstuff.c

   1 /*
   2         grahpstuff.c - Code to handle the various graph algorithms
   3         Written by Jonathan McDowell <noodles@earth.li>.
   4
   5         19/02/2000 - Started writing (sort of).
   6 */
   7
   8 // #include <ctype.h>
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12
  13 //#include "gpgstats.h"
  14 #include "hash.h"
  15 /* #include "ll.h"
  16 #include "parse.h" */
  17 #include "graphstuff.h"
  18
  19 struct keycount { unsigned long count; struct stats_key *k; };
  20
  21 struct ll *finished=NULL;
  22 struct ll *trees=NULL;
  23
  24
  25 int keycmp(struct stats_key *key1, struct stats_key *key2)
  26 {
  27         if (key1->keyid == key2->keyid) {
  28                 return 0;
  29         }
  30         return 1;
  31 }
  32
  33
  34 struct ll *addkey(struct ll *curkey, uint64_t keyid)
  35 {
  36         return lladd(curkey, createandaddtohash(keyid));
  37 }
  38
  39 void readkeys(const char *filename)
  40 {
  41         char curline[1024];
  42         unsigned long keys=0,sigs=0,pub=0, revoked=0;
  43         uint64_t keyin = 0;
  44         uint64_t cursig = 0;
  45         struct stats_key *curkey=NULL, *cursign=NULL;
  46         FILE *keyfile;
  47         int (*p)();
  48
  49         p=keycmp;
  50
  51         printf("Reading key info from '%s'.\n", filename);
  52         if ((keyfile=fopen(filename, "r"))==NULL) {
  53                 perror("readkeys()");
  54                 return;
  55         }
  56         /* read a line */
  57         fgets(curline, 1023, keyfile);
  58         while (!feof(keyfile)) {
  59                 if (curline[0]=='P') {
  60                         ++pub;
  61                         ++keys;
  62                         printf("\rRead %ld keys so far.", keys);
  63                         keyin = strtoul(&curline[1], NULL, 16);
  64                         curkey = createandaddtohash(keyin);
  65                 } else if (curline[0]=='S') {
  66                         cursig = strtoul(&curline[1], NULL, 16);
  67 /*                      if (curkey->keyid==cursig) {
  68                                 curkey->selfsigned=1;
  69                         } */
  70
  71                         if (!llfind(curkey->sigs, &cursig, p)) {
  72                                 curkey->sigs = addkey(curkey->sigs, cursig);
  73                                 ++sigs;
  74                         }
  75
  76                         if ((cursign=findinhash(cursig))==NULL) {
  77                                 cursign = createandaddtohash(cursig);
  78                         }
  79
  80 //SIGNS                 if (!llfind(cursign->signs, curkey, p)) {
  81 //SIGNS                         cursign->signs = addkey(cursign->signs,
  82 //SIGNS                                         curkey->keyid);
  83 //SIGNS                 }
  84                 } else if (curline[0]=='N') {
  85 /*                      if (curkey->name==NULL) {
  86                                 curkey->name=strdup(&curline[1]);
  87                                 curkey->name[strlen(curkey->name)-1]=0;
  88                                 if (strcmp(curkey->name, "[revoked]")==0) {
  89                                         curkey->revoked=1;
  90                                         ++revoked;
  91                                 }
  92                         } */
  93                 }
  94                 fgets(curline, 1023, keyfile);
  95         }
  96         fclose(keyfile);
  97         printf("\rRead %ld keys, %ld pub, %ld sigs, %ld revoked.\n", keys, pub, sigs, revoked);
  98         printf("\rRead %ld keys, %ld pub, %ld sigs, %ld revoked.\n", keys, pub, sigs, revoked);
  99 }
 100
 101
 102 void DFSVisit(int type, struct stats_key *key, unsigned long *time, unsigned long *depth)
 103 {
 104         struct ll *curkey;
 105         struct stats_key *v;
 106
 107         key->colour=1;
 108 //      key->d=(*time)++;
 109
 110         if (type == 0) {
 111 //SIGNS         curkey = key->signs;
 112         } else {
 113                 curkey = key->sigs;
 114         }
 115         while (curkey != NULL) {
 116                 v = (struct stats_key *)findinhash(
 117                                 ((struct stats_key *) curkey->object)->keyid);
 118                 if (v == NULL) {
 119                         printf("Couldn't find key in hash. Most odd.\n");
 120                 }
 121                 if (v != NULL && v->colour == 0) {
 122                         if (type == 1 && key->parent == 0) {
 123                                 printf("key->parent is 0.\n");
 124                         } else if (type == 1) {
 125                                 key->parent->object = lladd(key->parent->object,
 126                                                 v);
 127                                 v->parent = key->parent;
 128                         }
 129
 130                         (*depth)++;
 131                         DFSVisit(type, v, time, depth);
 132                 }
 133                 curkey=curkey->next;
 134         }
 135         key->colour = 2;
 136 //      key->f=(*time)++;
 137         if (type == 0) {
 138                 finished=lladd(finished, key);
 139         }
 140 }
 141
 142
 143 unsigned long DFS(void)
 144 {
 145         unsigned long loop,time=0,depth,maxdepth=0;
 146         struct ll *curkey;
 147
 148         initcolour(1);
 149         for (loop=0; loop<HASHSIZE; loop++) {
 150                 curkey=gethashtableentry(loop);
 151                 while (curkey!=NULL) {
 152                         if (((struct stats_key *)curkey->object)->colour==0) {
 153                                 depth=0;
 154                                 DFSVisit(0, ((struct stats_key *)curkey->object),
 155                                         &time, &depth);
 156                                 if (depth>maxdepth) maxdepth=depth;
 157                         }
 158                         curkey=curkey->next;
 159                 }
 160         }
 161         return maxdepth;
 162 }
 163
 164
 165 unsigned long DFSsorted(void)
 166 {
 167         unsigned long time=0,depth,maxdepth=0;
 168         struct ll *curkey;
 169
 170         initcolour(1);
 171         curkey=finished;
 172         while (curkey != NULL) {
 173                 if (((struct stats_key *)curkey->object)->colour == 0) {
 174                         trees = lladd(trees, curkey->object);
 175                         ((struct stats_key *)curkey->object)->parent =
 176                                 trees;
 177                         ((struct stats_key *)curkey->object)->parent->object =
 178                                 lladd(NULL, curkey->object);
 179
 180                         depth = 0;
 181                         DFSVisit(1, ((struct stats_key *)curkey->object),
 182                                 &time, &depth);
 183                         if (depth>maxdepth) {
 184                                 maxdepth = depth;
 185                         }
 186                 }
 187                 curkey = curkey->next;
 188         }
 189         return maxdepth;
 190 }
 191
 192 long checkselfsig()
 193 {
 194         unsigned long loop;
 195         struct ll *curkey;
 196         unsigned long selfsig=0;
 197
 198         for (loop = 0; loop < HASHSIZE; loop++) {
 199                 curkey = gethashtableentry(loop);
 200                 while (curkey != NULL) {
 201 //SELFSIGNED            if (((struct stats_key *)curkey->object)->selfsigned) {
 202 //SELFSIGNED                    ++selfsig;
 203 //SELFSIGNED            }
 204                         curkey = curkey->next;
 205                 }
 206         }
 207
 208         return selfsig;
 209 }
 210
 211
 212 unsigned long countdegree(struct stats_key *have, int sigs, int maxdegree)
 213 {
 214         unsigned long count = 0, curdegree = 0;
 215         struct ll *curll, *nextll, *sigll, *tmp;
 216
 217         ++curdegree;
 218
 219         nextll = NULL;
 220         curll = lladd(NULL, have);
 221
 222         while (curll != NULL && curdegree <= maxdegree) {
 223                 if (sigs) {
 224                         sigll = ((struct stats_key *)curll->object)->sigs;
 225                 } else {
 226 //SIGNS                 sigll = ((struct stats_key *)curll->object)->signs;
 227                 }
 228                 while (sigll!=NULL) {
 229                         if (((struct stats_key *) sigll->object)->colour==0) {
 230                                 /* We've never seen it. Count it, mark it and
 231                                         explore its subtree */
 232                                 count++;
 233                                 ((struct stats_key *)sigll->object)->colour=curdegree;
 234                                 ((struct stats_key *)sigll->object)->parent =
 235                                         ((struct stats_key *)
 236                                          curll->object)->keyid;
 237                                 nextll=lladd(nextll, sigll->object);
 238                         }
 239                         sigll = sigll->next;
 240                 }
 241                 tmp = curll->next;
 242                 free(curll);
 243                 curll = tmp;
 244                 if (curll == NULL) {
 245                         curll = nextll;
 246                         nextll = NULL;
 247                         ++curdegree;
 248                 };
 249         }
 250
 251         return count;
 252 }
 253