timsort.h

   1 /*
   2  * Taken from https://github.com/swenson/sort
   3  * Revision: 05fd77bfec049ce8b7c408c4d3dd2d51ee061a15
   4  * Removed all code unrelated to Timsort and made minor adjustments for
   5  * cross-platform compatibility.
   6  */
   7
   8 /*
   9  * The MIT License (MIT)
  10  *
  11  * Copyright (c) 2010-2017 Christopher Swenson.
  12  * Copyright (c) 2012 Vojtech Fried.
  13  * Copyright (c) 2012 Google Inc. All Rights Reserved.
  14  *
  15  * Permission is hereby granted, free of charge, to any person obtaining a
  16  * copy of this software and associated documentation files (the "Software"),
  17  * to deal in the Software without restriction, including without limitation
  18  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  19  * and/or sell copies of the Software, and to permit persons to whom the
  20  * Software is furnished to do so, subject to the following conditions:
  21  *
  22  * The above copyright notice and this permission notice shall be included in
  23  * all copies or substantial portions of the Software.
  24  *
  25  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  26  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  27  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  28  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  29  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  30  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  31  * DEALINGS IN THE SOFTWARE.
  32  */
  33
  34 #include <stdlib.h>
  35 #include <stdio.h>
  36 #include <string.h>
  37 #ifdef HAVE_STDINT_H
  38 #include <stdint.h>
  39 #elif defined(_WIN32)
  40 typedef unsigned __int64 uint64_t;
  41 #endif
  42
  43 #ifndef SORT_NAME
  44 #error "Must declare SORT_NAME"
  45 #endif
  46
  47 #ifndef SORT_TYPE
  48 #error "Must declare SORT_TYPE"
  49 #endif
  50
  51 #ifndef SORT_CMP
  52 #define SORT_CMP(x, y)  ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))
  53 #endif
  54
  55 #ifndef TIM_SORT_STACK_SIZE
  56 #define TIM_SORT_STACK_SIZE 128
  57 #endif
  58
  59 #define SORT_SWAP(x,y) {SORT_TYPE __SORT_SWAP_t = (x); (x) = (y); (y) = __SORT_SWAP_t;}
  60
  61
  62 /* Common, type-agnosting functions and constants that we don't want to declare twice. */
  63 #ifndef SORT_COMMON_H
  64 #define SORT_COMMON_H
  65
  66 #ifndef MAX
  67 #define MAX(x,y) (((x) > (y) ? (x) : (y)))
  68 #endif
  69
  70 #ifndef MIN
  71 #define MIN(x,y) (((x) < (y) ? (x) : (y)))
  72 #endif
  73
  74 static int compute_minrun(const uint64_t);
  75
  76 #ifndef CLZ
  77 #ifdef __GNUC__
  78 #define CLZ __builtin_clzll
  79 #else
  80
  81 static int clzll(uint64_t);
  82
  83 /* adapted from Hacker's Delight */
  84 static int clzll(uint64_t x) {
  85   int n;
  86
  87   if (x == 0) {
  88     return 64;
  89   }
  90
  91   n = 0;
  92
  93   if (x <= 0x00000000FFFFFFFFL) {
  94     n = n + 32;
  95     x = x << 32;
  96   }
  97
  98   if (x <= 0x0000FFFFFFFFFFFFL) {
  99     n = n + 16;
 100     x = x << 16;
 101   }
 102
 103   if (x <= 0x00FFFFFFFFFFFFFFL) {
 104     n = n + 8;
 105     x = x << 8;
 106   }
 107
 108   if (x <= 0x0FFFFFFFFFFFFFFFL) {
 109     n = n + 4;
 110     x = x << 4;
 111   }
 112
 113   if (x <= 0x3FFFFFFFFFFFFFFFL) {
 114     n = n + 2;
 115     x = x << 2;
 116   }
 117
 118   if (x <= 0x7FFFFFFFFFFFFFFFL) {
 119     n = n + 1;
 120   }
 121
 122   return n;
 123 }
 124
 125 #define CLZ clzll
 126 #endif
 127 #endif
 128
 129 static __inline int compute_minrun(const uint64_t size) {
 130   const int top_bit = 64 - CLZ(size);
 131   const int shift = MAX(top_bit, 6) - 6;
 132   const int minrun = size >> shift;
 133   const uint64_t mask = (1ULL << shift) - 1;
 134
 135   if (mask & size) {
 136     return minrun + 1;
 137   }
 138
 139   return minrun;
 140 }
 141
 142 #endif /* SORT_COMMON_H */
 143
 144 #define SORT_CONCAT(x, y) x ## _ ## y
 145 #define SORT_MAKE_STR1(x, y) SORT_CONCAT(x,y)
 146 #define SORT_MAKE_STR(x) SORT_MAKE_STR1(SORT_NAME,x)
 147
 148 #define BINARY_INSERTION_FIND          SORT_MAKE_STR(binary_insertion_find)
 149 #define BINARY_INSERTION_SORT_START    SORT_MAKE_STR(binary_insertion_sort_start)
 150 #define BINARY_INSERTION_SORT          SORT_MAKE_STR(binary_insertion_sort)
 151 #define REVERSE_ELEMENTS               SORT_MAKE_STR(reverse_elements)
 152 #define COUNT_RUN                      SORT_MAKE_STR(count_run)
 153 #define CHECK_INVARIANT                SORT_MAKE_STR(check_invariant)
 154 #define TIM_SORT                       SORT_MAKE_STR(tim_sort)
 155 #define TIM_SORT_RESIZE                SORT_MAKE_STR(tim_sort_resize)
 156 #define TIM_SORT_MERGE                 SORT_MAKE_STR(tim_sort_merge)
 157 #define TIM_SORT_COLLAPSE              SORT_MAKE_STR(tim_sort_collapse)
 158
 159 #ifndef MAX
 160 #define MAX(x,y) (((x) > (y) ? (x) : (y)))
 161 #endif
 162 #ifndef MIN
 163 #define MIN(x,y) (((x) < (y) ? (x) : (y)))
 164 #endif
 165
 166 typedef struct {
 167   size_t start;
 168   size_t length;
 169 } TIM_SORT_RUN_T;
 170
 171
 172 void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size);
 173 void TIM_SORT(SORT_TYPE *dst, const size_t size);
 174
 175
 176 /* Function used to do a binary search for binary insertion sort */
 177 static __inline size_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x,
 178     const size_t size) {
 179   size_t l, c, r;
 180   SORT_TYPE cx;
 181   l = 0;
 182   r = size - 1;
 183   c = r >> 1;
 184
 185   /* check for out of bounds at the beginning. */
 186   if (SORT_CMP(x, dst[0]) < 0) {
 187     return 0;
 188   } else if (SORT_CMP(x, dst[r]) > 0) {
 189     return r;
 190   }
 191
 192   cx = dst[c];
 193
 194   while (1) {
 195     const int val = SORT_CMP(x, cx);
 196
 197     if (val < 0) {
 198       if (c - l <= 1) {
 199         return c;
 200       }
 201
 202       r = c;
 203     } else { /* allow = for stability. The binary search favors the right. */
 204       if (r - c <= 1) {
 205         return c + 1;
 206       }
 207
 208       l = c;
 209     }
 210
 211     c = l + ((r - l) >> 1);
 212     cx = dst[c];
 213   }
 214 }
 215
 216 /* Binary insertion sort, but knowing that the first "start" entries are sorted.  Used in timsort. */
 217 static void BINARY_INSERTION_SORT_START(SORT_TYPE *dst, const size_t start, const size_t size) {
 218   size_t i;
 219
 220   for (i = start; i < size; i++) {
 221     size_t j;
 222     SORT_TYPE x;
 223     size_t location;
 224
 225     /* If this entry is already correct, just move along */
 226     if (SORT_CMP(dst[i - 1], dst[i]) <= 0) {
 227       continue;
 228     }
 229
 230     /* Else we need to find the right place, shift everything over, and squeeze in */
 231     x = dst[i];
 232     location = BINARY_INSERTION_FIND(dst, x, i);
 233
 234     for (j = i - 1; j >= location; j--) {
 235       dst[j + 1] = dst[j];
 236
 237       if (j == 0) { /* check edge case because j is unsigned */
 238         break;
 239       }
 240     }
 241
 242     dst[location] = x;
 243   }
 244 }
 245
 246 /* Binary insertion sort */
 247 void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size) {
 248   /* don't bother sorting an array of size <= 1 */
 249   if (size <= 1) {
 250     return;
 251   }
 252
 253   BINARY_INSERTION_SORT_START(dst, 1, size);
 254 }
 255
 256 /* timsort implementation, based on timsort.txt */
 257
 258 static __inline void REVERSE_ELEMENTS(SORT_TYPE *dst, size_t start, size_t end) {
 259   while (1) {
 260     if (start >= end) {
 261       return;
 262     }
 263
 264     SORT_SWAP(dst[start], dst[end]);
 265     start++;
 266     end--;
 267   }
 268 }
 269
 270 static size_t COUNT_RUN(SORT_TYPE *dst, const size_t start, const size_t size) {
 271   size_t curr;
 272
 273   if (size - start == 1) {
 274     return 1;
 275   }
 276
 277   if (start >= size - 2) {
 278     if (SORT_CMP(dst[size - 2], dst[size - 1]) > 0) {
 279       SORT_SWAP(dst[size - 2], dst[size - 1]);
 280     }
 281
 282     return 2;
 283   }
 284
 285   curr = start + 2;
 286
 287   if (SORT_CMP(dst[start], dst[start + 1]) <= 0) {
 288     /* increasing run */
 289     while (1) {
 290       if (curr == size - 1) {
 291         break;
 292       }
 293
 294       if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) {
 295         break;
 296       }
 297
 298       curr++;
 299     }
 300
 301     return curr - start;
 302   } else {
 303     /* decreasing run */
 304     while (1) {
 305       if (curr == size - 1) {
 306         break;
 307       }
 308
 309       if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) {
 310         break;
 311       }
 312
 313       curr++;
 314     }
 315
 316     /* reverse in-place */
 317     REVERSE_ELEMENTS(dst, start, curr - 1);
 318     return curr - start;
 319   }
 320 }
 321
 322 static int CHECK_INVARIANT(TIM_SORT_RUN_T *stack, const int stack_curr) {
 323   size_t A, B, C;
 324
 325   if (stack_curr < 2) {
 326     return 1;
 327   }
 328
 329   if (stack_curr == 2) {
 330     const size_t A1 = stack[stack_curr - 2].length;
 331     const size_t B1 = stack[stack_curr - 1].length;
 332
 333     if (A1 <= B1) {
 334       return 0;
 335     }
 336
 337     return 1;
 338   }
 339
 340   A = stack[stack_curr - 3].length;
 341   B = stack[stack_curr - 2].length;
 342   C = stack[stack_curr - 1].length;
 343
 344   if ((A <= B + C) || (B <= C)) {
 345     return 0;
 346   }
 347
 348   return 1;
 349 }
 350
 351 typedef struct {
 352   size_t alloc;
 353   SORT_TYPE *storage;
 354 } TEMP_STORAGE_T;
 355
 356 static void TIM_SORT_RESIZE(TEMP_STORAGE_T *store, const size_t new_size) {
 357   if (store->alloc < new_size) {
 358     SORT_TYPE *tempstore = (SORT_TYPE *)realloc(store->storage, new_size * sizeof(SORT_TYPE));
 359
 360     if (tempstore == NULL) {
 361       fprintf(stderr, "Error allocating temporary storage for tim sort: need %lu bytes",
 362               (unsigned long)(sizeof(SORT_TYPE) * new_size));
 363       exit(1);
 364     }
 365
 366     store->storage = tempstore;
 367     store->alloc = new_size;
 368   }
 369 }
 370
 371 static void TIM_SORT_MERGE(SORT_TYPE *dst, const TIM_SORT_RUN_T *stack, const int stack_curr,
 372                            TEMP_STORAGE_T *store) {
 373   const size_t A = stack[stack_curr - 2].length;
 374   const size_t B = stack[stack_curr - 1].length;
 375   const size_t curr = stack[stack_curr - 2].start;
 376   SORT_TYPE *storage;
 377   size_t i, j, k;
 378   TIM_SORT_RESIZE(store, MIN(A, B));
 379   storage = store->storage;
 380
 381   /* left merge */
 382   if (A < B) {
 383     memcpy(storage, &dst[curr], A * sizeof(SORT_TYPE));
 384     i = 0;
 385     j = curr + A;
 386
 387     for (k = curr; k < curr + A + B; k++) {
 388       if ((i < A) && (j < curr + A + B)) {
 389         if (SORT_CMP(storage[i], dst[j]) <= 0) {
 390           dst[k] = storage[i++];
 391         } else {
 392           dst[k] = dst[j++];
 393         }
 394       } else if (i < A) {
 395         dst[k] = storage[i++];
 396       } else {
 397         break;
 398       }
 399     }
 400   } else {
 401     /* right merge */
 402     memcpy(storage, &dst[curr + A], B * sizeof(SORT_TYPE));
 403     i = B;
 404     j = curr + A;
 405     k = curr + A + B;
 406
 407     while (k-- > curr) {
 408       if ((i > 0) && (j > curr)) {
 409         if (SORT_CMP(dst[j - 1], storage[i - 1]) > 0) {
 410           dst[k] = dst[--j];
 411         } else {
 412           dst[k] = storage[--i];
 413         }
 414       } else if (i > 0) {
 415         dst[k] = storage[--i];
 416       } else {
 417         break;
 418       }
 419     }
 420   }
 421 }
 422
 423 static int TIM_SORT_COLLAPSE(SORT_TYPE *dst, TIM_SORT_RUN_T *stack, int stack_curr,
 424                              TEMP_STORAGE_T *store, const size_t size) {
 425   while (1) {
 426     size_t A, B, C, D;
 427     int ABC, BCD, CD;
 428
 429     /* if the stack only has one thing on it, we are done with the collapse */
 430     if (stack_curr <= 1) {
 431       break;
 432     }
 433
 434     /* if this is the last merge, just do it */
 435     if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
 436       TIM_SORT_MERGE(dst, stack, stack_curr, store);
 437       stack[0].length += stack[1].length;
 438       stack_curr--;
 439       break;
 440     }
 441     /* check if the invariant is off for a stack of 2 elements */
 442     else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
 443       TIM_SORT_MERGE(dst, stack, stack_curr, store);
 444       stack[0].length += stack[1].length;
 445       stack_curr--;
 446       break;
 447     } else if (stack_curr == 2) {
 448       break;
 449     }
 450
 451     B = stack[stack_curr - 3].length;
 452     C = stack[stack_curr - 2].length;
 453     D = stack[stack_curr - 1].length;
 454
 455     if (stack_curr >= 4) {
 456       A = stack[stack_curr - 4].length;
 457       ABC = (A <= B + C);
 458     } else {
 459       ABC = 0;
 460     }
 461
 462     BCD = (B <= C + D) || ABC;
 463     CD = (C <= D);
 464
 465     /* Both invariants are good */
 466     if (!BCD && !CD) {
 467       break;
 468     }
 469
 470     /* left merge */
 471     if (BCD && !CD) {
 472       TIM_SORT_MERGE(dst, stack, stack_curr - 1, store);
 473       stack[stack_curr - 3].length += stack[stack_curr - 2].length;
 474       stack[stack_curr - 2] = stack[stack_curr - 1];
 475       stack_curr--;
 476     } else {
 477       /* right merge */
 478       TIM_SORT_MERGE(dst, stack, stack_curr, store);
 479       stack[stack_curr - 2].length += stack[stack_curr - 1].length;
 480       stack_curr--;
 481     }
 482   }
 483
 484   return stack_curr;
 485 }
 486
 487 static __inline int PUSH_NEXT(SORT_TYPE *dst,
 488                               const size_t size,
 489                               TEMP_STORAGE_T *store,
 490                               const size_t minrun,
 491                               TIM_SORT_RUN_T *run_stack,
 492                               size_t *stack_curr,
 493                               size_t *curr) {
 494   size_t len = COUNT_RUN(dst, *curr, size);
 495   size_t run = minrun;
 496
 497   if (run > size - *curr) {
 498     run = size - *curr;
 499   }
 500
 501   if (run > len) {
 502     BINARY_INSERTION_SORT_START(&dst[*curr], len, run);
 503     len = run;
 504   }
 505
 506   run_stack[*stack_curr].start = *curr;
 507   run_stack[*stack_curr].length = len;
 508   (*stack_curr)++;
 509   *curr += len;
 510
 511   if (*curr == size) {
 512     /* finish up */
 513     while (*stack_curr > 1) {
 514       TIM_SORT_MERGE(dst, run_stack, *stack_curr, store);
 515       run_stack[*stack_curr - 2].length += run_stack[*stack_curr - 1].length;
 516       (*stack_curr)--;
 517     }
 518
 519     if (store->storage != NULL) {
 520       free(store->storage);
 521       store->storage = NULL;
 522     }
 523
 524     return 0;
 525   }
 526
 527   return 1;
 528 }
 529
 530 void TIM_SORT(SORT_TYPE *dst, const size_t size) {
 531   size_t minrun;
 532   TEMP_STORAGE_T _store, *store;
 533   TIM_SORT_RUN_T run_stack[TIM_SORT_STACK_SIZE];
 534   size_t stack_curr = 0;
 535   size_t curr = 0;
 536
 537   /* don't bother sorting an array of size 1 */
 538   if (size <= 1) {
 539     return;
 540   }
 541
 542   if (size < 64) {
 543     BINARY_INSERTION_SORT(dst, size);
 544     return;
 545   }
 546
 547   /* compute the minimum run length */
 548   minrun = compute_minrun(size);
 549   /* temporary storage for merges */
 550   store = &_store;
 551   store->alloc = 0;
 552   store->storage = NULL;
 553
 554   if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
 555     return;
 556   }
 557
 558   if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
 559     return;
 560   }
 561
 562   if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
 563     return;
 564   }
 565
 566   while (1) {
 567     if (!CHECK_INVARIANT(run_stack, stack_curr)) {
 568       stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, stack_curr, store, size);
 569       continue;
 570     }
 571
 572     if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
 573       return;
 574     }
 575   }
 576 }
 577
 578 #undef SORT_CONCAT
 579 #undef SORT_MAKE_STR1
 580 #undef SORT_MAKE_STR
 581 #undef SORT_NAME
 582 #undef SORT_TYPE
 583 #undef SORT_CMP
 584 #undef TEMP_STORAGE_T
 585 #undef TIM_SORT_RUN_T
 586 #undef PUSH_NEXT
 587 #undef SORT_SWAP
 588 #undef SORT_CONCAT
 589 #undef SORT_MAKE_STR1
 590 #undef SORT_MAKE_STR
 591 #undef BINARY_INSERTION_FIND
 592 #undef BINARY_INSERTION_SORT_START
 593 #undef BINARY_INSERTION_SORT
 594 #undef REVERSE_ELEMENTS
 595 #undef COUNT_RUN
 596 #undef TIM_SORT
 597 #undef TIM_SORT_RESIZE
 598 #undef TIM_SORT_COLLAPSE
 599 #undef TIM_SORT_RUN_T
 600 #undef TEMP_STORAGE_T