fortcmp.c

   1 /*
   2  *              Fortune Cookie Comparison
   3  *
   4  *              (c) 1996 Martin Mares, <mj@atrey.karlin.mff.cuni.cz>
   5  */
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10
  11 static void
  12 die(char *msg)
  13 {
  14         fputs(msg, stderr);
  15         exit(1);
  16 }
  17
  18 static void *
  19 xmalloc(unsigned i)
  20 {
  21         void *k = malloc(i);
  22
  23         if (!k)
  24                 die("Out of memory!\n");
  25         return k;
  26 }
  27
  28 #define HASH 16384
  29
  30 struct woord {
  31         struct woord *next;
  32         unsigned id;
  33         char w[1];
  34         };
  35
  36 static struct woord *words[HASH];
  37 static unsigned lastid;
  38
  39 static struct woord *
  40 findword(char *wd)
  41 {
  42         unsigned h;
  43         char *c;
  44         struct woord *p;
  45
  46         c = wd;
  47         h = strlen(wd);
  48         while (*c)
  49                 h = 13*h + *c++;
  50         h = h & (HASH-1);
  51         for(p = words[h]; p; p = p->next)
  52                 if (!strcasecmp(p->w, wd))
  53                         return p;
  54         p = xmalloc(sizeof(struct woord) + strlen(wd));
  55         p->next = words[h];
  56         words[h] = p;
  57         strcpy(p->w, wd);
  58         p->id = lastid++;
  59 }
  60
  61 #define MFL 4096
  62 #define FHASH 16384
  63
  64 struct fortune {
  65         struct fortune *next;
  66         char *fn;
  67         unsigned line;
  68         unsigned count;
  69         unsigned words[0];
  70         };
  71
  72 static struct fortune *forts[FHASH];
  73
  74 static int
  75 comp(unsigned *p, unsigned *q)
  76 {
  77         if (*p < *q)
  78                 return -1;
  79         else if (*p > *q)
  80                 return 1;
  81         else
  82                 return 0;
  83 }
  84
  85 static void
  86 addfort(char *fn, unsigned line, unsigned *fort, unsigned len)
  87 {
  88         unsigned i, h;
  89         struct fortune *foo;
  90
  91 //      printf("Adding %s:%d (%d)\n", fn, line, len);
  92         qsort(fort, len, sizeof(unsigned), (void *) comp);
  93         h = len;
  94         for(i=0; i<len; i++)
  95                 h = 13*h + fort[i];
  96         h &= (FHASH-1);
  97         for(foo=forts[h]; foo; foo=foo->next)
  98                 if (len == foo->count && !memcmp(fort, foo->words, sizeof(unsigned)*len))
  99                         {
 100                                 printf("Possible DUP %s:%d with %s:%d\n", fn, line, foo->fn, foo->line);
 101                                 return;
 102                         }
 103         foo = xmalloc(sizeof(struct fortune) + sizeof(unsigned)*len);
 104         foo->next = forts[h];
 105         forts[h] = foo;
 106         foo->fn = fn;
 107         foo->line = line;
 108         foo->count = len;
 109         memcpy(foo->words, fort, len * sizeof(unsigned));
 110 }
 111
 112 static void
 113 dofort(char *fn)
 114 {
 115         struct woord *name = findword(fn);
 116         struct woord *wo;
 117         FILE *f;
 118         char line[256];
 119         unsigned forty[MFL];
 120         unsigned posn, lino, cnt, xxx;
 121         char *c, *d, e;
 122
 123         printf("%s...", fn);
 124         fflush(stdout);
 125         f = fopen(fn, "r");
 126         if (!f)
 127                 die("open failed!\n");
 128         xxx = lino = posn = cnt = 0;
 129         for(;;)
 130                 {
 131                         lino++;
 132                         fgets(line, 256, f);
 133                         if (feof(f))
 134                                 break;
 135                         c = strchr(line, '\n');
 136                         if (c)
 137                                 *c = 0;
 138                         if (line[0] == '%' && !line[1])
 139                                 {
 140                                         if (cnt)
 141                                                 {
 142                                                         addfort(name->w, posn, forty, cnt);
 143                                                         xxx++;
 144                                                 }
 145                                         cnt = 0;
 146                                 }
 147                         else
 148                                 {
 149                                         if (!cnt)
 150                                                 posn = lino;
 151                                         c = line;
 152                                         for(;;)
 153                                                 {
 154                                                         while (*c && (*c < 'A' || *c > 'Z') && (*c < 'a' || *c > 'z') && (*c < '0' || *c > '9'))
 155                                                                 c++;
 156                                                         if (!*c)
 157                                                                 break;
 158                                                         d = c;
 159                                                         while ((*c >= 'a' && *c <= 'z') || (*c >= 'A' && *c <= 'Z') || (*c >= '0' && *c <= '9'))
 160                                                                 {
 161                                                                         *c = toupper(*c);
 162                                                                         c++;
 163                                                                 }
 164                                                         e = *c;
 165                                                         *c = 0;
 166                                                         wo = findword(d);
 167                                                         *c = e;
 168                                                         if (cnt >= MFL)
 169                                                                 die("Too long!\n");
 170                                                         forty[cnt++] = wo->id;
 171                                                 }
 172                                 }
 173                 }
 174         fclose(f);
 175         printf("%d lines, %d fortunes\n", lino, xxx);
 176 }
 177
 178 int
 179 main(int argc, char **argv)
 180 {
 181         if (argc < 2)
 182                 die("Nothing to do.\n");
 183         while (argc > 1)
 184                 {
 185                         dofort(argv[1]);
 186                         argc--;
 187                         argv++;
 188                 }
 189         return 0;
 190 }