From d5736c560703725d13c88234f03e82693212c265 Mon Sep 17 00:00:00 2001 From: Denis Vlasenko Date: Wed, 18 Jun 2008 19:49:46 +0000 Subject: strrchr: bikeshed painting time! replace cubic running time implementation with quadratic make embedded test actually readable function old new delta strrstr 42 44 +2 --- libbb/strrstr.c | 94 ++++++++++++++++++++++++++------------------------------- 1 file changed, 43 insertions(+), 51 deletions(-) (limited to 'libbb') diff --git a/libbb/strrstr.c b/libbb/strrstr.c index 126fed75c..088d9f457 100644 --- a/libbb/strrstr.c +++ b/libbb/strrstr.c @@ -7,73 +7,65 @@ * Licensed under GPLv2 or later, see file License in this tarball for details. */ +#ifdef __DO_STRRSTR_TEST +#include +#include +#include +#else #include "libbb.h" +#endif /* * The strrstr() function finds the last occurrence of the substring needle * in the string haystack. The terminating nul characters are not compared. */ -char *strrstr(const char *haystack, const char *needle) +char* strrstr(const char *haystack, const char *needle) { char *r = NULL; - - do { + + if (!needle[0]) + return (char*)haystack; + while (1) { char *p = strstr(haystack, needle); - if (p) - r = p; - } while (*haystack++); - return r; + if (!p) + return r; + r = p; + haystack = p + 1; + } } #ifdef __DO_STRRSTR_TEST -/* Test */ int main(int argc, char **argv) { - int ret = 0; - int n; - char *tmp; - - ret |= !(n = ((tmp = strrstr("baaabaaab", "aaa")) != NULL && strcmp(tmp, "aaab") == 0)); - printf("'baaabaaab' vs. 'aaa' : %s\n", n ? "PASSED" : "FAILED"); - - ret |= !(n = ((tmp = strrstr("baaabaaaab", "aaa")) != NULL && strcmp(tmp, "aaab") == 0)); - printf("'baaabaaaab' vs. 'aaa' : %s\n", n ? "PASSED" : "FAILED"); - - ret |= !(n = ((tmp = strrstr("baaabaab", "aaa")) != NULL && strcmp(tmp, "aaabaab") == 0)); - printf("'baaabaab' vs. 'aaa' : %s\n", n ? "PASSED" : "FAILED"); - - ret |= !(n = (strrstr("aaa", "aaa") != NULL)); - printf("'aaa' vs. 'aaa' : %s\n", n ? "PASSED" : "FAILED"); - - ret |= !(n = (strrstr("aaa", "a") != NULL)); - printf("'aaa' vs. 'a' : %s\n", n ? "PASSED" : "FAILED"); - - ret |= !(n = (strrstr("aaa", "bbb") == NULL)); - printf("'aaa' vs. 'bbb' : %s\n", n ? "PASSED" : "FAILED"); - - ret |= !(n = (strrstr("a", "aaa") == NULL)); - printf("'a' vs. 'aaa' : %s\n", n ? "PASSED" : "FAILED"); - - ret |= !(n = ((tmp = strrstr("aaa", "")) != NULL && strcmp(tmp, "aaa") == 0)); - printf("'aaa' vs. '' : %s\n", n ? "FAILED" : "PASSED"); - - ret |= !(n = (strrstr("", "aaa") == NULL)); - printf("'' vs. 'aaa' : %s\n", n ? "PASSED" : "FAILED"); + static const struct { + const char *h, *n; + int pos; + } test_array[] = { + /* 0123456789 */ + { "baaabaaab", "aaa", 5 }, + { "baaabaaaab", "aaa", 6 }, + { "baaabaab", "aaa", 1 }, + { "aaa", "aaa", 0 }, + { "aaa", "a", 2 }, + { "aaa", "bbb", -1 }, + { "a", "aaa", -1 }, + { "aaa", "", 3 }, + { "", "aaa", -1 }, + { "", "", 0 }, + }; - ret |= !(n = ((tmp = strrstr("", "")) != NULL && strcmp(tmp, "") == 0)); - printf("'' vs. '' : %s\n", n ? "PASSED" : "FAILED"); + int i; - /*ret |= !(n = (strrstr(NULL, NULL) == NULL)); - printf("'NULL' vs. 'NULL' : %s\n", n ? "PASSED" : "FAILED"); - ret |= !(n = (strrstr("", NULL) == NULL)); - printf("'' vs. 'NULL' : %s\n", n ? "PASSED" : "FAILED"); - ret |= !(n = (strrstr(NULL, "") == NULL)); - printf("'NULL' vs. '' : %s\n", n ? "PASSED" : "FAILED"); - ret |= !(n = (strrstr("aaa", NULL) == NULL)); - printf("'aaa' vs. 'NULL' : %s\n", n ? "PASSED" : "FAILED"); - ret |= !(n = (strrstr(NULL, "aaa") == NULL)); - printf("'NULL' vs. 'aaa' : %s\n", n ? "PASSED" : "FAILED");*/ + i = 0; + while (i < sizeof(test_array) / sizeof(test_array[0])) { + const char *r = strrstr(test_array[i].h, test_array[i].n); + printf("'%s' vs. '%s': '%s' - ", test_array[i].h, test_array[i].n, r); + if (r == NULL) + r = test_array[i].h - 1; + printf("%s\n", r == test_array[i].h + test_array[i].pos ? "PASSED" : "FAILED"); + i++; + } - return ret; + return 0; } #endif -- cgit v1.2.3