From db6e9bac370093b13cfb6f0b81ac066fed64b004 Mon Sep 17 00:00:00 2001 From: Martin Ashby Date: Wed, 16 Nov 2022 19:17:08 +0000 Subject: Messing around replacing loops with recursion leveraging __attribute__((musttail)) in order to avoid stack overflow --- ex1-10.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++----------------- ex1-8.c | 49 +++++++++++++++++++++++++++++++++++------------ ex1-9.c | 38 +++++++++++++++++++------------------ fib.c | 35 ++++++++++++++++++++++++++++++++++ run | 2 +- test | 2 +- 6 files changed, 143 insertions(+), 49 deletions(-) create mode 100644 fib.c diff --git a/ex1-10.c b/ex1-10.c index 0b0c018..f17e748 100644 --- a/ex1-10.c +++ b/ex1-10.c @@ -6,31 +6,63 @@ typedef enum _state {IN,OUT} state; /* true if c is a 'word' character (not a blank, space, or a tab) */ -bool is_word(char c) { +static bool is_word(char c) { return c != ' ' && c != '\t' && c != '\n'; } +struct res { + uint32_t cc; + uint32_t lc; + uint32_t wc; +}; + +struct res_internal { + struct res res; + state s; +}; + +static struct res_internal nri(void) { + struct res_internal res = { + .s = OUT, + .res = { + .cc = 0, + .lc = 0, + .wc = 0, + } + }; + return res; +} + +static struct res_internal do_count_internal(FILE* fin, struct res_internal res) { + int c = fgetc(fin); + if (c == EOF) { + return res; + } + res.res.cc++; + if (c == '\n') { + res.res.lc++; + } + if (!is_word(c)) { + res.s = OUT; + } else if (res.s == OUT) { + res.s = IN; + res.res.wc++; + } + __attribute__((musttail)) + return do_count_internal(fin, res); +} + +struct res do_count() { + struct res_internal ri = do_count_internal(stdin, nri()); + return ri.res; +} /* Counts characters, lines, and words from stdin. 'characters' are single byte characters. No handling for encodings in c standard lib. 'lines' are newline characters. 'words' are contiguous sequences of characters other than space, tab, newline */ int main(void) { - int c; - state s = OUT; - uint32_t cc = 0, lc = 0, wc = 0; - while ((c = getchar()) != EOF) { - cc++; - if (c == '\n') { - lc++; - } - if (!is_word(c)) { - s = OUT; - } else if (s == OUT) { - s = IN; - wc++; - } - } - printf("cc=%d lc=%d wc=%d\n", cc, lc, wc); + struct res res = do_count(); + printf("cc=%d lc=%d wc=%d\n", res.cc, res.lc, res.wc); return 0; } \ No newline at end of file diff --git a/ex1-8.c b/ex1-8.c index cc70b64..7e8c3bd 100644 --- a/ex1-8.c +++ b/ex1-8.c @@ -1,18 +1,43 @@ #include #include -int main(void) { - int c; - uint32_t nl = 0, tb = 0, bl = 0; - while ((c = getchar()) != EOF) { - if (c == ' ') { - bl++; - } else if (c == '\n') { - nl++; - } else if (c == '\t') { - tb++; - } +struct res { + uint64_t nl; + uint64_t tb; + uint64_t bl; +}; + +struct res nr(void) { + struct res r = { + .nl = 0, + .tb = 0, + .bl = 0. + }; + return r; +} + +static struct res _loop(struct res res) { + int c = getchar(); + if (c == EOF) { + return res; } - printf("nl=%ld tb=%ld bl=%ld\n", nl, tb, bl); + if (c == ' ') { + res = (struct res){ + .bl = res.bl+1, + .nl = res.nl, + .tb = res.tb, + }; + } else if (c == '\n') { + res.nl++; + } else if (c == '\t') { + res.tb++; + } + __attribute__((musttail)) + return _loop(res); +} + +int main(void) { + struct res r = _loop(nr()); + printf("nl=%ld tb=%ld bl=%ld\n", r.nl, r.tb, r.bl); return 0; } diff --git a/ex1-9.c b/ex1-9.c index 07561d9..c2a625b 100644 --- a/ex1-9.c +++ b/ex1-9.c @@ -2,27 +2,29 @@ #include #include -/* Copy stdin to stdout, replacing consecutive spaces with a single space - Edge case: a leading space is retained if there are leading spaces. - Edge case: an empty file just doesn't echo anything, but emits a warning on stderr */ -int remspace(FILE* fin, FILE* fout, FILE* ferr) { - int c = fgetc(fin); - if (c == EOF) { - fprintf(ferr, "warning: no input\n"); - goto exit; - } - fputc(c, fout); - bool bl = (c == ' '); - while ((c = fgetc(fin)) != EOF) { - if ((!bl) || (c != ' ')) { +static int _remspace_internal(FILE* fin, FILE* fout, FILE* ferr, int pc) { + int c = fgetc(fin); + if (c == EOF) { + // Should I still put EOF here? does it work with pipes or not? + //fputc(c, fout); + return 0; + } + if (c == ' ' && pc == ' ') { + // skip it + } else { fputc(c, fout); } - bl = (c == ' '); - } -exit: + __attribute__((musttail)) + return _remspace_internal(fin, fout, ferr, c); +} + +/* Copy stdin to stdout, replacing consecutive spaces with a single space + Edge case: a leading space is retained if there are leading spaces. */ +int remspace(FILE* fin, FILE* fout, FILE* ferr) { + int res = _remspace_internal(fin, fout, ferr, -1); fflush(fout); fflush(ferr); - return 0; + return res; } #ifndef test @@ -47,7 +49,7 @@ void do_test(CuTest* tc, char* input, const char* expected, const char* err_expe CuAssertStrEquals(tc, err_expected, err_buf); } void test_remspace_empty(CuTest* tc) { - do_test(tc, "", "", "warning: no input\n"); + do_test(tc, "", "", ""); } void test_remspace_oneword(CuTest* tc) { do_test(tc, "foobar", "foobar", ""); diff --git a/fib.c b/fib.c new file mode 100644 index 0000000..6f510c2 --- /dev/null +++ b/fib.c @@ -0,0 +1,35 @@ +#include + +static long fib_internal(int n, long a, long b) { + if (n == 0) { + return a; + } else if (n == 1) { + return b; + } else { + __attribute__((musttail)) + return fib_internal(n-1, b, a + b); + } +} + +long fib(int n) { + return fib_internal(n, 0, 1); +} + +void test(int n) { + printf("fib [%d] = [%ld]\n", n, fib(n)); +} + +// static long recursion_depth(long n, long max) { +// if (n >= max) { +// return n; +// } +// __attribute__((musttail)) +// return recursion_depth(n+1, max); +// } + +int main(void) { + for (int i=1; i<300; i++) { + test(i); + } + //printf("%ld\n", recursion_depth(0, 1000000000)); +} \ No newline at end of file diff --git a/run b/run index 11c2851..96e9fac 100755 --- a/run +++ b/run @@ -1,6 +1,6 @@ #!/usr/bin/env bash set -e -cc -o exe $@ +clang -Wall -Werror -o exe $@ ./exe result=$? rm exe diff --git a/test b/test index 4e32886..77c4f7d 100755 --- a/test +++ b/test @@ -1,6 +1,6 @@ #!/usr/bin/env bash set -e -cc -Dtest=true -o test_exe CuTest.c $@ +clang -Wall -Werror -Dtest=true -o test_exe CuTest.c $@ ./test_exe result=$? rm test_exe -- cgit v1.2.3-ZIG