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
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
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
65int
66svn_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
79int
80svn_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
97int
98svn_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
110int
111svn_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
120int
121svn_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
136apr_array_header_t *
137svn_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 */
189static int
190bsearch_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
215int
216svn_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
225void
226svn_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
250void
251svn_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
275void
276svn_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}
310