From cd3001477e8cada39b9db728f65ff610d89a8895 Mon Sep 17 00:00:00 2001 From: mdw Date: Fri, 22 Oct 1999 22:36:37 +0000 Subject: [PATCH] New test structure for symbol tables. --- sym-gtest | 49 ++++++++++++++ sym-ref | 40 ++++++++++++ sym-test.c | 88 +++++++++++++++++++++++++ sym.c | 217 ++----------------------------------------------------------- 4 files changed, 181 insertions(+), 213 deletions(-) create mode 100755 sym-gtest create mode 100755 sym-ref create mode 100644 sym-test.c diff --git a/sym-gtest b/sym-gtest new file mode 100755 index 0000000..b3db964 --- /dev/null +++ b/sym-gtest @@ -0,0 +1,49 @@ +#! /usr/bin/perl +# +# Generate a random test file for symbol table testing. +# +# Syntax reference: +# +# set k v -- assign (textual) key k the (integer) value i +# get k -- display value at key k +# del k -- remove key k +# count -- show number of items +# show -- dump out the entire table, in alphabetical key order + +sub random ($) { + my $lim = shift; + return int(rand($lim)); +} + +open(DICT, "/usr/dict/words") or die("open(/usr/dict/words): $!"); +@w = ; +chomp(@w); +close(DICT); + +%a = (); + +$lines = shift || 100; +$serial = 1; +while ($lines) { + $what = random(4); + if ($what == 0) { + my $k = $w[random(@w)]; + my $i = $serial++; + print "set $k $i\n"; + $a{$k} = $i; + } elsif ($what == 1) { + my $k = $w[random(@w)]; + if (!exists($a{$w}) && random(8) != 0) { next; } + print "get $k\n"; + } elsif ($what == 2) { + my $k = $w[random(@w)]; + if (!exists($a{$w}) && random(8) != 0) { next; } + print "del $k\n"; + delete($w{$k}); + } elsif (random(5) == 0) { + print "count\n"; + } else { next; } + $lines--; +} + +print "show\n"; diff --git a/sym-ref b/sym-ref new file mode 100755 index 0000000..c0a4622 --- /dev/null +++ b/sym-ref @@ -0,0 +1,40 @@ +#! /usr/bin/perl +# +# Reference implementation for symbol table testing. + +%a = (); +while (<>) { + chomp(); + @F = split(); + if ($F[0] eq "set") { + $a{$F[1]} = $F[2]; + } elsif ($F[0] eq "get") { + if (exists($a{$F[1]})) { + print "$a{$F[1]}\n"; + } else { + print "*MISSING*\n"; + } + } elsif ($F[0] eq "del") { + if (exists($a{$F[1]})) { + delete($a{$F[1]}); + } else { + print "*MISSING*\n"; + } + } elsif ($F[0] eq "count") { + print int(keys(%a)), "\n"; + } elsif ($F[0] eq "show") { + if (!%a) { + print "*EMPTY*\n"; + } else { + my $s = ""; + foreach $k (sort(keys(%a))) { + print "$s$k:$a{$k}"; + $s = " "; + } + print "\n"; + } + } else { + print "*BAD*\n"; + } +} + diff --git a/sym-test.c b/sym-test.c new file mode 100644 index 0000000..dea3e60 --- /dev/null +++ b/sym-test.c @@ -0,0 +1,88 @@ +#include +#include +#include + +#include "sub.h" +#include "sym.h" + +typedef struct word { + sym_base _b; + int i; +} word; + +static int cmp(const void *a, const void *b) +{ + const word *const *v = b; + const word *const *w = a; + return (strcmp(SYM_NAME(*w), SYM_NAME(*v))); +} + +int main(void) +{ + char buf[256]; + char *p; + sym_table t; + size_t n = 0; + + sub_init(); + sym_create(&t); + + while (fgets(buf, sizeof(buf), stdin)) { + buf[strlen(buf) - 1] = 0; +/* printf("# %s\n", buf); */ + p = strtok(buf, " "); + + if (strcmp(p, "set") == 0) { + char *k = strtok(0, " "); + int i = atoi(strtok(0, " ")); + unsigned f; + word *w = sym_find(&t, k, -1, sizeof(word), &f); + w->i = i; + if (!f) + n++; + } else if (strcmp(p, "get") == 0) { + char *k = strtok(0, " "); + word *w = sym_find(&t, k, -1, 0, 0); + if (w) + printf("%i\n", w->i); + else + puts("*MISSING*"); + } else if (strcmp(p, "del") == 0) { + char *k = strtok(0, " "); + word *w = sym_find(&t, k, -1, 0, 0); + if (w) { + sym_remove(&t, w); + n--; + } else + puts("*MISSING*"); + } else if (strcmp(p, "count") == 0) { + printf("%i\n", n); + } else if (strcmp(p, "show") == 0) { + sym_iter i; + word *w; + word **v, **vv; + + if (!n) + puts("*EMPTY*"); + else { + v = malloc(n * sizeof(*v)); + if (!v) { + puts("*NOMEM*"); + continue; + } + for (vv = v, sym_mkiter(&i, &t); (w = sym_next(&i)) != 0; vv++) + *vv = w; + qsort(v, n, sizeof(*v), cmp); + printf("%s:%i", SYM_NAME(*v), (*v)->i); + for (vv = v + 1; --n; vv++) + printf(" %s:%i", SYM_NAME(*vv), (*vv)->i); + free(v); + putchar('\n'); + } + } else + puts("*BAD*"); + } + + sym_destroy(&t); + return (0); +} diff --git a/sym.c b/sym.c index 03d2e82..3bf52f3 100644 --- a/sym.c +++ b/sym.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: sym.c,v 1.8 1999/08/02 14:45:48 mdw Exp $ + * $Id: sym.c,v 1.9 1999/10/22 22:36:37 mdw Exp $ * * Symbol table management * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: sym.c,v $ + * Revision 1.9 1999/10/22 22:36:37 mdw + * New test structure for symbol tables. + * * Revision 1.8 1999/08/02 14:45:48 mdw * Break low-level hashtable code out from sym. * @@ -316,216 +319,4 @@ void *sym_next(sym_iter *i) return (p); } -/*----- Symbol table test code --------------------------------------------*/ - -#ifdef TEST_RIG - -#include -#include - -typedef struct sym_word { - sym_base base; - size_t i; -} sym_word; - - -/* --- What it does --- * - * - * Reads the file /usr/dict/words (change to some other file full of - * interesting and appropriate bits of text to taste) into a big buffer and - * picks apart into lines. Then picks lines at random and enters them into - * the symbol table. - */ - -int main(void) -{ - char *buff, *p, *lim; - size_t sz, done; - FILE *fp; - int i; - char **line; - sym_word **flag; - sym_table tbl; - int entries; - - /* --- Initialize for reading the file --- */ - - sz = BUFSIZ; - buff = xmalloc(sz + 1); - done = 0; - sub_init(); - - if ((fp = fopen("/usr/dict/words", "r")) == 0) - fprintf(stderr, "buggered ;-( (%s)\n", strerror(errno)); - - /* --- Read buffers of text --- * - * - * Read a buffer. If more to come, double the buffer size and try again. - * This is the method I recommended to comp.lang.c, so I may as well try - * it. - */ - - for (;;) { - i = fread(buff + done, 1, sz - done, fp); - done += i; - if (done != sz) - break; - sz <<= 1; - buff = xrealloc(buff, sz + 1); - } - - /* --- Count the lines --- */ - - lim = buff + done; - - sz = 1; - for (p = buff; p < lim; p++) - if (*p == '\n') sz++; - - /* --- Build a table of line starts --- */ - - line = xmalloc(sz * sizeof(char *)); - i = 0; - line[i++] = buff; - for (p = buff; p < lim; p++) - if (*p == '\n') *p = 0, line[i++] = p + 1; - *lim = 0; - - /* --- Build a table of lines --- * - * - * This reverses the mapping which the symbol table performs, so that its - * accuracy can be tested. - */ - - flag = xmalloc(sz * sizeof(sym_word *)); - for (i = 0; i < sz; i++) - flag[i] = 0; - entries = 0; - - sym_create(&tbl); - - for (;;) { - i = (unsigned)rand() % sz; - - switch (rand() % 5) - { - case 0: { - sym_word *w; - - printf("? %s\n", line[i]); - - w = sym_find(&tbl, line[i], -1, 0, 0); - if (w != flag[i]) - printf("*** error: find `%s' gave %p not %p\n", - line[i], (void *)w, (void *)flag[i]); - else if (w && w->i != i) - printf("*** error: find sym for `%s' gives index %i not %i\n", - line[i], w->i, i); - } break; - - case 1: { - unsigned f; - sym_word *w; - - printf("+ %s\n", line[i]); - - w = sym_find(&tbl, line[i], -1, sizeof(sym_word), &f); - if (f) - { - if (w != flag[i]) - printf("*** error: create `%s' gave %p not %p\n", - line[i], (void *)w, (void *)flag[i]); - else if (w && w->i != i) - printf("*** error: create sym for `%s' gives index %i not %i\n", - line[i], w->i, i); - } - else - { - if (flag[i]) - printf("*** error: create `%s' gave new block, should be %p\n", - line[i], (void *)flag[i]); - else { - flag[i] = w; - w->i = i; - entries++; - } - } - } break; - - case 2: { - sym_iter it; - sym_word *w, **ntbl; - int v; - - if (!entries) - break; - v = (rand() % entries) == 0; - if (!v) - break; - - printf(".\n"); - - ntbl = xmalloc(sz * sizeof(sym_word *)); - memcpy(ntbl, flag, sz * sizeof(sym_word *)); - sym_mkiter(&it, &tbl); - - while ((w = sym_next(&it)) != 0) { - if (ntbl[w->i] == 0) - printf("*** error: iterate returned duff item %s\n", SYM_NAME(w)); - else { - printf(": %s\n", SYM_NAME(w)); - ntbl[w->i] = 0; - } - } - - for (i = 0; i < sz; i++) - if (ntbl[i]) printf("*** error: iterate didn't return item %s\n", - SYM_NAME(ntbl[i])); - free(ntbl); - } break; - - case 3: { - sym_base *b; - int v = rand() & 255 ? 0 : 1; - break; - - printf("dump\n"); - - for (i = 0; i <= tbl.b.mask; i++) { - if (!tbl.b.v[i]) continue; - if (v) printf(" %i: ", i); - b = (sym_base *)tbl.b.v[i]; - while (b) { - if ((b->b.hash & tbl.b.mask) != i) - printf("*** error: bad hash value found"); - if (v) printf("`%s'(%08lx:%lu) ", - line[((sym_word *)b)->i], - b->b.hash, - b->b.hash & tbl.b.mask); - b = (sym_base *)b->b.next; - } - if (v) putchar('\n'); - } - } break; - - case 4: { - if (flag[i]) { - printf("- %s\n", SYM_NAME(&flag[i]->base)); - if ((rand() & 1023) == 0) { - putchar('-'); fflush(stdout); - } - sym_remove(&tbl, flag[i]); - flag[i] = 0; - entries--; - } - } break; - } - - } - - return (0); -} - -#endif - /*----- That's all, folks -------------------------------------------------*/ -- 2.11.0