judge/judge-shuff.c

   1 /*
   2  *      A judge comparing shuffled sequences of tokens
   3  *
   4  *      (c) 2007 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include <getopt.h>
  11 #include <math.h>
  12
  13 #include "judge.h"
  14
  15 static int ignore_nl, ignore_empty, ignore_case;
  16 static int shuffle_lines, shuffle_words;
  17
  18 typedef unsigned int uns;
  19
  20 /*** Token buffer ***/
  21
  22 struct tokpage {
  23   struct tokpage *next;
  24   char *pos, *end;
  25   char buf[];
  26 };
  27
  28 struct tokbuf {
  29   // For writing:
  30   struct tokpage *first_page, *last_page;
  31   uns num_tokens, num_lines;
  32   // For reading:
  33   struct tokpage *this_page;
  34   char *read_pos;
  35 };
  36
  37 #define TOKBUF_PAGE 65536
  38
  39 static void init_tokbuf(struct tokbuf *tb)
  40 {
  41   memset(tb, 0, sizeof(*tb));
  42 }
  43
  44 static void add_token(struct tokbuf *tb, char *token, int l)
  45 {
  46   l++;
  47   struct tokpage *pg = tb->last_page;
  48   if (!pg || pg->end - pg->pos < l)
  49     {
  50       if (pg)
  51         pg->end = pg->pos;
  52       int size = TOKBUF_PAGE - sizeof(struct tokbuf);
  53       if (l > size/5)
  54         size = l;
  55       pg = xmalloc(sizeof(struct tokbuf) + size);
  56       if (tb->last_page)
  57         tb->last_page->next = pg;
  58       else
  59         tb->first_page = pg;
  60       tb->last_page = pg;
  61       pg->next = NULL;
  62       pg->pos = pg->buf;
  63       pg->end = pg->buf + size;
  64     }
  65   memcpy(pg->pos, token, l);
  66   pg->pos += l;
  67   tb->num_tokens++;
  68   if (l == 1)
  69     tb->num_lines++;
  70 }
  71
  72 static void close_tokens(struct tokbuf *tb)
  73 {
  74   if (tb->last_page)
  75     tb->last_page->end = tb->last_page->pos;
  76 }
  77
  78 static char *get_next(struct tokbuf *tb)
  79 {
  80   struct tokpage *pg = tb->this_page;
  81   tb->read_pos += strlen(tb->read_pos) + 1;
  82   if (tb->read_pos >= pg->end)
  83     {
  84       tb->this_page = pg = pg->next;
  85       if (!pg)
  86         return NULL;
  87       tb->read_pos = pg->buf;
  88     }
  89   return tb->read_pos;
  90 }
  91
  92 static char *get_first(struct tokbuf *tb)
  93 {
  94   struct tokpage *pg = tb->first_page;
  95   if (!pg)
  96     return NULL;
  97   tb->this_page = pg;
  98   tb->read_pos = pg->buf;
  99   return pg->buf;
 100 }
 101
 102 /*** Reading and shuffling ***/
 103
 104 struct tok {
 105   char *token;
 106   uns hash;
 107 };
 108
 109 struct line {
 110   struct tok *toks;
 111   uns len;
 112   uns hash;
 113   uns orig_line;
 114 };
 115
 116 struct shouffle {
 117   struct tokbuf tb;
 118   struct tok *tok_array;
 119   struct line *line_array;
 120   uns num_lines;
 121 };
 122
 123 static void read_input(struct tokenizer *t, struct tokbuf *tb)
 124 {
 125   char *tok;
 126   int nl = 1;
 127
 128   init_tokbuf(tb);
 129   while (tok = get_token(t))
 130     {
 131       if (tok[0])
 132         {
 133           nl = 0;
 134           if (ignore_case)
 135             for (char *c=tok; *c; c++)
 136               if (*c >= 'a' && *c <= 'z')
 137                 *c = *c - 'a' + 'A';
 138         }
 139       else
 140         {
 141           if (nl && ignore_nl)
 142             continue;
 143           nl = 1;
 144         }
 145       add_token(tb, tok, t->toksize);
 146     }
 147   if (!nl)
 148     add_token(tb, "", 0);
 149   close_tokens(tb);
 150 }
 151
 152 static inline uns string_hash(unsigned char *x)
 153 {
 154   uns h = 1;
 155   while (*x)
 156     h = (h * 0x6011) + *x++;
 157   return h;
 158 }
 159
 160 static inline uns line_hash(struct tok *t, uns cnt)
 161 {
 162   uns h = 1;
 163   while (cnt--)
 164     h = (h * 0x6011) + (t++)->hash;
 165   return h;
 166 }
 167
 168 static int compare_toks(struct tok *x, struct tok *y)
 169 {
 170   if (x->hash < y->hash)
 171     return -1;
 172   if (x->hash > y->hash)
 173     return 1;
 174   return strcmp(x->token, y->token);
 175 }
 176
 177 static int compare_lines(struct line *x, struct line *y)
 178 {
 179   if (x->hash < y->hash)
 180     return -1;
 181   if (x->hash > y->hash)
 182     return 1;
 183
 184   if (x->len < y->len)
 185     return -1;
 186   if (x->len > y->len)
 187     return 1;
 188
 189   for (uns i=0; i < x->len; i++)
 190     {
 191       int c = compare_toks(&x->toks[i], &y->toks[i]);
 192       if (c)
 193         return c;
 194     }
 195   return 0;
 196 }
 197
 198 static void slurp(struct tokenizer *t, struct shouffle *s)
 199 {
 200   read_input(t, &s->tb);
 201   s->tok_array = xmalloc(sizeof(struct tok) * s->tb.num_tokens);
 202   s->line_array = xmalloc(sizeof(struct line) * (s->tb.num_lines+1));
 203   s->num_lines = 0;
 204
 205   struct tok *tok = s->tok_array;
 206   struct line *line = s->line_array;
 207   line->toks = tok;
 208   for (char *x = get_first(&s->tb); x; x = get_next(&s->tb))
 209     if (*x)
 210       {
 211         tok->token = x;
 212         tok->hash = string_hash(x);
 213         tok++;
 214       }
 215     else
 216       {
 217         line->len = tok - line->toks;
 218         if (shuffle_words)
 219           qsort(line->toks, line->len, sizeof(struct tok), (int(*)(const void *, const void *)) compare_toks);
 220         line->hash = line_hash(line->toks, line->len);
 221         line->orig_line = ++s->num_lines;
 222 #if 0
 223         for (struct tok *t=line->toks; t<tok; t++)
 224           printf("<%08x|%s>", t->hash, t->token);
 225         printf(" -> %08x (%d)\n", line->hash, line->orig_line);
 226 #endif
 227         line++;
 228         line->toks = tok;
 229       }
 230   if (line->toks != tok)
 231     die("Bug #41: unterminated line");
 232   if (s->num_lines != s->tb.num_lines)
 233     die("Bug #42: got %d lines, expected %d", s->num_lines, s->tb.num_lines);
 234
 235   if (shuffle_lines)
 236     qsort(s->line_array, s->num_lines, sizeof(struct line), (int(*)(const void *, const void *)) compare_lines);
 237 }
 238
 239 static void compare(struct shouffle *s1, struct shouffle *s2)
 240 {
 241   if (s1->num_lines != s2->num_lines)
 242     {
 243       printf("Output has %d lines, expecting %d\n", s1->num_lines, s2->num_lines);
 244       exit(1);
 245     }
 246
 247   uns errs = 0;
 248   for (uns i=0; i<s1->num_lines; i++)
 249     {
 250       struct line *l1 = &s1->line_array[i], *l2 = &s2->line_array[i];
 251       if (compare_lines(l1, l2))
 252         {
 253           printf("Line %d does not match\n", l1->orig_line);
 254           printf("  %08x(%d) vs. %08x(%d)\n", l1->hash, l1->orig_line, l2->hash, l2->orig_line);
 255           errs++;
 256         }
 257     }
 258   if (errs)
 259     exit(1);
 260 }
 261
 262 /*** Main ***/
 263
 264 static void usage(void)
 265 {
 266   fprintf(stderr, "Usage: judge-shuff [<options>] <output> <correct>\n\
 267 \n\
 268 Options:\n\
 269 -n\t\tIgnore newlines and match the whole input as a single line\n\
 270 -e\t\tIgnore empty lines\n\
 271 -l\t\tShuffle lines (i.e., ignore their order)\n\
 272 -w\t\tShuffle words in each line\n\
 273 -i\t\tIgnore case\n\
 274 ");
 275   exit(2);
 276 }
 277
 278 int main(int argc, char **argv)
 279 {
 280   struct tokenizer t1, t2;
 281   int opt;
 282
 283   while ((opt = getopt(argc, argv, "nelwi")) >= 0)
 284     switch (opt)
 285       {
 286       case 'n':
 287         ignore_nl++;
 288         break;
 289       case 'e':
 290         ignore_empty++;
 291         break;
 292       case 'l':
 293         shuffle_lines++;
 294         break;
 295       case 'w':
 296         shuffle_words++;
 297         break;
 298       case 'i':
 299         ignore_case++;
 300         break;
 301       default:
 302         usage();
 303       }
 304   if (optind + 2 != argc)
 305     usage();
 306
 307   tok_init(&t1, sopen_read(argv[optind]));
 308   tok_init(&t2, sopen_read(argv[optind+1]));
 309   if (!ignore_nl)
 310     t1.flags = t2.flags = TF_REPORT_LINES;
 311
 312   struct shouffle s1, s2;
 313   slurp(&t1, &s1);
 314   slurp(&t2, &s2);
 315
 316   compare(&s1, &s2);
 317   return 0;
 318 }