StdLib/LibC/String/Searching.c

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