contrib/subversion/subversion/libsvn_subr/sorts.c

   1 /*
   2  * sorts.c:   all sorts of sorts
   3  *
   4  * ====================================================================
   5  *    Licensed to the Apache Software Foundation (ASF) under one
   6  *    or more contributor license agreements.  See the NOTICE file
   7  *    distributed with this work for additional information
   8  *    regarding copyright ownership.  The ASF licenses this file
   9  *    to you under the Apache License, Version 2.0 (the
  10  *    "License"); you may not use this file except in compliance
  11  *    with the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  *    Unless required by applicable law or agreed to in writing,
  16  *    software distributed under the License is distributed on an
  17  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  18  *    KIND, either express or implied.  See the License for the
  19  *    specific language governing permissions and limitations
  20  *    under the License.
  21  * ====================================================================
  22  */
  23
  24
  25 \f
  26 #include <apr_pools.h>
  27 #include <apr_hash.h>
  28 #include <apr_tables.h>
  29 #include <stdlib.h>       /* for qsort()   */
  30 #include <assert.h>
  31 #include "svn_hash.h"
  32 #include "svn_path.h"
  33 #include "svn_sorts.h"
  34 #include "svn_error.h"
  35 #include "private/svn_sorts_private.h"
  36
  37
  38 \f
  39 /*** svn_sort__hash() ***/
  40
  41 /* (Should this be a permanent part of APR?)
  42
  43    OK, folks, here's what's going on.  APR hash tables hash on
  44    key/klen objects, and store associated generic values.  They work
  45    great, but they have no ordering.
  46
  47    The point of this exercise is to somehow arrange a hash's keys into
  48    an "ordered list" of some kind -- in this case, a nicely sorted
  49    one.
  50
  51    We're using APR arrays, therefore, because that's what they are:
  52    ordered lists.  However, what "keys" should we put in the array?
  53    Clearly, (const char *) objects aren't general enough.  Or rather,
  54    they're not as general as APR's hash implementation, which stores
  55    (void *)/length as keys.  We don't want to lose this information.
  56
  57    Therefore, it makes sense to store pointers to {void *, size_t}
  58    structures in our array.  No such apr object exists... BUT... if we
  59    can use a new type svn_sort__item_t which contains {char *, size_t, void
  60    *}.  If store these objects in our array, we get the hash value
  61    *for free*.  When looping over the final array, we don't need to
  62    call apr_hash_get().  Major bonus!
  63  */
  64
  65
  66 int
  67 svn_sort_compare_items_as_paths(const svn_sort__item_t *a,
  68                                 const svn_sort__item_t *b)
  69 {
  70   const char *astr, *bstr;
  71
  72   astr = a->key;
  73   bstr = b->key;
  74   assert(astr[a->klen] == '\0');
  75   assert(bstr[b->klen] == '\0');
  76   return svn_path_compare_paths(astr, bstr);
  77 }
  78
  79
  80 int
  81 svn_sort_compare_items_lexically(const svn_sort__item_t *a,
  82                                  const svn_sort__item_t *b)
  83 {
  84   int val;
  85   apr_size_t len;
  86
  87   /* Compare bytes of a's key and b's key up to the common length. */
  88   len = (a->klen < b->klen) ? a->klen : b->klen;
  89   val = memcmp(a->key, b->key, len);
  90   if (val != 0)
  91     return val;
  92
  93   /* They match up until one of them ends; whichever is longer is greater. */
  94   return (a->klen < b->klen) ? -1 : (a->klen > b->klen) ? 1 : 0;
  95 }
  96
  97
  98 int
  99 svn_sort_compare_revisions(const void *a, const void *b)
 100 {
 101   svn_revnum_t a_rev = *(const svn_revnum_t *)a;
 102   svn_revnum_t b_rev = *(const svn_revnum_t *)b;
 103
 104   if (a_rev == b_rev)
 105     return 0;
 106
 107   return a_rev < b_rev ? 1 : -1;
 108 }
 109
 110
 111 int
 112 svn_sort_compare_paths(const void *a, const void *b)
 113 {
 114   const char *item1 = *((const char * const *) a);
 115   const char *item2 = *((const char * const *) b);
 116
 117   return svn_path_compare_paths(item1, item2);
 118 }
 119
 120
 121 int
 122 svn_sort_compare_ranges(const void *a, const void *b)
 123 {
 124   const svn_merge_range_t *item1 = *((const svn_merge_range_t * const *) a);
 125   const svn_merge_range_t *item2 = *((const svn_merge_range_t * const *) b);
 126
 127   if (item1->start == item2->start
 128       && item1->end == item2->end)
 129     return 0;
 130
 131   if (item1->start == item2->start)
 132     return item1->end < item2->end ? -1 : 1;
 133
 134   return item1->start < item2->start ? -1 : 1;
 135 }
 136
 137 void
 138 svn_sort__array(apr_array_header_t *array,
 139                 int (*comparison_func)(const void *,
 140                                        const void *))
 141 {
 142   qsort(array->elts, array->nelts, array->elt_size, comparison_func);
 143 }
 144
 145 apr_array_header_t *
 146 svn_sort__hash(apr_hash_t *ht,
 147                int (*comparison_func)(const svn_sort__item_t *,
 148                                       const svn_sort__item_t *),
 149                apr_pool_t *pool)
 150 {
 151   apr_hash_index_t *hi;
 152   apr_array_header_t *ary;
 153   svn_boolean_t sorted;
 154   svn_sort__item_t *prev_item;
 155
 156   /* allocate an array with enough elements to hold all the keys. */
 157   ary = apr_array_make(pool, apr_hash_count(ht), sizeof(svn_sort__item_t));
 158
 159   /* loop over hash table and push all keys into the array */
 160   sorted = TRUE;
 161   prev_item = NULL;
 162   for (hi = apr_hash_first(pool, ht); hi; hi = apr_hash_next(hi))
 163     {
 164       svn_sort__item_t *item = apr_array_push(ary);
 165
 166       apr_hash_this(hi, &item->key, &item->klen, &item->value);
 167
 168       if (prev_item == NULL)
 169         {
 170           prev_item = item;
 171           continue;
 172         }
 173
 174       if (sorted)
 175         {
 176           sorted = (comparison_func(prev_item, item) < 0);
 177           prev_item = item;
 178         }
 179     }
 180
 181   /* quicksort the array if it isn't already sorted.  */
 182   if (!sorted)
 183     svn_sort__array(ary,
 184           (int (*)(const void *, const void *))comparison_func);
 185
 186   return ary;
 187 }
 188
 189 /* Return the lowest index at which the element *KEY should be inserted into
 190    the array at BASE which has NELTS elements of size ELT_SIZE bytes each,
 191    according to the ordering defined by COMPARE_FUNC.
 192    0 <= NELTS <= INT_MAX, 1 <= ELT_SIZE <= INT_MAX.
 193    The array must already be sorted in the ordering defined by COMPARE_FUNC.
 194    COMPARE_FUNC is defined as for the C stdlib function bsearch().
 195    Note: This function is modeled on bsearch() and on lower_bound() in the
 196    C++ STL.
 197  */
 198 static int
 199 bsearch_lower_bound(const void *key,
 200                     const void *base,
 201                     int nelts,
 202                     int elt_size,
 203                     int (*compare_func)(const void *, const void *))
 204 {
 205   int lower = 0;
 206   int upper = nelts - 1;
 207
 208   /* Binary search for the lowest position at which to insert KEY. */
 209   while (lower <= upper)
 210     {
 211       int try = lower + (upper - lower) / 2;  /* careful to avoid overflow */
 212       int cmp = compare_func((const char *)base + try * elt_size, key);
 213
 214       if (cmp < 0)
 215         lower = try + 1;
 216       else
 217         upper = try - 1;
 218     }
 219   assert(lower == upper + 1);
 220
 221   return lower;
 222 }
 223
 224 int
 225 svn_sort__bsearch_lower_bound(const apr_array_header_t *array,
 226                               const void *key,
 227                               int (*compare_func)(const void *, const void *))
 228 {
 229   return bsearch_lower_bound(key,
 230                              array->elts, array->nelts, array->elt_size,
 231                              compare_func);
 232 }
 233
 234 void *
 235 svn_sort__array_lookup(const apr_array_header_t *array,
 236                        const void *key,
 237                        int *hint,
 238                        int (*compare_func)(const void *, const void *))
 239 {
 240   void *result;
 241   int idx;
 242
 243   /* If provided, try the index following *HINT (i.e. probably the last
 244    * hit location) first.  This speeds up linear scans. */
 245   if (hint)
 246     {
 247       /* We intend to insert right behind *HINT.
 248        * Exit this function early, if we actually can. */
 249       idx = *hint + 1;
 250       if (idx >= array->nelts)
 251         {
 252           /* We intend to insert after the last entry.
 253            * That is only allowed if that last entry is smaller than KEY.
 254            * In that case, there will be no current entry, i.e. we must
 255            * return NULL. */
 256           apr_size_t offset;
 257
 258           *hint = array->nelts;
 259           if (array->nelts == 0)
 260             return NULL;
 261
 262           offset = (array->nelts - 1) * array->elt_size;
 263           if (compare_func(array->elts + offset, key) < 0)
 264             return NULL;
 265         }
 266       else if (idx > 0)
 267         {
 268           /* Intend to insert at a position inside the array, i.e. not
 269            * at one of the boundaries.  The predecessor must be smaller
 270            * and the current entry at IDX must be larger than KEY. */
 271           void *previous;
 272
 273           *hint = idx;
 274           previous = array->elts + (idx-1) * array->elt_size;
 275           result = array->elts + idx * array->elt_size;
 276           if (compare_func(previous, key) && !compare_func(result, key))
 277             return result;
 278         }
 279       else if (idx <= 0)
 280         {
 281           /* Intend to insert at the beginning of an non-empty array.
 282            * That requires the first entry to be larger than KEY. */
 283           *hint = 0;
 284           if (!compare_func(array->elts, key))
 285             return array->elts;
 286         }
 287
 288       /* The HINT did not help. */
 289     }
 290
 291   idx = bsearch_lower_bound(key, array->elts, array->nelts, array->elt_size,
 292                             compare_func);
 293   if (hint)
 294     *hint = idx;
 295   if (idx >= array->nelts)
 296     return NULL;
 297
 298   result = array->elts + idx * array->elt_size;
 299   return compare_func(result, key) ? NULL : result;
 300 }
 301
 302 void
 303 svn_sort__array_insert(apr_array_header_t *array,
 304                        const void *new_element,
 305                        int insert_index)
 306 {
 307   int elements_to_move;
 308   char *new_position;
 309
 310   assert(0 <= insert_index && insert_index <= array->nelts);
 311   elements_to_move = array->nelts - insert_index;  /* before bumping nelts */
 312
 313   /* Grow the array, allocating a new space at the end. Note: this can
 314      reallocate the array's "elts" at a different address. */
 315   apr_array_push(array);
 316
 317   /* Move the elements after INSERT_INDEX along. (When elements_to_move == 0,
 318      this is a no-op.) */
 319   new_position = (char *)array->elts + insert_index * array->elt_size;
 320   memmove(new_position + array->elt_size, new_position,
 321           array->elt_size * elements_to_move);
 322
 323   /* Copy in the new element */
 324   memcpy(new_position, new_element, array->elt_size);
 325 }
 326
 327 void
 328 svn_sort__array_delete(apr_array_header_t *arr,
 329                        int delete_index,
 330                        int elements_to_delete)
 331 {
 332   /* Do we have a valid index and are there enough elements? */
 333   if (delete_index >= 0
 334       && delete_index < arr->nelts
 335       && elements_to_delete > 0
 336       && (elements_to_delete + delete_index) <= arr->nelts)
 337     {
 338       /* If we are not deleting a block of elements that extends to the end
 339          of the array, then we need to move the remaining elements to keep
 340          the array contiguous. */
 341       if ((elements_to_delete + delete_index) < arr->nelts)
 342         memmove(
 343           arr->elts + arr->elt_size * delete_index,
 344           arr->elts + (arr->elt_size * (delete_index + elements_to_delete)),
 345           arr->elt_size * (arr->nelts - elements_to_delete - delete_index));
 346
 347       /* Delete the last ELEMENTS_TO_DELETE elements. */
 348       arr->nelts -= elements_to_delete;
 349     }
 350 }
 351
 352 void
 353 svn_sort__array_reverse(apr_array_header_t *array,
 354                         apr_pool_t *scratch_pool)
 355 {
 356   int i;
 357
 358   if (array->elt_size == sizeof(void *))
 359     {
 360       for (i = 0; i < array->nelts / 2; i++)
 361         {
 362           int swap_index = array->nelts - i - 1;
 363           void *tmp = APR_ARRAY_IDX(array, i, void *);
 364
 365           APR_ARRAY_IDX(array, i, void *) =
 366             APR_ARRAY_IDX(array, swap_index, void *);
 367           APR_ARRAY_IDX(array, swap_index, void *) = tmp;
 368         }
 369     }
 370   else
 371     {
 372       apr_size_t sz = array->elt_size;
 373       char *tmp = apr_palloc(scratch_pool, sz);
 374
 375       for (i = 0; i < array->nelts / 2; i++)
 376         {
 377           int swap_index = array->nelts - i - 1;
 378           char *x = array->elts + (sz * i);
 379           char *y = array->elts + (sz * swap_index);
 380
 381           memcpy(tmp, x, sz);
 382           memcpy(x, y, sz);
 383           memcpy(y, tmp, sz);
 384         }
 385     }
 386 }
 387
 388 /* Our priority queue data structure:
 389  * Simply remember the constructor parameters.
 390  */
 391 struct svn_priority_queue__t
 392 {
 393   /* the queue elements, ordered as a heap according to COMPARE_FUNC */
 394   apr_array_header_t *elements;
 395
 396   /* predicate used to order the heap */
 397   int (*compare_func)(const void *, const void *);
 398 };
 399
 400 /* Return TRUE, if heap element number LHS in QUEUE is smaller than element
 401  * number RHS according to QUEUE->COMPARE_FUNC
 402  */
 403 static int
 404 heap_is_less(svn_priority_queue__t *queue,
 405              apr_size_t lhs,
 406              apr_size_t rhs)
 407 {
 408   char *lhs_value = queue->elements->elts + lhs * queue->elements->elt_size;
 409   char *rhs_value = queue->elements->elts + rhs * queue->elements->elt_size;
 410
 411   /* nelts is never negative */
 412   assert(lhs < (apr_size_t)queue->elements->nelts);
 413   assert(rhs < (apr_size_t)queue->elements->nelts);
 414   return queue->compare_func(lhs_value, rhs_value) < 0;
 415 }
 416
 417 /* Exchange elements number LHS and RHS in QUEUE.
 418  */
 419 static void
 420 heap_swap(svn_priority_queue__t *queue,
 421           apr_size_t lhs,
 422           apr_size_t rhs)
 423 {
 424   int i;
 425   char *lhs_value = queue->elements->elts + lhs * queue->elements->elt_size;
 426   char *rhs_value = queue->elements->elts + rhs * queue->elements->elt_size;
 427
 428   for (i = 0; i < queue->elements->elt_size; ++i)
 429     {
 430       char temp = lhs_value[i];
 431       lhs_value[i] = rhs_value[i];
 432       rhs_value[i] = temp;
 433     }
 434 }
 435
 436 /* Move element number IDX to lower indexes until the heap criterion is
 437  * fulfilled again.
 438  */
 439 static void
 440 heap_bubble_down(svn_priority_queue__t *queue,
 441                  int idx)
 442 {
 443   while (idx > 0 && heap_is_less(queue, idx, (idx - 1) / 2))
 444     {
 445       heap_swap(queue, idx, (idx - 1) / 2);
 446       idx = (idx - 1) / 2;
 447     }
 448 }
 449
 450 /* Move element number IDX to higher indexes until the heap criterion is
 451  * fulfilled again.
 452  */
 453 static void
 454 heap_bubble_up(svn_priority_queue__t *queue,
 455                int idx)
 456 {
 457   while (2 * idx + 2 < queue->elements->nelts)
 458     {
 459       int child = heap_is_less(queue, 2 * idx + 1, 2 * idx + 2)
 460                 ? 2 * idx + 1
 461                 : 2 * idx + 2;
 462
 463       if (heap_is_less(queue, idx, child))
 464         return;
 465
 466       heap_swap(queue, idx, child);
 467       idx = child;
 468     }
 469
 470   if (   2 * idx + 1 < queue->elements->nelts
 471       && heap_is_less(queue, 2 * idx + 1, idx))
 472     heap_swap(queue, 2 * idx + 1, idx);
 473 }
 474
 475 svn_priority_queue__t *
 476 svn_priority_queue__create(apr_array_header_t *elements,
 477                            int (*compare_func)(const void *, const void *))
 478 {
 479   int i;
 480
 481   svn_priority_queue__t *queue = apr_pcalloc(elements->pool, sizeof(*queue));
 482   queue->elements = elements;
 483   queue->compare_func = compare_func;
 484
 485   for (i = elements->nelts / 2; i >= 0; --i)
 486     heap_bubble_up(queue, i);
 487
 488   return queue;
 489 }
 490
 491 apr_size_t
 492 svn_priority_queue__size(svn_priority_queue__t *queue)
 493 {
 494   return queue->elements->nelts;
 495 }
 496
 497 void *
 498 svn_priority_queue__peek(svn_priority_queue__t *queue)
 499 {
 500   return queue->elements->nelts ? queue->elements->elts : NULL;
 501 }
 502
 503 void
 504 svn_priority_queue__update(svn_priority_queue__t *queue)
 505 {
 506   heap_bubble_up(queue, 0);
 507 }
 508
 509 void
 510 svn_priority_queue__pop(svn_priority_queue__t *queue)
 511 {
 512   if (queue->elements->nelts)
 513     {
 514       memmove(queue->elements->elts,
 515               queue->elements->elts
 516               + (queue->elements->nelts - 1) * queue->elements->elt_size,
 517               queue->elements->elt_size);
 518       --queue->elements->nelts;
 519       heap_bubble_up(queue, 0);
 520     }
 521 }
 522
 523 void
 524 svn_priority_queue__push(svn_priority_queue__t *queue,
 525                          const void *element)
 526 {
 527   /* we cannot duplicate elements due to potential array re-allocs */
 528   assert(element && element != queue->elements->elts);
 529
 530   memcpy(apr_array_push(queue->elements), element, queue->elements->elt_size);
 531   heap_bubble_down(queue, queue->elements->nelts - 1);
 532 }