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