From a3cb81d88eb514af15ba6bd5279a1549c0ba5266 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 17 Nov 2007 22:31:07 +0100 Subject: [PATCH] Basic functions for building of judges. --- judge/Makefile | 16 +++++ judge/io.c | 87 ++++++++++++++++++++++++++ judge/judge.h | 98 ++++++++++++++++++++++++++++++ judge/test-io.c | 22 +++++++ judge/test-tok.c | 30 +++++++++ judge/token.c | 155 +++++++++++++++++++++++++++++++++++++++++++++++ judge/utils.c | 37 +++++++++++ 7 files changed, 445 insertions(+) create mode 100644 judge/Makefile create mode 100644 judge/io.c create mode 100644 judge/judge.h create mode 100644 judge/test-io.c create mode 100644 judge/test-tok.c create mode 100644 judge/token.c create mode 100644 judge/utils.c diff --git a/judge/Makefile b/judge/Makefile new file mode 100644 index 0000000..e5fcce7 --- /dev/null +++ b/judge/Makefile @@ -0,0 +1,16 @@ +CC=gcc-4.1.1 +CFLAGS=-O2 -Wall -W -Wno-parentheses -Wstrict-prototypes -Wmissing-prototypes -Wundef -Wredundant-decls -Winline $(DEBUG) -std=gnu99 +CFLAGS+=-Wno-pointer-sign -Wdisabled-optimization -Wno-missing-field-initializers + +all: test-io test-tok + +JLIB=utils.o io.o token.o + +test-io: test-io.o $(JLIB) +test-tok: test-tok.o $(JLIB) + +clean:: + rm -f `find . -name "*~" -or -name "*.[oa]" -or -name "\#*\#" -or -name TAGS -or -name core` + rm -f test-io test-tok + +.PHONY: all clean distclean diff --git a/judge/io.c b/judge/io.c new file mode 100644 index 0000000..68c2992 --- /dev/null +++ b/judge/io.c @@ -0,0 +1,87 @@ +/* + * I/O functions for judges + * + * (c) 2007 Martin Mares + */ + +#include +#include +#include +#include + +#include "judge.h" + +#define BUFSIZE 65536 + +struct stream *sopen_fd(char *name, int fd) +{ + struct stream *s = xmalloc(sizeof(*s) + BUFSIZE + strlen(name) + 1); + s->fd = fd; + s->pos = s->stop = s->buf; + s->end = s->buf + BUFSIZE; + s->name = s->end; + strcpy(s->name, name); + s->flags = 0; + return s; +} + +struct stream *sopen_read(char *name) +{ + int fd = open(name, O_RDONLY); + if (fd < 0) + die("Unable to open %s for reading: %m", name); + return sopen_fd(name, fd); +} + +struct stream *sopen_write(char *name) +{ + int fd = open(name, O_WRONLY | O_CREAT | O_TRUNC, 0666); + if (fd < 0) + die("Unable to open %s for writing: %m", name); + return sopen_fd(name, fd); +} + +void sflush(struct stream *s) +{ + if (s->pos > s->stop) + { + char *p = s->buf; + int len = s->pos - s->buf; + while (len > 0) + { + int c = write(s->fd, p, len); + if (c <= 0) + die("Error writing %s: %m", s->name); + p += c; + len -= c; + } + } + s->pos = s->stop = s->buf; +} + +void sclose(struct stream *s) +{ + sflush(s); + close(s->fd); + free(s); +} + +static int srefill(struct stream *s) +{ + int len = read(s->fd, s->buf, BUFSIZE); + if (len < 0) + die("Error reading %s: %m", s->name); + s->pos = s->buf; + s->stop = s->buf + len; + return len; +} + +int sgetc_slow(struct stream *s) +{ + return (srefill(s) ? *s->pos++ : -1); +} + +int speekc_slow(struct stream *s) +{ + return (srefill(s) ? *s->pos : -1); +} diff --git a/judge/judge.h b/judge/judge.h new file mode 100644 index 0000000..4290b44 --- /dev/null +++ b/judge/judge.h @@ -0,0 +1,98 @@ +/* + * A simple library for MO-Eval judges + * + * (c) 2007 Martin Mares + */ + +#include + +/* GCC extensions */ + +#ifdef __GNUC__ +#define NONRET __attribute__((noreturn)) +#else +#define NONRET +#endif + +/* utils.c: Utility functions */ + +void die(char *msg, ...) NONRET; +void *xmalloc(size_t size); +void *xrealloc(void *p, size_t size); + +/* io.c: Simple buffered I/O streams */ + +struct stream { + char *name; + int fd; + unsigned char *pos, *stop, *end; + unsigned char buf[]; +}; + +struct stream *sopen_read(char *name); +struct stream *sopen_write(char *name); +struct stream *sopen_fd(char *name, int fd); +void sflush(struct stream *s); +void sclose(struct stream *s); + +int sgetc_slow(struct stream *s); +int speekc_slow(struct stream *s); + +static inline int sgetc(struct stream *s) +{ + return (s->pos < s->stop) ? *s->pos++ : sgetc_slow(s); +} + +static inline int speekc(struct stream *s) +{ + return (s->pos < s->stop) ? *s->pos : speekc_slow(s); +} + +static inline void sputc(struct stream *s, int c) +{ + if (s->pos >= s->stop) + sflush(s); + *s->pos++ = c; +} + +static inline void sungetc(struct stream *s) +{ + s->pos--; +} + +/* token.c: Tokenization of input */ + +struct tokenizer { + struct stream *stream; + unsigned int bufsize; // Allocated buffer size + unsigned int maxsize; // Maximal allowed token size + unsigned int flags; // TF_xxx + unsigned char *token; // Current token (in the buffer) + unsigned int toksize; // ... and its size + int line; // ... and line number at its end +}; + +enum tokenizer_flags { + TF_REPORT_LINES = 1, // Report an empty token at the end of each line +}; + +void tok_init(struct tokenizer *t, struct stream *s); +void tok_cleanup(struct tokenizer *t); +void tok_err(struct tokenizer *t, char *msg) NONRET; +char *get_token(struct tokenizer *t); + +// Parsing functions +int to_int(struct tokenizer *t, int *x); +int to_uint(struct tokenizer *t, unsigned int *x); +int to_long(struct tokenizer *t, long int *x); +int to_ulong(struct tokenizer *t, unsigned long int *x); +int to_double(struct tokenizer *t, double *x); +int to_long_double(struct tokenizer *t, long double *x); + +// get_token() + parse or die +int get_int(struct tokenizer *t); +unsigned int get_uint(struct tokenizer *t); +long int get_long(struct tokenizer *t); +unsigned long int get_ulong(struct tokenizer *t); +double get_double(struct tokenizer *t); +long double get_long_double(struct tokenizer *t); diff --git a/judge/test-io.c b/judge/test-io.c new file mode 100644 index 0000000..3bff888 --- /dev/null +++ b/judge/test-io.c @@ -0,0 +1,22 @@ +#include + +#include "judge.h" + +int main(void) +{ +#if 0 + struct stream *i = sopen_read("/etc/profile"); + struct stream *o = sopen_write("/dev/stdout"); +#else + struct stream *i = sopen_fd("stdin", 0); + struct stream *o = sopen_fd("stdout", 1); +#endif + + int c; + while ((c = sgetc(i)) >= 0) + sputc(o, c); + + sclose(i); + sclose(o); + return 0; +} diff --git a/judge/test-tok.c b/judge/test-tok.c new file mode 100644 index 0000000..10e7b3b --- /dev/null +++ b/judge/test-tok.c @@ -0,0 +1,30 @@ +#include + +#include "judge.h" + +int main(void) +{ + struct stream *i = sopen_fd("stdin", 0); + + struct tokenizer t; + tok_init(&t, i); + t.flags = TF_REPORT_LINES; + char *tok; + while (tok = get_token(&t)) + { + printf("<%s>", tok); +#define T(f, type, fmt) { type x; if (to_##f(&t, &x)) printf(" = " #f " " fmt, x); } + T(int, int, "%d"); + T(uint, unsigned int, "%u"); + T(long, long int, "%ld"); + T(ulong, unsigned long int, "%lu"); + T(double, double, "%f"); + T(long_double, long double, "%Lf"); +#undef T + putchar('\n'); + } + tok_cleanup(&t); + + sclose(i); + return 0; +} diff --git a/judge/token.c b/judge/token.c new file mode 100644 index 0000000..2f43ddc --- /dev/null +++ b/judge/token.c @@ -0,0 +1,155 @@ +/* + * Tokenizer for judges + * + * (c) 2007 Martin Mares + */ + +#include +#include +#include +#include + +#include "judge.h" + +#define DEFAULT_MAX_TOKEN (32 << 20) + +void tok_init(struct tokenizer *t, struct stream *s) +{ + memset(t, 0, sizeof(*t)); + t->stream = s; + t->bufsize = 256; + t->token = xmalloc(t->bufsize); + t->maxsize = DEFAULT_MAX_TOKEN; + t->line = 1; +} + +void tok_cleanup(struct tokenizer *t) +{ + free(t->token); +} + +void tok_err(struct tokenizer *t, char *msg) +{ + die("%s:%d: %s", t->stream->name, t->line, msg); +} + +static inline int is_white(int c) +{ + return (c == ' ' || c == '\t' || c == '\r' || c == '\n'); +} + +char *get_token(struct tokenizer *t) +{ + unsigned int len = 0; + int c; + + // Skip whitespace + do + { + c = sgetc(t->stream); + if (c < 0) + return NULL; + if (c == '\n') + { + t->line++; + if (t->flags & TF_REPORT_LINES) + { + t->toksize = 0; + t->token[0] = 0; + return t->token; + } + } + } + while (is_white(c)); + + // This is the token itself + do + { + t->token[len++] = c; + if (len >= t->bufsize) + { + if (len >= t->maxsize) + tok_err(t, "Token too long"); + t->bufsize *= 2; + if (t->bufsize > t->maxsize) + t->bufsize = t->maxsize; + t->token = xrealloc(t->token, t->bufsize); + } + c = sgetc(t->stream); + } + while (c >= 0 && !is_white(c)); + if (c >= 0) + sungetc(t->stream); + + t->token[len] = 0; + t->toksize = len; + return t->token; +} + +/* + * Parsing functions. They return 1 if successfully parsed, 0 otherwise. + */ + +#define PARSE(f, ...) \ + char *end; \ + errno = 0; \ + *x = f(t->token, &end, ##__VA_ARGS__); \ + return !(errno || (unsigned char *) end != t->token + t->toksize) + +int to_long(struct tokenizer *t, long int *x) +{ + PARSE(strtol, 10); +} + +int to_ulong(struct tokenizer *t, unsigned long int *x) +{ + if (t->token[0] == '-') // strtoul accepts negative numbers, but we don't + return 0; + PARSE(strtoul, 10); +} + +int to_double(struct tokenizer *t, double *x) +{ + PARSE(strtod); +} + +int to_long_double(struct tokenizer *t, long double *x) +{ + PARSE(strtold); +} + +int to_int(struct tokenizer *t, int *x) +{ + long int y; + if (!to_long(t, &y) || y > LONG_MAX || y < LONG_MIN) + return 0; + *x = y; + return 1; +} + +int to_uint(struct tokenizer *t, unsigned int *x) +{ + unsigned long int y; + if (!to_ulong(t, &y) || y > ULONG_MAX) + return 0; + *x = y; + return 1; +} + +#define GET(fn, type) \ + type get_##fn(struct tokenizer *t) \ + { \ + type x; \ + if (!get_token(t)) \ + tok_err(t, "Unexpected end of file"); \ + if (!to_##fn(t, &x)) \ + tok_err(t, "Expected " #fn); \ + return x; \ + } + +GET(int, int) +GET(uint, unsigned int) +GET(long, long int) +GET(ulong, unsigned long int) +GET(double, double) +GET(long_double, long double) diff --git a/judge/utils.c b/judge/utils.c new file mode 100644 index 0000000..cbe5c3c --- /dev/null +++ b/judge/utils.c @@ -0,0 +1,37 @@ +/* + * Utility functions for judges + * + * (c) 2007 Martin Mares + */ + +#include +#include +#include + +#include "judge.h" + +void die(char *msg, ...) +{ + va_list args; + va_start(args, msg); + vfprintf(stderr, msg, args); + fputc('\n', stderr); + va_end(args); + exit(1); +} + +void *xmalloc(size_t size) +{ + void *p = malloc(size); + if (!p) + die("Out of memory (unable to allocate %z bytes)", size); + return p; +} + +void *xrealloc(void *p, size_t size) +{ + p = realloc(p, size); + if (!p) + die("Out of memory (unable to allocate %z bytes)", size); + return p; +} -- 2.39.2