From: mdw Date: Sun, 4 Feb 2001 17:14:42 +0000 (+0000) Subject: Initial checkin X-Git-Tag: 1.0.0~14 X-Git-Url: https://git.distorted.org.uk/~mdw/anag/commitdiff_plain/6e4032210ea6c167fcf14c70ae6b18661c011310 Initial checkin --- 6e4032210ea6c167fcf14c70ae6b18661c011310 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 -------------------------------------------------*/