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
  36
  37 \f
  38 /*** svn_sort__hash() ***/
  39
  40 /* (Should this be a permanent part of APR?)
  41
  42    OK, folks, here's what's going on.  APR hash tables hash on
  43    key/klen objects, and store associated generic values.  They work
  44    great, but they have no ordering.
  45
  46    The point of this exercise is to somehow arrange a hash's keys into
  47    an "ordered list" of some kind -- in this case, a nicely sorted
  48    one.
  49
  50    We're using APR arrays, therefore, because that's what they are:
  51    ordered lists.  However, what "keys" should we put in the array?
  52    Clearly, (const char *) objects aren't general enough.  Or rather,
  53    they're not as general as APR's hash implementation, which stores
  54    (void *)/length as keys.  We don't want to lose this information.
  55
  56    Therefore, it makes sense to store pointers to {void *, size_t}
  57    structures in our array.  No such apr object exists... BUT... if we
  58    can use a new type svn_sort__item_t which contains {char *, size_t, void
  59    *}.  If store these objects in our array, we get the hash value
  60    *for free*.  When looping over the final array, we don't need to
  61    call apr_hash_get().  Major bonus!
  62  */
  63
  64
  65 int
  66 svn_sort_compare_items_as_paths(const svn_sort__item_t *a,
  67                                 const svn_sort__item_t *b)
  68 {
  69   const char *astr, *bstr;
  70
  71   astr = a->key;
  72   bstr = b->key;
  73   assert(astr[a->klen] == '\0');
  74   assert(bstr[b->klen] == '\0');
  75   return svn_path_compare_paths(astr, bstr);
  76 }
  77
  78
  79 int
  80 svn_sort_compare_items_lexically(const svn_sort__item_t *a,
  81                                  const svn_sort__item_t *b)
  82 {
  83   int val;
  84   apr_size_t len;
  85
  86   /* Compare bytes of a's key and b's key up to the common length. */
  87   len = (a->klen < b->klen) ? a->klen : b->klen;
  88   val = memcmp(a->key, b->key, len);
  89   if (val != 0)
  90     return val;
  91
  92   /* They match up until one of them ends; whichever is longer is greater. */
  93   return (a->klen < b->klen) ? -1 : (a->klen > b->klen) ? 1 : 0;
  94 }
  95
  96
  97 int
  98 svn_sort_compare_revisions(const void *a, const void *b)
  99 {
 100   svn_revnum_t a_rev = *(const svn_revnum_t *)a;
 101   svn_revnum_t b_rev = *(const svn_revnum_t *)b;
 102
 103   if (a_rev == b_rev)
 104     return 0;
 105
 106   return a_rev < b_rev ? 1 : -1;
 107 }
 108
 109
 110 int
 111 svn_sort_compare_paths(const void *a, const void *b)
 112 {
 113   const char *item1 = *((const char * const *) a);
 114   const char *item2 = *((const char * const *) b);
 115
 116   return svn_path_compare_paths(item1, item2);
 117 }
 118
 119
 120 int
 121 svn_sort_compare_ranges(const void *a, const void *b)
 122 {
 123   const svn_merge_range_t *item1 = *((const svn_merge_range_t * const *) a);
 124   const svn_merge_range_t *item2 = *((const svn_merge_range_t * const *) b);
 125
 126   if (item1->start == item2->start
 127       && item1->end == item2->end)
 128     return 0;
 129
 130   if (item1->start == item2->start)
 131     return item1->end < item2->end ? -1 : 1;
 132
 133   return item1->start < item2->start ? -1 : 1;
 134 }
 135
 136 apr_array_header_t *
 137 svn_sort__hash(apr_hash_t *ht,
 138                int (*comparison_func)(const svn_sort__item_t *,
 139                                       const svn_sort__item_t *),
 140                apr_pool_t *pool)
 141 {
 142   apr_hash_index_t *hi;
 143   apr_array_header_t *ary;
 144   svn_boolean_t sorted;
 145   svn_sort__item_t *prev_item;
 146
 147   /* allocate an array with enough elements to hold all the keys. */
 148   ary = apr_array_make(pool, apr_hash_count(ht), sizeof(svn_sort__item_t));
 149
 150   /* loop over hash table and push all keys into the array */
 151   sorted = TRUE;
 152   prev_item = NULL;
 153   for (hi = apr_hash_first(pool, ht); hi; hi = apr_hash_next(hi))
 154     {
 155       svn_sort__item_t *item = apr_array_push(ary);
 156
 157       apr_hash_this(hi, &item->key, &item->klen, &item->value);
 158
 159       if (prev_item == NULL)
 160         {
 161           prev_item = item;
 162           continue;
 163         }
 164
 165       if (sorted)
 166         {
 167           sorted = (comparison_func(prev_item, item) < 0);
 168           prev_item = item;
 169         }
 170     }
 171
 172   /* quicksort the array if it isn't already sorted.  */
 173   if (!sorted)
 174     qsort(ary->elts, ary->nelts, ary->elt_size,
 175           (int (*)(const void *, const void *))comparison_func);
 176
 177   return ary;
 178 }
 179
 180 /* Return the lowest index at which the element *KEY should be inserted into
 181    the array at BASE which has NELTS elements of size ELT_SIZE bytes each,
 182    according to the ordering defined by COMPARE_FUNC.
 183    0 <= NELTS <= INT_MAX, 1 <= ELT_SIZE <= INT_MAX.
 184    The array must already be sorted in the ordering defined by COMPARE_FUNC.
 185    COMPARE_FUNC is defined as for the C stdlib function bsearch().
 186    Note: This function is modeled on bsearch() and on lower_bound() in the
 187    C++ STL.
 188  */
 189 static int
 190 bsearch_lower_bound(const void *key,
 191                     const void *base,
 192                     int nelts,
 193                     int elt_size,
 194                     int (*compare_func)(const void *, const void *))
 195 {
 196   int lower = 0;
 197   int upper = nelts - 1;
 198
 199   /* Binary search for the lowest position at which to insert KEY. */
 200   while (lower <= upper)
 201     {
 202       int try = lower + (upper - lower) / 2;  /* careful to avoid overflow */
 203       int cmp = compare_func((const char *)base + try * elt_size, key);
 204
 205       if (cmp < 0)
 206         lower = try + 1;
 207       else
 208         upper = try - 1;
 209     }
 210   assert(lower == upper + 1);
 211
 212   return lower;
 213 }
 214
 215 int
 216 svn_sort__bsearch_lower_bound(const void *key,
 217                               const apr_array_header_t *array,
 218                               int (*compare_func)(const void *, const void *))
 219 {
 220   return bsearch_lower_bound(key,
 221                              array->elts, array->nelts, array->elt_size,
 222                              compare_func);
 223 }
 224
 225 void
 226 svn_sort__array_insert(const void *new_element,
 227                        apr_array_header_t *array,
 228                        int insert_index)
 229 {
 230   int elements_to_move;
 231   char *new_position;
 232
 233   assert(0 <= insert_index && insert_index <= array->nelts);
 234   elements_to_move = array->nelts - insert_index;  /* before bumping nelts */
 235
 236   /* Grow the array, allocating a new space at the end. Note: this can
 237      reallocate the array's "elts" at a different address. */
 238   apr_array_push(array);
 239
 240   /* Move the elements after INSERT_INDEX along. (When elements_to_move == 0,
 241      this is a no-op.) */
 242   new_position = (char *)array->elts + insert_index * array->elt_size;
 243   memmove(new_position + array->elt_size, new_position,
 244           array->elt_size * elements_to_move);
 245
 246   /* Copy in the new element */
 247   memcpy(new_position, new_element, array->elt_size);
 248 }
 249
 250 void
 251 svn_sort__array_delete(apr_array_header_t *arr,
 252                        int delete_index,
 253                        int elements_to_delete)
 254 {
 255   /* Do we have a valid index and are there enough elements? */
 256   if (delete_index >= 0
 257       && delete_index < arr->nelts
 258       && elements_to_delete > 0
 259       && (elements_to_delete + delete_index) <= arr->nelts)
 260     {
 261       /* If we are not deleting a block of elements that extends to the end
 262          of the array, then we need to move the remaining elements to keep
 263          the array contiguous. */
 264       if ((elements_to_delete + delete_index) < arr->nelts)
 265         memmove(
 266           arr->elts + arr->elt_size * delete_index,
 267           arr->elts + (arr->elt_size * (delete_index + elements_to_delete)),
 268           arr->elt_size * (arr->nelts - elements_to_delete - delete_index));
 269
 270       /* Delete the last ELEMENTS_TO_DELETE elements. */
 271       arr->nelts -= elements_to_delete;
 272     }
 273 }
 274
 275 void
 276 svn_sort__array_reverse(apr_array_header_t *array,
 277                         apr_pool_t *scratch_pool)
 278 {
 279   int i;
 280
 281   if (array->elt_size == sizeof(void *))
 282     {
 283       for (i = 0; i < array->nelts / 2; i++)
 284         {
 285           int swap_index = array->nelts - i - 1;
 286           void *tmp = APR_ARRAY_IDX(array, i, void *);
 287
 288           APR_ARRAY_IDX(array, i, void *) =
 289             APR_ARRAY_IDX(array, swap_index, void *);
 290           APR_ARRAY_IDX(array, swap_index, void *) = tmp;
 291         }
 292     }
 293   else
 294     {
 295       apr_size_t sz = array->elt_size;
 296       char *tmp = apr_palloc(scratch_pool, sz);
 297
 298       for (i = 0; i < array->nelts / 2; i++)
 299         {
 300           int swap_index = array->nelts - i - 1;
 301           char *x = array->elts + (sz * i);
 302           char *y = array->elts + (sz * swap_index);
 303
 304           memcpy(tmp, x, sz);
 305           memcpy(x, y, sz);
 306           memcpy(y, tmp, sz);
 307         }
 308     }
 309 }