posix/fnmatch_loop.c

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