From 2eb18813b84ae8ad4faeb92b1d8570599135d537 Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Wed, 20 Sep 2006 22:22:25 -0700 Subject: [PATCH] Break wordgame.c into dict.c and grid.c in preparation for more programs --- .gitignore | 2 +- Makefile | 20 ++- dict.c | 276 +++++++++++++++++++++++++++++++++++++++++ dict.h | 97 +++++++++++++++ wordgame.c => grid.c | 287 +------------------------------------------ 5 files changed, 393 insertions(+), 289 deletions(-) create mode 100644 dict.c create mode 100644 dict.h rename wordgame.c => grid.c (54%) diff --git a/.gitignore b/.gitignore index c456d99..e572698 100644 --- a/.gitignore +++ b/.gitignore @@ -1,3 +1,3 @@ -wordgame +grid *.o *~ diff --git a/Makefile b/Makefile index 5d15674..651c1ef 100644 --- a/Makefile +++ b/Makefile @@ -1,2 +1,18 @@ -wordgame: wordgame.o - $(CC) $(CFLAGS) $(LDFLAGS) -lreadline -lm -o $@ $^ +WGCFLAGS=-Wall -Wextra -Wno-unused-parameter + +PROGRAMS=grid + +LIBRARY=dict.o + +all: $(PROGRAMS) + +%.o: %.c + $(CC) $(CFLAGS) $(WGCFLAGS) -c -o $@ $^ + +%.c: dict.h + +grid: grid.o $(LIBRARY) + $(CC) $(CFLAGS) $(WGCFLAGS) $(LDFLAGS) -lreadline -lm -o $@ $^ + +clean: + rm -f $(PROGRAMS) *.o diff --git a/dict.c b/dict.c new file mode 100644 index 0000000..98c9476 --- /dev/null +++ b/dict.c @@ -0,0 +1,276 @@ +/* + * Copyright © 2006 Carl Worth + * + * This program 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, or (at your option) + * any later version. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA." + */ + +/* Portably, schmortability. I want ease of programming. */ +#define _GNU_SOURCE +#include +#include +#include +#include +#include + +#include "dict.h" + +void * +xmalloc (size_t size) +{ + void *res; + + res = malloc (size); + if (res == NULL) { + fprintf (stderr, "Error: out of memory\n"); + exit (1); + } + + return res; +} + +void * +xrealloc (void *ptr, size_t size) +{ + void *res; + + res = realloc (ptr, size); + if (res == NULL) { + fprintf (stderr, "Error: out of memory\n"); + exit (1); + } + + return res; +} + +void +chomp (char *s) +{ + int len = strlen (s); + if (s[len - 1] == '\n') + s[len - 1] = '\0'; +} + +void +string_init (string_t *string) +{ + string->size = 0; + string->s = NULL; + string->len = 0; +} + +void +string_fini (string_t *string) +{ + string->size = 0; + if (string->s) + free (string->s); + string->len = 0; +} + +void +string_append_char (string_t *string, char c) +{ + if (string->size == 0) { + string->size = 8; + string->s = xmalloc (string->size); + string->s[0] = '\0'; + string->len = 0; + } + + if (string->len + 1 == string->size) { + string->size *= 2; + string->s = xrealloc (string->s, string->size); + } + + string->s[string->len++] = c; + string->s[string->len] = '\0'; +} + +void +string_chop (string_t *string) +{ + if (string->len == 0) + return; + + string->s[--string->len] = '\0'; +} + +static void +trie_init (trie_t *trie) +{ + int i; + trie->flags = 0; + for (i = 0; i < 26; i++) + trie->next[i] = NULL; +} + +trie_t * +trie_create (void) +{ + trie_t *trie; + + trie = xmalloc (sizeof (trie_t)); + + trie_init (trie); + + return trie; +} + +void +trie_destroy (trie_t *trie) +{ + int i; + + for (i = 0; i < 26; i++) + if (trie->next[i]) + trie_destroy (trie->next[i]); + + free (trie); +} + +void +trie_add (trie_t *trie, + const char *word_chunk) +{ + char c = word_chunk[0]; + int i; + + if (c == '\0') { + trie->flags |= TRIE_FLAGS_IS_WORD; + return; + } + + i = TRIE_CHAR_TO_INDEX (c); + if (trie->next[i] == NULL) + trie->next[i] = trie_create (); + + trie_add (trie->next[i], word_chunk + 1); +} + +trie_t * +trie_find (trie_t *trie, + const char *word_chunk) +{ + const char *s = word_chunk; + + while (trie && *s) + trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)]; + + return trie; +} + +int +trie_print (trie_t *trie, + string_t *string, + trie_predicate_t predicate) +{ + char c; + int i; + int count = 0; + + if (trie->flags & TRIE_FLAGS_IS_WORD + && (predicate == NULL || predicate (trie))) + { + count = 1; + printf ("%s ", string->s); + } + + /* Loop over each element, appending the character and recursing. */ + for (i = 0; i < 26; i++) { + if (trie->next[i] == NULL) + continue; + + c = TRIE_INDEX_TO_CHAR (i); + + string_append_char (string, c); + count += trie_print (trie->next[i], string, predicate); + string_chop (string); + } + + return count; +} + +bool_t +trie_seen_predicate (trie_t *trie) +{ + return (trie->flags & TRIE_FLAGS_SEEN); +} + +int +trie_print_seen (trie_t *trie, string_t *word) +{ + return trie_print (trie, word, trie_seen_predicate); +} + +bool_t +trie_unseen_predicate (trie_t *trie) +{ + return (! trie_seen_predicate (trie)); +} + +int +trie_print_unseen (trie_t *trie, string_t *word) +{ + return trie_print (trie, word, trie_unseen_predicate); +} + +void +dict_init (dict_t *dict, + const char *filename) +{ + FILE *file; + char *line = NULL; + size_t line_size = 0; + ssize_t bytes_read; + + file = fopen (filename, "r"); + if (file == NULL) { + fprintf (stderr, "Error: failed to open %s: %s\n", + filename, strerror (errno)); + exit (1); + } + + dict->trie = trie_create (); + + while (1) { + bytes_read = getline (&line, &line_size, file); + if (bytes_read == -1) + break; + chomp (line); + trie_add (dict->trie, line); + } + if (line) + free (line); + + fclose (file); +} + +void +dict_fini (dict_t *dict) +{ + trie_destroy (dict->trie); +} + +void +dict_print (dict_t *dict) +{ + string_t string; + + string_init (&string); + + trie_print (dict->trie, &string, NULL); + + string_fini (&string); +} diff --git a/dict.h b/dict.h new file mode 100644 index 0000000..4d4885c --- /dev/null +++ b/dict.h @@ -0,0 +1,97 @@ +/* + * Copyright © 2006 Carl Worth + * + * This program 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, or (at your option) + * any later version. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA." + */ + +#ifndef _DICT_H_ +#define _DICT_H_ + +#include + +#ifndef FALSE +# define FALSE 0 +#endif + +#ifndef TRUE +# define TRUE 1 +#endif + +typedef int bool_t; + +typedef struct _string { + size_t size; + char *s; + size_t len; +} string_t; + +void +string_init (string_t *string); + +void +string_fini (string_t *string); + +void +string_append_char (string_t *string, char c); + +void +string_chop (string_t *string); + +void +chomp (char *s); + +#define TRIE_FLAGS_IS_WORD (1<<0) +#define TRIE_FLAGS_SEEN (1<<1) + +typedef struct _trie { + uint32_t flags; + struct _trie *next[26]; +} trie_t; + +typedef bool_t +(*trie_predicate_t) (trie_t *trie); + +#define TRIE_CHAR_TO_INDEX(c) (tolower (c) - 'a') +#define TRIE_INDEX_TO_CHAR(i) (i + 'a') + +trie_t * +trie_create (void); + +void +trie_add (trie_t *trie, + const char *word_chunk); + +trie_t * +trie_find (trie_t *trie, + const char *word_chunk); + +int +trie_print_seen (trie_t *trie, string_t *word); + +int +trie_print_unseen (trie_t *trie, string_t *word); + +typedef struct _dict { + trie_t *trie; +} dict_t; + +void +dict_init (dict_t *dict, + const char *filename); + +void +dict_fini (dict_t *dict); + +#endif /* _DICT_H_ */ diff --git a/wordgame.c b/grid.c similarity index 54% rename from wordgame.c rename to grid.c index a9c18d6..b9c307b 100644 --- a/wordgame.c +++ b/grid.c @@ -16,13 +16,8 @@ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA." */ -/* Portably, schmortability. I want ease of programming. */ -#define _GNU_SOURCE #include #include -#include -#include -#include #include #include #include @@ -31,287 +26,7 @@ #include #include -#ifndef FALSE -# define FALSE 0 -#endif - -#ifndef TRUE -# define TRUE 1 -#endif - -typedef int bool_t; - -#define TRIE_FLAGS_IS_WORD (1<<0) -#define TRIE_FLAGS_SEEN (1<<1) - -typedef struct _trie { - uint32_t flags; - struct _trie *next[26]; -} trie_t; - -typedef bool_t -(*trie_predicate_t) (trie_t *trie); - -void * -xmalloc (size_t size) -{ - void *res; - - res = malloc (size); - if (res == NULL) { - fprintf (stderr, "Error: out of memory\n"); - exit (1); - } - - return res; -} - -void * -xrealloc (void *ptr, size_t size) -{ - void *res; - - res = realloc (ptr, size); - if (res == NULL) { - fprintf (stderr, "Error: out of memory\n"); - exit (1); - } - - return res; -} - -void -chomp (char *s) -{ - int len = strlen (s); - if (s[len - 1] == '\n') - s[len - 1] = '\0'; -} - -typedef struct _string { - size_t size; - char *s; - size_t len; -} string_t; - -void -string_init (string_t *string) -{ - string->size = 0; - string->s = NULL; - string->len = 0; -} - -void -string_fini (string_t *string) -{ - string->size = 0; - if (string->s) - free (string->s); - string->len = 0; -} - -void -string_append_char (string_t *string, char c) -{ - if (string->size == 0) { - string->size = 8; - string->s = xmalloc (string->size); - string->s[0] = '\0'; - string->len = 0; - } - - if (string->len + 1 == string->size) { - string->size *= 2; - string->s = xrealloc (string->s, string->size); - } - - string->s[string->len++] = c; - string->s[string->len] = '\0'; -} - -void -string_chop (string_t *string) -{ - if (string->len == 0) - return; - - string->s[--string->len] = '\0'; -} - -static void -trie_init (trie_t *trie) -{ - int i; - trie->flags = 0; - for (i = 0; i < 26; i++) - trie->next[i] = NULL; -} - -trie_t * -trie_create (void) -{ - trie_t *trie; - - trie = xmalloc (sizeof (trie_t)); - - trie_init (trie); - - return trie; -} - -void -trie_destroy (trie_t *trie) -{ - int i; - - for (i = 0; i < 26; i++) - if (trie->next[i]) - trie_destroy (trie->next[i]); - - free (trie); -} - -#define TRIE_CHAR_TO_INDEX(c) (tolower (c) - 'a') -#define TRIE_INDEX_TO_CHAR(i) (i + 'a') -void -trie_add (trie_t *trie, - const char *word_chunk) -{ - char c = word_chunk[0]; - int i; - - if (c == '\0') { - trie->flags |= TRIE_FLAGS_IS_WORD; - return; - } - - i = TRIE_CHAR_TO_INDEX (c); - if (trie->next[i] == NULL) - trie->next[i] = trie_create (); - - trie_add (trie->next[i], word_chunk + 1); -} - -trie_t * -trie_find (trie_t *trie, - const char *word_chunk) -{ - const char *s = word_chunk; - - while (trie && *s) - trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)]; - - return trie; -} - -int -trie_print (trie_t *trie, - string_t *string, - trie_predicate_t predicate) -{ - char c; - int i; - int count = 0; - - if (trie->flags & TRIE_FLAGS_IS_WORD - && (predicate == NULL || predicate (trie))) - { - count = 1; - printf ("%s ", string->s); - } - - /* Loop over each element, appending the character and recursing. */ - for (i = 0; i < 26; i++) { - if (trie->next[i] == NULL) - continue; - - c = TRIE_INDEX_TO_CHAR (i); - - string_append_char (string, c); - count += trie_print (trie->next[i], string, predicate); - string_chop (string); - } - - return count; -} - -bool_t -trie_seen_predicate (trie_t *trie) -{ - return (trie->flags & TRIE_FLAGS_SEEN); -} - -int -trie_print_seen (trie_t *trie, string_t *word) -{ - return trie_print (trie, word, trie_seen_predicate); -} - -bool_t -trie_unseen_predicate (trie_t *trie) -{ - return (! trie_seen_predicate (trie)); -} - -int -trie_print_unseen (trie_t *trie, string_t *word) -{ - return trie_print (trie, word, trie_unseen_predicate); -} - -typedef struct _dict { - trie_t *trie; -} dict_t; - -void -dict_init (dict_t *dict, - const char *filename) -{ - FILE *file; - char *line = NULL; - size_t line_size = 0; - ssize_t bytes_read; - - file = fopen (filename, "r"); - if (file == NULL) { - fprintf (stderr, "Error: failed to open %s: %s\n", - filename, strerror (errno)); - exit (1); - } - - dict->trie = trie_create (); - - while (1) { - bytes_read = getline (&line, &line_size, file); - if (bytes_read == -1) - break; - chomp (line); - trie_add (dict->trie, line); - } - if (line) - free (line); - - fclose (file); -} - -void -dict_fini (dict_t *dict) -{ - trie_destroy (dict->trie); -} - -void -dict_print (dict_t *dict) -{ - string_t string; - - string_init (&string); - - trie_print (dict->trie, &string, NULL); - - string_fini (&string); -} +#include "dict.h" char *cube_faces[16] = { "aaeeng", "abbjoo", "achops", "affkps", -- 2.43.0