From d74e2a35bb0db0d88b074e5715b051da9c8f658e Mon Sep 17 00:00:00 2001 Message-Id: From: Mark Wooding Date: Fri, 22 Oct 1999 22:37:09 +0000 Subject: [PATCH] Test rig for dynamic arrays. Organization: Straylight/Edgeware From: mdw --- da-gtest | 70 ++++++++++++++++++++++++++++ da-ref | 68 +++++++++++++++++++++++++++ da-test.c | 137 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 275 insertions(+) create mode 100755 da-gtest create mode 100755 da-ref create mode 100644 da-test.c diff --git a/da-gtest b/da-gtest new file mode 100755 index 0000000..4412e49 --- /dev/null +++ b/da-gtest @@ -0,0 +1,70 @@ +#! /usr/bin/perl +# +# Generate a random test file for dynamic array testing. +# +# Syntax reference: +# +# push n, pop, shift, unshift n -- normal stack ops (pop and shift print) +# insert x y z ... -- insert items at beginning +# append x y z ... -- append items at end +# delete n -- remove n items from beginning +# reduce n -- remove n items from end +# set i n -- assign item at index i to be n +# get i -- display item at index i +# show -- write entire array to stdout, space separated on one line + +sub random ($) { + my $lim = shift; + return int(rand($lim)); +} + +$lines = shift || 100; +$max = 0; # Estimate of size of array +$serial = 1; +while ($lines) { + $what = random(17); + if ($what < 8) { + my $op = (qw(push pop shift unshift))[$what % 4]; + if ($op eq "push" || $op eq "unshift") { + my $n = $serial++; + $max++; + print "$op $n\n"; + } elsif ($max > 0) { + $max--; + print "$op\n"; + } + } elsif ($what < 10) { + my @n = ($serial++); + my $op = (qw(insert append))[$what % 2]; + push(@n, $serial++) while random(4) < 3; + print "$op ", join(" ", @n), "\n"; + $max += @n; + } elsif ($what < 12) { + if ($max < 10000) { next; } + my $n = 1; + my $op = (qw(delete reduce))[$what % 2]; + $n++ while random(4) < 3; + print "$op $n\n"; + $max -= $n; + if ($max < 0) { + $max = 0; + } + } elsif ($what < 16) { + my $i = random($max); + $i++ while random(4) < 2; + if ($what % 2 == 0) { + my $n = $serial++; + print "set $i $n\n"; + if ($i >= $max) { + $max = $i + 1; + } + } else { + print "get $i\n"; + } + } elsif (random(10) == 0) { + print "show\n"; + } else { next; } + $lines--; +} + +print "show\n"; diff --git a/da-ref b/da-ref new file mode 100755 index 0000000..2c1e592 --- /dev/null +++ b/da-ref @@ -0,0 +1,68 @@ +#! /usr/bin/perl +# +# Reference implementation for dynamic array testing. + +@a = (); +while (<>) { + chomp(); + # print "$_\n"; + @F = split(); + if ($F[0] eq "push") { + push(@a, $F[1]); + } elsif ($F[0] eq "unshift") { + unshift(@a, $F[1]); + } elsif ($F[0] eq "pop") { + if (@a == 0) { + print "*UFLOW*\n"; + } else { + my $n = int(pop(@a)); + print "$n\n"; + } + } elsif ($F[0] eq "shift") { + if (@a == 0) { + print "*UFLOW*\n"; + } else { + my $n = int(shift(@a)); + print "$n\n"; + } + } elsif ($F[0] eq "insert") { + shift(@F); + unshift(@a, @F); + } elsif ($F[0] eq "append") { + shift(@F); + push(@a, @F); + } elsif ($F[0] eq "delete") { + if ($F[1] > @a) { + # @a = (); + print "*UFLOW*\n"; + } else { + splice(@a, 0, $F[1]); + } + } elsif ($F[0] eq "reduce") { + if ($F[1] > @a) { + # @a = (); + print "*UFLOW*\n"; + } else { + $#a -= $F[1]; + } + } elsif ($F[0] eq "set") { + if ($F[1] > @a) { + for (my $i = @a; $i < $F[1]; $i++) { $a[$i] = -1; } + } + $a[$F[1]] = int($F[2]); + } elsif ($F[0] eq "get") { + if ($F[1] >= @a) { + print "*RANGE*\n"; + } else { + print int($a[$F[1]]), "\n"; + } + } elsif ($F[0] eq "show") { + if (@a) { + print join(" ", map int, @a), "\n"; + } else { + print "*EMPTY*\n"; + } + } else { + print "*BAD*\n"; + } +} diff --git a/da-test.c b/da-test.c new file mode 100644 index 0000000..6a73b0b --- /dev/null +++ b/da-test.c @@ -0,0 +1,137 @@ +/* -*-c-*- + * + * Test driver for darray. + */ + +#include +#include +#include +#include + +#include "darray.h" +#include "exc.h" + +DA_DECL(vec, int); + +#ifdef notdef + +static void dump(vec *v) +{ + printf("# len = %lu, sz = %lu, off = %lu; push = %u, unshift = %u\n", + (unsigned long)v->b.len, + (unsigned long)v->b.sz, + (unsigned long)v->b.off, + v->b.push, v->b.unshift); + printf("# {"); + if (DA_LEN(v)) { + size_t i; + printf(" %i", DA(v)[0]); + for (i = 1; i < DA_LEN(v); i++) + printf(", %i", DA(v)[i]); + } + puts(" }"); + assert(v->b.sz + v->b.off == 128); +} + +#endif + +int main(void) +{ + char buf[1024]; + char *p; + vec v = DA_INIT; + +/* setvbuf(stdout, 0, _IOLBF, BUFSIZ); */ + + while (fgets(buf, sizeof(buf), stdin)) { + buf[strlen(buf) - 1] = 0; +/* printf("# %s\n", buf); */ + p = strtok(buf, " "); + + TRY { + if (strcmp(p, "push") == 0) { + int n = atoi(strtok(0, " ")); + DA_PUSH(&v, n); + } else if (strcmp(p, "unshift") == 0) { + int n = atoi(strtok(0, " ")); + DA_UNSHIFT(&v, n); + } else if (strcmp(p, "pop") == 0) { + printf("%i\n", DA_POP(&v)); + } else if (strcmp(p, "shift") == 0) { + printf("%i\n", DA_SHIFT(&v)); + } else if (strcmp(p, "insert") == 0 || + strcmp(p, "append") == 0) { + vec vv; + char *q = p; + DA_CREATE(&vv); +/* putchar('#'); */ + while ((p = strtok(0, " ")) != 0) { + int n = atoi(p); + DA_PUSH(&vv, n); + } + if (strcmp(q, "insert") == 0) { + DA_SHUNT(&v, DA_LEN(&vv)); + DA_SLIDE(&v, DA_LEN(&vv)); + memcpy(DA(&v), DA(&vv), DA_LEN(&vv) * sizeof(int)); + } else { + size_t l = DA_LEN(&v); + DA_ENSURE(&v, DA_LEN(&vv)); + DA_EXTEND(&v, DA_LEN(&vv)); + memcpy(DA(&v) + l, DA(&vv), DA_LEN(&vv) * sizeof(int)); + } + DA_DESTROY(&vv); + } else if (strcmp(p, "delete") == 0) { + int n = atoi(strtok(0, " ")); + DA_SLIDE(&v, -n); + } else if (strcmp(p, "reduce") == 0) { + int n = atoi(strtok(0, " ")); + DA_EXTEND(&v, -n); + } else if (strcmp(p, "set") == 0) { + size_t i = atoi(strtok(0, " ")); + int n = atoi(strtok(0, " ")); + size_t l = DA_LEN(&v); + DA_INCLUDE(&v, i); + if (i >= l) { + size_t j; + for (j = l; j < i; j++) + DA(&v)[j] = -1; + } + DA(&v)[i] = n; + } else if (strcmp(p, "get") == 0) { + size_t i = atoi(strtok(0, " ")); + if (i >= DA_LEN(&v)) + puts("*RANGE*"); + else + printf("%i\n", DA(&v)[i]); + } else if (strcmp(p, "show") == 0) { + if (DA_LEN(&v) == 0) + puts("*EMPTY*"); + else { + size_t i; + printf("%i", DA(&v)[0]); + for (i = 1; i < DA_LEN(&v); i++) + printf(" %i", DA(&v)[i]); + putchar('\n'); + } + } else + puts("*BAD*"); + } CATCH switch (exc_type) { + case DAEXC_UFLOW: + puts("*UFLOW*"); + break; + case DAEXC_OFLOW: + puts("*OFLOW*"); + break; + case EXC_NOMEM: + puts("*NOMEM*"); + break; + default: + puts("*UNKNOWN-EXCEPTION*"); + break; + } END_TRY; +/* dump(&v); */ + } + + DA_DESTROY(&v); + return (0); +} -- [mdw]