/* * sorts.c: all sorts of sorts * * ==================================================================== * Copyright (c) 2000-2006 CollabNet. All rights reserved. * * This software is licensed as described in the file COPYING, which * you should have received as part of this distribution. The terms * are also available at http://subversion.tigris.org/license-1.html. * If newer versions of this license are posted there, you may use a * newer version instead, at your option. * * This software consists of voluntary contributions made by many * individuals. For exact contribution history, see the revision * history and logs, available at http://subversion.tigris.org/. * ==================================================================== */ #include #include #include #include /* for qsort() */ #include #include "svn_path.h" #include "svn_sorts.h" #include "svn_error.h" /*** svn_sort__hash() ***/ /* (Should this be a permanent part of APR?) OK, folks, here's what's going on. APR hash tables hash on key/klen objects, and store associated generic values. They work great, but they have no ordering. The point of this exercise is to somehow arrange a hash's keys into an "ordered list" of some kind -- in this case, a nicely sorted one. We're using APR arrays, therefore, because that's what they are: ordered lists. However, what "keys" should we put in the array? Clearly, (const char *) objects aren't general enough. Or rather, they're not as general as APR's hash implementation, which stores (void *)/length as keys. We don't want to lose this information. Therefore, it makes sense to store pointers to {void *, size_t} structures in our array. No such apr object exists... BUT... if we can use a new type svn_sort__item_t which contains {char *, size_t, void *}. If store these objects in our array, we get the hash value *for free*. When looping over the final array, we don't need to call apr_hash_get(). Major bonus! */ int svn_sort_compare_items_as_paths(const svn_sort__item_t *a, const svn_sort__item_t *b) { const char *astr, *bstr; astr = a->key; bstr = b->key; assert(astr[a->klen] == '\0'); assert(bstr[b->klen] == '\0'); return svn_path_compare_paths(astr, bstr); } int svn_sort_compare_items_lexically(const svn_sort__item_t *a, const svn_sort__item_t *b) { int val; apr_size_t len; /* Compare bytes of a's key and b's key up to the common length. */ len = (a->klen < b->klen) ? a->klen : b->klen; val = memcmp(a->key, b->key, len); if (val != 0) return val; /* They match up until one of them ends; whichever is longer is greater. */ return (a->klen < b->klen) ? -1 : (a->klen > b->klen) ? 1 : 0; } int svn_sort_compare_revisions(const void *a, const void *b) { svn_revnum_t a_rev = *(const svn_revnum_t *)a; svn_revnum_t b_rev = *(const svn_revnum_t *)b; if (a_rev == b_rev) return 0; return a_rev < b_rev ? 1 : -1; } int svn_sort_compare_paths(const void *a, const void *b) { const char *item1 = *((const char * const *) a); const char *item2 = *((const char * const *) b); return svn_path_compare_paths(item1, item2); } int svn_sort_compare_ranges(const void *a, const void *b) { const svn_merge_range_t *item1 = *((const svn_merge_range_t * const *) a); const svn_merge_range_t *item2 = *((const svn_merge_range_t * const *) b); if (item1->start == item2->start && item1->end == item2->end) return 0; if (item1->start == item2->start) return item1->end < item2->end ? -1 : 1; return item1->start < item2->start ? -1 : 1; } apr_array_header_t * svn_sort__hash(apr_hash_t *ht, int (*comparison_func)(const svn_sort__item_t *, const svn_sort__item_t *), apr_pool_t *pool) { apr_hash_index_t *hi; apr_array_header_t *ary; /* allocate an array with enough elements to hold all the keys. */ ary = apr_array_make(pool, apr_hash_count(ht), sizeof(svn_sort__item_t)); /* loop over hash table and push all keys into the array */ for (hi = apr_hash_first(pool, ht); hi; hi = apr_hash_next(hi)) { svn_sort__item_t *item = apr_array_push(ary); apr_hash_this(hi, &item->key, &item->klen, &item->value); } /* now quicksort the array. */ qsort(ary->elts, ary->nelts, ary->elt_size, (int (*)(const void *, const void *))comparison_func); return ary; } /* Return the lowest index at which the element *KEY should be inserted into the array at BASE which has NELTS elements of size ELT_SIZE bytes each, according to the ordering defined by COMPARE_FUNC. 0 <= NELTS <= INT_MAX, 1 <= ELT_SIZE <= INT_MAX. The array must already be sorted in the ordering defined by COMPARE_FUNC. COMPARE_FUNC is defined as for the C stdlib function bsearch(). Note: This function is modeled on bsearch() and on lower_bound() in the C++ STL. */ static int bsearch_lower_bound(const void *key, const void *base, int nelts, int elt_size, int (*compare_func)(const void *, const void *)) { int lower = 0; int upper = nelts - 1; /* Binary search for the lowest position at which to insert KEY. */ while (lower <= upper) { int try = lower + (upper - lower) / 2; /* careful to avoid overflow */ int cmp = compare_func((const char *)base + try * elt_size, key); if (cmp < 0) lower = try + 1; else upper = try - 1; } assert(lower == upper + 1); return lower; } int svn_sort__bsearch_lower_bound(const void *key, apr_array_header_t *array, int (*compare_func)(const void *, const void *)) { return bsearch_lower_bound(key, array->elts, array->nelts, array->elt_size, compare_func); } void svn_sort__array_insert(const void *new_element, apr_array_header_t *array, int insert_index) { int elements_to_move; char *new_position; assert(0 <= insert_index && insert_index <= array->nelts); elements_to_move = array->nelts - insert_index; /* before bumping nelts */ /* Grow the array, allocating a new space at the end. Note: this can reallocate the array's "elts" at a different address. */ apr_array_push(array); /* Move the elements after INSERT_INDEX along. (When elements_to_move == 0, this is a no-op.) */ new_position = (char *)array->elts + insert_index * array->elt_size; memmove(new_position + array->elt_size, new_position, array->elt_size * elements_to_move); /* Copy in the new element */ memcpy(new_position, new_element, array->elt_size); }