Changeset 7e10aee in mainline

Timestamp:

2011-08-18T12:08:39Z (14 years ago)

Author:

Jiří Zárevúcky <zarevucky.jiri@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

3f33b95

Parents:

c53a705

Message:

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

Location:

uspace/lib/posix

Files:

• string.c (modified) (3 diffs)
• string.h (modified) (1 diff)

uspace/lib/posix/string.c

@@ -48 +48 @@
 
 /**
- * Decides whether s2 is a prefix of s1.
- *
- * @param s1 String in which to look for a prefix.
- * @param s2 Prefix string to look for.
- * @return True if s2 is a prefix of s1, false otherwise.
- */
-static bool begins_with(const char *s1, const char *s2)
-{
-        while (*s1 == *s2 && *s2 != '\0') {
-                s1++;
-                s2++;
-        }
-        
-        /* true if the end was reached */
-        return *s2 == '\0';
-}
-
-/**
  * The same as strpbrk, except it returns pointer to the nul terminator
  * if no occurence is found.
@@ -471 +453 @@
 
 /**
- * Find a substring.
+ * Find a substring. Uses Knuth-Morris-Pratt algorithm.
  *
  * @param s1 String in which to look for a substring.
@@ -478 +460 @@
  *     not found.
  */
-char *posix_strstr(const char *s1, const char *s2)
-{
-        assert(s1 != NULL);
-        assert(s2 != NULL);
-
-        /* special case - needle is an empty string */
-        if (*s2 == '\0') {
-                return (char *) s1;
-        }
-
-        // TODO: use faster algorithm
-        /* check for prefix from every position - quadratic complexity */
-        while (*s1 != '\0') {
-                if (begins_with(s1, s2)) {
-                        return (char *) s1;
-                }
+char* posix_strstr (const char* haystack, const char* needle)
+{
+        assert(haystack != NULL);
+        assert(needle != NULL);
+        
+        /* Special case - needle is an empty string. */
+        if (needle[0] == '\0') {
+                return (char*) haystack;
+        }
+        
+        /* Preprocess needle. */
+        size_t nlen = posix_strlen(needle);
+        size_t prefix_table[nlen + 1];
+        
+        {
+                size_t i = 0;
+                ssize_t j = -1;
                 
-                s1++;
+                prefix_table[i] = j;
+                
+                while (i < nlen) {
+                        while (j >= 0 && needle[i] != needle[j]) {
+                                j = prefix_table[j];
+                        }
+                        i++; j++;
+                        prefix_table[i] = j;
+                }
+        }
+        
+        /* Search needle using the precomputed table. */
+        size_t npos = 0;
+        
+        for (size_t hpos = 0; haystack[hpos] != '\0'; ++ hpos) {
+                while (npos != 0 && haystack[hpos] != needle[npos]) {
+                        npos = prefix_table[npos];
+                }
+                
+                if (haystack[hpos] == needle[npos]) {
+                        npos ++;
+                        
+                        if (npos == nlen) {
+                                return (char*) (haystack + hpos - nlen + 1);
+                        }
+                }
         }
         

uspace/lib/posix/string.h

@@ -86 +86 @@
 extern size_t posix_strcspn(const char *s1, const char *s2);
 extern size_t posix_strspn(const char *s1, const char *s2);
-extern char *posix_strstr(const char *s1, const char *s2);
+extern char *posix_strstr(const char *haystack, const char *needle);
 
 /* Collation Functions */