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