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