src/common/fnmatch_loop.c

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