2 * sorts.c: all sorts of sorts
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
13 * http://www.apache.org/licenses/LICENSE-2.0
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
21 * ====================================================================
26 #include <apr_pools.h>
28 #include <apr_tables.h>
29 #include <stdlib.h> /* for qsort() */
33 #include "svn_sorts.h"
34 #include "svn_error.h"
38 /*** svn_sort__hash() ***/
40 /* (Should this be a permanent part of APR?)
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.
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
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.
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!
66 svn_sort_compare_items_as_paths(const svn_sort__item_t
*a
,
67 const svn_sort__item_t
*b
)
69 const char *astr
, *bstr
;
73 assert(astr
[a
->klen
] == '\0');
74 assert(bstr
[b
->klen
] == '\0');
75 return svn_path_compare_paths(astr
, bstr
);
80 svn_sort_compare_items_lexically(const svn_sort__item_t
*a
,
81 const svn_sort__item_t
*b
)
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
);
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;
98 svn_sort_compare_revisions(const void *a
, const void *b
)
100 svn_revnum_t a_rev
= *(const svn_revnum_t
*)a
;
101 svn_revnum_t b_rev
= *(const svn_revnum_t
*)b
;
106 return a_rev
< b_rev
? 1 : -1;
111 svn_sort_compare_paths(const void *a
, const void *b
)
113 const char *item1
= *((const char * const *) a
);
114 const char *item2
= *((const char * const *) b
);
116 return svn_path_compare_paths(item1
, item2
);
121 svn_sort_compare_ranges(const void *a
, const void *b
)
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
);
126 if (item1
->start
== item2
->start
127 && item1
->end
== item2
->end
)
130 if (item1
->start
== item2
->start
)
131 return item1
->end
< item2
->end
? -1 : 1;
133 return item1
->start
< item2
->start
? -1 : 1;
137 svn_sort__hash(apr_hash_t
*ht
,
138 int (*comparison_func
)(const svn_sort__item_t
*,
139 const svn_sort__item_t
*),
142 apr_hash_index_t
*hi
;
143 apr_array_header_t
*ary
;
144 svn_boolean_t sorted
;
145 svn_sort__item_t
*prev_item
;
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
));
150 /* loop over hash table and push all keys into the array */
153 for (hi
= apr_hash_first(pool
, ht
); hi
; hi
= apr_hash_next(hi
))
155 svn_sort__item_t
*item
= apr_array_push(ary
);
157 apr_hash_this(hi
, &item
->key
, &item
->klen
, &item
->value
);
159 if (prev_item
== NULL
)
167 sorted
= (comparison_func(prev_item
, item
) < 0);
172 /* quicksort the array if it isn't already sorted. */
174 qsort(ary
->elts
, ary
->nelts
, ary
->elt_size
,
175 (int (*)(const void *, const void *))comparison_func
);
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
190 bsearch_lower_bound(const void *key
,
194 int (*compare_func
)(const void *, const void *))
197 int upper
= nelts
- 1;
199 /* Binary search for the lowest position at which to insert KEY. */
200 while (lower
<= upper
)
202 int try = lower
+ (upper
- lower
) / 2; /* careful to avoid overflow */
203 int cmp
= compare_func((const char *)base
+ try * elt_size
, key
);
210 assert(lower
== upper
+ 1);
216 svn_sort__bsearch_lower_bound(const void *key
,
217 const apr_array_header_t
*array
,
218 int (*compare_func
)(const void *, const void *))
220 return bsearch_lower_bound(key
,
221 array
->elts
, array
->nelts
, array
->elt_size
,
226 svn_sort__array_insert(const void *new_element
,
227 apr_array_header_t
*array
,
230 int elements_to_move
;
233 assert(0 <= insert_index
&& insert_index
<= array
->nelts
);
234 elements_to_move
= array
->nelts
- insert_index
; /* before bumping nelts */
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
);
240 /* Move the elements after INSERT_INDEX along. (When elements_to_move == 0,
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
);
246 /* Copy in the new element */
247 memcpy(new_position
, new_element
, array
->elt_size
);
251 svn_sort__array_delete(apr_array_header_t
*arr
,
253 int elements_to_delete
)
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
)
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
)
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
));
270 /* Delete the last ELEMENTS_TO_DELETE elements. */
271 arr
->nelts
-= elements_to_delete
;
276 svn_sort__array_reverse(apr_array_header_t
*array
,
277 apr_pool_t
*scratch_pool
)
281 if (array
->elt_size
== sizeof(void *))
283 for (i
= 0; i
< array
->nelts
/ 2; i
++)
285 int swap_index
= array
->nelts
- i
- 1;
286 void *tmp
= APR_ARRAY_IDX(array
, i
, void *);
288 APR_ARRAY_IDX(array
, i
, void *) =
289 APR_ARRAY_IDX(array
, swap_index
, void *);
290 APR_ARRAY_IDX(array
, swap_index
, void *) = tmp
;
295 apr_size_t sz
= array
->elt_size
;
296 char *tmp
= apr_palloc(scratch_pool
, sz
);
298 for (i
= 0; i
< array
->nelts
/ 2; i
++)
300 int swap_index
= array
->nelts
- i
- 1;
301 char *x
= array
->elts
+ (sz
* i
);
302 char *y
= array
->elts
+ (sz
* swap_index
);