Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset 7e10aee in mainline


Ignore:
Timestamp:
2011-08-18T12:08:39Z (10 years ago)
Author:
Jiří Zárevúcky <zarevucky.jiri@…>
Branches:
lfn, master
Children:
3f33b95
Parents:
c53a705
Message:

Rewrite strstr() using Knuth-Morris-Pratt algorithm.

Location:
uspace/lib/posix
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • uspace/lib/posix/string.c

    rc53a705 r7e10aee  
    4848
    4949/**
    50  * Decides whether s2 is a prefix of s1.
    51  *
    52  * @param s1 String in which to look for a prefix.
    53  * @param s2 Prefix string to look for.
    54  * @return True if s2 is a prefix of s1, false otherwise.
    55  */
    56 static bool begins_with(const char *s1, const char *s2)
    57 {
    58         while (*s1 == *s2 && *s2 != '\0') {
    59                 s1++;
    60                 s2++;
    61         }
    62        
    63         /* true if the end was reached */
    64         return *s2 == '\0';
    65 }
    66 
    67 /**
    6850 * The same as strpbrk, except it returns pointer to the nul terminator
    6951 * if no occurence is found.
     
    471453
    472454/**
    473  * Find a substring.
     455 * Find a substring. Uses Knuth-Morris-Pratt algorithm.
    474456 *
    475457 * @param s1 String in which to look for a substring.
     
    478460 *     not found.
    479461 */
    480 char *posix_strstr(const char *s1, const char *s2)
    481 {
    482         assert(s1 != NULL);
    483         assert(s2 != NULL);
    484 
    485         /* special case - needle is an empty string */
    486         if (*s2 == '\0') {
    487                 return (char *) s1;
    488         }
    489 
    490         // TODO: use faster algorithm
    491         /* check for prefix from every position - quadratic complexity */
    492         while (*s1 != '\0') {
    493                 if (begins_with(s1, s2)) {
    494                         return (char *) s1;
    495                 }
     462char* posix_strstr (const char* haystack, const char* needle)
     463{
     464        assert(haystack != NULL);
     465        assert(needle != NULL);
     466       
     467        /* Special case - needle is an empty string. */
     468        if (needle[0] == '\0') {
     469                return (char*) haystack;
     470        }
     471       
     472        /* Preprocess needle. */
     473        size_t nlen = posix_strlen(needle);
     474        size_t prefix_table[nlen + 1];
     475       
     476        {
     477                size_t i = 0;
     478                ssize_t j = -1;
    496479               
    497                 s1++;
     480                prefix_table[i] = j;
     481               
     482                while (i < nlen) {
     483                        while (j >= 0 && needle[i] != needle[j]) {
     484                                j = prefix_table[j];
     485                        }
     486                        i++; j++;
     487                        prefix_table[i] = j;
     488                }
     489        }
     490       
     491        /* Search needle using the precomputed table. */
     492        size_t npos = 0;
     493       
     494        for (size_t hpos = 0; haystack[hpos] != '\0'; ++ hpos) {
     495                while (npos != 0 && haystack[hpos] != needle[npos]) {
     496                        npos = prefix_table[npos];
     497                }
     498               
     499                if (haystack[hpos] == needle[npos]) {
     500                        npos ++;
     501                       
     502                        if (npos == nlen) {
     503                                return (char*) (haystack + hpos - nlen + 1);
     504                        }
     505                }
    498506        }
    499507       
  • uspace/lib/posix/string.h

    rc53a705 r7e10aee  
    8686extern size_t posix_strcspn(const char *s1, const char *s2);
    8787extern size_t posix_strspn(const char *s1, const char *s2);
    88 extern char *posix_strstr(const char *s1, const char *s2);
     88extern char *posix_strstr(const char *haystack, const char *needle);
    8989
    9090/* Collation Functions */
Note: See TracChangeset for help on using the changeset viewer.