Changeset a92cf94f in mainline for uspace/lib/posix

Timestamp:

2011-08-18T18:45:42Z (15 years ago)

Author:

Petr Koupy <petr.koupy@…>

Branches:

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

Children:

1f44b056

Parents:

ee24574 (diff), f55b12b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge libposix changes.

Location:

uspace/lib/posix

Files:

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

uspace/lib/posix/pwd.c

@@ -51 +51 @@
 
 /**
+ * Retrieve next broken-down entry from the user database.
+ *
  * Since HelenOS doesn't have user accounts, this always returns
  * the same made-up entry.
  *
- * @return
+ * @return Next user database entry or NULL if not possible. Since HelenOS
+ *     doesn't have user accounts, this always returns the same made-up entry.
  */
 struct posix_passwd *posix_getpwent(void)
@@ -67 +70 @@
 
 /**
- * "Rewind the user list".
+ * Rewind the user list.
  */
 void posix_setpwent(void)
@@ -86 +89 @@
  *
  * @param name Name of the entry.
- * @return
+ * @return Either found entry or NULL if no such entry exists.
  */
 struct posix_passwd *posix_getpwnam(const char *name)
@@ -103 +106 @@
  *
  * @param name Name of the entry.
- * @param pwd
- * @param buffer
- * @param bufsize
- * @param result
- * @return
+ * @param pwd Original structure.
+ * @param buffer Buffer for the strings referenced from the result structure.
+ * @param bufsize Length of the buffer.
+ * @param result Where to store updated structure.
+ * @return Zero on success (either found or not found, but without an error),
+ *     non-zero error number if error occured.
  */
 int posix_getpwnam_r(const char *name, struct posix_passwd *pwd,
@@ -129 +133 @@
  *
  * @param uid UID of the entry.
- * @return
+ * @return Either found entry or NULL if no such entry exists.
  */
 struct posix_passwd *posix_getpwuid(posix_uid_t uid)
@@ -144 +148 @@
  *
  * @param uid UID of the entry.
- * @param pwd
- * @param buffer
- * @param bufsize
- * @param result
- * @return
+ * @param pwd Original structure.
+ * @param buffer Buffer for the strings referenced from the result structure.
+ * @param bufsize Length of the buffer.
+ * @param result Where to store updated structure.
+ * @return Zero on success (either found or not found, but without an error),
+ *     non-zero error number if error occured.
  */
 int posix_getpwuid_r(posix_uid_t uid, struct posix_passwd *pwd,

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 */