src/tsort.c

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #include "common.h"
   9
  10 /**
  11  * An array-of-pointers implementation of Python's Timsort
  12  * Based on code by Christopher Swenson under the MIT license
  13  *
  14  * Copyright (c) 2010 Christopher Swenson
  15  * Copyright (c) 2011 Vicent Marti
  16  */
  17
  18 #ifndef MAX
  19 #       define MAX(x,y) (((x) > (y) ? (x) : (y)))
  20 #endif
  21
  22 #ifndef MIN
  23 #       define MIN(x,y) (((x) < (y) ? (x) : (y)))
  24 #endif
  25
  26 typedef int (*cmp_ptr_t)(const void *, const void *);
  27
  28 static int binsearch(void **dst, const void *x, size_t size, cmp_ptr_t cmp)
  29 {
  30         int l, c, r;
  31         void *lx, *cx;
  32
  33         assert(size > 0);
  34
  35         l = 0;
  36         r = (int)size - 1;
  37         c = r >> 1;
  38         lx = dst[l];
  39
  40         /* check for beginning conditions */
  41         if (cmp(x, lx) < 0)
  42                 return 0;
  43
  44         else if (cmp(x, lx) == 0) {
  45                 int i = 1;
  46                 while (cmp(x, dst[i]) == 0)
  47                         i++;
  48                 return i;
  49         }
  50
  51         /* guaranteed not to be >= rx */
  52         cx = dst[c];
  53         while (1) {
  54                 const int val = cmp(x, cx);
  55                 if (val < 0) {
  56                         if (c - l <= 1) return c;
  57                         r = c;
  58                 } else if (val > 0) {
  59                         if (r - c <= 1) return c + 1;
  60                         l = c;
  61                         lx = cx;
  62                 } else {
  63                         do {
  64                                 cx = dst[++c];
  65                         } while (cmp(x, cx) == 0);
  66                         return c;
  67                 }
  68                 c = l + ((r - l) >> 1);
  69                 cx = dst[c];
  70         }
  71 }
  72
  73 /* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
  74 static void bisort(void **dst, size_t start, size_t size, cmp_ptr_t cmp)
  75 {
  76         size_t i;
  77         void *x;
  78         int location;
  79
  80         for (i = start; i < size; i++) {
  81                 int j;
  82                 /* If this entry is already correct, just move along */
  83                 if (cmp(dst[i - 1], dst[i]) <= 0)
  84                         continue;
  85
  86                 /* Else we need to find the right place, shift everything over, and squeeze in */
  87                 x = dst[i];
  88                 location = binsearch(dst, x, i, cmp);
  89                 for (j = (int)i - 1; j >= location; j--) {
  90                         dst[j + 1] = dst[j];
  91                 }
  92                 dst[location] = x;
  93         }
  94 }
  95
  96
  97 /* timsort implementation, based on timsort.txt */
  98 struct tsort_run {
  99         ssize_t start;
 100         ssize_t length;
 101 };
 102
 103 struct tsort_store {
 104         size_t alloc;
 105         cmp_ptr_t cmp;
 106         void **storage;
 107 };
 108
 109 static void reverse_elements(void **dst, ssize_t start, ssize_t end)
 110 {
 111         while (start < end) {
 112                 void *tmp = dst[start];
 113                 dst[start] = dst[end];
 114                 dst[end] = tmp;
 115
 116                 start++;
 117                 end--;
 118         }
 119 }
 120
 121 static ssize_t count_run(void **dst, ssize_t start, ssize_t size, struct tsort_store *store)
 122 {
 123         ssize_t curr = start + 2;
 124
 125         if (size - start == 1)
 126                 return 1;
 127
 128         if (start >= size - 2) {
 129                 if (store->cmp(dst[size - 2], dst[size - 1]) > 0) {
 130                         void *tmp = dst[size - 1];
 131                         dst[size - 1] = dst[size - 2];
 132                         dst[size - 2] = tmp;
 133                 }
 134
 135                 return 2;
 136         }
 137
 138         if (store->cmp(dst[start], dst[start + 1]) <= 0) {
 139                 while (curr < size - 1 && store->cmp(dst[curr - 1], dst[curr]) <= 0)
 140                         curr++;
 141
 142                 return curr - start;
 143         } else {
 144                 while (curr < size - 1 && store->cmp(dst[curr - 1], dst[curr]) > 0)
 145                         curr++;
 146
 147                 /* reverse in-place */
 148                 reverse_elements(dst, start, curr - 1);
 149                 return curr - start;
 150         }
 151 }
 152
 153 static size_t compute_minrun(size_t n)
 154 {
 155         int r = 0;
 156         while (n >= 64) {
 157                 r |= n & 1;
 158                 n >>= 1;
 159         }
 160         return n + r;
 161 }
 162
 163 static int check_invariant(struct tsort_run *stack, ssize_t stack_curr)
 164 {
 165         if (stack_curr < 2)
 166                 return 1;
 167
 168         else if (stack_curr == 2) {
 169                 const ssize_t A = stack[stack_curr - 2].length;
 170                 const ssize_t B = stack[stack_curr - 1].length;
 171                 return (A > B);
 172         } else {
 173                 const ssize_t A = stack[stack_curr - 3].length;
 174                 const ssize_t B = stack[stack_curr - 2].length;
 175                 const ssize_t C = stack[stack_curr - 1].length;
 176                 return !((A <= B + C) || (B <= C));
 177         }
 178 }
 179
 180 static int resize(struct tsort_store *store, size_t new_size)
 181 {
 182         if (store->alloc < new_size) {
 183                 void **tempstore = git__realloc(store->storage, new_size * sizeof(void *));
 184
 185                 /**
 186                  * Do not propagate on OOM; this will abort the sort and
 187                  * leave the array unsorted, but no error code will be
 188                  * raised
 189                  */
 190                 if (tempstore == NULL)
 191                         return -1;
 192
 193                 store->storage = tempstore;
 194                 store->alloc = new_size;
 195         }
 196
 197         return 0;
 198 }
 199
 200 static void merge(void **dst, const struct tsort_run *stack, ssize_t stack_curr, struct tsort_store *store)
 201 {
 202         const ssize_t A = stack[stack_curr - 2].length;
 203         const ssize_t B = stack[stack_curr - 1].length;
 204         const ssize_t curr = stack[stack_curr - 2].start;
 205
 206         void **storage;
 207         ssize_t i, j, k;
 208
 209         if (resize(store, MIN(A, B)) < 0)
 210                 return;
 211
 212         storage = store->storage;
 213
 214         /* left merge */
 215         if (A < B) {
 216                 memcpy(storage, &dst[curr], A * sizeof(void *));
 217                 i = 0;
 218                 j = curr + A;
 219
 220                 for (k = curr; k < curr + A + B; k++) {
 221                         if ((i < A) && (j < curr + A + B)) {
 222                                 if (store->cmp(storage[i], dst[j]) <= 0)
 223                                         dst[k] = storage[i++];
 224                                 else
 225                                         dst[k] = dst[j++];
 226                         } else if (i < A) {
 227                                 dst[k] = storage[i++];
 228                         } else
 229                                 dst[k] = dst[j++];
 230                 }
 231         } else {
 232                 memcpy(storage, &dst[curr + A], B * sizeof(void *));
 233                 i = B - 1;
 234                 j = curr + A - 1;
 235
 236                 for (k = curr + A + B - 1; k >= curr; k--) {
 237                         if ((i >= 0) && (j >= curr)) {
 238                                 if (store->cmp(dst[j], storage[i]) > 0)
 239                                         dst[k] = dst[j--];
 240                                 else
 241                                         dst[k] = storage[i--];
 242                         } else if (i >= 0)
 243                                 dst[k] = storage[i--];
 244                         else
 245                                 dst[k] = dst[j--];
 246                 }
 247         }
 248 }
 249
 250 static ssize_t collapse(void **dst, struct tsort_run *stack, ssize_t stack_curr, struct tsort_store *store, ssize_t size)
 251 {
 252         ssize_t A, B, C;
 253
 254         while (1) {
 255                 /* if the stack only has one thing on it, we are done with the collapse */
 256                 if (stack_curr <= 1)
 257                         break;
 258
 259                 /* if this is the last merge, just do it */
 260                 if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
 261                         merge(dst, stack, stack_curr, store);
 262                         stack[0].length += stack[1].length;
 263                         stack_curr--;
 264                         break;
 265                 }
 266
 267                 /* check if the invariant is off for a stack of 2 elements */
 268                 else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
 269                         merge(dst, stack, stack_curr, store);
 270                         stack[0].length += stack[1].length;
 271                         stack_curr--;
 272                         break;
 273                 }
 274                 else if (stack_curr == 2)
 275                         break;
 276
 277                 A = stack[stack_curr - 3].length;
 278                 B = stack[stack_curr - 2].length;
 279                 C = stack[stack_curr - 1].length;
 280
 281                 /* check first invariant */
 282                 if (A <= B + C) {
 283                         if (A < C) {
 284                                 merge(dst, stack, stack_curr - 1, store);
 285                                 stack[stack_curr - 3].length += stack[stack_curr - 2].length;
 286                                 stack[stack_curr - 2] = stack[stack_curr - 1];
 287                                 stack_curr--;
 288                         } else {
 289                                 merge(dst, stack, stack_curr, store);
 290                                 stack[stack_curr - 2].length += stack[stack_curr - 1].length;
 291                                 stack_curr--;
 292                         }
 293                 } else if (B <= C) {
 294                         merge(dst, stack, stack_curr, store);
 295                         stack[stack_curr - 2].length += stack[stack_curr - 1].length;
 296                         stack_curr--;
 297                 } else
 298                         break;
 299         }
 300
 301         return stack_curr;
 302 }
 303
 304 #define PUSH_NEXT() do {\
 305         len = count_run(dst, curr, size, store);\
 306         run = minrun;\
 307         if (run < minrun) run = minrun;\
 308         if (run > (ssize_t)size - curr) run = size - curr;\
 309         if (run > len) {\
 310                 bisort(&dst[curr], len, run, cmp);\
 311                 len = run;\
 312         }\
 313         run_stack[stack_curr].start = curr;\
 314         run_stack[stack_curr++].length = len;\
 315         curr += len;\
 316         if (curr == (ssize_t)size) {\
 317                 /* finish up */ \
 318                 while (stack_curr > 1) { \
 319                         merge(dst, run_stack, stack_curr, store); \
 320                         run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length; \
 321                         stack_curr--; \
 322                 } \
 323                 if (store->storage != NULL) {\
 324                         git__free(store->storage);\
 325                         store->storage = NULL;\
 326                 }\
 327                 return;\
 328         }\
 329 }\
 330 while (0)
 331
 332 void git__tsort(void **dst, size_t size, cmp_ptr_t cmp)
 333 {
 334         struct tsort_store _store, *store = &_store;
 335         struct tsort_run run_stack[128];
 336
 337         ssize_t stack_curr = 0;
 338         ssize_t len, run;
 339         ssize_t curr = 0;
 340         ssize_t minrun;
 341
 342         if (size < 64) {
 343                 bisort(dst, 1, size, cmp);
 344                 return;
 345         }
 346
 347         /* compute the minimum run length */
 348         minrun = (ssize_t)compute_minrun(size);
 349
 350         /* temporary storage for merges */
 351         store->alloc = 0;
 352         store->storage = NULL;
 353         store->cmp = cmp;
 354
 355         PUSH_NEXT();
 356         PUSH_NEXT();
 357         PUSH_NEXT();
 358
 359         while (1) {
 360                 if (!check_invariant(run_stack, stack_curr)) {
 361                         stack_curr = collapse(dst, run_stack, stack_curr, store, size);
 362                         continue;
 363                 }
 364
 365                 PUSH_NEXT();
 366         }
 367 }