Add device abstraction code for the UEFI Console and UEFI Shell-based file systems.

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

/** @file\r
    Search Functions for <wchar.h>.\r
\r
  Unless explicitly stated otherwise, the functions defined in this file order\r
  two wide characters the same way as two integers of the underlying integer\r
  type designated by wchar_t.\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
#include  <Library/MemoryAllocationLib.h>\r
\r
#include  <LibConfig.h>\r
\r
#include  <wchar.h>\r
\r
/* Data initialized by the library constructor */\r
extern  UINT8  *__wchar_bitmap;\r
extern  UINTN   __wchar_bitmap_size;\r
extern  UINTN   __wchar_bitmap_64;\r
\r
/** The wcschr function locates the first occurrence of c in the wide string\r
    pointed to by s.  The terminating null wide character is considered to be\r
    part of the wide string.\r
\r
    @return   The wcschr function returns a pointer to the located wide\r
              character, or a null pointer if the wide character does not occur\r
              in the wide string.\r
**/\r
wchar_t *wcschr(const wchar_t *s, wchar_t c)\r
{\r
  do {\r
    if( *s == c) {\r
      return (wchar_t *)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 short)(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 wchar_t *s2, UINTN n)\r
{\r
  UINT8 bit;\r
  UINTN 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
  (void)wmemset( (wchar_t *)bitmap, 0, n / sizeof(wchar_t));\r
  bitmap[0] = 1;\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] |= bit;\r
  }\r
}\r
\r
/** The wcscspn function computes the length of the maximum initial segment of\r
    the wide string pointed to by s1 which consists entirely of wide characters\r
    not from the wide string pointed to by s2.\r
\r
    @return   The wcscspn function returns the length of the segment.\r
**/\r
size_t wcscspn(const wchar_t *s1, const wchar_t *s2)\r
{\r
  const wchar_t *str;\r
  UINT8 bit;\r
  int index;\r
  size_t s1len;\r
\r
  if(*s1 == 0)   return 0;\r
  s1len = wcslen(s1);\r
\r
  BuildBitmap( __wchar_bitmap, s2, __wchar_bitmap_size);\r
\r
  for(str = s1; str < &s1[s1len] ; str++) {\r
    index = WHICH8(*str);\r
    bit = WHICH_BIT(*str);\r
    if ((__wchar_bitmap[index] & bit) != 0)\r
      break;\r
  }\r
  return (str - s1);\r
}\r
\r
/** The wcspbrk function locates the first occurrence in the wide string\r
    pointed to by s1 of any wide character from the wide string\r
    pointed to by s2.\r
\r
    @return   The wcspbrk function returns a pointer to the wide character\r
              in s1, or a null pointer if no wide character from s2 occurs\r
              in s1.\r
**/\r
wchar_t *wcspbrk(const wchar_t *s1, const wchar_t *s2)\r
{\r
  UINT8 bit;\r
  int index;\r
\r
  BuildBitmap( __wchar_bitmap, s2, __wchar_bitmap_size);\r
\r
  for( ; *s1 != 0; ++s1) {\r
    index = WHICH8(*s1);\r
    bit = WHICH_BIT(*s1);\r
    if( (__wchar_bitmap[index] & bit) != 0) {\r
      return (wchar_t *)s1;\r
    }\r
  }\r
  return NULL;\r
}\r
\r
/** The wcsrchr function locates the last occurrence of c in the wide string\r
    pointed to by s. The terminating null wide character is considered to be\r
    part of the wide string.\r
\r
    @return   The wcsrchr function returns a pointer to the wide character,\r
              or a null pointer if c does not occur in the wide string.\r
**/\r
wchar_t *wcsrchr(const wchar_t *s, wchar_t c)\r
{\r
  wchar_t  *found  = NULL;\r
\r
  do {\r
    if( *s == c)  found = (wchar_t *)s;\r
  } while( *s++ != 0);\r
\r
  return found;\r
}\r
\r
/** The wcsspn function computes the length of the maximum initial segment of\r
    the wide string pointed to by s1 which consists entirely of wide characters\r
    from the wide string pointed to by s2.\r
\r
    @return   The wcsspn function returns the length of the segment.\r
**/\r
size_t wcsspn(const wchar_t *s1, const wchar_t *s2)\r
{\r
  size_t  length = 0;\r
  int     index;\r
  UINT8   bit;\r
\r
  BuildBitmap( __wchar_bitmap, s2, __wchar_bitmap_size);\r
\r
  for( ; *s1 != 0; ++s1) {\r
    index = WHICH8(*s1);\r
    bit = WHICH_BIT(*s1);\r
    if( (__wchar_bitmap[index] & bit) == 0)   break;\r
    ++length;\r
  }\r
  return length;\r
}\r
\r
/** The wcsstr function locates the first occurrence in the wide string pointed\r
    to by s1 of the sequence of wide characters (excluding the terminating null\r
    wide character) in the wide string pointed to by s2.\r
\r
    @return   The wcsstr function returns a pointer to the located wide string,\r
              or a null pointer if the wide string is not found. If s2 points\r
              to a wide string with zero length, the function returns s1.\r
**/\r
wchar_t *wcsstr(const wchar_t *s1, const wchar_t *s2)\r
{\r
  return (wchar_t *)StrStr( (CONST CHAR16 *)s1, (CONST CHAR16 *)s2);\r
}\r
\r
/** A sequence of calls to the wcstok function breaks the wide string pointed\r
    to by s1 into a sequence of tokens, each of which is delimited by a wide\r
    character from the wide string pointed to by s2. The third argument points\r
    to a caller-provided wchar_t pointer into which the wcstok function stores\r
    information necessary for it to continue scanning the same wide string.\r
\r
    The first call in a sequence has a non-null first argument and stores an\r
    initial value in the object pointed to by ptr. Subsequent calls in the\r
    sequence have a null first argument and the object pointed to by ptr is\r
    required to have the value stored by the previous call in the sequence,\r
    which is then updated. The separator wide string pointed to by s2 may be\r
    different from call to call.\r
\r
    The first call in the sequence searches the wide string pointed to by s1\r
    for the first wide character that is not contained in the current separator\r
    wide string pointed to by s2. If no such wide character is found, then\r
    there are no tokens in the wide string pointed to by s1 and the wcstok\r
    function returns a null pointer. If such a wide character is found, it is\r
    the start of the first token.\r
\r
    The wcstok function then searches from there for a wide character that is\r
    contained in the current separator wide string. If no such wide character\r
    is found, the current token extends to the end of the wide string pointed\r
    to by s1, and subsequent searches in the same wide string for a token\r
    return a null pointer. If such a wide character is found, it is overwritten\r
    by a null wide character, which terminates the current token.\r
\r
    In all cases, the wcstok function stores sufficient information in the\r
    pointer pointed to by ptr so that subsequent calls, with a null pointer for\r
    s1 and the unmodified pointer value for ptr, shall start searching just\r
    past the element overwritten by a null wide character (if any).\r
\r
    @return   The wcstok function returns a pointer to the first wide character\r
              of a token, or a null pointer if there is no token.\r
**/\r
wchar_t *wcstok(wchar_t * __restrict s1, const wchar_t * __restrict s2, wchar_t ** __restrict ptr)\r
{\r
  wchar_t        *Token = NULL;\r
  int             index;\r
  UINT8           bit;\r
\r
  if(     (s1 == NULL)\r
      &&  ((s1 = *ptr) == NULL))\r
  {\r
    return  NULL;\r
  }\r
\r
  // s2 can be different on each call, so build the bitmap each time.\r
  BuildBitmap( __wchar_bitmap, s2, __wchar_bitmap_size);\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( (__wchar_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( (__wchar_bitmap[index] & bit) != 0) {\r
        *s1++ = 0;\r
        *ptr = s1;\r
        return Token;\r
      }\r
    }\r
  }\r
  *ptr = NULL;\r
  return Token;\r
}\r
\r
/** The wmemchr function locates the first occurrence of c in the initial n\r
    wide characters of the object pointed to by s.\r
\r
    @return   The wmemchr function returns a pointer to the located wide\r
              character, or a null pointer if the wide character does not occur\r
              in the object.\r
**/\r
wchar_t *wmemchr(const wchar_t *s, wchar_t c, size_t n)\r
{\r
  return (wchar_t *)ScanMem16( s, (UINTN)(n * sizeof(wchar_t)), (UINT16)c);\r
}\r