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 static int binsearch(
  27         void **dst, const void *x, size_t size, git__sort_r_cmp cmp, void *payload)
  28 {
  29         int l, c, r;
  30         void *lx, *cx;
  31
  32         assert(size > 0);
  33
  34         l = 0;
  35         r = (int)size - 1;
  36         c = r >> 1;
  37         lx = dst[l];
  38
  39         /* check for beginning conditions */
  40         if (cmp(x, lx, payload) < 0)
  41                 return 0;
  42
  43         else if (cmp(x, lx, payload) == 0) {
  44                 int i = 1;
  45                 while (cmp(x, dst[i], payload) == 0)
  46                         i++;
  47                 return i;
  48         }
  49
  50         /* guaranteed not to be >= rx */
  51         cx = dst[c];
  52         while (1) {
  53                 const int val = cmp(x, cx, payload);
  54                 if (val < 0) {
  55                         if (c - l <= 1) return c;
  56                         r = c;
  57                 } else if (val > 0) {
  58                         if (r - c <= 1) return c + 1;
  59                         l = c;
  60                         lx = cx;
  61                 } else {
  62                         do {
  63                                 cx = dst[++c];
  64                         } while (cmp(x, cx, payload) == 0);
  65                         return c;
  66                 }
  67                 c = l + ((r - l) >> 1);
  68                 cx = dst[c];
  69         }
  70 }
  71
  72 /* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
  73 static void bisort(
  74         void **dst, size_t start, size_t size, git__sort_r_cmp cmp, void *payload)
  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], payload) <= 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, payload);
  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         git__sort_r_cmp cmp;
 106         void *payload;
 107         void **storage;
 108 };
 109
 110 static void reverse_elements(void **dst, ssize_t start, ssize_t end)
 111 {
 112         while (start < end) {
 113                 void *tmp = dst[start];
 114                 dst[start] = dst[end];
 115                 dst[end] = tmp;
 116
 117                 start++;
 118                 end--;
 119         }
 120 }
 121
 122 static ssize_t count_run(
 123         void **dst, ssize_t start, ssize_t size, struct tsort_store *store)
 124 {
 125         ssize_t curr = start + 2;
 126
 127         if (size - start == 1)
 128                 return 1;
 129
 130         if (start >= size - 2) {
 131                 if (store->cmp(dst[size - 2], dst[size - 1], store->payload) > 0) {
 132                         void *tmp = dst[size - 1];
 133                         dst[size - 1] = dst[size - 2];
 134                         dst[size - 2] = tmp;
 135                 }
 136
 137                 return 2;
 138         }
 139
 140         if (store->cmp(dst[start], dst[start + 1], store->payload) <= 0) {
 141                 while (curr < size - 1 &&
 142                                 store->cmp(dst[curr - 1], dst[curr], store->payload) <= 0)
 143                         curr++;
 144
 145                 return curr - start;
 146         } else {
 147                 while (curr < size - 1 &&
 148                                 store->cmp(dst[curr - 1], dst[curr], store->payload) > 0)
 149                         curr++;
 150
 151                 /* reverse in-place */
 152                 reverse_elements(dst, start, curr - 1);
 153                 return curr - start;
 154         }
 155 }
 156
 157 static size_t compute_minrun(size_t n)
 158 {
 159         int r = 0;
 160         while (n >= 64) {
 161                 r |= n & 1;
 162                 n >>= 1;
 163         }
 164         return n + r;
 165 }
 166
 167 static int check_invariant(struct tsort_run *stack, ssize_t stack_curr)
 168 {
 169         if (stack_curr < 2)
 170                 return 1;
 171
 172         else if (stack_curr == 2) {
 173                 const ssize_t A = stack[stack_curr - 2].length;
 174                 const ssize_t B = stack[stack_curr - 1].length;
 175                 return (A > B);
 176         } else {
 177                 const ssize_t A = stack[stack_curr - 3].length;
 178                 const ssize_t B = stack[stack_curr - 2].length;
 179                 const ssize_t C = stack[stack_curr - 1].length;
 180                 return !((A <= B + C) || (B <= C));
 181         }
 182 }
 183
 184 static int resize(struct tsort_store *store, size_t new_size)
 185 {
 186         if (store->alloc < new_size) {
 187                 void **tempstore;
 188
 189                 tempstore = git__reallocarray(store->storage, new_size, sizeof(void *));
 190
 191                 /**
 192                  * Do not propagate on OOM; this will abort the sort and
 193                  * leave the array unsorted, but no error code will be
 194                  * raised
 195                  */
 196                 if (tempstore == NULL)
 197                         return -1;
 198
 199                 store->storage = tempstore;
 200                 store->alloc = new_size;
 201         }
 202
 203         return 0;
 204 }
 205
 206 static void merge(void **dst, const struct tsort_run *stack, ssize_t stack_curr, struct tsort_store *store)
 207 {
 208         const ssize_t A = stack[stack_curr - 2].length;
 209         const ssize_t B = stack[stack_curr - 1].length;
 210         const ssize_t curr = stack[stack_curr - 2].start;
 211
 212         void **storage;
 213         ssize_t i, j, k;
 214
 215         if (resize(store, MIN(A, B)) < 0)
 216                 return;
 217
 218         storage = store->storage;
 219
 220         /* left merge */
 221         if (A < B) {
 222                 memcpy(storage, &dst[curr], A * sizeof(void *));
 223                 i = 0;
 224                 j = curr + A;
 225
 226                 for (k = curr; k < curr + A + B; k++) {
 227                         if ((i < A) && (j < curr + A + B)) {
 228                                 if (store->cmp(storage[i], dst[j], store->payload) <= 0)
 229                                         dst[k] = storage[i++];
 230                                 else
 231                                         dst[k] = dst[j++];
 232                         } else if (i < A) {
 233                                 dst[k] = storage[i++];
 234                         } else
 235                                 dst[k] = dst[j++];
 236                 }
 237         } else {
 238                 memcpy(storage, &dst[curr + A], B * sizeof(void *));
 239                 i = B - 1;
 240                 j = curr + A - 1;
 241
 242                 for (k = curr + A + B - 1; k >= curr; k--) {
 243                         if ((i >= 0) && (j >= curr)) {
 244                                 if (store->cmp(dst[j], storage[i], store->payload) > 0)
 245                                         dst[k] = dst[j--];
 246                                 else
 247                                         dst[k] = storage[i--];
 248                         } else if (i >= 0)
 249                                 dst[k] = storage[i--];
 250                         else
 251                                 dst[k] = dst[j--];
 252                 }
 253         }
 254 }
 255
 256 static ssize_t collapse(void **dst, struct tsort_run *stack, ssize_t stack_curr, struct tsort_store *store, ssize_t size)
 257 {
 258         ssize_t A, B, C;
 259
 260         while (1) {
 261                 /* if the stack only has one thing on it, we are done with the collapse */
 262                 if (stack_curr <= 1)
 263                         break;
 264
 265                 /* if this is the last merge, just do it */
 266                 if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
 267                         merge(dst, stack, stack_curr, store);
 268                         stack[0].length += stack[1].length;
 269                         stack_curr--;
 270                         break;
 271                 }
 272
 273                 /* check if the invariant is off for a stack of 2 elements */
 274                 else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
 275                         merge(dst, stack, stack_curr, store);
 276                         stack[0].length += stack[1].length;
 277                         stack_curr--;
 278                         break;
 279                 }
 280                 else if (stack_curr == 2)
 281                         break;
 282
 283                 A = stack[stack_curr - 3].length;
 284                 B = stack[stack_curr - 2].length;
 285                 C = stack[stack_curr - 1].length;
 286
 287                 /* check first invariant */
 288                 if (A <= B + C) {
 289                         if (A < C) {
 290                                 merge(dst, stack, stack_curr - 1, store);
 291                                 stack[stack_curr - 3].length += stack[stack_curr - 2].length;
 292                                 stack[stack_curr - 2] = stack[stack_curr - 1];
 293                                 stack_curr--;
 294                         } else {
 295                                 merge(dst, stack, stack_curr, store);
 296                                 stack[stack_curr - 2].length += stack[stack_curr - 1].length;
 297                                 stack_curr--;
 298                         }
 299                 } else if (B <= C) {
 300                         merge(dst, stack, stack_curr, store);
 301                         stack[stack_curr - 2].length += stack[stack_curr - 1].length;
 302                         stack_curr--;
 303                 } else
 304                         break;
 305         }
 306
 307         return stack_curr;
 308 }
 309
 310 #define PUSH_NEXT() do {\
 311         len = count_run(dst, curr, size, store);\
 312         run = minrun;\
 313         if (run < minrun) run = minrun;\
 314         if (run > (ssize_t)size - curr) run = size - curr;\
 315         if (run > len) {\
 316                 bisort(&dst[curr], len, run, cmp, payload);\
 317                 len = run;\
 318         }\
 319         run_stack[stack_curr].start = curr;\
 320         run_stack[stack_curr++].length = len;\
 321         curr += len;\
 322         if (curr == (ssize_t)size) {\
 323                 /* finish up */ \
 324                 while (stack_curr > 1) { \
 325                         merge(dst, run_stack, stack_curr, store); \
 326                         run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length; \
 327                         stack_curr--; \
 328                 } \
 329                 if (store->storage != NULL) {\
 330                         git__free(store->storage);\
 331                         store->storage = NULL;\
 332                 }\
 333                 return;\
 334         }\
 335 }\
 336 while (0)
 337
 338 void git__tsort_r(
 339         void **dst, size_t size, git__sort_r_cmp cmp, void *payload)
 340 {
 341         struct tsort_store _store, *store = &_store;
 342         struct tsort_run run_stack[128];
 343
 344         ssize_t stack_curr = 0;
 345         ssize_t len, run;
 346         ssize_t curr = 0;
 347         ssize_t minrun;
 348
 349         if (size < 64) {
 350                 bisort(dst, 1, size, cmp, payload);
 351                 return;
 352         }
 353
 354         /* compute the minimum run length */
 355         minrun = (ssize_t)compute_minrun(size);
 356
 357         /* temporary storage for merges */
 358         store->alloc = 0;
 359         store->storage = NULL;
 360         store->cmp = cmp;
 361         store->payload = payload;
 362
 363         PUSH_NEXT();
 364         PUSH_NEXT();
 365         PUSH_NEXT();
 366
 367         while (1) {
 368                 if (!check_invariant(run_stack, stack_curr)) {
 369                         stack_curr = collapse(dst, run_stack, stack_curr, store, size);
 370                         continue;
 371                 }
 372
 373                 PUSH_NEXT();
 374         }
 375 }
 376
 377 static int tsort_r_cmp(const void *a, const void *b, void *payload)
 378 {
 379         return ((git__tsort_cmp)payload)(a, b);
 380 }
 381
 382 void git__tsort(void **dst, size_t size, git__tsort_cmp cmp)
 383 {
 384         git__tsort_r(dst, size, tsort_r_cmp, cmp);
 385 }