usr.bin/sort/coll.c

   1 /*-
   2  * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
   3  * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  25  * SUCH DAMAGE.
  26  */
  27
  28 #include <sys/cdefs.h>
  29 __FBSDID("$FreeBSD$");
  30
  31 #include <sys/types.h>
  32
  33 #include <errno.h>
  34 #include <err.h>
  35 #include <langinfo.h>
  36 #include <limits.h>
  37 #include <math.h>
  38 #include <md5.h>
  39 #include <stdlib.h>
  40 #include <string.h>
  41 #include <wchar.h>
  42 #include <wctype.h>
  43
  44 #include "coll.h"
  45 #include "vsort.h"
  46
  47 struct key_specs *keys;
  48 size_t keys_num = 0;
  49
  50 wint_t symbol_decimal_point = L'.';
  51 /* there is no default thousands separator in collate rules: */
  52 wint_t symbol_thousands_sep = 0;
  53 wint_t symbol_negative_sign = L'-';
  54 wint_t symbol_positive_sign = L'+';
  55
  56 static int wstrcoll(struct key_value *kv1, struct key_value *kv2, size_t offset);
  57 static int gnumcoll(struct key_value*, struct key_value *, size_t offset);
  58 static int monthcoll(struct key_value*, struct key_value *, size_t offset);
  59 static int numcoll(struct key_value*, struct key_value *, size_t offset);
  60 static int hnumcoll(struct key_value*, struct key_value *, size_t offset);
  61 static int randomcoll(struct key_value*, struct key_value *, size_t offset);
  62 static int versioncoll(struct key_value*, struct key_value *, size_t offset);
  63
  64 /*
  65  * Allocate keys array
  66  */
  67 struct keys_array *
  68 keys_array_alloc(void)
  69 {
  70         struct keys_array *ka;
  71         size_t sz;
  72
  73         sz = keys_array_size();
  74         ka = sort_malloc(sz);
  75         memset(ka, 0, sz);
  76
  77         return (ka);
  78 }
  79
  80 /*
  81  * Calculate whether we need key hint space
  82  */
  83 static size_t
  84 key_hint_size(void)
  85 {
  86
  87         return (need_hint ? sizeof(struct key_hint) : 0);
  88 }
  89
  90 /*
  91  * Calculate keys array size
  92  */
  93 size_t
  94 keys_array_size(void)
  95 {
  96
  97         return (keys_num * (sizeof(struct key_value) + key_hint_size()));
  98 }
  99
 100 /*
 101  * Clean data of keys array
 102  */
 103 void
 104 clean_keys_array(const struct bwstring *s, struct keys_array *ka)
 105 {
 106
 107         if (ka) {
 108                 for (size_t i = 0; i < keys_num; ++i) {
 109                         const struct key_value *kv;
 110
 111                         kv = get_key_from_keys_array(ka, i);
 112                         if (kv->k && kv->k != s)
 113                                 bwsfree(kv->k);
 114                 }
 115                 memset(ka, 0, keys_array_size());
 116         }
 117 }
 118
 119 /*
 120  * Get pointer to a key value in the keys set
 121  */
 122 struct key_value *
 123 get_key_from_keys_array(struct keys_array *ka, size_t ind)
 124 {
 125
 126         return ((struct key_value *)((caddr_t)ka->key +
 127             ind * (sizeof(struct key_value) + key_hint_size())));
 128 }
 129
 130 /*
 131  * Set value of a key in the keys set
 132  */
 133 void
 134 set_key_on_keys_array(struct keys_array *ka, struct bwstring *s, size_t ind)
 135 {
 136
 137         if (ka && keys_num > ind) {
 138                 struct key_value *kv;
 139
 140                 kv = get_key_from_keys_array(ka, ind);
 141
 142                 if (kv->k && kv->k != s)
 143                         bwsfree(kv->k);
 144                 kv->k = s;
 145         }
 146 }
 147
 148 /*
 149  * Initialize a sort list item
 150  */
 151 struct sort_list_item *
 152 sort_list_item_alloc(void)
 153 {
 154         struct sort_list_item *si;
 155         size_t sz;
 156
 157         sz = sizeof(struct sort_list_item) + keys_array_size();
 158         si = sort_malloc(sz);
 159         memset(si, 0, sz);
 160
 161         return (si);
 162 }
 163
 164 size_t
 165 sort_list_item_size(struct sort_list_item *si)
 166 {
 167         size_t ret = 0;
 168
 169         if (si) {
 170                 ret = sizeof(struct sort_list_item) + keys_array_size();
 171                 if (si->str)
 172                         ret += bws_memsize(si->str);
 173                 for (size_t i = 0; i < keys_num; ++i) {
 174                         const struct key_value *kv;
 175
 176                         kv = get_key_from_keys_array(&si->ka, i);
 177
 178                         if (kv->k != si->str)
 179                                 ret += bws_memsize(kv->k);
 180                 }
 181         }
 182         return (ret);
 183 }
 184
 185 /*
 186  * Calculate key for a sort list item
 187  */
 188 static void
 189 sort_list_item_make_key(struct sort_list_item *si)
 190 {
 191
 192         preproc(si->str, &(si->ka));
 193 }
 194
 195 /*
 196  * Set value of a sort list item.
 197  * Return combined string and keys memory size.
 198  */
 199 void
 200 sort_list_item_set(struct sort_list_item *si, struct bwstring *str)
 201 {
 202
 203         if (si) {
 204                 clean_keys_array(si->str, &(si->ka));
 205                 if (si->str) {
 206                         if (si->str == str) {
 207                                 /* we are trying to reset the same string */
 208                                 return;
 209                         } else {
 210                                 bwsfree(si->str);
 211                                 si->str = NULL;
 212                         }
 213                 }
 214                 si->str = str;
 215                 sort_list_item_make_key(si);
 216         }
 217 }
 218
 219 /*
 220  * De-allocate a sort list item object memory
 221  */
 222 void
 223 sort_list_item_clean(struct sort_list_item *si)
 224 {
 225
 226         if (si) {
 227                 clean_keys_array(si->str, &(si->ka));
 228                 if (si->str) {
 229                         bwsfree(si->str);
 230                         si->str = NULL;
 231                 }
 232         }
 233 }
 234
 235 /*
 236  * Skip columns according to specs
 237  */
 238 static size_t
 239 skip_cols_to_start(const struct bwstring *s, size_t cols, size_t start,
 240     bool skip_blanks, bool *empty_key)
 241 {
 242         if (cols < 1)
 243                 return (BWSLEN(s) + 1);
 244
 245         if (skip_blanks)
 246                 while (start < BWSLEN(s) && iswblank(BWS_GET(s,start)))
 247                         ++start;
 248
 249         while (start < BWSLEN(s) && cols > 1) {
 250                 --cols;
 251                 ++start;
 252         }
 253
 254         if (start >= BWSLEN(s))
 255                 *empty_key = true;
 256
 257         return (start);
 258 }
 259
 260 /*
 261  * Skip fields according to specs
 262  */
 263 static size_t
 264 skip_fields_to_start(const struct bwstring *s, size_t fields, bool *empty_field)
 265 {
 266
 267         if (fields < 2) {
 268                 if (BWSLEN(s) == 0)
 269                         *empty_field = true;
 270                 return (0);
 271         } else if (!(sort_opts_vals.tflag)) {
 272                 size_t cpos = 0;
 273                 bool pb = true;
 274
 275                 while (cpos < BWSLEN(s)) {
 276                         bool isblank;
 277
 278                         isblank = iswblank(BWS_GET(s, cpos));
 279
 280                         if (isblank && !pb) {
 281                                 --fields;
 282                                 if (fields <= 1)
 283                                         return (cpos);
 284                         }
 285                         pb = isblank;
 286                         ++cpos;
 287                 }
 288                 if (fields > 1)
 289                         *empty_field = true;
 290                 return (cpos);
 291         } else {
 292                 size_t cpos = 0;
 293
 294                 while (cpos < BWSLEN(s)) {
 295                         if (BWS_GET(s,cpos) == (wchar_t)sort_opts_vals.field_sep) {
 296                                 --fields;
 297                                 if (fields <= 1)
 298                                         return (cpos + 1);
 299                         }
 300                         ++cpos;
 301                 }
 302                 if (fields > 1)
 303                         *empty_field = true;
 304                 return (cpos);
 305         }
 306 }
 307
 308 /*
 309  * Find fields start
 310  */
 311 static void
 312 find_field_start(const struct bwstring *s, struct key_specs *ks,
 313     size_t *field_start, size_t *key_start, bool *empty_field, bool *empty_key)
 314 {
 315
 316         *field_start = skip_fields_to_start(s, ks->f1, empty_field);
 317         if (!*empty_field)
 318                 *key_start = skip_cols_to_start(s, ks->c1, *field_start,
 319                     ks->pos1b, empty_key);
 320         else
 321                 *empty_key = true;
 322 }
 323
 324 /*
 325  * Find end key position
 326  */
 327 static size_t
 328 find_field_end(const struct bwstring *s, struct key_specs *ks)
 329 {
 330         size_t f2, next_field_start, pos_end;
 331         bool empty_field, empty_key;
 332
 333         pos_end = 0;
 334         next_field_start = 0;
 335         empty_field = false;
 336         empty_key = false;
 337         f2 = ks->f2;
 338
 339         if (f2 == 0)
 340                 return (BWSLEN(s) + 1);
 341         else {
 342                 if (ks->c2 == 0) {
 343                         next_field_start = skip_fields_to_start(s, f2 + 1,
 344                             &empty_field);
 345                         if ((next_field_start > 0) && sort_opts_vals.tflag &&
 346                             ((wchar_t)sort_opts_vals.field_sep == BWS_GET(s,
 347                             next_field_start - 1)))
 348                                 --next_field_start;
 349                 } else
 350                         next_field_start = skip_fields_to_start(s, f2,
 351                             &empty_field);
 352         }
 353
 354         if (empty_field || (next_field_start >= BWSLEN(s)))
 355                 return (BWSLEN(s) + 1);
 356
 357         if (ks->c2) {
 358                 pos_end = skip_cols_to_start(s, ks->c2, next_field_start,
 359                     ks->pos2b, &empty_key);
 360                 if (pos_end < BWSLEN(s))
 361                         ++pos_end;
 362         } else
 363                 pos_end = next_field_start;
 364
 365         return (pos_end);
 366 }
 367
 368 /*
 369  * Cut a field according to the key specs
 370  */
 371 static struct bwstring *
 372 cut_field(const struct bwstring *s, struct key_specs *ks)
 373 {
 374         struct bwstring *ret = NULL;
 375
 376         if (s && ks) {
 377                 size_t field_start, key_end, key_start, sz;
 378                 bool empty_field, empty_key;
 379
 380                 field_start = 0;
 381                 key_start = 0;
 382                 empty_field = false;
 383                 empty_key = false;
 384
 385                 find_field_start(s, ks, &field_start, &key_start,
 386                     &empty_field, &empty_key);
 387
 388                 if (empty_key)
 389                         sz = 0;
 390                 else {
 391                         key_end = find_field_end(s, ks);
 392                         sz = (key_end < key_start) ? 0 : (key_end - key_start);
 393                 }
 394
 395                 ret = bwsalloc(sz);
 396                 if (sz)
 397                         bwsnocpy(ret, s, key_start, sz);
 398         } else
 399                 ret = bwsalloc(0);
 400
 401         return (ret);
 402 }
 403
 404 /*
 405  * Preprocesses a line applying the necessary transformations
 406  * specified by command line options and returns the preprocessed
 407  * string, which can be used to compare.
 408  */
 409 int
 410 preproc(struct bwstring *s, struct keys_array *ka)
 411 {
 412
 413         if (sort_opts_vals.kflag)
 414                 for (size_t i = 0; i < keys_num; i++) {
 415                         struct bwstring *key;
 416                         struct key_specs *kspecs;
 417                         struct sort_mods *sm;
 418
 419                         kspecs = &(keys[i]);
 420                         key = cut_field(s, kspecs);
 421
 422                         sm = &(kspecs->sm);
 423                         if (sm->dflag)
 424                                 key = dictionary_order(key);
 425                         else if (sm->iflag)
 426                                 key = ignore_nonprinting(key);
 427                         if (sm->fflag || sm->Mflag)
 428                                 key = ignore_case(key);
 429
 430                         set_key_on_keys_array(ka, key, i);
 431                 }
 432         else {
 433                 struct bwstring *ret = NULL;
 434                 struct sort_mods *sm = default_sort_mods;
 435
 436                 if (sm->bflag) {
 437                         if (ret == NULL)
 438                                 ret = bwsdup(s);
 439                         ret = ignore_leading_blanks(ret);
 440                 }
 441                 if (sm->dflag) {
 442                         if (ret == NULL)
 443                                 ret = bwsdup(s);
 444                         ret = dictionary_order(ret);
 445                 } else if (sm->iflag) {
 446                         if (ret == NULL)
 447                                 ret = bwsdup(s);
 448                         ret = ignore_nonprinting(ret);
 449                 }
 450                 if (sm->fflag || sm->Mflag) {
 451                         if (ret == NULL)
 452                                 ret = bwsdup(s);
 453                         ret = ignore_case(ret);
 454                 }
 455                 if (ret == NULL)
 456                         set_key_on_keys_array(ka, s, 0);
 457                 else
 458                         set_key_on_keys_array(ka, ret, 0);
 459         }
 460
 461         return 0;
 462 }
 463
 464 cmpcoll_t
 465 get_sort_func(struct sort_mods *sm)
 466 {
 467
 468         if (sm->nflag)
 469                 return (numcoll);
 470         else if (sm->hflag)
 471                 return (hnumcoll);
 472         else if (sm->gflag)
 473                 return (gnumcoll);
 474         else if (sm->Mflag)
 475                 return (monthcoll);
 476         else if (sm->Rflag)
 477                 return (randomcoll);
 478         else if (sm->Vflag)
 479                 return (versioncoll);
 480         else
 481                 return (wstrcoll);
 482 }
 483
 484 /*
 485  * Compares the given strings.  Returns a positive number if
 486  * the first precedes the second, a negative number if the second is
 487  * the preceding one, and zero if they are equal.  This function calls
 488  * the underlying collate functions, which done the actual comparison.
 489  */
 490 int
 491 key_coll(struct keys_array *ps1, struct keys_array *ps2, size_t offset)
 492 {
 493         struct key_value *kv1, *kv2;
 494         struct sort_mods *sm;
 495         int res = 0;
 496
 497         for (size_t i = 0; i < keys_num; ++i) {
 498                 kv1 = get_key_from_keys_array(ps1, i);
 499                 kv2 = get_key_from_keys_array(ps2, i);
 500                 sm = &(keys[i].sm);
 501
 502                 if (sm->rflag)
 503                         res = sm->func(kv2, kv1, offset);
 504                 else
 505                         res = sm->func(kv1, kv2, offset);
 506
 507                 if (res)
 508                         break;
 509
 510                 /* offset applies to only the first key */
 511                 offset = 0;
 512         }
 513         return (res);
 514 }
 515
 516 /*
 517  * Compare two strings.
 518  * Plain symbol-by-symbol comparison.
 519  */
 520 int
 521 top_level_str_coll(const struct bwstring *s1, const struct bwstring *s2)
 522 {
 523
 524         if (default_sort_mods->rflag) {
 525                 const struct bwstring *tmp;
 526
 527                 tmp = s1;
 528                 s1 = s2;
 529                 s2 = tmp;
 530         }
 531
 532         return (bwscoll(s1, s2, 0));
 533 }
 534
 535 /*
 536  * Compare a string and a sort list item, according to the sort specs.
 537  */
 538 int
 539 str_list_coll(struct bwstring *str1, struct sort_list_item **ss2)
 540 {
 541         struct keys_array *ka1;
 542         int ret = 0;
 543
 544         ka1 = keys_array_alloc();
 545
 546         preproc(str1, ka1);
 547
 548         sort_list_item_make_key(*ss2);
 549
 550         if (debug_sort) {
 551                 bwsprintf(stdout, str1, "; s1=<", ">");
 552                 bwsprintf(stdout, (*ss2)->str, ", s2=<", ">");
 553         }
 554
 555         ret = key_coll(ka1, &((*ss2)->ka), 0);
 556
 557         if (debug_sort)
 558                 printf("; cmp1=%d", ret);
 559
 560         clean_keys_array(str1, ka1);
 561         sort_free(ka1);
 562
 563         if ((ret == 0) && !(sort_opts_vals.sflag) && sort_opts_vals.complex_sort) {
 564                 ret = top_level_str_coll(str1, ((*ss2)->str));
 565                 if (debug_sort)
 566                         printf("; cmp2=%d", ret);
 567         }
 568
 569         if (debug_sort)
 570                 printf("\n");
 571
 572         return (ret);
 573 }
 574
 575 /*
 576  * Compare two sort list items, according to the sort specs.
 577  */
 578 int
 579 list_coll_offset(struct sort_list_item **ss1, struct sort_list_item **ss2,
 580     size_t offset)
 581 {
 582         int ret;
 583
 584         ret = key_coll(&((*ss1)->ka), &((*ss2)->ka), offset);
 585
 586         if (debug_sort) {
 587                 if (offset)
 588                         printf("; offset=%d", (int) offset);
 589                 bwsprintf(stdout, ((*ss1)->str), "; s1=<", ">");
 590                 bwsprintf(stdout, ((*ss2)->str), ", s2=<", ">");
 591                 printf("; cmp1=%d\n", ret);
 592         }
 593
 594         if (ret)
 595                 return (ret);
 596
 597         if (!(sort_opts_vals.sflag) && sort_opts_vals.complex_sort) {
 598                 ret = top_level_str_coll(((*ss1)->str), ((*ss2)->str));
 599                 if (debug_sort)
 600                         printf("; cmp2=%d\n", ret);
 601         }
 602
 603         return (ret);
 604 }
 605
 606 /*
 607  * Compare two sort list items, according to the sort specs.
 608  */
 609 int
 610 list_coll(struct sort_list_item **ss1, struct sort_list_item **ss2)
 611 {
 612
 613         return (list_coll_offset(ss1, ss2, 0));
 614 }
 615
 616 #define LSCDEF(N)                                                                                       \
 617 static int                                                                                              \
 618 list_coll_##N(struct sort_list_item **ss1, struct sort_list_item **ss2)                                 \
 619 {                                                                                                       \
 620                                                                                                         \
 621         return (list_coll_offset(ss1, ss2, N));                                                         \
 622 }
 623
 624 LSCDEF(1)
 625 LSCDEF(2)
 626 LSCDEF(3)
 627 LSCDEF(4)
 628 LSCDEF(5)
 629 LSCDEF(6)
 630 LSCDEF(7)
 631 LSCDEF(8)
 632 LSCDEF(9)
 633 LSCDEF(10)
 634 LSCDEF(11)
 635 LSCDEF(12)
 636 LSCDEF(13)
 637 LSCDEF(14)
 638 LSCDEF(15)
 639 LSCDEF(16)
 640 LSCDEF(17)
 641 LSCDEF(18)
 642 LSCDEF(19)
 643 LSCDEF(20)
 644
 645 listcoll_t
 646 get_list_call_func(size_t offset)
 647 {
 648         static const listcoll_t lsarray[] = { list_coll, list_coll_1,
 649             list_coll_2, list_coll_3, list_coll_4, list_coll_5,
 650             list_coll_6, list_coll_7, list_coll_8, list_coll_9,
 651             list_coll_10, list_coll_11, list_coll_12, list_coll_13,
 652             list_coll_14, list_coll_15, list_coll_16, list_coll_17,
 653             list_coll_18, list_coll_19, list_coll_20 };
 654
 655         if (offset <= 20)
 656                 return (lsarray[offset]);
 657
 658         return (list_coll);
 659 }
 660
 661 /*
 662  * Compare two sort list items, only by their original string.
 663  */
 664 int
 665 list_coll_by_str_only(struct sort_list_item **ss1, struct sort_list_item **ss2)
 666 {
 667
 668         return (top_level_str_coll(((*ss1)->str), ((*ss2)->str)));
 669 }
 670
 671 /*
 672  * Maximum size of a number in the string (before or after decimal point)
 673  */
 674 #define MAX_NUM_SIZE (128)
 675
 676 /*
 677  * Set suffix value
 678  */
 679 static void setsuffix(wchar_t c, unsigned char *si)
 680 {
 681         switch (c){
 682         case L'k':
 683         case L'K':
 684                 *si = 1;
 685                 break;
 686         case L'M':
 687                 *si = 2;
 688                 break;
 689         case L'G':
 690                 *si = 3;
 691                 break;
 692         case L'T':
 693                 *si = 4;
 694                 break;
 695         case L'P':
 696                 *si = 5;
 697                 break;
 698         case L'E':
 699                 *si = 6;
 700                 break;
 701         case L'Z':
 702                 *si = 7;
 703                 break;
 704         case L'Y':
 705                 *si = 8;
 706                 break;
 707         default:
 708                 *si = 0;
 709         };
 710 }
 711
 712 /*
 713  * Read string s and parse the string into a fixed-decimal-point number.
 714  * sign equals -1 if the number is negative (explicit plus is not allowed,
 715  * according to GNU sort's "info sort".
 716  * The number part before decimal point is in the smain, after the decimal
 717  * point is in sfrac, tail is the pointer to the remainder of the string.
 718  */
 719 static int
 720 read_number(struct bwstring *s0, int *sign, wchar_t *smain, size_t *main_len, wchar_t *sfrac, size_t *frac_len, unsigned char *si)
 721 {
 722         bwstring_iterator s;
 723
 724         s = bws_begin(s0);
 725
 726         /* always end the fraction with zero, even if we have no fraction */
 727         sfrac[0] = 0;
 728
 729         while (iswblank(bws_get_iter_value(s)))
 730                 s = bws_iterator_inc(s, 1);
 731
 732         if (bws_get_iter_value(s) == (wchar_t)symbol_negative_sign) {
 733                 *sign = -1;
 734                 s = bws_iterator_inc(s, 1);
 735         }
 736
 737         // This is '0', not '\0', do not change this
 738         while (iswdigit(bws_get_iter_value(s)) &&
 739             (bws_get_iter_value(s) == L'0'))
 740                 s = bws_iterator_inc(s, 1);
 741
 742         while (bws_get_iter_value(s) && *main_len < MAX_NUM_SIZE) {
 743                 if (iswdigit(bws_get_iter_value(s))) {
 744                         smain[*main_len] = bws_get_iter_value(s);
 745                         s = bws_iterator_inc(s, 1);
 746                         *main_len += 1;
 747                 } else if (symbol_thousands_sep &&
 748                     (bws_get_iter_value(s) == (wchar_t)symbol_thousands_sep))
 749                         s = bws_iterator_inc(s, 1);
 750                 else
 751                         break;
 752         }
 753
 754         smain[*main_len] = 0;
 755
 756         if (bws_get_iter_value(s) == (wchar_t)symbol_decimal_point) {
 757                 s = bws_iterator_inc(s, 1);
 758                 while (iswdigit(bws_get_iter_value(s)) &&
 759                     *frac_len < MAX_NUM_SIZE) {
 760                         sfrac[*frac_len] = bws_get_iter_value(s);
 761                         s = bws_iterator_inc(s, 1);
 762                         *frac_len += 1;
 763                 }
 764                 sfrac[*frac_len] = 0;
 765
 766                 while (*frac_len > 0 && sfrac[*frac_len - 1] == L'0') {
 767                         --(*frac_len);
 768                         sfrac[*frac_len] = L'\0';
 769                 }
 770         }
 771
 772         setsuffix(bws_get_iter_value(s),si);
 773
 774         if ((*main_len + *frac_len) == 0)
 775                 *sign = 0;
 776
 777         return (0);
 778 }
 779
 780 /*
 781  * Implements string sort.
 782  */
 783 static int
 784 wstrcoll(struct key_value *kv1, struct key_value *kv2, size_t offset)
 785 {
 786
 787         if (debug_sort) {
 788                 if (offset)
 789                         printf("; offset=%d\n", (int) offset);
 790                 bwsprintf(stdout, kv1->k, "; k1=<", ">");
 791                 printf("(%zu)", BWSLEN(kv1->k));
 792                 bwsprintf(stdout, kv2->k, ", k2=<", ">");
 793                 printf("(%zu)", BWSLEN(kv2->k));
 794         }
 795
 796         return (bwscoll(kv1->k, kv2->k, offset));
 797 }
 798
 799 /*
 800  * Compare two suffixes
 801  */
 802 static inline int
 803 cmpsuffix(unsigned char si1, unsigned char si2)
 804 {
 805
 806         return ((char)si1 - (char)si2);
 807 }
 808
 809 /*
 810  * Implements numeric sort for -n and -h.
 811  */
 812 static int
 813 numcoll_impl(struct key_value *kv1, struct key_value *kv2,
 814     size_t offset __unused, bool use_suffix)
 815 {
 816         struct bwstring *s1, *s2;
 817         wchar_t sfrac1[MAX_NUM_SIZE + 1], sfrac2[MAX_NUM_SIZE + 1];
 818         wchar_t smain1[MAX_NUM_SIZE + 1], smain2[MAX_NUM_SIZE + 1];
 819         int cmp_res, sign1, sign2;
 820         size_t frac1, frac2, main1, main2;
 821         unsigned char SI1, SI2;
 822         bool e1, e2, key1_read, key2_read;
 823
 824         s1 = kv1->k;
 825         s2 = kv2->k;
 826         sign1 = sign2 = 0;
 827         main1 = main2 = 0;
 828         frac1 = frac2 = 0;
 829
 830         cmp_res = 0;
 831         key1_read = key2_read = false;
 832
 833         if (debug_sort) {
 834                 bwsprintf(stdout, s1, "; k1=<", ">");
 835                 bwsprintf(stdout, s2, ", k2=<", ">");
 836         }
 837
 838         if (s1 == s2)
 839                 return (0);
 840
 841         if (kv1->hint->status == HS_UNINITIALIZED) {
 842                 /* read the number from the string */
 843                 read_number(s1, &sign1, smain1, &main1, sfrac1, &frac1, &SI1);
 844                 key1_read = true;
 845                 kv1->hint->v.nh.n1 = wcstoull(smain1, NULL, 10);
 846                 if(main1 < 1 && frac1 < 1)
 847                         kv1->hint->v.nh.empty=true;
 848                 kv1->hint->v.nh.si = SI1;
 849                 kv1->hint->status = (kv1->hint->v.nh.n1 != ULLONG_MAX) ?
 850                     HS_INITIALIZED : HS_ERROR;
 851                 kv1->hint->v.nh.neg = (sign1 < 0) ? true : false;
 852         }
 853
 854         if (kv2->hint->status == HS_UNINITIALIZED) {
 855                 /* read the number from the string */
 856                 read_number(s2, &sign2, smain2, &main2, sfrac2, &frac2,&SI2);
 857                 key2_read = true;
 858                 kv2->hint->v.nh.n1 = wcstoull(smain2, NULL, 10);
 859                 if(main2 < 1 && frac2 < 1)
 860                         kv2->hint->v.nh.empty=true;
 861                 kv2->hint->v.nh.si = SI2;
 862                 kv2->hint->status = (kv2->hint->v.nh.n1 != ULLONG_MAX) ?
 863                     HS_INITIALIZED : HS_ERROR;
 864                 kv2->hint->v.nh.neg = (sign2 < 0) ? true : false;
 865         }
 866
 867         if (kv1->hint->status == HS_INITIALIZED && kv2->hint->status ==
 868             HS_INITIALIZED) {
 869                 unsigned long long n1, n2;
 870                 bool neg1, neg2;
 871
 872                 e1 = kv1->hint->v.nh.empty;
 873                 e2 = kv2->hint->v.nh.empty;
 874
 875                 if (e1 && e2)
 876                         return (0);
 877
 878                 neg1 = kv1->hint->v.nh.neg;
 879                 neg2 = kv2->hint->v.nh.neg;
 880
 881                 if (neg1 && !neg2)
 882                         return (-1);
 883                 if (neg2 && !neg1)
 884                         return (+1);
 885
 886                 if (e1)
 887                         return (neg2 ? +1 : -1);
 888                 else if (e2)
 889                         return (neg1 ? -1 : +1);
 890
 891
 892                 if (use_suffix) {
 893                         cmp_res = cmpsuffix(kv1->hint->v.nh.si, kv2->hint->v.nh.si);
 894                         if (cmp_res)
 895                                 return (neg1 ? -cmp_res : cmp_res);
 896                 }
 897
 898                 n1 = kv1->hint->v.nh.n1;
 899                 n2 = kv2->hint->v.nh.n1;
 900                 if (n1 < n2)
 901                         return (neg1 ? +1 : -1);
 902                 else if (n1 > n2)
 903                         return (neg1 ? -1 : +1);
 904         }
 905
 906         /* read the numbers from the strings */
 907         if (!key1_read)
 908                 read_number(s1, &sign1, smain1, &main1, sfrac1, &frac1, &SI1);
 909         if (!key2_read)
 910                 read_number(s2, &sign2, smain2, &main2, sfrac2, &frac2, &SI2);
 911
 912         e1 = ((main1 + frac1) == 0);
 913         e2 = ((main2 + frac2) == 0);
 914
 915         if (e1 && e2)
 916                 return (0);
 917
 918         /* we know the result if the signs are different */
 919         if (sign1 < 0 && sign2 >= 0)
 920                 return (-1);
 921         if (sign1 >= 0 && sign2 < 0)
 922                 return (+1);
 923
 924         if (e1)
 925                 return ((sign2 < 0) ? +1 : -1);
 926         else if (e2)
 927                 return ((sign1 < 0) ? -1 : +1);
 928
 929         if (use_suffix) {
 930                 cmp_res = cmpsuffix(SI1, SI2);
 931                 if (cmp_res)
 932                         return ((sign1 < 0) ? -cmp_res : cmp_res);
 933         }
 934
 935         /* if both numbers are empty assume that the strings are equal */
 936         if (main1 < 1 && main2 < 1 && frac1 < 1 && frac2 < 1)
 937                 return (0);
 938
 939         /*
 940          * if the main part is of different size, we know the result
 941          * (because the leading zeros are removed)
 942          */
 943         if (main1 < main2)
 944                 cmp_res = -1;
 945         else if (main1 > main2)
 946                 cmp_res = +1;
 947         /* if the sizes are equal then simple non-collate string compare gives the correct result */
 948         else
 949                 cmp_res = wcscmp(smain1, smain2);
 950
 951         /* check fraction */
 952         if (!cmp_res)
 953                 cmp_res = wcscmp(sfrac1, sfrac2);
 954
 955         if (!cmp_res)
 956                 return (0);
 957
 958         /* reverse result if the signs are negative */
 959         if (sign1 < 0 && sign2 < 0)
 960                 cmp_res = -cmp_res;
 961
 962         return (cmp_res);
 963 }
 964
 965 /*
 966  * Implements numeric sort (-n).
 967  */
 968 static int
 969 numcoll(struct key_value *kv1, struct key_value *kv2, size_t offset)
 970 {
 971
 972         return (numcoll_impl(kv1, kv2, offset, false));
 973 }
 974
 975 /*
 976  * Implements 'human' numeric sort (-h).
 977  */
 978 static int
 979 hnumcoll(struct key_value *kv1, struct key_value *kv2, size_t offset)
 980 {
 981
 982         return (numcoll_impl(kv1, kv2, offset, true));
 983 }
 984
 985 /*
 986  * Implements random sort (-R).
 987  */
 988 static int
 989 randomcoll(struct key_value *kv1, struct key_value *kv2,
 990     size_t offset __unused)
 991 {
 992         struct bwstring *s1, *s2;
 993         MD5_CTX ctx1, ctx2;
 994         char *b1, *b2;
 995
 996         s1 = kv1->k;
 997         s2 = kv2->k;
 998
 999         if (debug_sort) {
1000                 bwsprintf(stdout, s1, "; k1=<", ">");
1001                 bwsprintf(stdout, s2, ", k2=<", ">");
1002         }
1003
1004         if (s1 == s2)
1005                 return (0);
1006
1007         memcpy(&ctx1,&md5_ctx,sizeof(MD5_CTX));
1008         memcpy(&ctx2,&md5_ctx,sizeof(MD5_CTX));
1009
1010         MD5Update(&ctx1, bwsrawdata(s1), bwsrawlen(s1));
1011         MD5Update(&ctx2, bwsrawdata(s2), bwsrawlen(s2));
1012         b1 = MD5End(&ctx1, NULL);
1013         b2 = MD5End(&ctx2, NULL);
1014         if (b1 == NULL) {
1015                 if (b2 == NULL)
1016                         return (0);
1017                 else {
1018                         sort_free(b2);
1019                         return (-1);
1020                 }
1021         } else if (b2 == NULL) {
1022                 sort_free(b1);
1023                 return (+1);
1024         } else {
1025                 int cmp_res;
1026
1027                 cmp_res = strcmp(b1,b2);
1028                 sort_free(b1);
1029                 sort_free(b2);
1030
1031                 if (!cmp_res)
1032                         cmp_res = bwscoll(s1, s2, 0);
1033
1034                 return (cmp_res);
1035         }
1036 }
1037
1038 /*
1039  * Implements version sort (-V).
1040  */
1041 static int
1042 versioncoll(struct key_value *kv1, struct key_value *kv2,
1043     size_t offset __unused)
1044 {
1045         struct bwstring *s1, *s2;
1046
1047         s1 = kv1->k;
1048         s2 = kv2->k;
1049
1050         if (debug_sort) {
1051                 bwsprintf(stdout, s1, "; k1=<", ">");
1052                 bwsprintf(stdout, s2, ", k2=<", ">");
1053         }
1054
1055         if (s1 == s2)
1056                 return (0);
1057
1058         return (vcmp(s1, s2));
1059 }
1060
1061 /*
1062  * Check for minus infinity
1063  */
1064 static inline bool
1065 huge_minus(double d, int err1)
1066 {
1067
1068         if (err1 == ERANGE)
1069                 if (d == -HUGE_VAL || d == -HUGE_VALF || d == -HUGE_VALL)
1070                         return (+1);
1071
1072         return (0);
1073 }
1074
1075 /*
1076  * Check for plus infinity
1077  */
1078 static inline bool
1079 huge_plus(double d, int err1)
1080 {
1081
1082         if (err1 == ERANGE)
1083                 if (d == HUGE_VAL || d == HUGE_VALF || d == HUGE_VALL)
1084                         return (+1);
1085
1086         return (0);
1087 }
1088
1089 /*
1090  * Check whether a function is a NAN
1091  */
1092 static bool
1093 is_nan(double d)
1094 {
1095
1096         return ((d == NAN) || (isnan(d)));
1097 }
1098
1099 /*
1100  * Compare two NANs
1101  */
1102 static int
1103 cmp_nans(double d1, double d2)
1104 {
1105
1106         if (d1 < d2)
1107                 return (-1);
1108         if (d1 > d2)
1109                 return (+1);
1110         return (0);
1111 }
1112
1113 /*
1114  * Implements general numeric sort (-g).
1115  */
1116 static int
1117 gnumcoll(struct key_value *kv1, struct key_value *kv2,
1118     size_t offset __unused)
1119 {
1120         double d1, d2;
1121         int err1, err2;
1122         bool empty1, empty2, key1_read, key2_read;
1123
1124         d1 = d2 = 0;
1125         err1 = err2 = 0;
1126         key1_read = key2_read = false;
1127
1128         if (debug_sort) {
1129                 bwsprintf(stdout, kv1->k, "; k1=<", ">");
1130                 bwsprintf(stdout, kv2->k, "; k2=<", ">");
1131         }
1132
1133         if (kv1->hint->status == HS_UNINITIALIZED) {
1134                 errno = 0;
1135                 d1 = bwstod(kv1->k, &empty1);
1136                 err1 = errno;
1137
1138                 if (empty1)
1139                         kv1->hint->v.gh.notnum = true;
1140                 else if (err1 == 0) {
1141                         kv1->hint->v.gh.d = d1;
1142                         kv1->hint->v.gh.nan = is_nan(d1);
1143                         kv1->hint->status = HS_INITIALIZED;
1144                 } else
1145                         kv1->hint->status = HS_ERROR;
1146
1147                 key1_read = true;
1148         }
1149
1150         if (kv2->hint->status == HS_UNINITIALIZED) {
1151                 errno = 0;
1152                 d2 = bwstod(kv2->k, &empty2);
1153                 err2 = errno;
1154
1155                 if (empty2)
1156                         kv2->hint->v.gh.notnum = true;
1157                 else if (err2 == 0) {
1158                         kv2->hint->v.gh.d = d2;
1159                         kv2->hint->v.gh.nan = is_nan(d2);
1160                         kv2->hint->status = HS_INITIALIZED;
1161                 } else
1162                         kv2->hint->status = HS_ERROR;
1163
1164                 key2_read = true;
1165         }
1166
1167         if (kv1->hint->status == HS_INITIALIZED &&
1168             kv2->hint->status == HS_INITIALIZED) {
1169                 if (kv1->hint->v.gh.notnum)
1170                         return ((kv2->hint->v.gh.notnum) ? 0 : -1);
1171                 else if (kv2->hint->v.gh.notnum)
1172                         return (+1);
1173
1174                 if (kv1->hint->v.gh.nan)
1175                         return ((kv2->hint->v.gh.nan) ?
1176                             cmp_nans(kv1->hint->v.gh.d, kv2->hint->v.gh.d) :
1177                             -1);
1178                 else if (kv2->hint->v.gh.nan)
1179                         return (+1);
1180
1181                 d1 = kv1->hint->v.gh.d;
1182                 d2 = kv2->hint->v.gh.d;
1183
1184                 if (d1 < d2)
1185                         return (-1);
1186                 else if (d1 > d2)
1187                         return (+1);
1188                 else
1189                         return (0);
1190         }
1191
1192         if (!key1_read) {
1193                 errno = 0;
1194                 d1 = bwstod(kv1->k, &empty1);
1195                 err1 = errno;
1196         }
1197
1198         if (!key2_read) {
1199                 errno = 0;
1200                 d2 = bwstod(kv2->k, &empty2);
1201                 err2 = errno;
1202         }
1203
1204         /* Non-value case: */
1205         if (empty1)
1206                 return (empty2 ? 0 : -1);
1207         else if (empty2)
1208                 return (+1);
1209
1210         /* NAN case */
1211         if (is_nan(d1))
1212                 return (is_nan(d2) ? cmp_nans(d1, d2) : -1);
1213         else if (is_nan(d2))
1214                 return (+1);
1215
1216         /* Infinities */
1217         if (err1 == ERANGE || err2 == ERANGE) {
1218                 /* Minus infinity case */
1219                 if (huge_minus(d1, err1)) {
1220                         if (huge_minus(d2, err2)) {
1221                                 if (d1 < d2)
1222                                         return (-1);
1223                                 if (d1 > d2)
1224                                         return (+1);
1225                                 return (0);
1226                         } else
1227                                 return (-1);
1228
1229                 } else if (huge_minus(d2, err2)) {
1230                         if (huge_minus(d1, err1)) {
1231                                 if (d1 < d2)
1232                                         return (-1);
1233                                 if (d1 > d2)
1234                                         return (+1);
1235                                 return (0);
1236                         } else
1237                                 return (+1);
1238                 }
1239
1240                 /* Plus infinity case */
1241                 if (huge_plus(d1, err1)) {
1242                         if (huge_plus(d2, err2)) {
1243                                 if (d1 < d2)
1244                                         return (-1);
1245                                 if (d1 > d2)
1246                                         return (+1);
1247                                 return (0);
1248                         } else
1249                                 return (+1);
1250                 } else if (huge_plus(d2, err2)) {
1251                         if (huge_plus(d1, err1)) {
1252                                 if (d1 < d2)
1253                                         return (-1);
1254                                 if (d1 > d2)
1255                                         return (+1);
1256                                 return (0);
1257                         } else
1258                                 return (-1);
1259                 }
1260         }
1261
1262         if (d1 < d2)
1263                 return (-1);
1264         if (d1 > d2)
1265                 return (+1);
1266
1267         return (0);
1268 }
1269
1270 /*
1271  * Implements month sort (-M).
1272  */
1273 static int
1274 monthcoll(struct key_value *kv1, struct key_value *kv2, size_t offset __unused)
1275 {
1276         int val1, val2;
1277         bool key1_read, key2_read;
1278
1279         val1 = val2 = 0;
1280         key1_read = key2_read = false;
1281
1282         if (debug_sort) {
1283                 bwsprintf(stdout, kv1->k, "; k1=<", ">");
1284                 bwsprintf(stdout, kv2->k, "; k2=<", ">");
1285         }
1286
1287         if (kv1->hint->status == HS_UNINITIALIZED) {
1288                 kv1->hint->v.Mh.m = bws_month_score(kv1->k);
1289                 key1_read = true;
1290                 kv1->hint->status = HS_INITIALIZED;
1291         }
1292
1293         if (kv2->hint->status == HS_UNINITIALIZED) {
1294                 kv2->hint->v.Mh.m = bws_month_score(kv2->k);
1295                 key2_read = true;
1296                 kv2->hint->status = HS_INITIALIZED;
1297         }
1298
1299         if (kv1->hint->status == HS_INITIALIZED) {
1300                 val1 = kv1->hint->v.Mh.m;
1301                 key1_read = true;
1302         }
1303
1304         if (kv2->hint->status == HS_INITIALIZED) {
1305                 val2 = kv2->hint->v.Mh.m;
1306                 key2_read = true;
1307         }
1308
1309         if (!key1_read)
1310                 val1 = bws_month_score(kv1->k);
1311         if (!key2_read)
1312                 val2 = bws_month_score(kv2->k);
1313
1314         if (val1 == val2) {
1315                 return (0);
1316         }
1317         if (val1 < val2)
1318                 return (-1);
1319         return (+1);
1320 }