Src/sort.c

   1 /*
   2  * sort.c - comparison and sorting of strings
   3  *
   4  * This file is part of zsh, the Z shell.
   5  *
   6  * Copyright (c) 1992-2007 Paul Falstad
   7  * All rights reserved.
   8  *
   9  * Permission is hereby granted, without written agreement and without
  10  * license or royalty fees, to use, copy, modify, and distribute this
  11  * software and to distribute modified versions of this software for any
  12  * purpose, provided that the above copyright notice and the following
  13  * two paragraphs appear in all copies of this software.
  14  *
  15  * In no event shall Paul Falstad or the Zsh Development Group be liable
  16  * to any party for direct, indirect, special, incidental, or consequential
  17  * damages arising out of the use of this software and its documentation,
  18  * even if Paul Falstad and the Zsh Development Group have been advised of
  19  * the possibility of such damage.
  20  *
  21  * Paul Falstad and the Zsh Development Group specifically disclaim any
  22  * warranties, including, but not limited to, the implied warranties of
  23  * merchantability and fitness for a particular purpose.  The software
  24  * provided hereunder is on an "as is" basis, and Paul Falstad and the
  25  * Zsh Development Group have no obligation to provide maintenance,
  26  * support, updates, enhancements, or modifications.
  27  *
  28  */
  29
  30 #include "zsh.mdh"
  31 #include "sort.pro"
  32
  33 /* Flag for direction of sort: 1 forwards, -1 reverse */
  34 static int sortdir;
  35
  36 /* Flag that sort is numeric */
  37 static int sortnumeric;
  38
  39 /**/
  40 static int
  41 eltpcmp(const void *a, const void *b)
  42 {
  43     const SortElt ae = *(const SortElt *)a;
  44     const SortElt be = *(const SortElt *)b;
  45     const char *as = ae->cmp, *bs = be->cmp;
  46     const char *ao = as;
  47     int cmp;
  48
  49     if (ae->len != -1 || be->len != -1) {
  50         /*
  51          * Length recorded.  We only do that if there are embedded
  52          * nulls we need to treat as regular characters.
  53          *
  54          * Since we don't know where multibyte characters start,
  55          * but do know that a null character can't occur inside
  56          * one (we are relying on multibyte characters being extensions
  57          * of ASCII), we can compare starting from after the last
  58          * null character that occurred in both strings.
  59          */
  60         const char *cmpa, *cmpb;
  61         const char *laststarta = as;
  62         int len;
  63         if (ae->len != -1) {
  64             len = ae->len;
  65             if (be->len != -1 && len > be->len)
  66                 len = be->len;
  67         }
  68         else
  69             len = be->len;
  70
  71         for (cmpa = as, cmpb = bs; *cmpa == *cmpb && len--; cmpa++, cmpb++) {
  72             if (!*cmpa) {
  73                 /*
  74                  * If either string doesn't have a length, we've reached
  75                  * the end.  This is covered in the test below.
  76                  */
  77                 if (ae->len == -1 || be->len == -1)
  78                     break;
  79                 laststarta = cmpa + 1;
  80             }
  81         }
  82         if (*cmpa == *cmpb && ae->len != be->len) {
  83             /*
  84              * Special case: one of the strings has finished, but
  85              * another one continues after the NULL.  The string
  86              * that's finished sorts below the other.  We need
  87              * to handle this here since strcoll() or strcmp()
  88              * will just compare the strings as equal.
  89              */
  90             if (ae->len != -1) {
  91                 if (be->len != -1) {
  92                     /*
  93                      * if a is shorter it's earlier, so return -1 and
  94                      * vice versa
  95                      */
  96                     return (ae->len - be->len) * sortdir;
  97                 } else {
  98                     /*
  99                      * a has a length and so continues, hence
 100                      * b sorts lower.
 101                      */
 102                     return sortdir;
 103                 }
 104             } else {
 105                 /*
 106                  * b must continue because it has a recorded length,
 107                  * so a sorts lower.
 108                  */
 109                 return - sortdir;
 110             }
 111         }
 112
 113         bs += (laststarta - as);
 114         as += (laststarta - as);
 115     }
 116 #ifdef HAVE_STRCOLL
 117     cmp = strcoll(as, bs);
 118 #endif
 119     if (sortnumeric) {
 120         for (; *as == *bs && *as; as++, bs++);
 121 #ifndef HAVE_STRCOLL
 122         cmp = (int)STOUC(*as) - (int)STOUC(*bs);
 123 #endif
 124         if (idigit(*as) || idigit(*bs)) {
 125             for (; as > ao && idigit(as[-1]); as--, bs--);
 126             if (idigit(*as) && idigit(*bs)) {
 127                 while (*as == '0')
 128                     as++;
 129                 while (*bs == '0')
 130                     bs++;
 131                 for (; idigit(*as) && *as == *bs; as++, bs++);
 132                 if (idigit(*as) || idigit(*bs)) {
 133                     cmp = (int)STOUC(*as) - (int)STOUC(*bs);
 134                     while (idigit(*as) && idigit(*bs))
 135                         as++, bs++;
 136                     if (idigit(*as) && !idigit(*bs))
 137                         return sortdir;
 138                     if (idigit(*bs) && !idigit(*as))
 139                         return -sortdir;
 140                 }
 141             }
 142         }
 143     }
 144 #ifndef HAVE_STRCOLL
 145     else
 146         cmp = strcmp(as, bs);
 147 #endif
 148
 149     return sortdir * cmp;
 150 }
 151
 152
 153 /*
 154  * Front-end to eltpcmp() to compare strings.
 155  * TODO: it would be better to eliminate this altogether by
 156  * making the calling function call into the sort code
 157  * at a higher level.
 158  */
 159
 160 /**/
 161 mod_export int
 162 zstrcmp(const char *as, const char *bs, int sortflags)
 163 {
 164     struct sortelt ae, be, *aeptr, *beptr;
 165     int oldsortdir = sortdir, oldsortnumeric = sortnumeric, ret;
 166
 167     ae.cmp = as;
 168     be.cmp = bs;
 169     ae.len = -1;
 170     be.len = -1;
 171
 172     aeptr = &ae;
 173     beptr = &be;
 174
 175     sortdir = 1;
 176     sortnumeric = (sortflags & SORTIT_NUMERICALLY) ? 1 : 0;
 177
 178     ret = eltpcmp(&aeptr, &beptr);
 179
 180     /* Paranoia: I don't think we ever need to restore these. */
 181     sortnumeric = oldsortnumeric;
 182     sortdir = oldsortdir;
 183
 184     return ret;
 185 }
 186
 187
 188 /*
 189  * Sort an array of metafied strings.  Use an "or" of bit flags
 190  * to decide how to sort.  See the SORTIT_* flags in zsh.h.
 191  *
 192  * If unmetalenp is not NULL, the strings in array are already
 193  * unmetafied and unmetalenp is an array containing the corresponding
 194  * lengths.
 195  */
 196
 197 /**/
 198 mod_export void
 199 strmetasort(char **array, int sortwhat, int *unmetalenp)
 200 {
 201     char **arrptr;
 202     /*
 203      * Array of elements containing stuff to sort.  Note sortptrarr
 204      * is an array of pointers, since that's more efficient
 205      * for qsort() to manipulate.  sortarr is the array of
 206      * structures.
 207      */
 208     SortElt *sortptrarr, *sortptrarrptr;
 209     SortElt sortarr, sortarrptr;
 210     int oldsortdir, oldsortnumeric, nsort;
 211
 212     nsort = arrlen(array);
 213     if (nsort < 2)
 214         return;
 215
 216     pushheap();
 217
 218     sortptrarr = (SortElt *) zhalloc(nsort * sizeof(SortElt));
 219     sortarr = (SortElt) zhalloc(nsort * sizeof(struct sortelt));
 220     for (arrptr = array, sortptrarrptr = sortptrarr, sortarrptr = sortarr;
 221          *arrptr; arrptr++, sortptrarrptr++, sortarrptr++) {
 222         char *metaptr;
 223         int needlen, needalloc;
 224         *sortptrarrptr = sortarrptr;
 225         sortarrptr->orig = *arrptr;
 226
 227         if (unmetalenp) {
 228             /*
 229              * Already unmetafied.  We just need to check for
 230              * embededded nulls.
 231              */
 232             int count = unmetalenp[arrptr-array];
 233             /* Remember this length for sorted array */
 234             sortarrptr->origlen = count;
 235             for (metaptr = *arrptr; *metaptr != '\0' && count--; metaptr++)
 236                 ;
 237             /* *metaptr must now be \0, even if we reached the end */
 238             needlen = (count != 0);
 239         } else {
 240             /*
 241              * Not yet unmetafied.  See if it needs unmetafying.
 242              * If it doesn't, there can't be any embedded nulls,
 243              * since these are metafied.
 244              */
 245             needlen = 0;
 246             for (metaptr = *arrptr; *metaptr && *metaptr != Meta;
 247                  metaptr++);
 248         }
 249         /*
 250          * See if we need to do some special checking.
 251          * Either we're going to need to copy it to transform it,
 252          * or we need to unmetafy it.
 253          */
 254         if ((needalloc = (sortwhat &
 255                           (SORTIT_IGNORING_CASE|SORTIT_IGNORING_BACKSLASHES)))
 256             || *metaptr == Meta) {
 257             char *s, *t, *src = *arrptr, *dst;
 258             int len;
 259             sortarrptr->cmp = dst =
 260                 (char *)zhalloc(((sortwhat & SORTIT_IGNORING_CASE)?2:1)*strlen(src)+1);
 261
 262             if (unmetalenp) {
 263                 /* Already unmetafied and we have the length. */
 264                 len = unmetalenp[arrptr-array];
 265             } else if (*metaptr != '\0') {
 266                 /*
 267                  * Needs unmetafying.  We need to check for
 268                  * embedded nulls while we do this.
 269                  */
 270                 char *t = dst + (metaptr - src);
 271
 272                 if (metaptr != src)
 273                     memcpy(dst, src, metaptr - src);
 274                 while ((*t = *metaptr++)) {
 275                     if (*t++ == Meta) {
 276                         if ((t[-1] = *metaptr++ ^ 32) == '\0')
 277                             needlen = 1;
 278                     }
 279                 }
 280                 len = t - dst;
 281                 src = dst;
 282             } else {
 283                 /*
 284                  * Doesn't need unmetafying.
 285                  * This means metaptr is the NULL at the
 286                  * end of the string, so we have the length, and
 287                  * there are no embedded nulls, so we don't
 288                  * need the length later.
 289                  * We're only copying the string to transform it
 290                  * below.
 291                  */
 292                 len = metaptr - src;
 293             }
 294             if (sortwhat & SORTIT_IGNORING_CASE) {
 295                 char *send = src + len;
 296 #ifdef MULTIBYTE_SUPPORT
 297                 if (isset(MULTIBYTE)) {
 298                     /*
 299                      * Lower the case the hard way.  Convert to a wide
 300                      * character, process that, and convert back.  We
 301                      * don't assume the characters have the same
 302                      * multibyte length.  We can't use casemodify()
 303                      * because we have unmetafied data, which may have
 304                      * been passed down to use.
 305                      */
 306                     mbstate_t mbsin, mbsout;
 307                     int clen;
 308                     wchar_t wc;
 309                     memset(&mbsin, 0, sizeof(mbstate_t));
 310                     memset(&mbsout, 0, sizeof(mbstate_t));
 311
 312                     for (s = src, t = dst; s < send; ) {
 313                         clen = mbrtowc(&wc, s, send-s, &mbsin);
 314                         if (clen < 0) {
 315                             /* invalid or unfinished: treat as single bytes */
 316                             while (s < send)
 317                                 *t++ = tulower(*s++);
 318                             break;
 319                         }
 320                         if (clen == 0) {
 321                             /* embedded null */
 322                             *t++ = '\0';
 323                             s++;
 324                             continue;
 325                         }
 326                         s += clen;
 327                         wc = towlower(wc);
 328                         clen = wcrtomb(t, wc, &mbsout);
 329                         t += clen;
 330                         DPUTS(clen < 0, "Bad conversion when lowering case");
 331                     }
 332                     *t = '\0';
 333                     len = t - dst;
 334                 } else
 335 #endif
 336                     for (s = src, t = dst; s < send; )
 337                         *t++ = tulower(*s++);
 338                 src = dst;
 339             }
 340             if (sortwhat & SORTIT_IGNORING_BACKSLASHES) {
 341                 char *end = src + len + 1;
 342                 /* copy null byte, so increment length */
 343                 for (s = src, t = dst; s < end; ) {
 344                     if (*s == '\\') {
 345                         s++;
 346                         len--;
 347                     }
 348                     *t++ = *s++;
 349                 }
 350             }
 351             /* Do we need to store the length (embedded null)? */
 352             sortarrptr->len = needlen ? len : -1;
 353         } else {
 354             /*
 355              * We can use the string as is, although it's possible
 356              * we still need to take account of an embedded null.
 357              */
 358             sortarrptr->cmp = *arrptr;
 359             sortarrptr->len = needlen ? unmetalenp[arrptr-array] : -1;
 360         }
 361     }
 362     /*
 363      * We probably don't need to restore the following, but it's pretty cheap.
 364      */
 365     oldsortdir = sortdir;
 366     oldsortnumeric = sortnumeric;
 367
 368     sortdir = (sortwhat & SORTIT_BACKWARDS) ? -1 : 1;
 369     sortnumeric = (sortwhat & SORTIT_NUMERICALLY) ? 1 : 0;
 370
 371     qsort(sortptrarr, nsort, sizeof(SortElt *), eltpcmp);
 372
 373     sortnumeric = oldsortnumeric;
 374     sortdir = oldsortdir;
 375     for (arrptr = array, sortptrarrptr = sortptrarr; nsort--; ) {
 376         if (unmetalenp)
 377             unmetalenp[arrptr-array] = (*sortptrarrptr)->origlen;
 378         *arrptr++ = (*sortptrarrptr++)->orig;
 379     }
 380
 381     popheap();
 382 }