From 6e4032210ea6c167fcf14c70ae6b18661c011310 Mon Sep 17 00:00:00 2001 Message-Id: <6e4032210ea6c167fcf14c70ae6b18661c011310.1714004338.git.mdw@distorted.org.uk> From: Mark Wooding Date: Sun, 4 Feb 2001 17:14:42 +0000 Subject: [PATCH] Initial checkin Organization: Straylight/Edgeware From: mdw --- .cvsignore | 6 + .links | 4 + .skelrc | 9 ++ Makefile.am | 39 +++++ acconfig.h | 62 ++++++++ anag.c | 442 +++++++++++++++++++++++++++++++++++++++++++++++++++ anag.h | 203 +++++++++++++++++++++++ anagram.c | 115 ++++++++++++++ configure.in | 46 ++++++ setup | 9 ++ trackword.c | 240 ++++++++++++++++++++++++++++ util.c | 295 ++++++++++++++++++++++++++++++++++ wildcard.c | 162 +++++++++++++++++++ 13 files changed, 1632 insertions(+) create mode 100644 .cvsignore create mode 100644 .links create mode 100644 .skelrc create mode 100644 Makefile.am create mode 100644 acconfig.h create mode 100644 anag.c create mode 100644 anag.h create mode 100644 anagram.c create mode 100644 configure.in create mode 100755 setup create mode 100644 trackword.c create mode 100644 util.c create mode 100644 wildcard.c diff --git a/.cvsignore b/.cvsignore new file mode 100644 index 0000000..f1487c7 --- /dev/null +++ b/.cvsignore @@ -0,0 +1,6 @@ +Makefile.in +configure +aclocal.m4 +build +stamp-h.in +config.h.in diff --git a/.links b/.links new file mode 100644 index 0000000..b3f8cad --- /dev/null +++ b/.links @@ -0,0 +1,4 @@ +COPYING +install-sh +mkinstalldirs +missing diff --git a/.skelrc b/.skelrc new file mode 100644 index 0000000..2cc57bb --- /dev/null +++ b/.skelrc @@ -0,0 +1,9 @@ +;;; -*-emacs-lisp-*- + +(setq skel-alist + (append + '((author . "Mark Wooding") + (full-title . "Anag: a simple wordgame helper") + (program . "Anag")) + skel-alist)) + diff --git a/Makefile.am b/Makefile.am new file mode 100644 index 0000000..620b1cc --- /dev/null +++ b/Makefile.am @@ -0,0 +1,39 @@ +## -*-makefile-*- +## +## $Id: Makefile.am,v 1.1 2001/02/04 17:14:42 mdw Exp $ +## +## Makefile for Anag +## +## (c) 2001 Mark Wooding +## + +##----- Licensing notice ---------------------------------------------------- +## +## This file is part of Anag: a simple wordgame helper. +## +## Anag is free software; you can redistribute it and/or modify +## it under the terms of the GNU General Public License as published by +## the Free Software Foundation; either version 2 of the License, or +## (at your option) any later version. +## +## Anag is distributed in the hope that it will be useful, +## but WITHOUT ANY WARRANTY; without even the implied warranty of +## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +## GNU General Public License for more details. +## +## You should have received a copy of the GNU General Public License +## along with Anag; if not, write to the Free Software Foundation, +## Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + +##----- Revision history ---------------------------------------------------- +## +## $Log: Makefile.am,v $ +## Revision 1.1 2001/02/04 17:14:42 mdw +## Initial checkin +## + +AUTOMAKE_OPTIONS = foreign +bin_PROGRAMS = anag +anag_SOURCES = anag.c anag.h wildcard.c anagram.c trackword.c util.c + +##----- That's all, folks --------------------------------------------------- diff --git a/acconfig.h b/acconfig.h new file mode 100644 index 0000000..86765be --- /dev/null +++ b/acconfig.h @@ -0,0 +1,62 @@ +/* -*-c-*- + * + * $Id: acconfig.h,v 1.1 2001/02/04 17:14:42 mdw Exp $ + * + * Configuration header for Anag + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Anag: a simple wordgame helper. + * + * Anag is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * Anag is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Anag; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: acconfig.h,v $ + * Revision 1.1 2001/02/04 17:14:42 mdw + * Initial checkin + * + */ + +#ifndef ACCONFIG_H +#define ACCONFIG_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Autoconfiguration data --------------------------------------------*/ +@TOP@ + +/* Package and version number. */ +#define PACKAGE "anag" +#define VERSION "1.0.0" + +/* Define this to be your default wordlist location. */ +#define DICTIONARY "/usr/dict/words" + +@BOTTOM@ + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/anag.c b/anag.c new file mode 100644 index 0000000..97b31c1 --- /dev/null +++ b/anag.c @@ -0,0 +1,442 @@ +/* -*-c-*- + * + * $Id: anag.c,v 1.1 2001/02/04 17:14:42 mdw Exp $ + * + * Main driver for anag + * + * (c) 2001 Mark Wooding + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Anag: a simple wordgame helper. + * + * Anag is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * Anag is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Anag; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: anag.c,v $ + * Revision 1.1 2001/02/04 17:14:42 mdw + * Initial checkin + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "anag.h" + +/*----- Static variables --------------------------------------------------*/ + +static const char *file = DICTIONARY; + +/*----- Help text functions -----------------------------------------------*/ + +static void usage(FILE *fp) +{ + pquis(fp, "Usage: $ [-f file] expression\n"); +} + +static void version(FILE *fp) +{ + pquis(fp, "$, version " VERSION "\n"); +} + +static void help(FILE *fp) +{ + version(fp); + fputc('\n', fp); + usage(fp); + fputs("\n\ +Searches a wordlist, printing all of the words which match an expression.\n\ +The basic tests in the expression are:\n\ +\n\ +-anagram WORD matches a full-length anagram\n\ +-subgram WORD matches words which only use letters in WORD\n\ +-wildcard PATTERN matches with wildcards `*' and `?'\n\ +-trackword WORD matches words which can be found in a trackword\n\ +\n\ +These simple tests can be combined using the operators `-a', `-o' and `-n'\n\ +(for `and', `or' and `not'; they may also be written `&', `|' and `!' if\n\ +you like), and grouped using parentheses `(' and `)'.\n\ +", fp); +} + +/*----- The options parser ------------------------------------------------*/ + +/* --- Options table structure --- */ + +struct opt { + const char *name; + unsigned nargs; + unsigned f; + unsigned tag; +}; + +enum { + O_HELP, O_VERSION, O_USAGE, + O_FILE, + O_AND, O_OR, O_NOT, O_LPAREN, O_RPAREN, + O_ANAG, O_SUBG, O_WILD, O_TRACK, + O_EOF +}; + +#define OF_SHORT 1u + +static const struct opt opttab[] = { + + /* --- Options -- don't form part of the language --- */ + + { "help", 0, OF_SHORT, O_HELP }, + { "version", 0, OF_SHORT, O_VERSION }, + { "usage", 0, OF_SHORT, O_USAGE }, + { "file", 1, OF_SHORT, O_FILE }, + + /* --- Operators -- provide the basic structure of the language --- * + * + * These are also given magical names by the parser. + */ + + { "and", 0, OF_SHORT, O_AND }, + { "or", 0, OF_SHORT, O_OR }, + { "not", 0, OF_SHORT, O_NOT }, + + /* --- Actual matching oeprations -- do something useful --- */ + + { "anagram", 1, 0, O_ANAG }, + { "subgram", 1, 0, O_SUBG }, + { "wildcard", 1, 0, O_WILD }, + { "trackword", 1, 0, O_TRACK }, + + /* --- End marker --- */ + + { 0, 0, 0, 0 } +}; + +static int ac; +static const char *const *av; +static int ai; + +/* --- @nextopt@ --- * + * + * Arguments: @const char ***arg@ = where to store the arg pointer + * + * Returns: The tag of the next option. + * + * Use: Scans the next option off the command line. If the option + * doesn't form part of the language, it's processed internally, + * and you'll never see it from here. On exit, the @arg@ + * pointer is set to contain the address of the option scanned, + * followed by its arguments if any. You're expected to know + * how many arguments there are for your option. + */ + +static unsigned nextopt(const char *const **arg) +{ + for (;;) { + const struct opt *o, *oo; + size_t sz; + const char *p; + + /* --- Pick the next option off the front --- */ + + *arg = av + ai; + if (ai >= ac) + return (O_EOF); + p = av[ai++]; + + /* --- Cope with various forms of magic --- */ + + if (p[0] != '-') { + if (!p[1]) switch (*p) { + case '&': return (O_AND); + case '|': return (O_OR); + case '!': return (O_NOT); + case '(': return (O_LPAREN); + case ')': return (O_RPAREN); + } + goto bad; + } + + /* --- Now cope with other sorts of weirdies --- * + * + * By the end of this, a leading `-' or `--' will have been stripped. + */ + + p++; + if (!*p) + goto bad; + if (*p == '-') + p++; + if (!*p) { + if (ai < ac) + die("syntax error near `--': rubbish at end of line"); + return (O_EOF); + } + + /* --- Now look the word up in my table --- */ + + sz = strlen(p); + oo = 0; + for (o = opttab; o->name; o++) { + if (strncmp(p, o->name, sz) == 0) { + if (strlen(o->name) == sz || ((o->f & OF_SHORT) && sz == 1)) { + oo = o; + break; + } + if (oo) { + die("ambiguous option name `-%s' (could match `-%s' or `-%s')", + p, oo->name, o->name); + } + oo = o; + } + } + if (!oo) + die("unrecognized option name `-%s'", p); + + /* --- Sort out the arguments --- */ + + if (ai + oo->nargs > ac) + die("too few arguments for `-%s' (need %u)", oo->name, oo->nargs); + ai += oo->nargs; + + /* --- Now process the option --- */ + + switch (oo->tag) { + case O_HELP: + help(stdout); + exit(0); + case O_VERSION: + version(stdout); + exit(0); + case O_USAGE: + usage(stdout); + exit(0); + case O_FILE: + file = (*arg)[1]; + break; + default: + return (oo->tag); + } + bad: + die("syntax error near `%s': unknown token type", av[ai - 1]); + } +} + +/*----- Node types for operators ------------------------------------------*/ + +/* --- Node structures --- */ + +typedef struct node_bin { + node n; + node *left; + node *right; +} node_bin; + +typedef struct node_un { + node n; + node *arg; +} node_un; + +/* --- Node functions --- */ + +static int n_or(node *nn, const char *p, size_t sz) +{ + node_bin *n = (node_bin *)nn; + return (n->left->func(n->left, p, sz) || n->right->func(n->right, p, sz)); +} + +static int n_and(node *nn, const char *p, size_t sz) +{ + node_bin *n = (node_bin *)nn; + return (n->left->func(n->left, p, sz) && n->right->func(n->right, p, sz)); +} + +static int n_not(node *nn, const char *p, size_t sz) +{ + node_un *n = (node_un *)nn; + return (!n->arg->func(n->arg, p, sz)); +} + +/*----- Parser for the expression syntax ----------------------------------*/ + +/* --- A parser context --- */ + +typedef struct p_ctx { + unsigned t; + const char *const *a; +} p_ctx; + +/* --- Parser structure --- * + * + * This is a simple recursive descent parser. The context retains + * information about the current token. Each function is passed the address + * of a node pointer to fill in. This simplifies the binary operator code + * somewhat, relative to returning pointers to node trees. + */ + +static void p_expr(p_ctx *p, node **/*nn*/); + +static void p_next(p_ctx *p) +{ + static const char *const eof[] = { "", 0 }; + p->t = nextopt(&p->a); + if (p->t == O_EOF) + p->a = eof; +} + +static void p_factor(p_ctx *p, node **nn) +{ + node_un *n; + if (p->t == O_LPAREN) { + p_next(p); + p_expr(p, nn); + if (p->t != O_RPAREN) + die("syntax error near `%s': missing `('", *p->a); + p_next(p); + } else if (p->t == O_NOT) { + n = xmalloc(sizeof(node_un)); + n->n.func = n_not; + *nn = &n->n; + p_next(p); + p_factor(p, &n->arg); + } else { + switch (p->t) { + case O_ANAG: *nn = anagram(p->a + 1); break; + case O_SUBG: *nn = subgram(p->a + 1); break; + case O_WILD: *nn = wildcard(p->a + 1); break; + case O_TRACK: *nn = trackword(p->a + 1); break; + default: die("syntax error near `%s': unexpected token", *p->a); + } + p_next(p); + } +} + +static void p_term(p_ctx *p, node **nn) +{ + node_bin *n; + for (;;) { + p_factor(p, nn); + switch (p->t) { + case O_AND: + p_next(p); + default: + break; + case O_LPAREN: + case O_RPAREN: + case O_OR: + case O_EOF: + return; + } + n = xmalloc(sizeof(node_bin)); + n->left = *nn; + n->n.func = n_and; + *nn = &n->n; + nn = &n->right; + } +} + +static void p_expr(p_ctx *p, node **nn) +{ + node_bin *n; + for (;;) { + p_term(p, nn); + if (p->t != O_OR) + break; + p_next(p); + n = xmalloc(sizeof(node_bin)); + n->left = *nn; + n->n.func = n_or; + *nn = &n->n; + nn = &n->right; + } +} + +/* --- @p_argv@ --- * + * + * Arguments: @int argc@ = number of command-line arguments + * @const char *const argv[]@ = vectoor of arguments + * + * Returns: A compiled node, parsed from the arguments. + * + * Use: Does the donkey-work of parsing a command-line. + */ + +static node *p_argv(int argc, const char *const argv[]) +{ + p_ctx p; + node *n; + + av = argv; + ac = argc; + ai = 1; + p_next(&p); + p_expr(&p, &n); + if (p.t != O_EOF) { + die("syntax error near `%s': rubbish at end of line (too many `)'s?)", + *p.a); + } + return (n); +} + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @main@ --- * + * + * Arguments: @int argc@ = number of command-line arguments + * @char *argv[]@ = vector of argument words + * + * Returns: Zero on success, nonzero on failure. + * + * Use: Picks entries from a word list which match particular + * expressions. This might be of assistance to word-game types. + */ + +int main(int argc, char *argv[]) +{ + node *n; + FILE *fp; + dstr d = DSTR_INIT; + char *p, *q, *l; + + ego(argv[0]); + n = p_argv(argc, (const char *const *)argv); + + if ((fp = fopen(file, "r")) == 0) + die("error opening `%s': %s", file, strerror(errno)); + for (;;) { + dstr_reset(&d); + if (dstr_putline(&d, fp) < 0) + break; + l = d.buf + d.len; + for (p = q = d.buf; p < l; p++) { + if (!isalnum((unsigned char)*p)) + continue; + *q++ = tolower((unsigned char)*p); + } + *q = 0; + d.len = q - d.buf; + if (n->func(n, d.buf, d.len)) { + fwrite(d.buf, 1, d.len, stdout); + fputc('\n', stdout); + } + } + if (!feof(fp)) + die("error reading `%s': %s", file, strerror(errno)); + fclose(fp); + return (0); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/anag.h b/anag.h new file mode 100644 index 0000000..5f2b8e3 --- /dev/null +++ b/anag.h @@ -0,0 +1,203 @@ +/* -*-c-*- + * + * $Id: anag.h,v 1.1 2001/02/04 17:14:42 mdw Exp $ + * + * External definitions for Anag + * + * (c) 2001 Mark Wooding + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Anag: a simple wordgame helper. + * + * Anag is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * Anag is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Anag; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: anag.h,v $ + * Revision 1.1 2001/02/04 17:14:42 mdw + * Initial checkin + * + */ + +#ifndef ANAG_H +#define ANAG_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include "config.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct node { + int (*func)(struct node */*n*/, const char */*p*/, size_t /*sz*/); +} node; + +typedef struct dstr { + char *buf; + size_t len; + size_t sz; +} dstr; + +#define DSTR_INIT { 0, 0, 0 } + +/*----- Node types --------------------------------------------------------*/ + +extern node *anagram(const char *const */*av*/); +extern node *subgram(const char *const */*av*/); +extern node *wildcard(const char *const */*av*/); +extern node *trackword(const char *const */*av*/); + +/*----- Error reporting ---------------------------------------------------*/ + +/* --- @ego@ --- * + * + * Arguments: @const char *p@ = pointer to program name + * + * Returns: --- + * + * Use: Stores what the program's name is. + */ + +extern void ego(const char */*p*/); + +/* --- @pquis@ --- * + * + * Arguments: @FILE *fp@ = output stream to write on + * @const char *p@ = pointer to string to write + * + * Returns: Zero if everything worked, EOF if not. + * + * Use: Writes the string @p@ to the output stream @fp@. Occurrences + * of the character `$' in @p@ are replaced by the program name + * as reported by @quis@. A `$$' is replaced by a single `$' + * sign. + */ + +extern int pquis(FILE */*fp*/, const char */*p*/); + +/* --- @die@ --- * + * + * Arguments: @const char *f@ = a @printf@-style format string + * @...@ = other arguments + * + * Returns: Never. + * + * Use: Reports an error and exits. + */ + +extern void die(const char */*f*/, ...); + +/*----- Memory allocation -------------------------------------------------*/ + +/* --- @xmalloc@ --- * + * + * Arguments: @size_t sz@ = size of block to allocate + * + * Returns: Pointer to allocated block. + * + * Use: Allocates memory. If there's not enough memory, the + * program exits. + */ + +extern void *xmalloc(size_t /*sz*/); + +/* --- @xrealloc@ --- * + * + * Arguments: @void *p@ = a pointer to allocated memory + * @size_t sz@ = new size of block wanted + * + * Returns: Pointer to resized block. + * + * Use: Resizes an allocated block. If there's not enough memory, + * the program exits. + */ + +extern void *xrealloc(void */*p*/, size_t /*sz*/); + +/*----- Dynamic string handling -------------------------------------------*/ + +/* --- @dstr_destroy@ --- * + * + * Arguments: @dstr *d@ = pointer to a dynamic string block + * + * Returns: --- + * + * Use: Reclaims the space used by a dynamic string. + */ + +extern void dstr_destroy(dstr */*d*/); + +/* --- @dstr_reset@ --- * + * + * Arguments: @dstr *d@ = pointer to a dynamic string block + * + * Returns: --- + * + * Use: Resets a string so that new data gets put at the beginning. + */ + +extern void dstr_reset(dstr */*d*/); + +/* --- @dstr_ensure@ --- * + * + * Arguments: @dstr *d@ = pointer to a dynamic string block + * @size_t sz@ = amount of free space to ensure + * + * Returns: --- + * + * Use: Ensures that at least @sz@ bytes are available in the + * given string. + */ + +extern void dstr_ensure(dstr */*d*/, size_t /*sz*/); + +/* --- @dstr_putline@ --- * + * + * Arguments: @dstr *d@ = pointer to a dynamic string block + * @FILE *fp@ = a stream to read from + * + * Returns: The number of characters read into the buffer, or @EOF@ if + * end-of-file was reached before any characters were read. + * + * Use: Appends the next line from the given input stream to the + * string. A trailing newline is not added; a trailing null + * byte is appended, as for @dstr_putz@. + */ + +extern int dstr_putline(dstr */*d*/, FILE */*fp*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/anagram.c b/anagram.c new file mode 100644 index 0000000..5fc9c80 --- /dev/null +++ b/anagram.c @@ -0,0 +1,115 @@ +/* -*-c-*- + * + * $Id: anagram.c,v 1.1 2001/02/04 17:14:42 mdw Exp $ + * + * Matches anagrams and subgrams + * + * (c) 2001 Mark Wooding + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Anag: a simple wordgame helper. + * + * Anag is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * Anag is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Anag; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: anagram.c,v $ + * Revision 1.1 2001/02/04 17:14:42 mdw + * Initial checkin + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "anag.h" + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct node_gram { + node n; + size_t sz; + unsigned f[UCHAR_MAX + 1]; +} node_gram; + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @compile@ --- * + * + * Arguments: @node_gram *n@ = pointer to node to fill in + * @const char *p@ = pointer to string to compile from + * + * Returns: The length of the string. + * + * Use: Fills in an anagram node with letter frequencies. + */ + +static size_t compile(node_gram *n, const char *p) +{ + size_t len = 0; + unsigned i; + memset(n->f, 0, sizeof(n->f)); + while (*p) { + i = (unsigned char)*p++; + n->f[i]++; + len++; + } + return (len); +} + +/* --- Node matcher --- */ + +static int n_gram(node *nn, const char *p, size_t sz) +{ + node_gram *n = (node_gram *)nn; + unsigned f[UCHAR_MAX]; + const char *q; + unsigned i; + + if (n->sz && sz != n->sz) + return (0); + memcpy(f, n->f, sizeof(f)); + q = p + sz; + while (p < q) { + i = (unsigned char)*p++; + if (!f[i]) + return (0); + f[i]--; + } + return (1); +} + +/* --- Node creation --- */ + +node *anagram(const char *const *av) +{ + node_gram *n = xmalloc(sizeof(*n)); + n->n.func = n_gram; + n->sz = compile(n, av[0]); + return (&n->n); +} + +node *subgram(const char *const *av) +{ + node_gram *n = xmalloc(sizeof(*n)); + n->n.func = n_gram; + n->sz = 0; + compile(n, av[0]); + return (&n->n); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/configure.in b/configure.in new file mode 100644 index 0000000..bbe801f --- /dev/null +++ b/configure.in @@ -0,0 +1,46 @@ +dnl -*-fundamental-*- +dnl +dnl $Id: configure.in,v 1.1 2001/02/04 17:14:42 mdw Exp $ +dnl +dnl Configuration script +dnl +dnl (c) 2001 Mark Wooding +dnl + +dnl ----- Licensing notice -------------------------------------------------- +dnl +dnl This file is part of Anag: a simple wordgame helper. +dnl +dnl Anag is free software; you can redistribute it and/or modify +dnl it under the terms of the GNU General Public License as published by +dnl the Free Software Foundation; either version 2 of the License, or +dnl (at your option) any later version. +dnl +dnl Anag is distributed in the hope that it will be useful, +dnl but WITHOUT ANY WARRANTY; without even the implied warranty of +dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +dnl GNU General Public License for more details. +dnl +dnl You should have received a copy of the GNU General Public License +dnl along with Anag; if not, write to the Free Software Foundation, +dnl Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + +dnl ----- Revision history -------------------------------------------------- +dnl +dnl $Log: configure.in,v $ +dnl Revision 1.1 2001/02/04 17:14:42 mdw +dnl Initial checkin +dnl + +AC_INIT(anag.c) +AM_INIT_AUTOMAKE(anag, 1.0.0) +AM_CONFIG_HEADER(config.h) +AC_PROG_CC +mdw_GCC_FLAGS +AC_ARG_WITH(dictionary, +[ --with-dictionary=DICT set default word list to be DICT], +[AC_DEFINE_UNQUOTED(DICTIONARY, "$withval")], +[AC_DEFINE(DICTIONARY, "/usr/dict/words")]) +AC_OUTPUT(Makefile) + +dnl ----- That's all, folks ------------------------------------------------- diff --git a/setup b/setup new file mode 100755 index 0000000..5173638 --- /dev/null +++ b/setup @@ -0,0 +1,9 @@ +#! /bin/sh + +set -e +mklinks +mkaclocal +autoheader +autoconf +automake +mkdir build diff --git a/trackword.c b/trackword.c new file mode 100644 index 0000000..1dae3d1 --- /dev/null +++ b/trackword.c @@ -0,0 +1,240 @@ +/* -*-c-*- + * + * $Id: trackword.c,v 1.1 2001/02/04 17:14:42 mdw Exp $ + * + * Matches trackwords + * + * (c) 2001 Mark Wooding + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Anag: a simple wordgame helper. + * + * Anag is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * Anag is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Anag; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: trackword.c,v $ + * Revision 1.1 2001/02/04 17:14:42 mdw + * Initial checkin + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "anag.h" + +/*----- Data structures ---------------------------------------------------*/ + +enum { N, NE, E, SE, S, SW, W, NW, NDIR }; + +typedef struct tcell { + struct tcell *hop[NDIR]; + char ch; + unsigned char f; +} tcell; + +typedef struct node_track { + node n; + unsigned x; + unsigned y; + tcell *c; +} node_track; + +/*----- Utility functions -------------------------------------------------*/ + +/* --- @isqrt@ --- * + * + * Arguments: @long a@ = the target value + * + * Returns: %$\lfloor \sqrt{a} \rfloor$% + * + * Use: Computes an integer square root. This algorithm is + * Newton-Raphson with integers. I've stolen this more-or-less + * wholesale fom the multiprecision integer square-root function + * in Catacomb. + */ + +long isqrt(long a) +{ + long i, q; + + /* --- Initial guess is half the input length --- */ + + for (i = q = a; q; q >>= 2) + i >>= 1; + + /* --- Do the main series iteration --- */ + + for (;;) { + q = i * i - a; + if (!q || (q < 0 && -q <= 2 * i)) + return (i); + q /= 2 * i; + if (!q) + i--; + else + i -= q; + } +} + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @track@ --- * + * + * Arguments: @tcell *c@ = pointer to start cell + * @const char *p@ = string to match + * + * Returns: Nonzero for a match, zero if no match was found. + * + * Use: Searches for a match in a trackword. + */ + +static int track(tcell *c, const char *p) +{ + int i; + + if (*p++ != c->ch) + return (0); + if (!*p) + return (1); + c->f = 1; + for (i = 0; i < NDIR; i++) { + if (!c->hop[i] || c->hop[i]->f) + continue; + if (track(c->hop[i], p)) { + c->f = 0; + return (1); + } + } + c->f = 0; + return (0); +} + +/* --- Node matcher --- */ + +static int n_track(node *nn, const char *p, size_t sz) +{ + node_track *n = (node_track *)nn; + tcell *c; + + if (!*p) + return (1); + for (c = n->c; c->ch; c++) { + if (track(c, p)) + return (1); + } + return (0); +} + +/* --- Node creation --- */ + +node *trackword(const char *const *av) +{ + node_track *n; + unsigned x, y; + unsigned i, j; + const char *p = av[0], *q, *l; + size_t sz = strlen(p); + tcell *c; + + /* --- Work out the dimensions --- */ + + x = strcspn(p, "/"); + if (!p[x]) { + x = isqrt(sz); + if (x * x != sz) + die("bad trackword `%s': not square, and no line markers", p); + y = x; + } + + if (!x) + die("bad trackword `%s': no columns", p); + + y = 0; + l = p + sz; + q = p; + for (;;) { + if (*q == '/') + q++; + if (!*q) + break; + if (l - q < x) + die("bad trackword `%s': inconsistent line lengths", p); + q += x; + y++; + } + + if (!y) + die("bad trackword `%s': no rows", p); + + /* --- Build the match node --- */ + + n = xmalloc(sizeof(*n)); + n->n.func = n_track; + n->x = x; n->y = y; + n->c = xmalloc((x * y + 1) * sizeof(tcell)); + + q = p; + c = n->c; + for (j = 0; j < y; j++) { + if (*q == '/') + q++; + for (i = 0; i < x; i++) { + c->ch = *q++; + c->f = 0; + +#define NOK (j > 0) +#define SOK (j < y - 1) +#define WOK (i > 0) +#define EOK (i < x - 1) + + c->hop[N] = NOK ? c - x : 0; + c->hop[S] = SOK ? c + x : 0; + c->hop[W] = WOK ? c - 1 : 0; + c->hop[E] = EOK ? c + 1 : 0; + + c->hop[NW] = NOK && WOK ? c - x - 1 : 0; + c->hop[NE] = NOK && EOK ? c - x + 1 : 0; + c->hop[SW] = SOK && WOK ? c + x - 1 : 0; + c->hop[SE] = SOK && EOK ? c + x + 1 : 0; + +#undef NOK +#undef SOK +#undef WOK +#undef EOK + + c++; + } + } + c->ch = 0; + + /* --- Done --- */ + + c = n->c; + for (j = 0; j < y; j++) { + for (i = 0; i < x; i++) { + printf("%c ", c->ch); + c++; + } + fputc('\n', stdout); + } + + return (&n->n); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/util.c b/util.c new file mode 100644 index 0000000..13171e3 --- /dev/null +++ b/util.c @@ -0,0 +1,295 @@ +/* -*-c-*- + * + * $Id: util.c,v 1.1 2001/02/04 17:14:42 mdw Exp $ + * + * Various useful utilities, stolen from mLib + * + * (c) 2001 Mark Wooding + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Anag: a simple wordgame helper. + * + * Anag is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * Anag is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Anag; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: util.c,v $ + * Revision 1.1 2001/02/04 17:14:42 mdw + * Initial checkin + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "anag.h" + +/*----- Static variables --------------------------------------------------*/ + +static const char *quis = ""; + +/*----- Error reporting ---------------------------------------------------*/ + +/* --- @ego@ --- * + * + * Arguments: @const char *p@ = pointer to program name + * + * Returns: --- + * + * Use: Stores what the program's name is. + */ + +#ifndef PATHSEP +# if defined(__riscos) +# define PATHSEP '.' +# elif defined(__unix) || defined(unix) +# define PATHSEP '/' +# else +# define PATHSEP '\\' +# endif +#endif + +void ego(const char *p) +{ + const char *q = p; + while (*q) { + if (*q++ == PATHSEP) + p = q; + } + if (*p == '-') + p++; + quis = p; +} + +#undef PATHSEP + +/* --- @pquis@ --- * + * + * Arguments: @FILE *fp@ = output stream to write on + * @const char *p@ = pointer to string to write + * + * Returns: Zero if everything worked, EOF if not. + * + * Use: Writes the string @p@ to the output stream @fp@. Occurrences + * of the character `$' in @p@ are replaced by the program name + * as reported by @quis@. A `$$' is replaced by a single `$' + * sign. + */ + +int pquis(FILE *fp, const char *p) +{ + size_t sz; + + while (*p) { + sz = strcspn(p, "$"); + if (sz) { + if (fwrite(p, 1, sz, fp) < sz) + return (EOF); + p += sz; + } + if (*p == '$') { + p++; + if (*p == '$') { + if (fputc('$', fp) == EOF) + return (EOF); + p++; + } else { + if (fputs(quis, fp) == EOF) + return (EOF); + } + } + } + return (0); +} + +/* --- @die@ --- * + * + * Arguments: @const char *f@ = a @printf@-style format string + * @...@ = other arguments + * + * Returns: Never. + * + * Use: Reports an error and exits. + */ + +void die(const char *f, ...) +{ + va_list ap; + va_start(ap, f); + fprintf(stderr, "%s: ", quis); + vfprintf(stderr, f, ap); + va_end(ap); + putc('\n', stderr); + exit(EXIT_FAILURE); +} + +/*----- Memory allocation -------------------------------------------------*/ + +/* --- @xmalloc@ --- * + * + * Arguments: @size_t sz@ = size of block to allocate + * + * Returns: Pointer to allocated block. + * + * Use: Allocates memory. If there's not enough memory, the + * program exits. + */ + +void *xmalloc(size_t sz) +{ + void *p = malloc(sz); + if (!p) + die("not enough memory"); + return (p); +} + +/* --- @xrealloc@ --- * + * + * Arguments: @void *p@ = a pointer to allocated memory + * @size_t sz@ = new size of block wanted + * + * Returns: Pointer to resized block. + * + * Use: Resizes an allocated block. If there's not enough memory, + * the program exits. + */ + +void *xrealloc(void *p, size_t sz) +{ + p = realloc(p, sz); + if (!p) + die("not enough memory"); + return (p); +} + +/*----- Dynamic string handling -------------------------------------------*/ + +#define DSTR_INITSZ 64 + +/* --- @dstr_destroy@ --- * + * + * Arguments: @dstr *d@ = pointer to a dynamic string block + * + * Returns: --- + * + * Use: Reclaims the space used by a dynamic string. + */ + +void dstr_destroy(dstr *d) { free(d->buf); d->len = 0; d->sz = 0; } + +/* --- @dstr_reset@ --- * + * + * Arguments: @dstr *d@ = pointer to a dynamic string block + * + * Returns: --- + * + * Use: Resets a string so that new data gets put at the beginning. + */ + +void dstr_reset(dstr *d) { d->len = 0; } + +/* --- @dstr_ensure@ --- * + * + * Arguments: @dstr *d@ = pointer to a dynamic string block + * @size_t sz@ = amount of free space to ensure + * + * Returns: --- + * + * Use: Ensures that at least @sz@ bytes are available in the + * given string. + */ + +void dstr_ensure(dstr *d, size_t sz) +{ + size_t rq = d->len + sz; + size_t nsz; + + /* --- If we have enough space, just leave it --- */ + + if (rq <= d->sz) + return; + + /* --- Grow the buffer --- */ + + nsz = d->sz; + + if (nsz == 0) + nsz = (DSTR_INITSZ >> 1); + do nsz <<= 1; while (nsz < rq); + + if (d->buf) + d->buf = xrealloc(d->buf, nsz); + else + d->buf = xmalloc(nsz); + d->sz = nsz; +} + +/* --- @dstr_putline@ --- * + * + * Arguments: @dstr *d@ = pointer to a dynamic string block + * @FILE *fp@ = a stream to read from + * + * Returns: The number of characters read into the buffer, or @EOF@ if + * end-of-file was reached before any characters were read. + * + * Use: Appends the next line from the given input stream to the + * string. A trailing newline is not added; a trailing null + * byte is appended, as for @dstr_putz@. + */ + +int dstr_putline(dstr *d, FILE *fp) +{ + size_t left = d->sz - d->len; + size_t off = d->len; + int rd = 0; + int ch; + + for (;;) { + + /* --- Read the next byte --- */ + + ch = getc(fp); + + /* --- End-of-file when no characters read is special --- */ + + if (ch == EOF && !rd) + return (EOF); + + /* --- Make sure there's some buffer space --- */ + + if (!left) { + d->len = off; + dstr_ensure(d, 1); + left = d->sz - off; + } + + /* --- End-of-file or newline ends the loop --- */ + + if (ch == EOF || ch == '\n') { + d->buf[off] = 0; + d->len = off; + return rd; + } + + /* --- Append the character and continue --- */ + + d->buf[off++] = ch; + left--; rd++; + } +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/wildcard.c b/wildcard.c new file mode 100644 index 0000000..d28720a --- /dev/null +++ b/wildcard.c @@ -0,0 +1,162 @@ +/* -*-c-*- + * + * $Id: wildcard.c,v 1.1 2001/02/04 17:14:42 mdw Exp $ + * + * Matches wildcard patterns + * + * (c) 2001 Mark Wooding + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Anag: a simple wordgame helper. + * + * Anag is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * Anag is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Anag; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: wildcard.c,v $ + * Revision 1.1 2001/02/04 17:14:42 mdw + * Initial checkin + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "anag.h" + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct node_wild { + node n; + const char *p; +} node_wild; + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @match@ --- * + * + * Arguments: @const char *p@ = pointer to pattern string + * @const char *s@ = string to compare with + * + * Returns: Nonzero if the pattern matches the string. + * + * Use: Does simple wildcard matching. This is quite nasty and more + * than a little slow. Supports metacharacters `*', `?' and + * '['. + */ + +static int match(const char *p, const char *s) +{ + for (;;) { + char pch = *p++, pche, sch; + int sense; + + switch (pch) { + case '?': + if (!*s) + return (0); + s++; + break; + case '*': + if (!*p) + return (1); + while (*s) { + if (match(p, s)) + return (1); + s++; + } + return (0); + case '[': + if (!*s) + return (0); + sch = *s++; + pch = *p++; + sense = 1; + if (pch == '^' || pch == '!') { + sense = !sense; + pch = *p++; + } + if (pch == ']') { + if (*p == '-' && p[1] && p[1] != ']') { + pche = p[1]; + p += 2; + if (pch <= sch && sch <= pche) + goto class_match; + } else if (pch == sch) + goto class_match; + pch = *p++; + } + for (;; pch = *p++) { + if (!pch || pch == ']') + goto class_nomatch; + if (*p == '-' && p[1] && p[1] != ']') { + pche = p[1]; + p += 2; + if (pch <= sch && sch <= pche) + goto class_match; + } else if (pch == sch) + goto class_match; + } + class_match: + if (!sense) + return (0); + for (;;) { + pch = *p++; + if (!pch) + return (0); + if (pch == ']') + break; + if (*p == '-' && p[1] && p[1] != ']') + p += 2; + } + break; + class_nomatch: + if (sense) + return (0); + break; + case '\\': + pch = *p++; + default: + if (pch != *s) + return (0); + if (!pch) + return (1); + s++; + break; + } + } +} + +/* --- Node matcher --- */ + +static int n_wild(node *nn, const char *p, size_t sz) +{ + node_wild *n = (node_wild *)nn; + return (match(n->p, p)); +} + +/* --- Node creation --- */ + +node *wildcard(const char *const *av) +{ + node_wild *n = xmalloc(sizeof(*n)); + n->n.func = n_wild; + n->p = av[0]; + return (&n->n); +} + +/*----- That's all, folks -------------------------------------------------*/ -- [mdw]