diff options
Diffstat (limited to 'StdLib/LibC/String/Searching.c')
| -rw-r--r-- | StdLib/LibC/String/Searching.c | 262 |
1 files changed, 262 insertions, 0 deletions
diff --git a/StdLib/LibC/String/Searching.c b/StdLib/LibC/String/Searching.c new file mode 100644 index 0000000000..e22655621c --- /dev/null +++ b/StdLib/LibC/String/Searching.c @@ -0,0 +1,262 @@ +/** @file
+ Search Functions for <string.h>.
+
+ Copyright (c) 2010 - 2011, Intel Corporation. All rights reserved.<BR>
+ This program and the accompanying materials are licensed and made available under
+ the terms and conditions of the BSD License that accompanies this distribution.
+ The full text of the license may be found at
+ http://opensource.org/licenses/bsd-license.php.
+
+ THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
+ WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
+**/
+#include <Uefi.h>
+#include <Library/BaseLib.h>
+#include <Library/BaseMemoryLib.h>
+
+#include <LibConfig.h>
+#include <limits.h>
+#include <string.h>
+
+/** The memchr function locates the first occurrence of c (converted to an
+ unsigned char) in the initial n characters (each interpreted as
+ unsigned char) of the object pointed to by s.
+
+ @return The memchr function returns a pointer to the located character,
+ or a null pointer if the character does not occur in the object.
+**/
+void *
+memchr(const void *s, int c, size_t n)
+{
+ return ScanMem8( s, (UINTN)n, (UINT8)c);
+}
+
+/** The strchr function locates the first occurrence of c (converted to a char)
+ in the string pointed to by s. The terminating null character is considered
+ to be part of the string.
+
+ @return The strchr function returns a pointer to the located character,
+ or a null pointer if the character does not occur in the string.
+**/
+char *
+strchr(const char *s, int c)
+{
+ char tgt = (char)c;
+
+ do {
+ if( *s == tgt) {
+ return (char *)s;
+ }
+ } while(*s++ != '\0');
+ return NULL;
+}
+
+static UINT8 BitMask[] = {
+ 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80
+ };
+
+#define WHICH8(c) ((unsigned char)(c) >> 3)
+#define WHICH_BIT(c) (BitMask[((c) & 0x7)])
+#define BITMAP64 ((UINT64 *)bitmap)
+
+static
+void
+BuildBitmap(unsigned char * bitmap, const char *s2, int n)
+{
+ unsigned char bit;
+ int index;
+
+ // Initialize bitmap. Bit 0 is always 1 which corresponds to '\0'
+ for (BITMAP64[0] = index = 1; index < n; index++)
+ BITMAP64[index] = 0;
+
+ // Set bits in bitmap corresponding to the characters in s2
+ for (; *s2 != '\0'; s2++) {
+ index = WHICH8(*s2);
+ bit = WHICH_BIT(*s2);
+ bitmap[index] = bitmap[index] | bit;
+ }
+}
+
+/** The strcspn function computes the length of the maximum initial segment of
+ the string pointed to by s1 which consists entirely of characters not from
+ the string pointed to by s2.
+
+ @return The strcspn function returns the length of the segment.
+**/
+size_t
+strcspn(const char *s1, const char *s2)
+{
+ UINT8 bitmap[ (((UCHAR_MAX + 1) / CHAR_BIT) + (CHAR_BIT - 1)) & ~7U];
+ const char *str;
+ UINT8 bit;
+ int index;
+
+ if(*s1 == '\0') return 0;
+
+ BuildBitmap( bitmap, s2, sizeof(bitmap) / sizeof(UINT64));
+
+ for(str = s1; ; str++) {
+ index = WHICH8(*str);
+ bit = WHICH_BIT(*str);
+ if ((bitmap[index] & bit) != 0)
+ break;
+ }
+ return (str - s1);
+}
+
+/** The strpbrk function locates the first occurrence in the string pointed to
+ by s1 of any character from the string pointed to by s2.
+
+ @return The strpbrk function returns a pointer to the character, or a
+ null pointer if no character from s2 occurs in s1.
+**/
+char *
+strpbrk(const char *s1, const char *s2)
+{
+ UINT8 bitmap[ (((UCHAR_MAX + 1) / CHAR_BIT) + (CHAR_BIT - 1)) & ~7U];
+ UINT8 bit;
+ int index;
+
+ BuildBitmap( bitmap, s2, sizeof(bitmap) / sizeof(UINT64));
+
+ for( ; *s1 != '\0'; ++s1) {
+ index = WHICH8(*s1);
+ bit = WHICH_BIT(*s1);
+ if( (bitmap[index] & bit) != 0) {
+ return (char *)s1;
+ }
+ }
+ return NULL;
+}
+
+/** The strrchr function locates the last occurrence of c (converted to a char)
+ in the string pointed to by s. The terminating null character is considered
+ to be part of the string.
+
+ @return The strrchr function returns a pointer to the character, or a
+ null pointer if c does not occur in the string.
+**/
+char *
+strrchr(const char *s, int c)
+{
+ char *found = NULL;
+ char tgt = (char)c;
+
+ do {
+ if( *s == tgt) found = (char *)s;
+ } while( *s++ != '\0');
+
+ return found;
+}
+
+/** The strspn function computes the length of the maximum initial segment of
+ the string pointed to by s1 which consists entirely of characters from the
+ string pointed to by s2.
+
+ @return The strspn function returns the length of the segment.
+**/
+size_t
+strspn(const char *s1 , const char *s2)
+{
+ UINT8 bitmap[ (((UCHAR_MAX + 1) / CHAR_BIT) + (CHAR_BIT - 1)) & ~7U];
+ size_t length = 0;
+ int index;
+ UINT8 bit;
+
+ BuildBitmap( bitmap, s2, sizeof(bitmap) / sizeof(UINT64));
+
+ for( ; *s1 != '\0'; ++s1) {
+ index = WHICH8(*s1);
+ bit = WHICH_BIT(*s1);
+ if( (bitmap[index] & bit) == 0) break;
+ ++length;
+ }
+ return length;
+}
+
+/** The strstr function locates the first occurrence in the string pointed to
+ by s1 of the sequence of characters (excluding the terminating null
+ character) in the string pointed to by s2.
+
+ @return The strstr function returns a pointer to the located string, or a
+ null pointer if the string is not found. If s2 points to a string
+ with zero length, the function returns s1.
+**/
+char *
+strstr(const char *s1 , const char *s2)
+{
+ return AsciiStrStr( s1, s2);
+}
+
+/** A sequence of calls to the strtok function breaks the string pointed to by
+ s1 into a sequence of tokens, each of which is delimited by a character
+ from the string pointed to by s2. The first call in the sequence has a
+ non-null first argument; subsequent calls in the sequence have a null first
+ argument. The separator string pointed to by s2 may be different from call
+ to call.
+
+ The first call in the sequence searches the string pointed to by s1 for the
+ first character that is not contained in the current separator string
+ pointed to by s2. If no such character is found, then there are no tokens
+ in the string pointed to by s1 and the strtok function returns a null
+ pointer. If such a character is found, it is the start of the first token.
+
+ The strtok function then searches from there for a character that is
+ contained in the current separator string. If no such character is found,
+ the current token extends to the end of the string pointed to by s1, and
+ subsequent searches for a token will return a null pointer. If such a
+ character is found, it is overwritten by a null character, which terminates
+ the current token. The strtok function saves a pointer to the following
+ character, from which the next search for a token will start.
+
+ Each subsequent call, with a null pointer as the value of the first
+ argument, starts searching from the saved pointer and behaves as
+ described above.
+
+ @return The strtok function returns a pointer to the first character of a
+ token, or a null pointer if there is no token.
+**/
+char *
+strtok(char * __restrict s1, const char * __restrict s2)
+{
+ static char *Next = NULL;
+ UINT8 bitmap[ (((UCHAR_MAX + 1) / CHAR_BIT) + (CHAR_BIT - 1)) & ~7U];
+ char *Token = NULL;
+ int index;
+ UINT8 bit;
+
+ if( (s1 == NULL)
+ && ((s1 = Next) == NULL))
+ {
+ return NULL;
+ }
+
+ // s2 can be different on each call, so build the bitmap each time.
+ BuildBitmap( bitmap, s2, sizeof(bitmap) / sizeof(UINT64));
+
+ // skip leading delimiters: all chars in s2
+ for( ; *s1 != '\0'; ++s1) {
+ index = WHICH8(*s1);
+ bit = WHICH_BIT(*s1);
+ if( (bitmap[index] & bit) == 0) break;
+ }
+ if( *s1 != 0)
+ {
+ // Remember this point, it is the start of the token
+ Token = s1++;
+
+ // find the next delimiter and replace it with a '\0'
+ for( ; *s1 != '\0'; ++s1) {
+ index = WHICH8(*s1);
+ bit = WHICH_BIT(*s1);
+ if( (bitmap[index] & bit) != 0) {
+ *s1++ = '\0';
+ Next = s1;
+ return Token;
+ }
+ }
+ }
+ Next = NULL;
+ return Token;
+}
|