l4/pkg/l4re-core/uclibc/lib/contrib/uclibc/libc/misc/fnmatch/fnmatch_loop.c

   1 /* Copyright (C) 1991,1992,1993,1996,1997,1998,1999,2000,2001,2003,2004,2005
   2    Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <http://www.gnu.org/licenses/>.  */
  18
  19 /* Match STRING against the filename pattern PATTERN, returning zero if
  20    it matches, nonzero if not.  */
  21 static int FCT (const CHAR *pattern, const CHAR *string,
  22                 const CHAR *string_end, int no_leading_period, int flags)
  23      internal_function;
  24 static int EXT (INT opt, const CHAR *pattern, const CHAR *string,
  25                 const CHAR *string_end, int no_leading_period, int flags)
  26      internal_function;
  27 static const CHAR *END (const CHAR *patternp) internal_function;
  28
  29 static int
  30 internal_function
  31 FCT (const CHAR *pattern, const CHAR *string, const CHAR *string_end,
  32      int no_leading_period, int flags)
  33 {
  34   register const CHAR *p = pattern, *n = string;
  35   register UCHAR c;
  36 #ifdef _LIBC
  37 # if WIDE_CHAR_VERSION
  38   const char *collseq = (const char *)
  39     _NL_CURRENT(LC_COLLATE, _NL_COLLATE_COLLSEQWC);
  40 # else
  41   const UCHAR *collseq = (const UCHAR *)
  42     _NL_CURRENT(LC_COLLATE, _NL_COLLATE_COLLSEQMB);
  43 # endif
  44 #endif
  45
  46   while ((c = *p++) != L('\0'))
  47     {
  48       int new_no_leading_period = 0;
  49       c = FOLD (c);
  50
  51       switch (c)
  52         {
  53         case L('?'):
  54           if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
  55             {
  56               int res;
  57
  58               res = EXT (c, p, n, string_end, no_leading_period,
  59                          flags);
  60               if (res != -1)
  61                 return res;
  62             }
  63
  64           if (n == string_end)
  65             return FNM_NOMATCH;
  66           else if (*n == L('/') && (flags & FNM_FILE_NAME))
  67             return FNM_NOMATCH;
  68           else if (*n == L('.') && no_leading_period)
  69             return FNM_NOMATCH;
  70           break;
  71
  72         case L('\\'):
  73           if (!(flags & FNM_NOESCAPE))
  74             {
  75               c = *p++;
  76               if (c == L('\0'))
  77                 /* Trailing \ loses.  */
  78                 return FNM_NOMATCH;
  79               c = FOLD (c);
  80             }
  81           if (n == string_end || FOLD ((UCHAR) *n) != c)
  82             return FNM_NOMATCH;
  83           break;
  84
  85         case L('*'):
  86           if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
  87             {
  88               int res;
  89
  90               res = EXT (c, p, n, string_end, no_leading_period,
  91                          flags);
  92               if (res != -1)
  93                 return res;
  94             }
  95
  96           if (n != string_end && *n == L('.') && no_leading_period)
  97             return FNM_NOMATCH;
  98
  99           for (c = *p++; c == L('?') || c == L('*'); c = *p++)
 100             {
 101               if (*p == L('(') && (flags & FNM_EXTMATCH) != 0)
 102                 {
 103                   const CHAR *endp = END (p);
 104                   if (endp != p)
 105                     {
 106                       /* This is a pattern.  Skip over it.  */
 107                       p = endp;
 108                       continue;
 109                     }
 110                 }
 111
 112               if (c == L('?'))
 113                 {
 114                   /* A ? needs to match one character.  */
 115                   if (n == string_end)
 116                     /* There isn't another character; no match.  */
 117                     return FNM_NOMATCH;
 118                   else if (*n == L('/')
 119                            && __builtin_expect (flags & FNM_FILE_NAME, 0))
 120                     /* A slash does not match a wildcard under
 121                        FNM_FILE_NAME.  */
 122                     return FNM_NOMATCH;
 123                   else
 124                     /* One character of the string is consumed in matching
 125                        this ? wildcard, so *??? won't match if there are
 126                        less than three characters.  */
 127                     ++n;
 128                 }
 129             }
 130
 131           if (c == L('\0'))
 132             /* The wildcard(s) is/are the last element of the pattern.
 133                If the name is a file name and contains another slash
 134                this means it cannot match, unless the FNM_LEADING_DIR
 135                flag is set.  */
 136             {
 137               int result = (flags & FNM_FILE_NAME) == 0 ? 0 : FNM_NOMATCH;
 138
 139               if (flags & FNM_FILE_NAME)
 140                 {
 141                   if (flags & FNM_LEADING_DIR)
 142                     result = 0;
 143                   else
 144                     {
 145                       if (MEMCHR (n, L('/'), string_end - n) == NULL)
 146                         result = 0;
 147                     }
 148                 }
 149
 150               return result;
 151             }
 152           else
 153             {
 154               const CHAR *endp;
 155
 156               endp = MEMCHR (n, (flags & FNM_FILE_NAME) ? L('/') : L('\0'),
 157                              string_end - n);
 158               if (endp == NULL)
 159                 endp = string_end;
 160
 161               if (c == L('[')
 162                   || (__builtin_expect (flags & FNM_EXTMATCH, 0) != 0
 163                       && (c == L('@') || c == L('+') || c == L('!'))
 164                       && *p == L('(')))
 165                 {
 166                   int flags2 = ((flags & FNM_FILE_NAME)
 167                                 ? flags : (flags & ~FNM_PERIOD));
 168                   int no_leading_period2 = no_leading_period;
 169
 170                   for (--p; n < endp; ++n, no_leading_period2 = 0)
 171                     if (FCT (p, n, string_end, no_leading_period2, flags2)
 172                         == 0)
 173                       return 0;
 174                 }
 175               else if (c == L('/') && (flags & FNM_FILE_NAME))
 176                 {
 177                   while (n < string_end && *n != L('/'))
 178                     ++n;
 179                   if (n < string_end && *n == L('/')
 180                       && (FCT (p, n + 1, string_end, flags & FNM_PERIOD, flags)
 181                           == 0))
 182                     return 0;
 183                 }
 184               else
 185                 {
 186                   int flags2 = ((flags & FNM_FILE_NAME)
 187                                 ? flags : (flags & ~FNM_PERIOD));
 188                   int no_leading_period2 = no_leading_period;
 189
 190                   if (c == L('\\') && !(flags & FNM_NOESCAPE))
 191                     c = *p;
 192                   c = FOLD (c);
 193                   for (--p; n < endp; ++n, no_leading_period2 = 0)
 194                     if (FOLD ((UCHAR) *n) == c
 195                         && (FCT (p, n, string_end, no_leading_period2, flags2)
 196                             == 0))
 197                       return 0;
 198                 }
 199             }
 200
 201           /* If we come here no match is possible with the wildcard.  */
 202           return FNM_NOMATCH;
 203
 204         case L('['):
 205           {
 206             /* Nonzero if the sense of the character class is inverted.  */
 207             register int not;
 208             CHAR cold;
 209             UCHAR fn;
 210
 211             if (posixly_correct == 0)
 212               posixly_correct = getenv ("POSIXLY_CORRECT") != NULL ? 1 : -1;
 213
 214             if (n == string_end)
 215               return FNM_NOMATCH;
 216
 217             if (*n == L('.') && no_leading_period)
 218               return FNM_NOMATCH;
 219
 220             if (*n == L('/') && (flags & FNM_FILE_NAME))
 221               /* `/' cannot be matched.  */
 222               return FNM_NOMATCH;
 223
 224             not = (*p == L('!') || (posixly_correct < 0 && *p == L('^')));
 225             if (not)
 226               ++p;
 227
 228             fn = FOLD ((UCHAR) *n);
 229
 230             c = *p++;
 231             for (;;)
 232               {
 233                 if (!(flags & FNM_NOESCAPE) && c == L('\\'))
 234                   {
 235                     if (*p == L('\0'))
 236                       return FNM_NOMATCH;
 237                     c = FOLD ((UCHAR) *p);
 238                     ++p;
 239
 240                     goto normal_bracket;
 241                   }
 242                 else if (c == L('[') && *p == L(':'))
 243                   {
 244                     /* Leave room for the null.  */
 245                     CHAR str[CHAR_CLASS_MAX_LENGTH + 1];
 246                     size_t c1 = 0;
 247 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
 248                     wctype_t wt;
 249 #endif
 250                     const CHAR *startp = p;
 251
 252                     for (;;)
 253                       {
 254                         if (c1 == CHAR_CLASS_MAX_LENGTH)
 255                           /* The name is too long and therefore the pattern
 256                              is ill-formed.  */
 257                           return FNM_NOMATCH;
 258
 259                         c = *++p;
 260                         if (c == L(':') && p[1] == L(']'))
 261                           {
 262                             p += 2;
 263                             break;
 264                           }
 265                         if (c < L('a') || c >= L('z'))
 266                           {
 267                             /* This cannot possibly be a character class name.
 268                                Match it as a normal range.  */
 269                             p = startp;
 270                             c = L('[');
 271                             goto normal_bracket;
 272                           }
 273                         str[c1++] = c;
 274                       }
 275                     str[c1] = L('\0');
 276
 277 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
 278                     wt = IS_CHAR_CLASS (str);
 279                     if (wt == 0)
 280                       /* Invalid character class name.  */
 281                       return FNM_NOMATCH;
 282
 283 # if defined _LIBC && ! WIDE_CHAR_VERSION
 284                     /* The following code is glibc specific but does
 285                        there a good job in speeding up the code since
 286                        we can avoid the btowc() call.  */
 287                     if (_ISCTYPE ((UCHAR) *n, wt))
 288                       goto matched;
 289 # else
 290                     if (ISWCTYPE (BTOWC ((UCHAR) *n), wt))
 291                       goto matched;
 292 # endif
 293 #else
 294                     if ((STREQ (str, L("alnum")) && ISALNUM ((UCHAR) *n))
 295                         || (STREQ (str, L("alpha")) && ISALPHA ((UCHAR) *n))
 296                         || (STREQ (str, L("blank")) && ISBLANK ((UCHAR) *n))
 297                         || (STREQ (str, L("cntrl")) && ISCNTRL ((UCHAR) *n))
 298                         || (STREQ (str, L("digit")) && ISDIGIT ((UCHAR) *n))
 299                         || (STREQ (str, L("graph")) && ISGRAPH ((UCHAR) *n))
 300                         || (STREQ (str, L("lower")) && ISLOWER ((UCHAR) *n))
 301                         || (STREQ (str, L("print")) && ISPRINT ((UCHAR) *n))
 302                         || (STREQ (str, L("punct")) && ISPUNCT ((UCHAR) *n))
 303                         || (STREQ (str, L("space")) && ISSPACE ((UCHAR) *n))
 304                         || (STREQ (str, L("upper")) && ISUPPER ((UCHAR) *n))
 305                         || (STREQ (str, L("xdigit")) && ISXDIGIT ((UCHAR) *n)))
 306                       goto matched;
 307 #endif
 308                     c = *p++;
 309                   }
 310 #ifdef _LIBC
 311                 else if (c == L('[') && *p == L('='))
 312                   {
 313                     UCHAR str[1];
 314                     uint32_t nrules =
 315                       _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
 316                     const CHAR *startp = p;
 317
 318                     c = *++p;
 319                     if (c == L('\0'))
 320                       {
 321                         p = startp;
 322                         c = L('[');
 323                         goto normal_bracket;
 324                       }
 325                     str[0] = c;
 326
 327                     c = *++p;
 328                     if (c != L('=') || p[1] != L(']'))
 329                       {
 330                         p = startp;
 331                         c = L('[');
 332                         goto normal_bracket;
 333                       }
 334                     p += 2;
 335
 336                     if (nrules == 0)
 337                       {
 338                         if ((UCHAR) *n == str[0])
 339                           goto matched;
 340                       }
 341                     else
 342                       {
 343                         const int32_t *table;
 344 # if WIDE_CHAR_VERSION
 345                         const int32_t *weights;
 346                         const int32_t *extra;
 347 # else
 348                         const unsigned char *weights;
 349                         const unsigned char *extra;
 350 # endif
 351                         const int32_t *indirect;
 352                         int32_t idx;
 353                         const UCHAR *cp = (const UCHAR *) str;
 354
 355                         /* This #include defines a local function!  */
 356 # if WIDE_CHAR_VERSION
 357 #  include <locale/weightwc.h>
 358 # else
 359 #  include <locale/weight.h>
 360 # endif
 361
 362 # if WIDE_CHAR_VERSION
 363                         table = (const int32_t *)
 364                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEWC);
 365                         weights = (const int32_t *)
 366                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTWC);
 367                         extra = (const int32_t *)
 368                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAWC);
 369                         indirect = (const int32_t *)
 370                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTWC);
 371 # else
 372                         table = (const int32_t *)
 373                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
 374                         weights = (const unsigned char *)
 375                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
 376                         extra = (const unsigned char *)
 377                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
 378                         indirect = (const int32_t *)
 379                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
 380 # endif
 381
 382                         idx = findidx (&cp);
 383                         if (idx != 0)
 384                           {
 385                             /* We found a table entry.  Now see whether the
 386                                character we are currently at has the same
 387                                equivalance class value.  */
 388                             int len = weights[idx];
 389                             int32_t idx2;
 390                             const UCHAR *np = (const UCHAR *) n;
 391
 392                             idx2 = findidx (&np);
 393                             if (idx2 != 0 && len == weights[idx2])
 394                               {
 395                                 int cnt = 0;
 396
 397                                 while (cnt < len
 398                                        && (weights[idx + 1 + cnt]
 399                                            == weights[idx2 + 1 + cnt]))
 400                                   ++cnt;
 401
 402                                 if (cnt == len)
 403                                   goto matched;
 404                               }
 405                           }
 406                       }
 407
 408                     c = *p++;
 409                   }
 410 #endif
 411                 else if (c == L('\0'))
 412                   /* [ (unterminated) loses.  */
 413                   return FNM_NOMATCH;
 414                 else
 415                   {
 416                     int is_range = 0;
 417
 418 #ifdef _LIBC
 419                     int is_seqval = 0;
 420
 421                     if (c == L('[') && *p == L('.'))
 422                       {
 423                         uint32_t nrules =
 424                           _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
 425                         const CHAR *startp = p;
 426                         size_t c1 = 0;
 427
 428                         while (1)
 429                           {
 430                             c = *++p;
 431                             if (c == L('.') && p[1] == L(']'))
 432                               {
 433                                 p += 2;
 434                                 break;
 435                               }
 436                             if (c == '\0')
 437                               return FNM_NOMATCH;
 438                             ++c1;
 439                           }
 440
 441                         /* We have to handling the symbols differently in
 442                            ranges since then the collation sequence is
 443                            important.  */
 444                         is_range = *p == L('-') && p[1] != L('\0');
 445
 446                         if (nrules == 0)
 447                           {
 448                             /* There are no names defined in the collation
 449                                data.  Therefore we only accept the trivial
 450                                names consisting of the character itself.  */
 451                             if (c1 != 1)
 452                               return FNM_NOMATCH;
 453
 454                             if (!is_range && *n == startp[1])
 455                               goto matched;
 456
 457                             cold = startp[1];
 458                             c = *p++;
 459                           }
 460                         else
 461                           {
 462                             int32_t table_size;
 463                             const int32_t *symb_table;
 464 # ifdef WIDE_CHAR_VERSION
 465                             char str[c1];
 466                             unsigned int strcnt;
 467 # else
 468 #  define str (startp + 1)
 469 # endif
 470                             const unsigned char *extra;
 471                             int32_t idx;
 472                             int32_t elem;
 473                             int32_t second;
 474                             int32_t hash;
 475
 476 # ifdef WIDE_CHAR_VERSION
 477                             /* We have to convert the name to a single-byte
 478                                string.  This is possible since the names
 479                                consist of ASCII characters and the internal
 480                                representation is UCS4.  */
 481                             for (strcnt = 0; strcnt < c1; ++strcnt)
 482                               str[strcnt] = startp[1 + strcnt];
 483 #endif
 484
 485                             table_size =
 486                               _NL_CURRENT_WORD (LC_COLLATE,
 487                                                 _NL_COLLATE_SYMB_HASH_SIZEMB);
 488                             symb_table = (const int32_t *)
 489                               _NL_CURRENT (LC_COLLATE,
 490                                            _NL_COLLATE_SYMB_TABLEMB);
 491                             extra = (const unsigned char *)
 492                               _NL_CURRENT (LC_COLLATE,
 493                                            _NL_COLLATE_SYMB_EXTRAMB);
 494
 495                             /* Locate the character in the hashing table.  */
 496                             hash = elem_hash (str, c1);
 497
 498                             idx = 0;
 499                             elem = hash % table_size;
 500                             if (symb_table[2 * elem] != 0)
 501                               {
 502                                 second = hash % (table_size - 2) + 1;
 503
 504                                 do
 505                                   {
 506                                     /* First compare the hashing value.  */
 507                                     if (symb_table[2 * elem] == hash
 508                                         && (c1
 509                                             == extra[symb_table[2 * elem + 1]])
 510                                         && memcmp (str,
 511                                                    &extra[symb_table[2 * elem
 512                                                                      + 1]
 513                                                           + 1], c1) == 0)
 514                                       {
 515                                         /* Yep, this is the entry.  */
 516                                         idx = symb_table[2 * elem + 1];
 517                                         idx += 1 + extra[idx];
 518                                         break;
 519                                       }
 520
 521                                     /* Next entry.  */
 522                                     elem += second;
 523                                   }
 524                                 while (symb_table[2 * elem] != 0);
 525                               }
 526
 527                             if (symb_table[2 * elem] != 0)
 528                               {
 529                                 /* Compare the byte sequence but only if
 530                                    this is not part of a range.  */
 531 # ifdef WIDE_CHAR_VERSION
 532                                 int32_t *wextra;
 533
 534                                 idx += 1 + extra[idx];
 535                                 /* Adjust for the alignment.  */
 536                                 idx = (idx + 3) & ~3;
 537
 538                                 wextra = (int32_t *) &extra[idx + 4];
 539 # endif
 540
 541                                 if (! is_range)
 542                                   {
 543 # ifdef WIDE_CHAR_VERSION
 544                                     for (c1 = 0;
 545                                          (int32_t) c1 < wextra[idx];
 546                                          ++c1)
 547                                       if (n[c1] != wextra[1 + c1])
 548                                         break;
 549
 550                                     if ((int32_t) c1 == wextra[idx])
 551                                       goto matched;
 552 # else
 553                                     for (c1 = 0; c1 < extra[idx]; ++c1)
 554                                       if (n[c1] != extra[1 + c1])
 555                                         break;
 556
 557                                     if (c1 == extra[idx])
 558                                       goto matched;
 559 # endif
 560                                   }
 561
 562                                 /* Get the collation sequence value.  */
 563                                 is_seqval = 1;
 564 # ifdef WIDE_CHAR_VERSION
 565                                 cold = wextra[1 + wextra[idx]];
 566 # else
 567                                 /* Adjust for the alignment.  */
 568                                 idx += 1 + extra[idx];
 569                                 idx = (idx + 3) & ~4;
 570                                 cold = *((int32_t *) &extra[idx]);
 571 # endif
 572
 573                                 c = *p++;
 574                               }
 575                             else if (c1 == 1)
 576                               {
 577                                 /* No valid character.  Match it as a
 578                                    single byte.  */
 579                                 if (!is_range && *n == str[0])
 580                                   goto matched;
 581
 582                                 cold = str[0];
 583                                 c = *p++;
 584                               }
 585                             else
 586                               return FNM_NOMATCH;
 587                           }
 588                       }
 589                     else
 590 # undef str
 591 #endif
 592                       {
 593                         c = FOLD (c);
 594                       normal_bracket:
 595
 596                         /* We have to handling the symbols differently in
 597                            ranges since then the collation sequence is
 598                            important.  */
 599                         is_range = (*p == L('-') && p[1] != L('\0')
 600                                     && p[1] != L(']'));
 601
 602                         if (!is_range && c == fn)
 603                           goto matched;
 604
 605                         /* This is needed if we goto normal_bracket; from
 606                            outside of is_seqval's scope.  */
 607 #ifndef __UCLIBC__ /* this should be probably ifdef _LIBC*/
 608                         is_seqval = 0;
 609 #endif
 610                         cold = c;
 611                         c = *p++;
 612                       }
 613
 614                     if (c == L('-') && *p != L(']'))
 615                       {
 616 #if _LIBC
 617                         /* We have to find the collation sequence
 618                            value for C.  Collation sequence is nothing
 619                            we can regularly access.  The sequence
 620                            value is defined by the order in which the
 621                            definitions of the collation values for the
 622                            various characters appear in the source
 623                            file.  A strange concept, nowhere
 624                            documented.  */
 625                         uint32_t fcollseq;
 626                         uint32_t lcollseq;
 627                         UCHAR cend = *p++;
 628
 629 # ifdef WIDE_CHAR_VERSION
 630                         /* Search in the `names' array for the characters.  */
 631                         fcollseq = __collseq_table_lookup (collseq, fn);
 632                         if (fcollseq == ~((uint32_t) 0))
 633                           /* XXX We don't know anything about the character
 634                              we are supposed to match.  This means we are
 635                              failing.  */
 636                           goto range_not_matched;
 637
 638                         if (is_seqval)
 639                           lcollseq = cold;
 640                         else
 641                           lcollseq = __collseq_table_lookup (collseq, cold);
 642 # else
 643                         fcollseq = collseq[fn];
 644                         lcollseq = is_seqval ? cold : collseq[(UCHAR) cold];
 645 # endif
 646
 647                         is_seqval = 0;
 648                         if (cend == L('[') && *p == L('.'))
 649                           {
 650                             uint32_t nrules =
 651                               _NL_CURRENT_WORD (LC_COLLATE,
 652                                                 _NL_COLLATE_NRULES);
 653                             const CHAR *startp = p;
 654                             size_t c1 = 0;
 655
 656                             while (1)
 657                               {
 658                                 c = *++p;
 659                                 if (c == L('.') && p[1] == L(']'))
 660                                   {
 661                                     p += 2;
 662                                     break;
 663                                   }
 664                                 if (c == '\0')
 665                                   return FNM_NOMATCH;
 666                                 ++c1;
 667                               }
 668
 669                             if (nrules == 0)
 670                               {
 671                                 /* There are no names defined in the
 672                                    collation data.  Therefore we only
 673                                    accept the trivial names consisting
 674                                    of the character itself.  */
 675                                 if (c1 != 1)
 676                                   return FNM_NOMATCH;
 677
 678                                 cend = startp[1];
 679                               }
 680                             else
 681                               {
 682                                 int32_t table_size;
 683                                 const int32_t *symb_table;
 684 # ifdef WIDE_CHAR_VERSION
 685                                 char str[c1];
 686                                 unsigned int strcnt;
 687 # else
 688 #  define str (startp + 1)
 689 # endif
 690                                 const unsigned char *extra;
 691                                 int32_t idx;
 692                                 int32_t elem;
 693                                 int32_t second;
 694                                 int32_t hash;
 695
 696 # ifdef WIDE_CHAR_VERSION
 697                                 /* We have to convert the name to a single-byte
 698                                    string.  This is possible since the names
 699                                    consist of ASCII characters and the internal
 700                                    representation is UCS4.  */
 701                                 for (strcnt = 0; strcnt < c1; ++strcnt)
 702                                   str[strcnt] = startp[1 + strcnt];
 703 # endif
 704
 705                                 table_size =
 706                                   _NL_CURRENT_WORD (LC_COLLATE,
 707                                                     _NL_COLLATE_SYMB_HASH_SIZEMB);
 708                                 symb_table = (const int32_t *)
 709                                   _NL_CURRENT (LC_COLLATE,
 710                                                _NL_COLLATE_SYMB_TABLEMB);
 711                                 extra = (const unsigned char *)
 712                                   _NL_CURRENT (LC_COLLATE,
 713                                                _NL_COLLATE_SYMB_EXTRAMB);
 714
 715                                 /* Locate the character in the hashing
 716                                    table.  */
 717                                 hash = elem_hash (str, c1);
 718
 719                                 idx = 0;
 720                                 elem = hash % table_size;
 721                                 if (symb_table[2 * elem] != 0)
 722                                   {
 723                                     second = hash % (table_size - 2) + 1;
 724
 725                                     do
 726                                       {
 727                                         /* First compare the hashing value.  */
 728                                         if (symb_table[2 * elem] == hash
 729                                             && (c1
 730                                                 == extra[symb_table[2 * elem + 1]])
 731                                             && memcmp (str,
 732                                                        &extra[symb_table[2 * elem + 1]
 733                                                               + 1], c1) == 0)
 734                                           {
 735                                             /* Yep, this is the entry.  */
 736                                             idx = symb_table[2 * elem + 1];
 737                                             idx += 1 + extra[idx];
 738                                             break;
 739                                           }
 740
 741                                         /* Next entry.  */
 742                                         elem += second;
 743                                       }
 744                                     while (symb_table[2 * elem] != 0);
 745                                   }
 746
 747                                 if (symb_table[2 * elem] != 0)
 748                                   {
 749                                     /* Compare the byte sequence but only if
 750                                        this is not part of a range.  */
 751 # ifdef WIDE_CHAR_VERSION
 752                                     int32_t *wextra;
 753
 754                                     idx += 1 + extra[idx];
 755                                     /* Adjust for the alignment.  */
 756                                     idx = (idx + 3) & ~4;
 757
 758                                     wextra = (int32_t *) &extra[idx + 4];
 759 # endif
 760                                     /* Get the collation sequence value.  */
 761                                     is_seqval = 1;
 762 # ifdef WIDE_CHAR_VERSION
 763                                     cend = wextra[1 + wextra[idx]];
 764 # else
 765                                     /* Adjust for the alignment.  */
 766                                     idx += 1 + extra[idx];
 767                                     idx = (idx + 3) & ~4;
 768                                     cend = *((int32_t *) &extra[idx]);
 769 # endif
 770                                   }
 771                                 else if (symb_table[2 * elem] != 0 && c1 == 1)
 772                                   {
 773                                     cend = str[0];
 774                                     c = *p++;
 775                                   }
 776                                 else
 777                                   return FNM_NOMATCH;
 778                               }
 779 # undef str
 780                           }
 781                         else
 782                           {
 783                             if (!(flags & FNM_NOESCAPE) && cend == L('\\'))
 784                               cend = *p++;
 785                             if (cend == L('\0'))
 786                               return FNM_NOMATCH;
 787                             cend = FOLD (cend);
 788                           }
 789
 790                         /* XXX It is not entirely clear to me how to handle
 791                            characters which are not mentioned in the
 792                            collation specification.  */
 793                         if (
 794 # ifdef WIDE_CHAR_VERSION
 795                             lcollseq == 0xffffffff ||
 796 # endif
 797                             lcollseq <= fcollseq)
 798                           {
 799                             /* We have to look at the upper bound.  */
 800                             uint32_t hcollseq;
 801
 802                             if (is_seqval)
 803                               hcollseq = cend;
 804                             else
 805                               {
 806 # ifdef WIDE_CHAR_VERSION
 807                                 hcollseq =
 808                                   __collseq_table_lookup (collseq, cend);
 809                                 if (hcollseq == ~((uint32_t) 0))
 810                                   {
 811                                     /* Hum, no information about the upper
 812                                        bound.  The matching succeeds if the
 813                                        lower bound is matched exactly.  */
 814                                     if (lcollseq != fcollseq)
 815                                       goto range_not_matched;
 816
 817                                     goto matched;
 818                                   }
 819 # else
 820                                 hcollseq = collseq[cend];
 821 # endif
 822                               }
 823
 824                             if (lcollseq <= hcollseq && fcollseq <= hcollseq)
 825                               goto matched;
 826                           }
 827 # ifdef WIDE_CHAR_VERSION
 828                       range_not_matched:
 829 # endif
 830 #else
 831                         /* We use a boring value comparison of the character
 832                            values.  This is better than comparing using
 833                            `strcoll' since the latter would have surprising
 834                            and sometimes fatal consequences.  */
 835                         UCHAR cend = *p++;
 836
 837                         if (!(flags & FNM_NOESCAPE) && cend == L('\\'))
 838                           cend = *p++;
 839                         if (cend == L('\0'))
 840                           return FNM_NOMATCH;
 841
 842                         /* It is a range.  */
 843                         if (cold <= fn && fn <= cend)
 844                           goto matched;
 845 #endif
 846
 847                         c = *p++;
 848                       }
 849                   }
 850
 851                 if (c == L(']'))
 852                   break;
 853               }
 854
 855             if (!not)
 856               return FNM_NOMATCH;
 857             break;
 858
 859           matched:
 860             /* Skip the rest of the [...] that already matched.  */
 861             do
 862               {
 863               ignore_next:
 864                 c = *p++;
 865
 866                 if (c == L('\0'))
 867                   /* [... (unterminated) loses.  */
 868                   return FNM_NOMATCH;
 869
 870                 if (!(flags & FNM_NOESCAPE) && c == L('\\'))
 871                   {
 872                     if (*p == L('\0'))
 873                       return FNM_NOMATCH;
 874                     /* XXX 1003.2d11 is unclear if this is right.  */
 875                     ++p;
 876                   }
 877                 else if (c == L('[') && *p == L(':'))
 878                   {
 879                     int c1 = 0;
 880                     const CHAR *startp = p;
 881
 882                     while (1)
 883                       {
 884                         c = *++p;
 885                         if (++c1 == CHAR_CLASS_MAX_LENGTH)
 886                           return FNM_NOMATCH;
 887
 888                         if (*p == L(':') && p[1] == L(']'))
 889                           break;
 890
 891                         if (c < L('a') || c >= L('z'))
 892                           {
 893                             p = startp;
 894                             goto ignore_next;
 895                           }
 896                       }
 897                     p += 2;
 898                     c = *p++;
 899                   }
 900                 else if (c == L('[') && *p == L('='))
 901                   {
 902                     c = *++p;
 903                     if (c == L('\0'))
 904                       return FNM_NOMATCH;
 905                     c = *++p;
 906                     if (c != L('=') || p[1] != L(']'))
 907                       return FNM_NOMATCH;
 908                     p += 2;
 909                     c = *p++;
 910                   }
 911                 else if (c == L('[') && *p == L('.'))
 912                   {
 913                     ++p;
 914                     while (1)
 915                       {
 916                         c = *++p;
 917                         if (c == '\0')
 918                           return FNM_NOMATCH;
 919
 920                         if (*p == L('.') && p[1] == L(']'))
 921                           break;
 922                       }
 923                     p += 2;
 924                     c = *p++;
 925                   }
 926               }
 927             while (c != L(']'));
 928             if (not)
 929               return FNM_NOMATCH;
 930           }
 931           break;
 932
 933         case L('+'):
 934         case L('@'):
 935         case L('!'):
 936           if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
 937             {
 938               int res;
 939
 940               res = EXT (c, p, n, string_end, no_leading_period, flags);
 941               if (res != -1)
 942                 return res;
 943             }
 944           goto normal_match;
 945
 946         case L('/'):
 947           if (NO_LEADING_PERIOD (flags))
 948             {
 949               if (n == string_end || c != (UCHAR) *n)
 950                 return FNM_NOMATCH;
 951
 952               new_no_leading_period = 1;
 953               break;
 954             }
 955           /* FALLTHROUGH */
 956         default:
 957         normal_match:
 958           if (n == string_end || c != FOLD ((UCHAR) *n))
 959             return FNM_NOMATCH;
 960         }
 961
 962       no_leading_period = new_no_leading_period;
 963       ++n;
 964     }
 965
 966   if (n == string_end)
 967     return 0;
 968
 969   if ((flags & FNM_LEADING_DIR) && n != string_end && *n == L('/'))
 970     /* The FNM_LEADING_DIR flag says that "foo*" matches "foobar/frobozz".  */
 971     return 0;
 972
 973   return FNM_NOMATCH;
 974 }
 975
 976
 977 static const CHAR *
 978 internal_function
 979 END (const CHAR *pattern)
 980 {
 981   const CHAR *p = pattern;
 982
 983   while (1)
 984     if (*++p == L('\0'))
 985       /* This is an invalid pattern.  */
 986       return pattern;
 987     else if (*p == L('['))
 988       {
 989         /* Handle brackets special.  */
 990         if (posixly_correct == 0)
 991           posixly_correct = getenv ("POSIXLY_CORRECT") != NULL ? 1 : -1;
 992
 993         /* Skip the not sign.  We have to recognize it because of a possibly
 994            following ']'.  */
 995         if (*++p == L('!') || (posixly_correct < 0 && *p == L('^')))
 996           ++p;
 997         /* A leading ']' is recognized as such.  */
 998         if (*p == L(']'))
 999           ++p;
1000         /* Skip over all characters of the list.  */
1001         while (*p != L(']'))
1002           if (*p++ == L('\0'))
1003             /* This is no valid pattern.  */
1004             return pattern;
1005       }
1006     else if ((*p == L('?') || *p == L('*') || *p == L('+') || *p == L('@')
1007               || *p == L('!')) && p[1] == L('('))
1008       p = END (p + 1);
1009     else if (*p == L(')'))
1010       break;
1011
1012   return p + 1;
1013 }
1014
1015
1016 static int
1017 internal_function
1018 EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
1019      int no_leading_period, int flags)
1020 {
1021   const CHAR *startp;
1022   int level;
1023   struct patternlist
1024   {
1025     struct patternlist *next;
1026     CHAR str[0];
1027   } *list = NULL;
1028   struct patternlist **lastp = &list;
1029   size_t pattern_len = STRLEN (pattern);
1030   const CHAR *p;
1031   const CHAR *rs;
1032
1033   /* Parse the pattern.  Store the individual parts in the list.  */
1034   level = 0;
1035   for (startp = p = pattern + 1; level >= 0; ++p)
1036     if (*p == L('\0'))
1037       /* This is an invalid pattern.  */
1038       return -1;
1039     else if (*p == L('['))
1040       {
1041         /* Handle brackets special.  */
1042         if (posixly_correct == 0)
1043           posixly_correct = getenv ("POSIXLY_CORRECT") != NULL ? 1 : -1;
1044
1045         /* Skip the not sign.  We have to recognize it because of a possibly
1046            following ']'.  */
1047         if (*++p == L('!') || (posixly_correct < 0 && *p == L('^')))
1048           ++p;
1049         /* A leading ']' is recognized as such.  */
1050         if (*p == L(']'))
1051           ++p;
1052         /* Skip over all characters of the list.  */
1053         while (*p != L(']'))
1054           if (*p++ == L('\0'))
1055             /* This is no valid pattern.  */
1056             return -1;
1057       }
1058     else if ((*p == L('?') || *p == L('*') || *p == L('+') || *p == L('@')
1059               || *p == L('!')) && p[1] == L('('))
1060       /* Remember the nesting level.  */
1061       ++level;
1062     else if (*p == L(')'))
1063       {
1064         if (level-- == 0)
1065           {
1066             /* This means we found the end of the pattern.  */
1067 #define NEW_PATTERN \
1068             struct patternlist *newp;                                         \
1069                                                                               \
1070             if (opt == L('?') || opt == L('@'))                               \
1071               newp = alloca (sizeof (struct patternlist)                      \
1072                              + (pattern_len * sizeof (CHAR)));                \
1073             else                                                              \
1074               newp = alloca (sizeof (struct patternlist)                      \
1075                              + ((p - startp + 1) * sizeof (CHAR)));           \
1076             *((CHAR *) MEMPCPY (newp->str, startp, p - startp)) = L('\0');    \
1077             newp->next = NULL;                                                \
1078             *lastp = newp;                                                    \
1079             lastp = &newp->next
1080             NEW_PATTERN;
1081           }
1082       }
1083     else if (*p == L('|'))
1084       {
1085         if (level == 0)
1086           {
1087             NEW_PATTERN;
1088             startp = p + 1;
1089           }
1090       }
1091   assert (list != NULL);
1092   assert (p[-1] == L(')'));
1093 #undef NEW_PATTERN
1094
1095   switch (opt)
1096     {
1097     case L('*'):
1098       if (FCT (p, string, string_end, no_leading_period, flags) == 0)
1099         return 0;
1100       /* FALLTHROUGH */
1101
1102     case L('+'):
1103       do
1104         {
1105           for (rs = string; rs <= string_end; ++rs)
1106             /* First match the prefix with the current pattern with the
1107                current pattern.  */
1108             if (FCT (list->str, string, rs, no_leading_period,
1109                      flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD) == 0
1110                 /* This was successful.  Now match the rest with the rest
1111                    of the pattern.  */
1112                 && (FCT (p, rs, string_end,
1113                          rs == string
1114                          ? no_leading_period
1115                          : rs[-1] == '/' && NO_LEADING_PERIOD (flags) ? 1 : 0,
1116                          flags & FNM_FILE_NAME
1117                          ? flags : flags & ~FNM_PERIOD) == 0
1118                     /* This didn't work.  Try the whole pattern.  */
1119                     || (rs != string
1120                         && FCT (pattern - 1, rs, string_end,
1121                                 rs == string
1122                                 ? no_leading_period
1123                                 : (rs[-1] == '/' && NO_LEADING_PERIOD (flags)
1124                                    ? 1 : 0),
1125                                 flags & FNM_FILE_NAME
1126                                 ? flags : flags & ~FNM_PERIOD) == 0)))
1127               /* It worked.  Signal success.  */
1128               return 0;
1129         }
1130       while ((list = list->next) != NULL);
1131
1132       /* None of the patterns lead to a match.  */
1133       return FNM_NOMATCH;
1134
1135     case L('?'):
1136       if (FCT (p, string, string_end, no_leading_period, flags) == 0)
1137         return 0;
1138       /* FALLTHROUGH */
1139
1140     case L('@'):
1141       do
1142         /* I cannot believe it but `strcat' is actually acceptable
1143            here.  Match the entire string with the prefix from the
1144            pattern list and the rest of the pattern following the
1145            pattern list.  */
1146         if (FCT (STRCAT (list->str, p), string, string_end,
1147                  no_leading_period,
1148                  flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD) == 0)
1149           /* It worked.  Signal success.  */
1150           return 0;
1151       while ((list = list->next) != NULL);
1152
1153       /* None of the patterns lead to a match.  */
1154       return FNM_NOMATCH;
1155
1156     case L('!'):
1157       for (rs = string; rs <= string_end; ++rs)
1158         {
1159           struct patternlist *runp;
1160
1161           for (runp = list; runp != NULL; runp = runp->next)
1162             if (FCT (runp->str, string, rs,  no_leading_period,
1163                      flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD) == 0)
1164               break;
1165
1166           /* If none of the patterns matched see whether the rest does.  */
1167           if (runp == NULL
1168               && (FCT (p, rs, string_end,
1169                        rs == string
1170                        ? no_leading_period
1171                        : rs[-1] == '/' && NO_LEADING_PERIOD (flags) ? 1 : 0,
1172                        flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD)
1173                   == 0))
1174             /* This is successful.  */
1175             return 0;
1176         }
1177
1178       /* None of the patterns together with the rest of the pattern
1179          lead to a match.  */
1180       return FNM_NOMATCH;
1181
1182     default:
1183       assert (! "Invalid extended matching operator");
1184       break;
1185     }
1186
1187   return -1;
1188 }
1189
1190
1191 #undef FOLD
1192 #undef CHAR
1193 #undef UCHAR
1194 #undef INT
1195 #undef FCT
1196 #undef EXT
1197 #undef END
1198 #undef MEMPCPY
1199 #undef MEMCHR
1200 #undef STRCOLL
1201 #undef STRLEN
1202 #undef STRCAT
1203 #undef L
1204 #undef BTOWC