usr.bin/sort/coll.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
   5  * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  29
  30 #include <sys/cdefs.h>
  31 __FBSDID("$FreeBSD$");
  32
  33 #include <sys/types.h>
  34
  35 #include <errno.h>
  36 #include <err.h>
  37 #include <langinfo.h>
  38 #include <limits.h>
  39 #include <math.h>
  40 #include <md5.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include <wchar.h>
  44 #include <wctype.h>
  45
  46 #include "coll.h"
  47 #include "vsort.h"
  48
  49 struct key_specs *keys;
  50 size_t keys_num = 0;
  51
  52 wint_t symbol_decimal_point = L'.';
  53 /* there is no default thousands separator in collate rules: */
  54 wint_t symbol_thousands_sep = 0;
  55 wint_t symbol_negative_sign = L'-';
  56 wint_t symbol_positive_sign = L'+';
  57
  58 static int wstrcoll(struct key_value *kv1, struct key_value *kv2, size_t offset);
  59 static int gnumcoll(struct key_value*, struct key_value *, size_t offset);
  60 static int monthcoll(struct key_value*, struct key_value *, size_t offset);
  61 static int numcoll(struct key_value*, struct key_value *, size_t offset);
  62 static int hnumcoll(struct key_value*, struct key_value *, size_t offset);
  63 static int randomcoll(struct key_value*, struct key_value *, size_t offset);
  64 static int versioncoll(struct key_value*, struct key_value *, size_t offset);
  65
  66 /*
  67  * Allocate keys array
  68  */
  69 struct keys_array *
  70 keys_array_alloc(void)
  71 {
  72         struct keys_array *ka;
  73         size_t sz;
  74
  75         sz = keys_array_size();
  76         ka = sort_malloc(sz);
  77         memset(ka, 0, sz);
  78
  79         return (ka);
  80 }
  81
  82 /*
  83  * Calculate whether we need key hint space
  84  */
  85 static size_t
  86 key_hint_size(void)
  87 {
  88
  89         return (need_hint ? sizeof(struct key_hint) : 0);
  90 }
  91
  92 /*
  93  * Calculate keys array size
  94  */
  95 size_t
  96 keys_array_size(void)
  97 {
  98
  99         return (keys_num * (sizeof(struct key_value) + key_hint_size()));
 100 }
 101
 102 /*
 103  * Clean data of keys array
 104  */
 105 void
 106 clean_keys_array(const struct bwstring *s, struct keys_array *ka)
 107 {
 108
 109         if (ka) {
 110                 for (size_t i = 0; i < keys_num; ++i) {
 111                         const struct key_value *kv;
 112
 113                         kv = get_key_from_keys_array(ka, i);
 114                         if (kv->k && kv->k != s)
 115                                 bwsfree(kv->k);
 116                 }
 117                 memset(ka, 0, keys_array_size());
 118         }
 119 }
 120
 121 /*
 122  * Get pointer to a key value in the keys set
 123  */
 124 struct key_value *
 125 get_key_from_keys_array(struct keys_array *ka, size_t ind)
 126 {
 127
 128         return ((struct key_value *)((caddr_t)ka->key +
 129             ind * (sizeof(struct key_value) + key_hint_size())));
 130 }
 131
 132 /*
 133  * Set value of a key in the keys set
 134  */
 135 void
 136 set_key_on_keys_array(struct keys_array *ka, struct bwstring *s, size_t ind)
 137 {
 138
 139         if (ka && keys_num > ind) {
 140                 struct key_value *kv;
 141
 142                 kv = get_key_from_keys_array(ka, ind);
 143
 144                 if (kv->k && kv->k != s)
 145                         bwsfree(kv->k);
 146                 kv->k = s;
 147         }
 148 }
 149
 150 /*
 151  * Initialize a sort list item
 152  */
 153 struct sort_list_item *
 154 sort_list_item_alloc(void)
 155 {
 156         struct sort_list_item *si;
 157         size_t sz;
 158
 159         sz = sizeof(struct sort_list_item) + keys_array_size();
 160         si = sort_malloc(sz);
 161         memset(si, 0, sz);
 162
 163         return (si);
 164 }
 165
 166 size_t
 167 sort_list_item_size(struct sort_list_item *si)
 168 {
 169         size_t ret = 0;
 170
 171         if (si) {
 172                 ret = sizeof(struct sort_list_item) + keys_array_size();
 173                 if (si->str)
 174                         ret += bws_memsize(si->str);
 175                 for (size_t i = 0; i < keys_num; ++i) {
 176                         const struct key_value *kv;
 177
 178                         kv = get_key_from_keys_array(&si->ka, i);
 179
 180                         if (kv->k != si->str)
 181                                 ret += bws_memsize(kv->k);
 182                 }
 183         }
 184         return (ret);
 185 }
 186
 187 /*
 188  * Calculate key for a sort list item
 189  */
 190 static void
 191 sort_list_item_make_key(struct sort_list_item *si)
 192 {
 193
 194         preproc(si->str, &(si->ka));
 195 }
 196
 197 /*
 198  * Set value of a sort list item.
 199  * Return combined string and keys memory size.
 200  */
 201 void
 202 sort_list_item_set(struct sort_list_item *si, struct bwstring *str)
 203 {
 204
 205         if (si) {
 206                 clean_keys_array(si->str, &(si->ka));
 207                 if (si->str) {
 208                         if (si->str == str) {
 209                                 /* we are trying to reset the same string */
 210                                 return;
 211                         } else {
 212                                 bwsfree(si->str);
 213                                 si->str = NULL;
 214                         }
 215                 }
 216                 si->str = str;
 217                 sort_list_item_make_key(si);
 218         }
 219 }
 220
 221 /*
 222  * De-allocate a sort list item object memory
 223  */
 224 void
 225 sort_list_item_clean(struct sort_list_item *si)
 226 {
 227
 228         if (si) {
 229                 clean_keys_array(si->str, &(si->ka));
 230                 if (si->str) {
 231                         bwsfree(si->str);
 232                         si->str = NULL;
 233                 }
 234         }
 235 }
 236
 237 /*
 238  * Skip columns according to specs
 239  */
 240 static size_t
 241 skip_cols_to_start(const struct bwstring *s, size_t cols, size_t start,
 242     bool skip_blanks, bool *empty_key)
 243 {
 244         if (cols < 1)
 245                 return (BWSLEN(s) + 1);
 246
 247         if (skip_blanks)
 248                 while (start < BWSLEN(s) && iswblank(BWS_GET(s,start)))
 249                         ++start;
 250
 251         while (start < BWSLEN(s) && cols > 1) {
 252                 --cols;
 253                 ++start;
 254         }
 255
 256         if (start >= BWSLEN(s))
 257                 *empty_key = true;
 258
 259         return (start);
 260 }
 261
 262 /*
 263  * Skip fields according to specs
 264  */
 265 static size_t
 266 skip_fields_to_start(const struct bwstring *s, size_t fields, bool *empty_field)
 267 {
 268
 269         if (fields < 2) {
 270                 if (BWSLEN(s) == 0)
 271                         *empty_field = true;
 272                 return (0);
 273         } else if (!(sort_opts_vals.tflag)) {
 274                 size_t cpos = 0;
 275                 bool pb = true;
 276
 277                 while (cpos < BWSLEN(s)) {
 278                         bool isblank;
 279
 280                         isblank = iswblank(BWS_GET(s, cpos));
 281
 282                         if (isblank && !pb) {
 283                                 --fields;
 284                                 if (fields <= 1)
 285                                         return (cpos);
 286                         }
 287                         pb = isblank;
 288                         ++cpos;
 289                 }
 290                 if (fields > 1)
 291                         *empty_field = true;
 292                 return (cpos);
 293         } else {
 294                 size_t cpos = 0;
 295
 296                 while (cpos < BWSLEN(s)) {
 297                         if (BWS_GET(s,cpos) == (wchar_t)sort_opts_vals.field_sep) {
 298                                 --fields;
 299                                 if (fields <= 1)
 300                                         return (cpos + 1);
 301                         }
 302                         ++cpos;
 303                 }
 304                 if (fields > 1)
 305                         *empty_field = true;
 306                 return (cpos);
 307         }
 308 }
 309
 310 /*
 311  * Find fields start
 312  */
 313 static void
 314 find_field_start(const struct bwstring *s, struct key_specs *ks,
 315     size_t *field_start, size_t *key_start, bool *empty_field, bool *empty_key)
 316 {
 317
 318         *field_start = skip_fields_to_start(s, ks->f1, empty_field);
 319         if (!*empty_field)
 320                 *key_start = skip_cols_to_start(s, ks->c1, *field_start,
 321                     ks->pos1b, empty_key);
 322         else
 323                 *empty_key = true;
 324 }
 325
 326 /*
 327  * Find end key position
 328  */
 329 static size_t
 330 find_field_end(const struct bwstring *s, struct key_specs *ks)
 331 {
 332         size_t f2, next_field_start, pos_end;
 333         bool empty_field, empty_key;
 334
 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         key1_read = key2_read = false;
 831
 832         if (debug_sort) {
 833                 bwsprintf(stdout, s1, "; k1=<", ">");
 834                 bwsprintf(stdout, s2, ", k2=<", ">");
 835         }
 836
 837         if (s1 == s2)
 838                 return (0);
 839
 840         if (kv1->hint->status == HS_UNINITIALIZED) {
 841                 /* read the number from the string */
 842                 read_number(s1, &sign1, smain1, &main1, sfrac1, &frac1, &SI1);
 843                 key1_read = true;
 844                 kv1->hint->v.nh.n1 = wcstoull(smain1, NULL, 10);
 845                 if(main1 < 1 && frac1 < 1)
 846                         kv1->hint->v.nh.empty=true;
 847                 kv1->hint->v.nh.si = SI1;
 848                 kv1->hint->status = (kv1->hint->v.nh.n1 != ULLONG_MAX) ?
 849                     HS_INITIALIZED : HS_ERROR;
 850                 kv1->hint->v.nh.neg = (sign1 < 0) ? true : false;
 851         }
 852
 853         if (kv2->hint->status == HS_UNINITIALIZED) {
 854                 /* read the number from the string */
 855                 read_number(s2, &sign2, smain2, &main2, sfrac2, &frac2,&SI2);
 856                 key2_read = true;
 857                 kv2->hint->v.nh.n1 = wcstoull(smain2, NULL, 10);
 858                 if(main2 < 1 && frac2 < 1)
 859                         kv2->hint->v.nh.empty=true;
 860                 kv2->hint->v.nh.si = SI2;
 861                 kv2->hint->status = (kv2->hint->v.nh.n1 != ULLONG_MAX) ?
 862                     HS_INITIALIZED : HS_ERROR;
 863                 kv2->hint->v.nh.neg = (sign2 < 0) ? true : false;
 864         }
 865
 866         if (kv1->hint->status == HS_INITIALIZED && kv2->hint->status ==
 867             HS_INITIALIZED) {
 868                 unsigned long long n1, n2;
 869                 bool neg1, neg2;
 870
 871                 e1 = kv1->hint->v.nh.empty;
 872                 e2 = kv2->hint->v.nh.empty;
 873
 874                 if (e1 && e2)
 875                         return (0);
 876
 877                 neg1 = kv1->hint->v.nh.neg;
 878                 neg2 = kv2->hint->v.nh.neg;
 879
 880                 if (neg1 && !neg2)
 881                         return (-1);
 882                 if (neg2 && !neg1)
 883                         return (+1);
 884
 885                 if (e1)
 886                         return (neg2 ? +1 : -1);
 887                 else if (e2)
 888                         return (neg1 ? -1 : +1);
 889
 890
 891                 if (use_suffix) {
 892                         cmp_res = cmpsuffix(kv1->hint->v.nh.si, kv2->hint->v.nh.si);
 893                         if (cmp_res)
 894                                 return (neg1 ? -cmp_res : cmp_res);
 895                 }
 896
 897                 n1 = kv1->hint->v.nh.n1;
 898                 n2 = kv2->hint->v.nh.n1;
 899                 if (n1 < n2)
 900                         return (neg1 ? +1 : -1);
 901                 else if (n1 > n2)
 902                         return (neg1 ? -1 : +1);
 903         }
 904
 905         /* read the numbers from the strings */
 906         if (!key1_read)
 907                 read_number(s1, &sign1, smain1, &main1, sfrac1, &frac1, &SI1);
 908         if (!key2_read)
 909                 read_number(s2, &sign2, smain2, &main2, sfrac2, &frac2, &SI2);
 910
 911         e1 = ((main1 + frac1) == 0);
 912         e2 = ((main2 + frac2) == 0);
 913
 914         if (e1 && e2)
 915                 return (0);
 916
 917         /* we know the result if the signs are different */
 918         if (sign1 < 0 && sign2 >= 0)
 919                 return (-1);
 920         if (sign1 >= 0 && sign2 < 0)
 921                 return (+1);
 922
 923         if (e1)
 924                 return ((sign2 < 0) ? +1 : -1);
 925         else if (e2)
 926                 return ((sign1 < 0) ? -1 : +1);
 927
 928         if (use_suffix) {
 929                 cmp_res = cmpsuffix(SI1, SI2);
 930                 if (cmp_res)
 931                         return ((sign1 < 0) ? -cmp_res : cmp_res);
 932         }
 933
 934         /* if both numbers are empty assume that the strings are equal */
 935         if (main1 < 1 && main2 < 1 && frac1 < 1 && frac2 < 1)
 936                 return (0);
 937
 938         /*
 939          * if the main part is of different size, we know the result
 940          * (because the leading zeros are removed)
 941          */
 942         if (main1 < main2)
 943                 cmp_res = -1;
 944         else if (main1 > main2)
 945                 cmp_res = +1;
 946         /* if the sizes are equal then simple non-collate string compare gives the correct result */
 947         else
 948                 cmp_res = wcscmp(smain1, smain2);
 949
 950         /* check fraction */
 951         if (!cmp_res)
 952                 cmp_res = wcscmp(sfrac1, sfrac2);
 953
 954         if (!cmp_res)
 955                 return (0);
 956
 957         /* reverse result if the signs are negative */
 958         if (sign1 < 0 && sign2 < 0)
 959                 cmp_res = -cmp_res;
 960
 961         return (cmp_res);
 962 }
 963
 964 /*
 965  * Implements numeric sort (-n).
 966  */
 967 static int
 968 numcoll(struct key_value *kv1, struct key_value *kv2, size_t offset)
 969 {
 970
 971         return (numcoll_impl(kv1, kv2, offset, false));
 972 }
 973
 974 /*
 975  * Implements 'human' numeric sort (-h).
 976  */
 977 static int
 978 hnumcoll(struct key_value *kv1, struct key_value *kv2, size_t offset)
 979 {
 980
 981         return (numcoll_impl(kv1, kv2, offset, true));
 982 }
 983
 984 /* Use hint space to memoize md5 computations, at least. */
 985 static void
 986 randomcoll_init_hint(struct key_value *kv, void *hash)
 987 {
 988
 989         memcpy(kv->hint->v.Rh.cached, hash, sizeof(kv->hint->v.Rh.cached));
 990         kv->hint->status = HS_INITIALIZED;
 991 }
 992
 993 /*
 994  * Implements random sort (-R).
 995  */
 996 static int
 997 randomcoll(struct key_value *kv1, struct key_value *kv2,
 998     size_t offset __unused)
 999 {
1000         struct bwstring *s1, *s2;
1001         MD5_CTX ctx1, ctx2;
1002         unsigned char hash1[MD5_DIGEST_LENGTH], hash2[MD5_DIGEST_LENGTH];
1003         int cmp;
1004
1005         s1 = kv1->k;
1006         s2 = kv2->k;
1007
1008         if (debug_sort) {
1009                 bwsprintf(stdout, s1, "; k1=<", ">");
1010                 bwsprintf(stdout, s2, ", k2=<", ">");
1011         }
1012
1013         if (s1 == s2)
1014                 return (0);
1015
1016         if (kv1->hint->status == HS_INITIALIZED &&
1017             kv2->hint->status == HS_INITIALIZED) {
1018                 cmp = memcmp(kv1->hint->v.Rh.cached,
1019                     kv2->hint->v.Rh.cached, sizeof(kv1->hint->v.Rh.cached));
1020                 if (cmp != 0)
1021                         return (cmp);
1022         }
1023
1024         memcpy(&ctx1, &md5_ctx, sizeof(MD5_CTX));
1025         memcpy(&ctx2, &md5_ctx, sizeof(MD5_CTX));
1026
1027         MD5Update(&ctx1, bwsrawdata(s1), bwsrawlen(s1));
1028         MD5Update(&ctx2, bwsrawdata(s2), bwsrawlen(s2));
1029
1030         MD5Final(hash1, &ctx1);
1031         MD5Final(hash2, &ctx2);
1032
1033         if (kv1->hint->status == HS_UNINITIALIZED)
1034                 randomcoll_init_hint(kv1, hash1);
1035         if (kv2->hint->status == HS_UNINITIALIZED)
1036                 randomcoll_init_hint(kv2, hash2);
1037
1038         return (memcmp(hash1, hash2, sizeof(hash1)));
1039 }
1040
1041 /*
1042  * Implements version sort (-V).
1043  */
1044 static int
1045 versioncoll(struct key_value *kv1, struct key_value *kv2,
1046     size_t offset __unused)
1047 {
1048         struct bwstring *s1, *s2;
1049
1050         s1 = kv1->k;
1051         s2 = kv2->k;
1052
1053         if (debug_sort) {
1054                 bwsprintf(stdout, s1, "; k1=<", ">");
1055                 bwsprintf(stdout, s2, ", k2=<", ">");
1056         }
1057
1058         if (s1 == s2)
1059                 return (0);
1060
1061         return (vcmp(s1, s2));
1062 }
1063
1064 /*
1065  * Check for minus infinity
1066  */
1067 static inline bool
1068 huge_minus(double d, int err1)
1069 {
1070
1071         if (err1 == ERANGE)
1072                 if (d == -HUGE_VAL || d == -HUGE_VALF || d == -HUGE_VALL)
1073                         return (+1);
1074
1075         return (0);
1076 }
1077
1078 /*
1079  * Check for plus infinity
1080  */
1081 static inline bool
1082 huge_plus(double d, int err1)
1083 {
1084
1085         if (err1 == ERANGE)
1086                 if (d == HUGE_VAL || d == HUGE_VALF || d == HUGE_VALL)
1087                         return (+1);
1088
1089         return (0);
1090 }
1091
1092 /*
1093  * Check whether a function is a NAN
1094  */
1095 static bool
1096 is_nan(double d)
1097 {
1098
1099         return ((d == NAN) || (isnan(d)));
1100 }
1101
1102 /*
1103  * Compare two NANs
1104  */
1105 static int
1106 cmp_nans(double d1, double d2)
1107 {
1108
1109         if (d1 < d2)
1110                 return (-1);
1111         if (d1 > d2)
1112                 return (+1);
1113         return (0);
1114 }
1115
1116 /*
1117  * Implements general numeric sort (-g).
1118  */
1119 static int
1120 gnumcoll(struct key_value *kv1, struct key_value *kv2,
1121     size_t offset __unused)
1122 {
1123         double d1, d2;
1124         int err1, err2;
1125         bool empty1, empty2, key1_read, key2_read;
1126
1127         d1 = d2 = 0;
1128         err1 = err2 = 0;
1129         key1_read = key2_read = false;
1130
1131         if (debug_sort) {
1132                 bwsprintf(stdout, kv1->k, "; k1=<", ">");
1133                 bwsprintf(stdout, kv2->k, "; k2=<", ">");
1134         }
1135
1136         if (kv1->hint->status == HS_UNINITIALIZED) {
1137                 errno = 0;
1138                 d1 = bwstod(kv1->k, &empty1);
1139                 err1 = errno;
1140
1141                 if (empty1)
1142                         kv1->hint->v.gh.notnum = true;
1143                 else if (err1 == 0) {
1144                         kv1->hint->v.gh.d = d1;
1145                         kv1->hint->v.gh.nan = is_nan(d1);
1146                         kv1->hint->status = HS_INITIALIZED;
1147                 } else
1148                         kv1->hint->status = HS_ERROR;
1149
1150                 key1_read = true;
1151         }
1152
1153         if (kv2->hint->status == HS_UNINITIALIZED) {
1154                 errno = 0;
1155                 d2 = bwstod(kv2->k, &empty2);
1156                 err2 = errno;
1157
1158                 if (empty2)
1159                         kv2->hint->v.gh.notnum = true;
1160                 else if (err2 == 0) {
1161                         kv2->hint->v.gh.d = d2;
1162                         kv2->hint->v.gh.nan = is_nan(d2);
1163                         kv2->hint->status = HS_INITIALIZED;
1164                 } else
1165                         kv2->hint->status = HS_ERROR;
1166
1167                 key2_read = true;
1168         }
1169
1170         if (kv1->hint->status == HS_INITIALIZED &&
1171             kv2->hint->status == HS_INITIALIZED) {
1172                 if (kv1->hint->v.gh.notnum)
1173                         return ((kv2->hint->v.gh.notnum) ? 0 : -1);
1174                 else if (kv2->hint->v.gh.notnum)
1175                         return (+1);
1176
1177                 if (kv1->hint->v.gh.nan)
1178                         return ((kv2->hint->v.gh.nan) ?
1179                             cmp_nans(kv1->hint->v.gh.d, kv2->hint->v.gh.d) :
1180                             -1);
1181                 else if (kv2->hint->v.gh.nan)
1182                         return (+1);
1183
1184                 d1 = kv1->hint->v.gh.d;
1185                 d2 = kv2->hint->v.gh.d;
1186
1187                 if (d1 < d2)
1188                         return (-1);
1189                 else if (d1 > d2)
1190                         return (+1);
1191                 else
1192                         return (0);
1193         }
1194
1195         if (!key1_read) {
1196                 errno = 0;
1197                 d1 = bwstod(kv1->k, &empty1);
1198                 err1 = errno;
1199         }
1200
1201         if (!key2_read) {
1202                 errno = 0;
1203                 d2 = bwstod(kv2->k, &empty2);
1204                 err2 = errno;
1205         }
1206
1207         /* Non-value case: */
1208         if (empty1)
1209                 return (empty2 ? 0 : -1);
1210         else if (empty2)
1211                 return (+1);
1212
1213         /* NAN case */
1214         if (is_nan(d1))
1215                 return (is_nan(d2) ? cmp_nans(d1, d2) : -1);
1216         else if (is_nan(d2))
1217                 return (+1);
1218
1219         /* Infinities */
1220         if (err1 == ERANGE || err2 == ERANGE) {
1221                 /* Minus infinity case */
1222                 if (huge_minus(d1, err1)) {
1223                         if (huge_minus(d2, err2)) {
1224                                 if (d1 < d2)
1225                                         return (-1);
1226                                 if (d1 > d2)
1227                                         return (+1);
1228                                 return (0);
1229                         } else
1230                                 return (-1);
1231
1232                 } else if (huge_minus(d2, err2)) {
1233                         if (huge_minus(d1, err1)) {
1234                                 if (d1 < d2)
1235                                         return (-1);
1236                                 if (d1 > d2)
1237                                         return (+1);
1238                                 return (0);
1239                         } else
1240                                 return (+1);
1241                 }
1242
1243                 /* Plus infinity case */
1244                 if (huge_plus(d1, err1)) {
1245                         if (huge_plus(d2, err2)) {
1246                                 if (d1 < d2)
1247                                         return (-1);
1248                                 if (d1 > d2)
1249                                         return (+1);
1250                                 return (0);
1251                         } else
1252                                 return (+1);
1253                 } else if (huge_plus(d2, err2)) {
1254                         if (huge_plus(d1, err1)) {
1255                                 if (d1 < d2)
1256                                         return (-1);
1257                                 if (d1 > d2)
1258                                         return (+1);
1259                                 return (0);
1260                         } else
1261                                 return (-1);
1262                 }
1263         }
1264
1265         if (d1 < d2)
1266                 return (-1);
1267         if (d1 > d2)
1268                 return (+1);
1269
1270         return (0);
1271 }
1272
1273 /*
1274  * Implements month sort (-M).
1275  */
1276 static int
1277 monthcoll(struct key_value *kv1, struct key_value *kv2, size_t offset __unused)
1278 {
1279         int val1, val2;
1280         bool key1_read, key2_read;
1281
1282         val1 = val2 = 0;
1283         key1_read = key2_read = false;
1284
1285         if (debug_sort) {
1286                 bwsprintf(stdout, kv1->k, "; k1=<", ">");
1287                 bwsprintf(stdout, kv2->k, "; k2=<", ">");
1288         }
1289
1290         if (kv1->hint->status == HS_UNINITIALIZED) {
1291                 kv1->hint->v.Mh.m = bws_month_score(kv1->k);
1292                 key1_read = true;
1293                 kv1->hint->status = HS_INITIALIZED;
1294         }
1295
1296         if (kv2->hint->status == HS_UNINITIALIZED) {
1297                 kv2->hint->v.Mh.m = bws_month_score(kv2->k);
1298                 key2_read = true;
1299                 kv2->hint->status = HS_INITIALIZED;
1300         }
1301
1302         if (kv1->hint->status == HS_INITIALIZED) {
1303                 val1 = kv1->hint->v.Mh.m;
1304                 key1_read = true;
1305         }
1306
1307         if (kv2->hint->status == HS_INITIALIZED) {
1308                 val2 = kv2->hint->v.Mh.m;
1309                 key2_read = true;
1310         }
1311
1312         if (!key1_read)
1313                 val1 = bws_month_score(kv1->k);
1314         if (!key2_read)
1315                 val2 = bws_month_score(kv2->k);
1316
1317         if (val1 == val2) {
1318                 return (0);
1319         }
1320         if (val1 < val2)
1321                 return (-1);
1322         return (+1);
1323 }