StdLib/LibC/Wchar/Searching.c

   1 /** @file
   2     Search Functions for <wchar.h>.
   3
   4   Unless explicitly stated otherwise, the functions defined in this file order
   5   two wide characters the same way as two integers of the underlying integer
   6   type designated by wchar_t.
   7
   8   Copyright (c) 2010 - 2011, Intel Corporation. All rights reserved.<BR>
   9   This program and the accompanying materials are licensed and made available under
  10   the terms and conditions of the BSD License that accompanies this distribution.
  11   The full text of the license may be found at
  12   http://opensource.org/licenses/bsd-license.php.
  13
  14   THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
  15   WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  16 **/
  17 #include  <Uefi.h>
  18 #include  <Library/BaseLib.h>
  19 #include  <Library/BaseMemoryLib.h>
  20 #include  <Library/MemoryAllocationLib.h>
  21
  22 #include  <LibConfig.h>
  23
  24 #include  <wchar.h>
  25
  26 /* Data initialized by the library constructor */
  27 extern  UINT8  *__wchar_bitmap;
  28 extern  UINTN   __wchar_bitmap_size;
  29 extern  UINTN   __wchar_bitmap_64;
  30
  31 /** The wcschr function locates the first occurrence of c in the wide string
  32     pointed to by s.  The terminating null wide character is considered to be
  33     part of the wide string.
  34
  35     @return   The wcschr function returns a pointer to the located wide
  36               character, or a null pointer if the wide character does not occur
  37               in the wide string.
  38 **/
  39 wchar_t *wcschr(const wchar_t *s, wchar_t c)
  40 {
  41   do {
  42     if( *s == c) {
  43       return (wchar_t *)s;
  44     }
  45   } while(*s++ != 0);
  46   return NULL;
  47 }
  48
  49 static UINT8  BitMask[] = {
  50   0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80
  51   };
  52
  53 #define WHICH8(c)     ((unsigned short)(c) >> 3)
  54 #define WHICH_BIT(c)  (BitMask[((c) & 0x7)])
  55 #define BITMAP64      ((UINT64 *)bitmap)
  56
  57 static
  58 void
  59 BuildBitmap(unsigned char * bitmap, const wchar_t *s2, UINTN n)
  60 {
  61   UINT8 bit;
  62   UINTN index;
  63
  64   //// Initialize bitmap.  Bit 0 is always 1 which corresponds to '\0'
  65   //for (BITMAP64[0] = index = 1; index < n; index++)
  66   //  BITMAP64[index] = 0;
  67   (void)wmemset( (wchar_t *)bitmap, 0, n / sizeof(wchar_t));
  68   bitmap[0] = 1;
  69
  70   // Set bits in bitmap corresponding to the characters in s2
  71   for (; *s2 != 0; ++s2) {
  72     index = WHICH8(*s2);
  73     bit = WHICH_BIT(*s2);
  74     bitmap[index] |= bit;
  75   }
  76 }
  77
  78 /** The wcscspn function computes the length of the maximum initial segment of
  79     the wide string pointed to by s1 which consists entirely of wide characters
  80     not from the wide string pointed to by s2.
  81
  82     @return   The wcscspn function returns the length of the segment.
  83 **/
  84 size_t wcscspn(const wchar_t *s1, const wchar_t *s2)
  85 {
  86   const wchar_t *str;
  87   UINT8 bit;
  88   int index;
  89   size_t s1len;
  90
  91   if(*s1 == 0)   return 0;
  92   s1len = wcslen(s1);
  93
  94   BuildBitmap( __wchar_bitmap, s2, __wchar_bitmap_size);
  95
  96   for(str = s1; str < &s1[s1len] ; str++) {
  97     index = WHICH8(*str);
  98     bit = WHICH_BIT(*str);
  99     if ((__wchar_bitmap[index] & bit) != 0)
 100       break;
 101   }
 102   return (str - s1);
 103 }
 104
 105 /** The wcspbrk function locates the first occurrence in the wide string
 106     pointed to by s1 of any wide character from the wide string
 107     pointed to by s2.
 108
 109     @return   The wcspbrk function returns a pointer to the wide character
 110               in s1, or a null pointer if no wide character from s2 occurs
 111               in s1.
 112 **/
 113 wchar_t *wcspbrk(const wchar_t *s1, const wchar_t *s2)
 114 {
 115   UINT8 bit;
 116   int index;
 117
 118   BuildBitmap( __wchar_bitmap, s2, __wchar_bitmap_size);
 119
 120   for( ; *s1 != 0; ++s1) {
 121     index = WHICH8(*s1);
 122     bit = WHICH_BIT(*s1);
 123     if( (__wchar_bitmap[index] & bit) != 0) {
 124       return (wchar_t *)s1;
 125     }
 126   }
 127   return NULL;
 128 }
 129
 130 /** The wcsrchr function locates the last occurrence of c in the wide string
 131     pointed to by s. The terminating null wide character is considered to be
 132     part of the wide string.
 133
 134     @return   The wcsrchr function returns a pointer to the wide character,
 135               or a null pointer if c does not occur in the wide string.
 136 **/
 137 wchar_t *wcsrchr(const wchar_t *s, wchar_t c)
 138 {
 139   wchar_t  *found  = NULL;
 140
 141   do {
 142     if( *s == c)  found = (wchar_t *)s;
 143   } while( *s++ != 0);
 144
 145   return found;
 146 }
 147
 148 /** The wcsspn function computes the length of the maximum initial segment of
 149     the wide string pointed to by s1 which consists entirely of wide characters
 150     from the wide string pointed to by s2.
 151
 152     @return   The wcsspn function returns the length of the segment.
 153 **/
 154 size_t wcsspn(const wchar_t *s1, const wchar_t *s2)
 155 {
 156   size_t  length = 0;
 157   int     index;
 158   UINT8   bit;
 159
 160   BuildBitmap( __wchar_bitmap, s2, __wchar_bitmap_size);
 161
 162   for( ; *s1 != 0; ++s1) {
 163     index = WHICH8(*s1);
 164     bit = WHICH_BIT(*s1);
 165     if( (__wchar_bitmap[index] & bit) == 0)   break;
 166     ++length;
 167   }
 168   return length;
 169 }
 170
 171 /** The wcsstr function locates the first occurrence in the wide string pointed
 172     to by s1 of the sequence of wide characters (excluding the terminating null
 173     wide character) in the wide string pointed to by s2.
 174
 175     @return   The wcsstr function returns a pointer to the located wide string,
 176               or a null pointer if the wide string is not found. If s2 points
 177               to a wide string with zero length, the function returns s1.
 178 **/
 179 wchar_t *wcsstr(const wchar_t *s1, const wchar_t *s2)
 180 {
 181   return (wchar_t *)StrStr( (CONST CHAR16 *)s1, (CONST CHAR16 *)s2);
 182 }
 183
 184 /** A sequence of calls to the wcstok function breaks the wide string pointed
 185     to by s1 into a sequence of tokens, each of which is delimited by a wide
 186     character from the wide string pointed to by s2. The third argument points
 187     to a caller-provided wchar_t pointer into which the wcstok function stores
 188     information necessary for it to continue scanning the same wide string.
 189
 190     The first call in a sequence has a non-null first argument and stores an
 191     initial value in the object pointed to by ptr. Subsequent calls in the
 192     sequence have a null first argument and the object pointed to by ptr is
 193     required to have the value stored by the previous call in the sequence,
 194     which is then updated. The separator wide string pointed to by s2 may be
 195     different from call to call.
 196
 197     The first call in the sequence searches the wide string pointed to by s1
 198     for the first wide character that is not contained in the current separator
 199     wide string pointed to by s2. If no such wide character is found, then
 200     there are no tokens in the wide string pointed to by s1 and the wcstok
 201     function returns a null pointer. If such a wide character is found, it is
 202     the start of the first token.
 203
 204     The wcstok function then searches from there for a wide character that is
 205     contained in the current separator wide string. If no such wide character
 206     is found, the current token extends to the end of the wide string pointed
 207     to by s1, and subsequent searches in the same wide string for a token
 208     return a null pointer. If such a wide character is found, it is overwritten
 209     by a null wide character, which terminates the current token.
 210
 211     In all cases, the wcstok function stores sufficient information in the
 212     pointer pointed to by ptr so that subsequent calls, with a null pointer for
 213     s1 and the unmodified pointer value for ptr, shall start searching just
 214     past the element overwritten by a null wide character (if any).
 215
 216     @return   The wcstok function returns a pointer to the first wide character
 217               of a token, or a null pointer if there is no token.
 218 **/
 219 wchar_t *wcstok(wchar_t * __restrict s1, const wchar_t * __restrict s2, wchar_t ** __restrict ptr)
 220 {
 221   wchar_t        *Token = NULL;
 222   int             index;
 223   UINT8           bit;
 224
 225   if(     (s1 == NULL)
 226       &&  ((s1 = *ptr) == NULL))
 227   {
 228     return  NULL;
 229   }
 230
 231   // s2 can be different on each call, so build the bitmap each time.
 232   BuildBitmap( __wchar_bitmap, s2, __wchar_bitmap_size);
 233
 234   // skip leading delimiters: all chars in s2
 235   for( ; *s1 != 0; ++s1) {
 236     index = WHICH8(*s1);
 237     bit = WHICH_BIT(*s1);
 238     if( (__wchar_bitmap[index] & bit) == 0)   break;
 239   }
 240   if( *s1 != 0)
 241   {
 242     // Remember this point, it is the start of the token
 243     Token = s1++;
 244
 245     // find the next delimiter and replace it with a '\0'
 246     for( ; *s1 != 0; ++s1) {
 247       index = WHICH8(*s1);
 248       bit = WHICH_BIT(*s1);
 249       if( (__wchar_bitmap[index] & bit) != 0) {
 250         *s1++ = 0;
 251         *ptr = s1;
 252         return Token;
 253       }
 254     }
 255   }
 256   *ptr = NULL;
 257   return Token;
 258 }
 259
 260 /** The wmemchr function locates the first occurrence of c in the initial n
 261     wide characters of the object pointed to by s.
 262
 263     @return   The wmemchr function returns a pointer to the located wide
 264               character, or a null pointer if the wide character does not occur
 265               in the object.
 266 **/
 267 wchar_t *wmemchr(const wchar_t *s, wchar_t c, size_t n)
 268 {
 269   return (wchar_t *)ScanMem16( s, (UINTN)(n * sizeof(wchar_t)), (UINT16)c);
 270 }