EmbeddedPkg: Extend NvVarStoreFormattedLib LIBRARY_CLASS

[mirror_edk2.git] / StdLib / LibC / String / Searching.c

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