1235267Sgabor/*- 2235267Sgabor * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org> 3251245Sgabor * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com> 4235267Sgabor * All rights reserved. 5235267Sgabor * 6235267Sgabor * Redistribution and use in source and binary forms, with or without 7235267Sgabor * modification, are permitted provided that the following conditions 8235267Sgabor * are met: 9235267Sgabor * 1. Redistributions of source code must retain the above copyright 10235267Sgabor * notice, this list of conditions and the following disclaimer. 11235267Sgabor * 2. Redistributions in binary form must reproduce the above copyright 12235267Sgabor * notice, this list of conditions and the following disclaimer in the 13235267Sgabor * documentation and/or other materials provided with the distribution. 14235267Sgabor * 15235267Sgabor * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16235267Sgabor * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17235267Sgabor * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18235267Sgabor * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19235267Sgabor * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20235267Sgabor * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21235267Sgabor * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22235267Sgabor * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23235267Sgabor * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24235267Sgabor * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25235267Sgabor * SUCH DAMAGE. 26235267Sgabor */ 27235267Sgabor 28235267Sgabor#include <sys/cdefs.h> 29235267Sgabor__FBSDID("$FreeBSD: releng/10.2/usr.bin/sort/coll.c 251245 2013-06-02 09:43:48Z gabor $"); 30235267Sgabor 31235267Sgabor#include <sys/types.h> 32235267Sgabor 33235267Sgabor#include <errno.h> 34235267Sgabor#include <err.h> 35235267Sgabor#include <langinfo.h> 36235267Sgabor#include <limits.h> 37235267Sgabor#include <math.h> 38235267Sgabor#include <md5.h> 39235267Sgabor#include <stdlib.h> 40235267Sgabor#include <string.h> 41235267Sgabor#include <wchar.h> 42235267Sgabor#include <wctype.h> 43235267Sgabor 44235267Sgabor#include "coll.h" 45235267Sgabor#include "vsort.h" 46235267Sgabor 47235435Sgaborstruct key_specs *keys; 48235267Sgaborsize_t keys_num = 0; 49235267Sgabor 50242430Sgaborwint_t symbol_decimal_point = L'.'; 51235267Sgabor/* there is no default thousands separator in collate rules: */ 52242430Sgaborwint_t symbol_thousands_sep = 0; 53242430Sgaborwint_t symbol_negative_sign = L'-'; 54242430Sgaborwint_t symbol_positive_sign = L'+'; 55235267Sgabor 56235267Sgaborstatic int wstrcoll(struct key_value *kv1, struct key_value *kv2, size_t offset); 57235267Sgaborstatic int gnumcoll(struct key_value*, struct key_value *, size_t offset); 58235267Sgaborstatic int monthcoll(struct key_value*, struct key_value *, size_t offset); 59235267Sgaborstatic int numcoll(struct key_value*, struct key_value *, size_t offset); 60235267Sgaborstatic int hnumcoll(struct key_value*, struct key_value *, size_t offset); 61235267Sgaborstatic int randomcoll(struct key_value*, struct key_value *, size_t offset); 62235267Sgaborstatic int versioncoll(struct key_value*, struct key_value *, size_t offset); 63235267Sgabor 64235267Sgabor/* 65235267Sgabor * Allocate keys array 66235267Sgabor */ 67235267Sgaborstruct keys_array * 68235267Sgaborkeys_array_alloc(void) 69235267Sgabor{ 70235267Sgabor struct keys_array *ka; 71235267Sgabor size_t sz; 72235267Sgabor 73235267Sgabor sz = keys_array_size(); 74235267Sgabor ka = sort_malloc(sz); 75235267Sgabor memset(ka, 0, sz); 76235267Sgabor 77235267Sgabor return (ka); 78235267Sgabor} 79235267Sgabor 80235267Sgabor/* 81235267Sgabor * Calculate whether we need key hint space 82235267Sgabor */ 83235267Sgaborstatic size_t 84235267Sgaborkey_hint_size(void) 85235267Sgabor{ 86235267Sgabor 87235267Sgabor return (need_hint ? sizeof(struct key_hint) : 0); 88235267Sgabor} 89235267Sgabor 90235267Sgabor/* 91235267Sgabor * Calculate keys array size 92235267Sgabor */ 93235267Sgaborsize_t 94235267Sgaborkeys_array_size(void) 95235267Sgabor{ 96235267Sgabor 97235267Sgabor return (keys_num * (sizeof(struct key_value) + key_hint_size())); 98235267Sgabor} 99235267Sgabor 100235267Sgabor/* 101235267Sgabor * Clean data of keys array 102235267Sgabor */ 103235267Sgaborvoid 104235267Sgaborclean_keys_array(const struct bwstring *s, struct keys_array *ka) 105235267Sgabor{ 106235267Sgabor 107235267Sgabor if (ka) { 108235267Sgabor for (size_t i = 0; i < keys_num; ++i) 109235267Sgabor if (ka->key[i].k && ka->key[i].k != s) 110235267Sgabor bwsfree(ka->key[i].k); 111235267Sgabor memset(ka, 0, keys_array_size()); 112235267Sgabor } 113235267Sgabor} 114235267Sgabor 115235267Sgabor/* 116235267Sgabor * Set value of a key in the keys set 117235267Sgabor */ 118235267Sgaborvoid 119235267Sgaborset_key_on_keys_array(struct keys_array *ka, struct bwstring *s, size_t ind) 120235267Sgabor{ 121235267Sgabor 122235267Sgabor if (ka && keys_num > ind) { 123235267Sgabor struct key_value *kv; 124235267Sgabor 125235267Sgabor kv = &(ka->key[ind]); 126235267Sgabor 127235267Sgabor if (kv->k && kv->k != s) 128235267Sgabor bwsfree(kv->k); 129235267Sgabor kv->k = s; 130235267Sgabor } 131235267Sgabor} 132235267Sgabor 133235267Sgabor/* 134235267Sgabor * Initialize a sort list item 135235267Sgabor */ 136235267Sgaborstruct sort_list_item * 137235267Sgaborsort_list_item_alloc(void) 138235267Sgabor{ 139235267Sgabor struct sort_list_item *si; 140235267Sgabor size_t sz; 141235267Sgabor 142235267Sgabor sz = sizeof(struct sort_list_item) + keys_array_size(); 143235267Sgabor si = sort_malloc(sz); 144235267Sgabor memset(si, 0, sz); 145235267Sgabor 146235267Sgabor return (si); 147235267Sgabor} 148235267Sgabor 149235267Sgaborsize_t 150235267Sgaborsort_list_item_size(struct sort_list_item *si) 151235267Sgabor{ 152235267Sgabor size_t ret = 0; 153235267Sgabor 154235267Sgabor if (si) { 155235267Sgabor ret = sizeof(struct sort_list_item) + keys_array_size(); 156235267Sgabor if (si->str) 157235267Sgabor ret += bws_memsize(si->str); 158235267Sgabor for (size_t i = 0; i < keys_num; ++i) { 159235267Sgabor struct key_value *kv; 160235267Sgabor 161235267Sgabor kv = &(si->ka.key[i]); 162235267Sgabor 163235267Sgabor if (kv->k != si->str) 164235267Sgabor ret += bws_memsize(kv->k); 165235267Sgabor } 166235267Sgabor } 167235267Sgabor return (ret); 168235267Sgabor} 169235267Sgabor 170235267Sgabor/* 171235267Sgabor * Calculate key for a sort list item 172235267Sgabor */ 173235267Sgaborstatic void 174235267Sgaborsort_list_item_make_key(struct sort_list_item *si) 175235267Sgabor{ 176235267Sgabor 177235267Sgabor preproc(si->str, &(si->ka)); 178235267Sgabor} 179235267Sgabor 180235267Sgabor/* 181235267Sgabor * Set value of a sort list item. 182235267Sgabor * Return combined string and keys memory size. 183235267Sgabor */ 184235267Sgaborvoid 185235267Sgaborsort_list_item_set(struct sort_list_item *si, struct bwstring *str) 186235267Sgabor{ 187235267Sgabor 188235267Sgabor if (si) { 189235267Sgabor clean_keys_array(si->str, &(si->ka)); 190235267Sgabor if (si->str) { 191235267Sgabor if (si->str == str) { 192235267Sgabor /* we are trying to reset the same string */ 193235267Sgabor return; 194235267Sgabor } else { 195235267Sgabor bwsfree(si->str); 196235267Sgabor si->str = NULL; 197235267Sgabor } 198235267Sgabor } 199235267Sgabor si->str = str; 200235267Sgabor sort_list_item_make_key(si); 201235267Sgabor } 202235267Sgabor} 203235267Sgabor 204235267Sgabor/* 205235267Sgabor * De-allocate a sort list item object memory 206235267Sgabor */ 207235267Sgaborvoid 208235267Sgaborsort_list_item_clean(struct sort_list_item *si) 209235267Sgabor{ 210235267Sgabor 211235267Sgabor if (si) { 212235267Sgabor clean_keys_array(si->str, &(si->ka)); 213235267Sgabor if (si->str) { 214235267Sgabor bwsfree(si->str); 215235267Sgabor si->str = NULL; 216235267Sgabor } 217235267Sgabor } 218235267Sgabor} 219235267Sgabor 220235267Sgabor/* 221235267Sgabor * Skip columns according to specs 222235267Sgabor */ 223235267Sgaborstatic size_t 224235267Sgaborskip_cols_to_start(const struct bwstring *s, size_t cols, size_t start, 225235267Sgabor bool skip_blanks, bool *empty_key) 226235267Sgabor{ 227235267Sgabor if (cols < 1) 228235267Sgabor return (BWSLEN(s) + 1); 229235267Sgabor 230235267Sgabor if (skip_blanks) 231235267Sgabor while (start < BWSLEN(s) && iswblank(BWS_GET(s,start))) 232235267Sgabor ++start; 233235267Sgabor 234235267Sgabor while (start < BWSLEN(s) && cols > 1) { 235235267Sgabor --cols; 236235267Sgabor ++start; 237235267Sgabor } 238235267Sgabor 239235267Sgabor if (start >= BWSLEN(s)) 240235267Sgabor *empty_key = true; 241235267Sgabor 242235267Sgabor return (start); 243235267Sgabor} 244235267Sgabor 245235267Sgabor/* 246235267Sgabor * Skip fields according to specs 247235267Sgabor */ 248235267Sgaborstatic size_t 249235267Sgaborskip_fields_to_start(const struct bwstring *s, size_t fields, bool *empty_field) 250235267Sgabor{ 251235267Sgabor 252235267Sgabor if (fields < 2) { 253235267Sgabor if (BWSLEN(s) == 0) 254235267Sgabor *empty_field = true; 255235267Sgabor return (0); 256235267Sgabor } else if (!(sort_opts_vals.tflag)) { 257235267Sgabor size_t cpos = 0; 258235267Sgabor bool pb = true; 259235267Sgabor 260235267Sgabor while (cpos < BWSLEN(s)) { 261235267Sgabor bool isblank; 262235267Sgabor 263242430Sgabor isblank = iswblank(BWS_GET(s, cpos)); 264235267Sgabor 265235267Sgabor if (isblank && !pb) { 266235267Sgabor --fields; 267235267Sgabor if (fields <= 1) 268235267Sgabor return (cpos); 269235267Sgabor } 270235267Sgabor pb = isblank; 271235267Sgabor ++cpos; 272235267Sgabor } 273235267Sgabor if (fields > 1) 274235267Sgabor *empty_field = true; 275235267Sgabor return (cpos); 276235267Sgabor } else { 277235267Sgabor size_t cpos = 0; 278235267Sgabor 279235267Sgabor while (cpos < BWSLEN(s)) { 280242430Sgabor if (BWS_GET(s,cpos) == (wchar_t)sort_opts_vals.field_sep) { 281235267Sgabor --fields; 282235267Sgabor if (fields <= 1) 283235267Sgabor return (cpos + 1); 284235267Sgabor } 285235267Sgabor ++cpos; 286235267Sgabor } 287235267Sgabor if (fields > 1) 288235267Sgabor *empty_field = true; 289235267Sgabor return (cpos); 290235267Sgabor } 291235267Sgabor} 292235267Sgabor 293235267Sgabor/* 294235267Sgabor * Find fields start 295235267Sgabor */ 296235267Sgaborstatic void 297235267Sgaborfind_field_start(const struct bwstring *s, struct key_specs *ks, 298235267Sgabor size_t *field_start, size_t *key_start, bool *empty_field, bool *empty_key) 299235267Sgabor{ 300235267Sgabor 301235267Sgabor *field_start = skip_fields_to_start(s, ks->f1, empty_field); 302235267Sgabor if (!*empty_field) 303235267Sgabor *key_start = skip_cols_to_start(s, ks->c1, *field_start, 304235267Sgabor ks->pos1b, empty_key); 305235267Sgabor else 306235267Sgabor *empty_key = true; 307235267Sgabor} 308235267Sgabor 309235267Sgabor/* 310235267Sgabor * Find end key position 311235267Sgabor */ 312235267Sgaborstatic size_t 313235267Sgaborfind_field_end(const struct bwstring *s, struct key_specs *ks) 314235267Sgabor{ 315235267Sgabor size_t f2, next_field_start, pos_end; 316235267Sgabor bool empty_field, empty_key; 317235267Sgabor 318235267Sgabor pos_end = 0; 319235267Sgabor next_field_start = 0; 320235267Sgabor empty_field = false; 321235267Sgabor empty_key = false; 322235267Sgabor f2 = ks->f2; 323235267Sgabor 324235267Sgabor if (f2 == 0) 325235267Sgabor return (BWSLEN(s) + 1); 326235267Sgabor else { 327235267Sgabor if (ks->c2 == 0) { 328235267Sgabor next_field_start = skip_fields_to_start(s, f2 + 1, 329235267Sgabor &empty_field); 330235267Sgabor if ((next_field_start > 0) && sort_opts_vals.tflag && 331242430Sgabor ((wchar_t)sort_opts_vals.field_sep == BWS_GET(s, 332235267Sgabor next_field_start - 1))) 333235267Sgabor --next_field_start; 334235267Sgabor } else 335235267Sgabor next_field_start = skip_fields_to_start(s, f2, 336235267Sgabor &empty_field); 337235267Sgabor } 338235267Sgabor 339235267Sgabor if (empty_field || (next_field_start >= BWSLEN(s))) 340235267Sgabor return (BWSLEN(s) + 1); 341235267Sgabor 342235267Sgabor if (ks->c2) { 343235267Sgabor pos_end = skip_cols_to_start(s, ks->c2, next_field_start, 344235267Sgabor ks->pos2b, &empty_key); 345235267Sgabor if (pos_end < BWSLEN(s)) 346235267Sgabor ++pos_end; 347235267Sgabor } else 348235267Sgabor pos_end = next_field_start; 349235267Sgabor 350235267Sgabor return (pos_end); 351235267Sgabor} 352235267Sgabor 353235267Sgabor/* 354235267Sgabor * Cut a field according to the key specs 355235267Sgabor */ 356235267Sgaborstatic struct bwstring * 357235267Sgaborcut_field(const struct bwstring *s, struct key_specs *ks) 358235267Sgabor{ 359235267Sgabor struct bwstring *ret = NULL; 360235267Sgabor 361235267Sgabor if (s && ks) { 362235267Sgabor size_t field_start, key_end, key_start, sz; 363235267Sgabor bool empty_field, empty_key; 364235267Sgabor 365235267Sgabor field_start = 0; 366235267Sgabor key_start = 0; 367235267Sgabor empty_field = false; 368235267Sgabor empty_key = false; 369235267Sgabor 370235267Sgabor find_field_start(s, ks, &field_start, &key_start, 371235267Sgabor &empty_field, &empty_key); 372235267Sgabor 373235267Sgabor if (empty_key) 374235267Sgabor sz = 0; 375235267Sgabor else { 376235267Sgabor key_end = find_field_end(s, ks); 377235267Sgabor sz = (key_end < key_start) ? 0 : (key_end - key_start); 378235267Sgabor } 379235267Sgabor 380235267Sgabor ret = bwsalloc(sz); 381235267Sgabor if (sz) 382235267Sgabor bwsnocpy(ret, s, key_start, sz); 383235267Sgabor } else 384235267Sgabor ret = bwsalloc(0); 385235267Sgabor 386235267Sgabor return (ret); 387235267Sgabor} 388235267Sgabor 389235267Sgabor/* 390235267Sgabor * Preprocesses a line applying the necessary transformations 391235267Sgabor * specified by command line options and returns the preprocessed 392235267Sgabor * string, which can be used to compare. 393235267Sgabor */ 394235267Sgaborint 395235267Sgaborpreproc(struct bwstring *s, struct keys_array *ka) 396235267Sgabor{ 397235267Sgabor 398235267Sgabor if (sort_opts_vals.kflag) 399235267Sgabor for (size_t i = 0; i < keys_num; i++) { 400235267Sgabor struct bwstring *key; 401235267Sgabor struct key_specs *kspecs; 402235267Sgabor struct sort_mods *sm; 403235267Sgabor 404235267Sgabor kspecs = &(keys[i]); 405235267Sgabor key = cut_field(s, kspecs); 406235267Sgabor 407235267Sgabor sm = &(kspecs->sm); 408235267Sgabor if (sm->dflag) 409235267Sgabor key = dictionary_order(key); 410235267Sgabor else if (sm->iflag) 411235267Sgabor key = ignore_nonprinting(key); 412235267Sgabor if (sm->fflag || sm->Mflag) 413235267Sgabor key = ignore_case(key); 414235267Sgabor 415235267Sgabor set_key_on_keys_array(ka, key, i); 416235267Sgabor } 417235267Sgabor else { 418235267Sgabor struct bwstring *ret = NULL; 419235267Sgabor struct sort_mods *sm = default_sort_mods; 420235267Sgabor 421235267Sgabor if (sm->bflag) { 422235267Sgabor if (ret == NULL) 423235267Sgabor ret = bwsdup(s); 424235267Sgabor ret = ignore_leading_blanks(ret); 425235267Sgabor } 426235267Sgabor if (sm->dflag) { 427235267Sgabor if (ret == NULL) 428235267Sgabor ret = bwsdup(s); 429235267Sgabor ret = dictionary_order(ret); 430235267Sgabor } else if (sm->iflag) { 431235267Sgabor if (ret == NULL) 432235267Sgabor ret = bwsdup(s); 433235267Sgabor ret = ignore_nonprinting(ret); 434235267Sgabor } 435235267Sgabor if (sm->fflag || sm->Mflag) { 436235267Sgabor if (ret == NULL) 437235267Sgabor ret = bwsdup(s); 438235267Sgabor ret = ignore_case(ret); 439235267Sgabor } 440235267Sgabor if (ret == NULL) 441235267Sgabor set_key_on_keys_array(ka, s, 0); 442235267Sgabor else 443235267Sgabor set_key_on_keys_array(ka, ret, 0); 444235267Sgabor } 445235267Sgabor 446235267Sgabor return 0; 447235267Sgabor} 448235267Sgabor 449235267Sgaborcmpcoll_t 450235267Sgaborget_sort_func(struct sort_mods *sm) 451235267Sgabor{ 452235267Sgabor 453235267Sgabor if (sm->nflag) 454235267Sgabor return (numcoll); 455235267Sgabor else if (sm->hflag) 456235267Sgabor return (hnumcoll); 457235267Sgabor else if (sm->gflag) 458235267Sgabor return (gnumcoll); 459235267Sgabor else if (sm->Mflag) 460235267Sgabor return (monthcoll); 461235267Sgabor else if (sm->Rflag) 462235267Sgabor return (randomcoll); 463235267Sgabor else if (sm->Vflag) 464235267Sgabor return (versioncoll); 465235267Sgabor else 466235267Sgabor return (wstrcoll); 467235267Sgabor} 468235267Sgabor 469235267Sgabor/* 470235267Sgabor * Compares the given strings. Returns a positive number if 471235267Sgabor * the first precedes the second, a negative number if the second is 472235267Sgabor * the preceding one, and zero if they are equal. This function calls 473235267Sgabor * the underlying collate functions, which done the actual comparison. 474235267Sgabor */ 475235267Sgaborint 476235267Sgaborkey_coll(struct keys_array *ps1, struct keys_array *ps2, size_t offset) 477235267Sgabor{ 478235267Sgabor struct sort_mods *sm; 479235267Sgabor int res = 0; 480235267Sgabor 481235267Sgabor for (size_t i = 0; i < keys_num; ++i) { 482235267Sgabor sm = &(keys[i].sm); 483235267Sgabor 484235267Sgabor if (sm->rflag) 485235267Sgabor res = sm->func(&(ps2->key[i]), &(ps1->key[i]), offset); 486235267Sgabor else 487235267Sgabor res = sm->func(&(ps1->key[i]), &(ps2->key[i]), offset); 488235267Sgabor 489235267Sgabor if (res) 490235267Sgabor break; 491235267Sgabor 492235267Sgabor /* offset applies to only the first key */ 493235267Sgabor offset = 0; 494235267Sgabor } 495235267Sgabor return (res); 496235267Sgabor} 497235267Sgabor 498235267Sgabor/* 499235267Sgabor * Compare two strings. 500235267Sgabor * Plain symbol-by-symbol comparison. 501235267Sgabor */ 502235267Sgaborint 503235267Sgabortop_level_str_coll(const struct bwstring *s1, const struct bwstring *s2) 504235267Sgabor{ 505235267Sgabor 506235267Sgabor if (default_sort_mods->rflag) { 507235267Sgabor const struct bwstring *tmp; 508235267Sgabor 509235267Sgabor tmp = s1; 510235267Sgabor s1 = s2; 511235267Sgabor s2 = tmp; 512235267Sgabor } 513235267Sgabor 514235267Sgabor return (bwscoll(s1, s2, 0)); 515235267Sgabor} 516235267Sgabor 517235267Sgabor/* 518235267Sgabor * Compare a string and a sort list item, according to the sort specs. 519235267Sgabor */ 520235267Sgaborint 521235267Sgaborstr_list_coll(struct bwstring *str1, struct sort_list_item **ss2) 522235267Sgabor{ 523235267Sgabor struct keys_array *ka1; 524235267Sgabor int ret = 0; 525235267Sgabor 526235267Sgabor ka1 = keys_array_alloc(); 527235267Sgabor 528235267Sgabor preproc(str1, ka1); 529235267Sgabor 530235267Sgabor sort_list_item_make_key(*ss2); 531235267Sgabor 532235267Sgabor if (debug_sort) { 533235267Sgabor bwsprintf(stdout, str1, "; s1=<", ">"); 534235267Sgabor bwsprintf(stdout, (*ss2)->str, ", s2=<", ">"); 535235267Sgabor } 536235267Sgabor 537235267Sgabor ret = key_coll(ka1, &((*ss2)->ka), 0); 538235267Sgabor 539235267Sgabor if (debug_sort) 540235267Sgabor printf("; cmp1=%d", ret); 541235267Sgabor 542235267Sgabor clean_keys_array(str1, ka1); 543235267Sgabor sort_free(ka1); 544235267Sgabor 545235267Sgabor if ((ret == 0) && !(sort_opts_vals.sflag) && sort_opts_vals.complex_sort) { 546235267Sgabor ret = top_level_str_coll(str1, ((*ss2)->str)); 547235267Sgabor if (debug_sort) 548235267Sgabor printf("; cmp2=%d", ret); 549235267Sgabor } 550235267Sgabor 551235267Sgabor if (debug_sort) 552235267Sgabor printf("\n"); 553235267Sgabor 554235267Sgabor return (ret); 555235267Sgabor} 556235267Sgabor 557235267Sgabor/* 558235267Sgabor * Compare two sort list items, according to the sort specs. 559235267Sgabor */ 560235267Sgaborint 561235267Sgaborlist_coll_offset(struct sort_list_item **ss1, struct sort_list_item **ss2, 562235267Sgabor size_t offset) 563235267Sgabor{ 564235267Sgabor int ret; 565235267Sgabor 566235267Sgabor ret = key_coll(&((*ss1)->ka), &((*ss2)->ka), offset); 567235267Sgabor 568235267Sgabor if (debug_sort) { 569235267Sgabor if (offset) 570235267Sgabor printf("; offset=%d", (int) offset); 571235267Sgabor bwsprintf(stdout, ((*ss1)->str), "; s1=<", ">"); 572235267Sgabor bwsprintf(stdout, ((*ss2)->str), ", s2=<", ">"); 573235267Sgabor printf("; cmp1=%d\n", ret); 574235267Sgabor } 575235267Sgabor 576235267Sgabor if (ret) 577235267Sgabor return (ret); 578235267Sgabor 579235267Sgabor if (!(sort_opts_vals.sflag) && sort_opts_vals.complex_sort) { 580235267Sgabor ret = top_level_str_coll(((*ss1)->str), ((*ss2)->str)); 581235267Sgabor if (debug_sort) 582235267Sgabor printf("; cmp2=%d\n", ret); 583235267Sgabor } 584235267Sgabor 585235267Sgabor return (ret); 586235267Sgabor} 587235267Sgabor 588235267Sgabor/* 589235267Sgabor * Compare two sort list items, according to the sort specs. 590235267Sgabor */ 591235267Sgaborint 592235267Sgaborlist_coll(struct sort_list_item **ss1, struct sort_list_item **ss2) 593235267Sgabor{ 594235267Sgabor 595235267Sgabor return (list_coll_offset(ss1, ss2, 0)); 596235267Sgabor} 597235267Sgabor 598235267Sgabor#define LSCDEF(N) \ 599235267Sgaborstatic int \ 600235267Sgaborlist_coll_##N(struct sort_list_item **ss1, struct sort_list_item **ss2) \ 601235267Sgabor{ \ 602235267Sgabor \ 603235267Sgabor return (list_coll_offset(ss1, ss2, N)); \ 604235267Sgabor} 605235267Sgabor 606235267SgaborLSCDEF(1) 607235267SgaborLSCDEF(2) 608235267SgaborLSCDEF(3) 609235267SgaborLSCDEF(4) 610235267SgaborLSCDEF(5) 611235267SgaborLSCDEF(6) 612235267SgaborLSCDEF(7) 613235267SgaborLSCDEF(8) 614235267SgaborLSCDEF(9) 615235267SgaborLSCDEF(10) 616235267SgaborLSCDEF(11) 617235267SgaborLSCDEF(12) 618235267SgaborLSCDEF(13) 619235267SgaborLSCDEF(14) 620235267SgaborLSCDEF(15) 621235267SgaborLSCDEF(16) 622235267SgaborLSCDEF(17) 623235267SgaborLSCDEF(18) 624235267SgaborLSCDEF(19) 625235267SgaborLSCDEF(20) 626235267Sgabor 627235267Sgaborlistcoll_t 628235267Sgaborget_list_call_func(size_t offset) 629235267Sgabor{ 630235267Sgabor static const listcoll_t lsarray[] = { list_coll, list_coll_1, 631235267Sgabor list_coll_2, list_coll_3, list_coll_4, list_coll_5, 632235267Sgabor list_coll_6, list_coll_7, list_coll_8, list_coll_9, 633235267Sgabor list_coll_10, list_coll_11, list_coll_12, list_coll_13, 634235267Sgabor list_coll_14, list_coll_15, list_coll_16, list_coll_17, 635235267Sgabor list_coll_18, list_coll_19, list_coll_20 }; 636235267Sgabor 637235267Sgabor if (offset <= 20) 638235267Sgabor return (lsarray[offset]); 639235267Sgabor 640235267Sgabor return (list_coll); 641235267Sgabor} 642235267Sgabor 643235267Sgabor/* 644235267Sgabor * Compare two sort list items, only by their original string. 645235267Sgabor */ 646235267Sgaborint 647235267Sgaborlist_coll_by_str_only(struct sort_list_item **ss1, struct sort_list_item **ss2) 648235267Sgabor{ 649235267Sgabor 650235267Sgabor return (top_level_str_coll(((*ss1)->str), ((*ss2)->str))); 651235267Sgabor} 652235267Sgabor 653235267Sgabor/* 654235267Sgabor * Maximum size of a number in the string (before or after decimal point) 655235267Sgabor */ 656235267Sgabor#define MAX_NUM_SIZE (128) 657235267Sgabor 658235267Sgabor/* 659235267Sgabor * Set suffix value 660235267Sgabor */ 661235267Sgaborstatic void setsuffix(wchar_t c, unsigned char *si) 662235267Sgabor{ 663235267Sgabor switch (c){ 664235267Sgabor case L'k': 665235267Sgabor case L'K': 666235267Sgabor *si = 1; 667235267Sgabor break; 668235267Sgabor case L'M': 669235267Sgabor *si = 2; 670235267Sgabor break; 671235267Sgabor case L'G': 672235267Sgabor *si = 3; 673235267Sgabor break; 674235267Sgabor case L'T': 675235267Sgabor *si = 4; 676235267Sgabor break; 677235267Sgabor case L'P': 678235267Sgabor *si = 5; 679235267Sgabor break; 680235267Sgabor case L'E': 681235267Sgabor *si = 6; 682235267Sgabor break; 683235267Sgabor case L'Z': 684235267Sgabor *si = 7; 685235267Sgabor break; 686235267Sgabor case L'Y': 687235267Sgabor *si = 8; 688235267Sgabor break; 689235267Sgabor default: 690235267Sgabor *si = 0; 691235267Sgabor }; 692235267Sgabor} 693235267Sgabor 694235267Sgabor/* 695235267Sgabor * Read string s and parse the string into a fixed-decimal-point number. 696235267Sgabor * sign equals -1 if the number is negative (explicit plus is not allowed, 697235267Sgabor * according to GNU sort's "info sort". 698235267Sgabor * The number part before decimal point is in the smain, after the decimal 699235267Sgabor * point is in sfrac, tail is the pointer to the remainder of the string. 700235267Sgabor */ 701235267Sgaborstatic int 702242430Sgaborread_number(struct bwstring *s0, int *sign, wchar_t *smain, size_t *main_len, wchar_t *sfrac, size_t *frac_len, unsigned char *si) 703235267Sgabor{ 704235267Sgabor bwstring_iterator s; 705235267Sgabor 706235267Sgabor s = bws_begin(s0); 707235267Sgabor 708235267Sgabor /* always end the fraction with zero, even if we have no fraction */ 709235267Sgabor sfrac[0] = 0; 710235267Sgabor 711235267Sgabor while (iswblank(bws_get_iter_value(s))) 712235267Sgabor s = bws_iterator_inc(s, 1); 713235267Sgabor 714242430Sgabor if (bws_get_iter_value(s) == (wchar_t)symbol_negative_sign) { 715235267Sgabor *sign = -1; 716235267Sgabor s = bws_iterator_inc(s, 1); 717235267Sgabor } 718235267Sgabor 719235267Sgabor // This is '0', not '\0', do not change this 720235267Sgabor while (iswdigit(bws_get_iter_value(s)) && 721235267Sgabor (bws_get_iter_value(s) == L'0')) 722235267Sgabor s = bws_iterator_inc(s, 1); 723235267Sgabor 724235267Sgabor while (bws_get_iter_value(s) && *main_len < MAX_NUM_SIZE) { 725235267Sgabor if (iswdigit(bws_get_iter_value(s))) { 726235267Sgabor smain[*main_len] = bws_get_iter_value(s); 727235267Sgabor s = bws_iterator_inc(s, 1); 728235267Sgabor *main_len += 1; 729235267Sgabor } else if (symbol_thousands_sep && 730242430Sgabor (bws_get_iter_value(s) == (wchar_t)symbol_thousands_sep)) 731235267Sgabor s = bws_iterator_inc(s, 1); 732235267Sgabor else 733235267Sgabor break; 734235267Sgabor } 735235267Sgabor 736235267Sgabor smain[*main_len] = 0; 737235267Sgabor 738242430Sgabor if (bws_get_iter_value(s) == (wchar_t)symbol_decimal_point) { 739235267Sgabor s = bws_iterator_inc(s, 1); 740235267Sgabor while (iswdigit(bws_get_iter_value(s)) && 741235267Sgabor *frac_len < MAX_NUM_SIZE) { 742235267Sgabor sfrac[*frac_len] = bws_get_iter_value(s); 743235267Sgabor s = bws_iterator_inc(s, 1); 744235267Sgabor *frac_len += 1; 745235267Sgabor } 746235267Sgabor sfrac[*frac_len] = 0; 747235267Sgabor 748235267Sgabor while (*frac_len > 0 && sfrac[*frac_len - 1] == L'0') { 749235267Sgabor --(*frac_len); 750235267Sgabor sfrac[*frac_len] = L'\0'; 751235267Sgabor } 752235267Sgabor } 753235267Sgabor 754235267Sgabor setsuffix(bws_get_iter_value(s),si); 755235267Sgabor 756235267Sgabor if ((*main_len + *frac_len) == 0) 757235267Sgabor *sign = 0; 758235267Sgabor 759235267Sgabor return (0); 760235267Sgabor} 761235267Sgabor 762235267Sgabor/* 763235267Sgabor * Implements string sort. 764235267Sgabor */ 765235267Sgaborstatic int 766235267Sgaborwstrcoll(struct key_value *kv1, struct key_value *kv2, size_t offset) 767235267Sgabor{ 768235267Sgabor 769235267Sgabor if (debug_sort) { 770235267Sgabor if (offset) 771235267Sgabor printf("; offset=%d\n", (int) offset); 772235267Sgabor bwsprintf(stdout, kv1->k, "; k1=<", ">"); 773235267Sgabor printf("(%zu)", BWSLEN(kv1->k)); 774235267Sgabor bwsprintf(stdout, kv2->k, ", k2=<", ">"); 775235267Sgabor printf("(%zu)", BWSLEN(kv2->k)); 776235267Sgabor } 777235267Sgabor 778235267Sgabor return (bwscoll(kv1->k, kv2->k, offset)); 779235267Sgabor} 780235267Sgabor 781235267Sgabor/* 782235267Sgabor * Compare two suffixes 783235267Sgabor */ 784235267Sgaborstatic inline int 785235267Sgaborcmpsuffix(unsigned char si1, unsigned char si2) 786235267Sgabor{ 787235267Sgabor 788235267Sgabor return ((char)si1 - (char)si2); 789235267Sgabor} 790235267Sgabor 791235267Sgabor/* 792235267Sgabor * Implements numeric sort for -n and -h. 793235267Sgabor */ 794235267Sgaborstatic int 795236764Sgabornumcoll_impl(struct key_value *kv1, struct key_value *kv2, 796236764Sgabor size_t offset __unused, bool use_suffix) 797235267Sgabor{ 798235267Sgabor struct bwstring *s1, *s2; 799235267Sgabor wchar_t sfrac1[MAX_NUM_SIZE + 1], sfrac2[MAX_NUM_SIZE + 1]; 800235267Sgabor wchar_t smain1[MAX_NUM_SIZE + 1], smain2[MAX_NUM_SIZE + 1]; 801242430Sgabor int cmp_res, sign1, sign2; 802242430Sgabor size_t frac1, frac2, main1, main2; 803235267Sgabor unsigned char SI1, SI2; 804235267Sgabor bool e1, e2, key1_read, key2_read; 805235267Sgabor 806235267Sgabor s1 = kv1->k; 807235267Sgabor s2 = kv2->k; 808235267Sgabor sign1 = sign2 = 0; 809235267Sgabor main1 = main2 = 0; 810235267Sgabor frac1 = frac2 = 0; 811235267Sgabor 812235267Sgabor cmp_res = 0; 813235267Sgabor key1_read = key2_read = false; 814235267Sgabor 815235267Sgabor if (debug_sort) { 816235267Sgabor bwsprintf(stdout, s1, "; k1=<", ">"); 817235267Sgabor bwsprintf(stdout, s2, ", k2=<", ">"); 818235267Sgabor } 819235267Sgabor 820235267Sgabor if (s1 == s2) 821235267Sgabor return (0); 822235267Sgabor 823235267Sgabor if (kv1->hint->status == HS_UNINITIALIZED) { 824235267Sgabor /* read the number from the string */ 825235267Sgabor read_number(s1, &sign1, smain1, &main1, sfrac1, &frac1, &SI1); 826235267Sgabor key1_read = true; 827235267Sgabor kv1->hint->v.nh.n1 = wcstoull(smain1, NULL, 10); 828235267Sgabor if(main1 < 1 && frac1 < 1) 829235267Sgabor kv1->hint->v.nh.empty=true; 830235267Sgabor kv1->hint->v.nh.si = SI1; 831235267Sgabor kv1->hint->status = (kv1->hint->v.nh.n1 != ULLONG_MAX) ? 832235267Sgabor HS_INITIALIZED : HS_ERROR; 833235267Sgabor kv1->hint->v.nh.neg = (sign1 < 0) ? true : false; 834235267Sgabor } 835235267Sgabor 836235267Sgabor if (kv2->hint->status == HS_UNINITIALIZED) { 837235267Sgabor /* read the number from the string */ 838235267Sgabor read_number(s2, &sign2, smain2, &main2, sfrac2, &frac2,&SI2); 839235267Sgabor key2_read = true; 840235267Sgabor kv2->hint->v.nh.n1 = wcstoull(smain2, NULL, 10); 841235267Sgabor if(main2 < 1 && frac2 < 1) 842235267Sgabor kv2->hint->v.nh.empty=true; 843235267Sgabor kv2->hint->v.nh.si = SI2; 844235267Sgabor kv2->hint->status = (kv2->hint->v.nh.n1 != ULLONG_MAX) ? 845235267Sgabor HS_INITIALIZED : HS_ERROR; 846235267Sgabor kv2->hint->v.nh.neg = (sign2 < 0) ? true : false; 847235267Sgabor } 848235267Sgabor 849235267Sgabor if (kv1->hint->status == HS_INITIALIZED && kv2->hint->status == 850235267Sgabor HS_INITIALIZED) { 851235267Sgabor unsigned long long n1, n2; 852235267Sgabor bool neg1, neg2; 853235267Sgabor 854235267Sgabor e1 = kv1->hint->v.nh.empty; 855235267Sgabor e2 = kv2->hint->v.nh.empty; 856235267Sgabor 857235267Sgabor if (e1 && e2) 858235267Sgabor return (0); 859235267Sgabor 860235267Sgabor neg1 = kv1->hint->v.nh.neg; 861235267Sgabor neg2 = kv2->hint->v.nh.neg; 862235267Sgabor 863235267Sgabor if (neg1 && !neg2) 864235267Sgabor return (-1); 865235267Sgabor if (neg2 && !neg1) 866235267Sgabor return (+1); 867235267Sgabor 868235267Sgabor if (e1) 869235267Sgabor return (neg2 ? +1 : -1); 870235267Sgabor else if (e2) 871235267Sgabor return (neg1 ? -1 : +1); 872235267Sgabor 873235267Sgabor 874235267Sgabor if (use_suffix) { 875235267Sgabor cmp_res = cmpsuffix(kv1->hint->v.nh.si, kv2->hint->v.nh.si); 876235267Sgabor if (cmp_res) 877235267Sgabor return (neg1 ? -cmp_res : cmp_res); 878235267Sgabor } 879235267Sgabor 880235267Sgabor n1 = kv1->hint->v.nh.n1; 881235267Sgabor n2 = kv2->hint->v.nh.n1; 882235267Sgabor if (n1 < n2) 883235267Sgabor return (neg1 ? +1 : -1); 884235267Sgabor else if (n1 > n2) 885235267Sgabor return (neg1 ? -1 : +1); 886235267Sgabor } 887235267Sgabor 888235267Sgabor /* read the numbers from the strings */ 889235267Sgabor if (!key1_read) 890235267Sgabor read_number(s1, &sign1, smain1, &main1, sfrac1, &frac1, &SI1); 891235267Sgabor if (!key2_read) 892235267Sgabor read_number(s2, &sign2, smain2, &main2, sfrac2, &frac2, &SI2); 893235267Sgabor 894235267Sgabor e1 = ((main1 + frac1) == 0); 895235267Sgabor e2 = ((main2 + frac2) == 0); 896235267Sgabor 897235267Sgabor if (e1 && e2) 898235267Sgabor return (0); 899235267Sgabor 900235267Sgabor /* we know the result if the signs are different */ 901235267Sgabor if (sign1 < 0 && sign2 >= 0) 902235267Sgabor return (-1); 903235267Sgabor if (sign1 >= 0 && sign2 < 0) 904235267Sgabor return (+1); 905235267Sgabor 906235267Sgabor if (e1) 907235267Sgabor return ((sign2 < 0) ? +1 : -1); 908235267Sgabor else if (e2) 909235267Sgabor return ((sign1 < 0) ? -1 : +1); 910235267Sgabor 911235267Sgabor if (use_suffix) { 912235267Sgabor cmp_res = cmpsuffix(SI1, SI2); 913235267Sgabor if (cmp_res) 914235267Sgabor return ((sign1 < 0) ? -cmp_res : cmp_res); 915235267Sgabor } 916235267Sgabor 917235267Sgabor /* if both numbers are empty assume that the strings are equal */ 918235267Sgabor if (main1 < 1 && main2 < 1 && frac1 < 1 && frac2 < 1) 919235267Sgabor return (0); 920235267Sgabor 921235267Sgabor /* 922235267Sgabor * if the main part is of different size, we know the result 923235267Sgabor * (because the leading zeros are removed) 924235267Sgabor */ 925235267Sgabor if (main1 < main2) 926235267Sgabor cmp_res = -1; 927235267Sgabor else if (main1 > main2) 928235267Sgabor cmp_res = +1; 929235267Sgabor /* if the sizes are equal then simple non-collate string compare gives the correct result */ 930235267Sgabor else 931235267Sgabor cmp_res = wcscmp(smain1, smain2); 932235267Sgabor 933235267Sgabor /* check fraction */ 934235267Sgabor if (!cmp_res) 935235267Sgabor cmp_res = wcscmp(sfrac1, sfrac2); 936235267Sgabor 937235267Sgabor if (!cmp_res) 938235267Sgabor return (0); 939235267Sgabor 940235267Sgabor /* reverse result if the signs are negative */ 941235267Sgabor if (sign1 < 0 && sign2 < 0) 942235267Sgabor cmp_res = -cmp_res; 943235267Sgabor 944235267Sgabor return (cmp_res); 945235267Sgabor} 946235267Sgabor 947235267Sgabor/* 948235267Sgabor * Implements numeric sort (-n). 949235267Sgabor */ 950235267Sgaborstatic int 951235267Sgabornumcoll(struct key_value *kv1, struct key_value *kv2, size_t offset) 952235267Sgabor{ 953235267Sgabor 954235267Sgabor return (numcoll_impl(kv1, kv2, offset, false)); 955235267Sgabor} 956235267Sgabor 957235267Sgabor/* 958235267Sgabor * Implements 'human' numeric sort (-h). 959235267Sgabor */ 960235267Sgaborstatic int 961235267Sgaborhnumcoll(struct key_value *kv1, struct key_value *kv2, size_t offset) 962235267Sgabor{ 963235267Sgabor 964235267Sgabor return (numcoll_impl(kv1, kv2, offset, true)); 965235267Sgabor} 966235267Sgabor 967235267Sgabor/* 968235267Sgabor * Implements random sort (-R). 969235267Sgabor */ 970235267Sgaborstatic int 971236764Sgaborrandomcoll(struct key_value *kv1, struct key_value *kv2, 972236764Sgabor size_t offset __unused) 973235267Sgabor{ 974235267Sgabor struct bwstring *s1, *s2; 975235267Sgabor MD5_CTX ctx1, ctx2; 976235267Sgabor char *b1, *b2; 977235267Sgabor 978235267Sgabor s1 = kv1->k; 979235267Sgabor s2 = kv2->k; 980235267Sgabor 981235267Sgabor if (debug_sort) { 982235267Sgabor bwsprintf(stdout, s1, "; k1=<", ">"); 983235267Sgabor bwsprintf(stdout, s2, ", k2=<", ">"); 984235267Sgabor } 985235267Sgabor 986235267Sgabor if (s1 == s2) 987235267Sgabor return (0); 988235267Sgabor 989235267Sgabor memcpy(&ctx1,&md5_ctx,sizeof(MD5_CTX)); 990235267Sgabor memcpy(&ctx2,&md5_ctx,sizeof(MD5_CTX)); 991235267Sgabor 992235267Sgabor MD5Update(&ctx1, bwsrawdata(s1), bwsrawlen(s1)); 993235267Sgabor MD5Update(&ctx2, bwsrawdata(s2), bwsrawlen(s2)); 994235267Sgabor b1 = MD5End(&ctx1, NULL); 995235267Sgabor b2 = MD5End(&ctx2, NULL); 996235267Sgabor if (b1 == NULL) { 997235267Sgabor if (b2 == NULL) 998235267Sgabor return (0); 999235267Sgabor else { 1000235267Sgabor sort_free(b2); 1001235267Sgabor return (-1); 1002235267Sgabor } 1003235267Sgabor } else if (b2 == NULL) { 1004235267Sgabor sort_free(b1); 1005235267Sgabor return (+1); 1006235267Sgabor } else { 1007235267Sgabor int cmp_res; 1008235267Sgabor 1009235267Sgabor cmp_res = strcmp(b1,b2); 1010235267Sgabor sort_free(b1); 1011235267Sgabor sort_free(b2); 1012235267Sgabor 1013235267Sgabor if (!cmp_res) 1014235267Sgabor cmp_res = bwscoll(s1, s2, 0); 1015235267Sgabor 1016235267Sgabor return (cmp_res); 1017235267Sgabor } 1018235267Sgabor} 1019235267Sgabor 1020235267Sgabor/* 1021235267Sgabor * Implements version sort (-V). 1022235267Sgabor */ 1023235267Sgaborstatic int 1024236764Sgaborversioncoll(struct key_value *kv1, struct key_value *kv2, 1025236764Sgabor size_t offset __unused) 1026235267Sgabor{ 1027235267Sgabor struct bwstring *s1, *s2; 1028235267Sgabor 1029235267Sgabor s1 = kv1->k; 1030235267Sgabor s2 = kv2->k; 1031235267Sgabor 1032235267Sgabor if (debug_sort) { 1033235267Sgabor bwsprintf(stdout, s1, "; k1=<", ">"); 1034235267Sgabor bwsprintf(stdout, s2, ", k2=<", ">"); 1035235267Sgabor } 1036235267Sgabor 1037235267Sgabor if (s1 == s2) 1038235267Sgabor return (0); 1039235267Sgabor 1040235267Sgabor return (vcmp(s1, s2)); 1041235267Sgabor} 1042235267Sgabor 1043235267Sgabor/* 1044235267Sgabor * Check for minus infinity 1045235267Sgabor */ 1046235267Sgaborstatic inline bool 1047235267Sgaborhuge_minus(double d, int err1) 1048235267Sgabor{ 1049235267Sgabor 1050235267Sgabor if (err1 == ERANGE) 1051235267Sgabor if (d == -HUGE_VAL || d == -HUGE_VALF || d == -HUGE_VALL) 1052235267Sgabor return (+1); 1053235267Sgabor 1054235267Sgabor return (0); 1055235267Sgabor} 1056235267Sgabor 1057235267Sgabor/* 1058235267Sgabor * Check for plus infinity 1059235267Sgabor */ 1060235267Sgaborstatic inline bool 1061235267Sgaborhuge_plus(double d, int err1) 1062235267Sgabor{ 1063235267Sgabor 1064235267Sgabor if (err1 == ERANGE) 1065235267Sgabor if (d == HUGE_VAL || d == HUGE_VALF || d == HUGE_VALL) 1066235267Sgabor return (+1); 1067235267Sgabor 1068235267Sgabor return (0); 1069235267Sgabor} 1070235267Sgabor 1071235267Sgabor/* 1072235267Sgabor * Check whether a function is a NAN 1073235267Sgabor */ 1074235267Sgaborstatic bool 1075235267Sgaboris_nan(double d) 1076235267Sgabor{ 1077235267Sgabor 1078235267Sgabor return ((d == NAN) || (isnan(d))); 1079235267Sgabor} 1080235267Sgabor 1081235267Sgabor/* 1082235267Sgabor * Compare two NANs 1083235267Sgabor */ 1084235267Sgaborstatic int 1085235267Sgaborcmp_nans(double d1, double d2) 1086235267Sgabor{ 1087235267Sgabor 1088235267Sgabor if (d1 < d2) 1089235267Sgabor return (-1); 1090235267Sgabor if (d2 > d2) 1091235267Sgabor return (+1); 1092235267Sgabor return (0); 1093235267Sgabor} 1094235267Sgabor 1095235267Sgabor/* 1096235267Sgabor * Implements general numeric sort (-g). 1097235267Sgabor */ 1098235267Sgaborstatic int 1099236764Sgaborgnumcoll(struct key_value *kv1, struct key_value *kv2, 1100236764Sgabor size_t offset __unused) 1101235267Sgabor{ 1102235267Sgabor double d1, d2; 1103235267Sgabor int err1, err2; 1104235267Sgabor bool empty1, empty2, key1_read, key2_read; 1105235267Sgabor 1106235267Sgabor d1 = d2 = 0; 1107235267Sgabor err1 = err2 = 0; 1108235267Sgabor key1_read = key2_read = false; 1109235267Sgabor 1110235267Sgabor if (debug_sort) { 1111235267Sgabor bwsprintf(stdout, kv1->k, "; k1=<", ">"); 1112235267Sgabor bwsprintf(stdout, kv2->k, "; k2=<", ">"); 1113235267Sgabor } 1114235267Sgabor 1115235267Sgabor if (kv1->hint->status == HS_UNINITIALIZED) { 1116235267Sgabor errno = 0; 1117235267Sgabor d1 = bwstod(kv1->k, &empty1); 1118235267Sgabor err1 = errno; 1119235267Sgabor 1120235267Sgabor if (empty1) 1121235267Sgabor kv1->hint->v.gh.notnum = true; 1122235267Sgabor else if (err1 == 0) { 1123235267Sgabor kv1->hint->v.gh.d = d1; 1124235267Sgabor kv1->hint->v.gh.nan = is_nan(d1); 1125235267Sgabor kv1->hint->status = HS_INITIALIZED; 1126235267Sgabor } else 1127235267Sgabor kv1->hint->status = HS_ERROR; 1128235267Sgabor 1129235267Sgabor key1_read = true; 1130235267Sgabor } 1131235267Sgabor 1132235267Sgabor if (kv2->hint->status == HS_UNINITIALIZED) { 1133235267Sgabor errno = 0; 1134235267Sgabor d2 = bwstod(kv2->k, &empty2); 1135235267Sgabor err2 = errno; 1136235267Sgabor 1137235267Sgabor if (empty2) 1138235267Sgabor kv2->hint->v.gh.notnum = true; 1139235267Sgabor else if (err2 == 0) { 1140235267Sgabor kv2->hint->v.gh.d = d2; 1141235267Sgabor kv2->hint->v.gh.nan = is_nan(d2); 1142235267Sgabor kv2->hint->status = HS_INITIALIZED; 1143235267Sgabor } else 1144235267Sgabor kv2->hint->status = HS_ERROR; 1145235267Sgabor 1146235267Sgabor key2_read = true; 1147235267Sgabor } 1148235267Sgabor 1149235267Sgabor if (kv1->hint->status == HS_INITIALIZED && 1150235267Sgabor kv2->hint->status == HS_INITIALIZED) { 1151235267Sgabor if (kv1->hint->v.gh.notnum) 1152235267Sgabor return ((kv2->hint->v.gh.notnum) ? 0 : -1); 1153235267Sgabor else if (kv2->hint->v.gh.notnum) 1154235267Sgabor return (+1); 1155235267Sgabor 1156235267Sgabor if (kv1->hint->v.gh.nan) 1157235267Sgabor return ((kv2->hint->v.gh.nan) ? 1158235267Sgabor cmp_nans(kv1->hint->v.gh.d, kv2->hint->v.gh.d) : 1159235267Sgabor -1); 1160235267Sgabor else if (kv2->hint->v.gh.nan) 1161235267Sgabor return (+1); 1162235267Sgabor 1163235267Sgabor d1 = kv1->hint->v.gh.d; 1164235267Sgabor d2 = kv2->hint->v.gh.d; 1165235267Sgabor 1166235267Sgabor if (d1 < d2) 1167235267Sgabor return (-1); 1168235267Sgabor else if (d1 > d2) 1169235267Sgabor return (+1); 1170235267Sgabor else 1171235267Sgabor return (0); 1172235267Sgabor } 1173235267Sgabor 1174235267Sgabor if (!key1_read) { 1175235267Sgabor errno = 0; 1176235267Sgabor d1 = bwstod(kv1->k, &empty1); 1177235267Sgabor err1 = errno; 1178235267Sgabor } 1179235267Sgabor 1180235267Sgabor if (!key2_read) { 1181235267Sgabor errno = 0; 1182235267Sgabor d2 = bwstod(kv2->k, &empty2); 1183235267Sgabor err2 = errno; 1184235267Sgabor } 1185235267Sgabor 1186235267Sgabor /* Non-value case: */ 1187235267Sgabor if (empty1) 1188235267Sgabor return (empty2 ? 0 : -1); 1189235267Sgabor else if (empty2) 1190235267Sgabor return (+1); 1191235267Sgabor 1192235267Sgabor /* NAN case */ 1193235267Sgabor if (is_nan(d1)) 1194235267Sgabor return (is_nan(d2) ? cmp_nans(d1, d2) : -1); 1195235267Sgabor else if (is_nan(d2)) 1196235267Sgabor return (+1); 1197235267Sgabor 1198235267Sgabor /* Infinities */ 1199235267Sgabor if (err1 == ERANGE || err2 == ERANGE) { 1200235267Sgabor /* Minus infinity case */ 1201235267Sgabor if (huge_minus(d1, err1)) { 1202235267Sgabor if (huge_minus(d2, err2)) { 1203235267Sgabor if (d1 < d2) 1204235267Sgabor return (-1); 1205235267Sgabor if (d1 > d2) 1206235267Sgabor return (+1); 1207235267Sgabor return (0); 1208235267Sgabor } else 1209235267Sgabor return (-1); 1210235267Sgabor 1211235267Sgabor } else if (huge_minus(d2, err2)) { 1212235267Sgabor if (huge_minus(d1, err1)) { 1213235267Sgabor if (d1 < d2) 1214235267Sgabor return (-1); 1215235267Sgabor if (d1 > d2) 1216235267Sgabor return (+1); 1217235267Sgabor return (0); 1218235267Sgabor } else 1219235267Sgabor return (+1); 1220235267Sgabor } 1221235267Sgabor 1222235267Sgabor /* Plus infinity case */ 1223235267Sgabor if (huge_plus(d1, err1)) { 1224235267Sgabor if (huge_plus(d2, err2)) { 1225235267Sgabor if (d1 < d2) 1226235267Sgabor return (-1); 1227235267Sgabor if (d1 > d2) 1228235267Sgabor return (+1); 1229235267Sgabor return (0); 1230235267Sgabor } else 1231235267Sgabor return (+1); 1232235267Sgabor } else if (huge_plus(d2, err2)) { 1233235267Sgabor if (huge_plus(d1, err1)) { 1234235267Sgabor if (d1 < d2) 1235235267Sgabor return (-1); 1236235267Sgabor if (d1 > d2) 1237235267Sgabor return (+1); 1238235267Sgabor return (0); 1239235267Sgabor } else 1240235267Sgabor return (-1); 1241235267Sgabor } 1242235267Sgabor } 1243235267Sgabor 1244235267Sgabor if (d1 < d2) 1245235267Sgabor return (-1); 1246235267Sgabor if (d1 > d2) 1247235267Sgabor return (+1); 1248235267Sgabor 1249235267Sgabor return (0); 1250235267Sgabor} 1251235267Sgabor 1252235267Sgabor/* 1253235267Sgabor * Implements month sort (-M). 1254235267Sgabor */ 1255235267Sgaborstatic int 1256236764Sgabormonthcoll(struct key_value *kv1, struct key_value *kv2, size_t offset __unused) 1257235267Sgabor{ 1258235267Sgabor int val1, val2; 1259235267Sgabor bool key1_read, key2_read; 1260235267Sgabor 1261235267Sgabor val1 = val2 = 0; 1262235267Sgabor key1_read = key2_read = false; 1263235267Sgabor 1264235267Sgabor if (debug_sort) { 1265235267Sgabor bwsprintf(stdout, kv1->k, "; k1=<", ">"); 1266235267Sgabor bwsprintf(stdout, kv2->k, "; k2=<", ">"); 1267235267Sgabor } 1268235267Sgabor 1269235267Sgabor if (kv1->hint->status == HS_UNINITIALIZED) { 1270235267Sgabor kv1->hint->v.Mh.m = bws_month_score(kv1->k); 1271235267Sgabor key1_read = true; 1272235267Sgabor kv1->hint->status = HS_INITIALIZED; 1273235267Sgabor } 1274235267Sgabor 1275235267Sgabor if (kv2->hint->status == HS_UNINITIALIZED) { 1276235267Sgabor kv2->hint->v.Mh.m = bws_month_score(kv2->k); 1277235267Sgabor key2_read = true; 1278235267Sgabor kv2->hint->status = HS_INITIALIZED; 1279235267Sgabor } 1280235267Sgabor 1281235267Sgabor if (kv1->hint->status == HS_INITIALIZED) { 1282235267Sgabor val1 = kv1->hint->v.Mh.m; 1283235267Sgabor key1_read = true; 1284235267Sgabor } 1285235267Sgabor 1286235267Sgabor if (kv2->hint->status == HS_INITIALIZED) { 1287235267Sgabor val2 = kv2->hint->v.Mh.m; 1288235267Sgabor key2_read = true; 1289235267Sgabor } 1290235267Sgabor 1291235267Sgabor if (!key1_read) 1292235267Sgabor val1 = bws_month_score(kv1->k); 1293235267Sgabor if (!key2_read) 1294235267Sgabor val2 = bws_month_score(kv2->k); 1295235267Sgabor 1296235267Sgabor if (val1 == val2) { 1297235267Sgabor return (0); 1298235267Sgabor } 1299235267Sgabor if (val1 < val2) 1300235267Sgabor return (-1); 1301235267Sgabor return (+1); 1302235267Sgabor} 1303