00001 /** 00002 * @copyright 00003 * ==================================================================== 00004 * Licensed to the Apache Software Foundation (ASF) under one 00005 * or more contributor license agreements. See the NOTICE file 00006 * distributed with this work for additional information 00007 * regarding copyright ownership. The ASF licenses this file 00008 * to you under the Apache License, Version 2.0 (the 00009 * "License"); you may not use this file except in compliance 00010 * with the License. You may obtain a copy of the License at 00011 * 00012 * http://www.apache.org/licenses/LICENSE-2.0 00013 * 00014 * Unless required by applicable law or agreed to in writing, 00015 * software distributed under the License is distributed on an 00016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 00017 * KIND, either express or implied. See the License for the 00018 * specific language governing permissions and limitations 00019 * under the License. 00020 * ==================================================================== 00021 * @endcopyright 00022 * 00023 * @file svn_sorts.h 00024 * @brief all sorts of sorts. 00025 */ 00026 00027 00028 #ifndef SVN_SORTS_H 00029 #define SVN_SORTS_H 00030 00031 #include <apr.h> /* for apr_ssize_t */ 00032 #include <apr_pools.h> /* for apr_pool_t */ 00033 #include <apr_tables.h> /* for apr_array_header_t */ 00034 #include <apr_hash.h> /* for apr_hash_t */ 00035 00036 /* Define a MAX macro if we don't already have one */ 00037 #ifndef MAX 00038 #define MAX(a, b) ((a) < (b) ? (b) : (a)) 00039 #endif 00040 00041 /* Define a MIN macro if we don't already have one */ 00042 #ifndef MIN 00043 #define MIN(a, b) ((a) < (b) ? (a) : (b)) 00044 #endif 00045 00046 #ifdef __cplusplus 00047 extern "C" { 00048 #endif /* __cplusplus */ 00049 00050 00051 00052 /** This structure is used to hold a key/value from a hash table. 00053 * @note Private. For use by Subversion's own code only. See issue #1644. 00054 */ 00055 typedef struct svn_sort__item_t { 00056 /** pointer to the key */ 00057 const void *key; 00058 00059 /** size of the key */ 00060 apr_ssize_t klen; 00061 00062 /** pointer to the value */ 00063 void *value; 00064 } svn_sort__item_t; 00065 00066 00067 /** Compare two @c svn_sort__item_t's, returning an integer greater than, 00068 * equal to, or less than 0, according to whether the key of @a a is 00069 * greater than, equal to, or less than the key of @a b as determined 00070 * by comparing them with svn_path_compare_paths(). 00071 * 00072 * The key strings must be NULL-terminated, even though klen does not 00073 * include the terminator. 00074 * 00075 * This is useful for converting a hash into a sorted 00076 * @c apr_array_header_t. For example, to convert hash @a hsh to a sorted 00077 * array, do this: 00078 * 00079 * @code 00080 apr_array_header_t *array; 00081 array = svn_sort__hash(hsh, svn_sort_compare_items_as_paths, pool); 00082 @endcode 00083 * 00084 * This function works like svn_sort_compare_items_lexically() except that it 00085 * orders children in subdirectories directly after their parents. This allows 00086 * using the given ordering for a depth first walk, but at a performance 00087 * penalty. Code that doesn't need this special behavior for children, e.g. when 00088 * sorting files at a single directory level should use 00089 * svn_sort_compare_items_lexically() instead. 00090 */ 00091 int 00092 svn_sort_compare_items_as_paths(const svn_sort__item_t *a, 00093 const svn_sort__item_t *b); 00094 00095 00096 /** Compare two @c svn_sort__item_t's, returning an integer greater than, 00097 * equal to, or less than 0, according as @a a is greater than, equal to, 00098 * or less than @a b according to a lexical key comparison. The keys are 00099 * not required to be zero-terminated. 00100 */ 00101 int 00102 svn_sort_compare_items_lexically(const svn_sort__item_t *a, 00103 const svn_sort__item_t *b); 00104 00105 /** Compare two @c svn_revnum_t's, returning an integer greater than, equal 00106 * to, or less than 0, according as @a b is greater than, equal to, or less 00107 * than @a a. Note that this sorts newest revision to oldest (IOW, descending 00108 * order). 00109 * 00110 * This function is compatible for use with qsort(). 00111 * 00112 * This is useful for converting an array of revisions into a sorted 00113 * @c apr_array_header_t. You are responsible for detecting, preventing or 00114 * removing duplicates. 00115 */ 00116 int 00117 svn_sort_compare_revisions(const void *a, 00118 const void *b); 00119 00120 00121 /** 00122 * Compare two @c const char * paths, @a *a and @a *b, returning an 00123 * integer greater than, equal to, or less than 0, using the same 00124 * comparison rules as are used by svn_path_compare_paths(). 00125 * 00126 * This function is compatible for use with qsort(). 00127 * 00128 * @since New in 1.1. 00129 */ 00130 int 00131 svn_sort_compare_paths(const void *a, 00132 const void *b); 00133 00134 /** 00135 * Compare two @c svn_merge_range_t *'s, @a *a and @a *b, returning an 00136 * integer greater than, equal to, or less than 0 if the first range is 00137 * greater than, equal to, or less than, the second range. 00138 * 00139 * Both @c svn_merge_range_t *'s must describe forward merge ranges. 00140 * 00141 * If @a *a and @a *b intersect then the range with the lower start revision 00142 * is considered the lesser range. If the ranges' start revisions are 00143 * equal then the range with the lower end revision is considered the 00144 * lesser range. 00145 * 00146 * @since New in 1.5 00147 */ 00148 int 00149 svn_sort_compare_ranges(const void *a, 00150 const void *b); 00151 00152 /** Sort @a ht according to its keys, return an @c apr_array_header_t 00153 * containing @c svn_sort__item_t structures holding those keys and values 00154 * (i.e. for each @c svn_sort__item_t @a item in the returned array, 00155 * @a item->key and @a item->size are the hash key, and @a item->value points to 00156 * the hash value). 00157 * 00158 * Storage is shared with the original hash, not copied. 00159 * 00160 * @a comparison_func should take two @c svn_sort__item_t's and return an 00161 * integer greater than, equal to, or less than 0, according as the first item 00162 * is greater than, equal to, or less than the second. 00163 * 00164 * @note Private. For use by Subversion's own code only. See issue #1644. 00165 * 00166 * @note This function and the @c svn_sort__item_t should go over to APR. 00167 */ 00168 apr_array_header_t * 00169 svn_sort__hash(apr_hash_t *ht, 00170 int (*comparison_func)(const svn_sort__item_t *, 00171 const svn_sort__item_t *), 00172 apr_pool_t *pool); 00173 00174 /* Return the lowest index at which the element @a *key should be inserted into 00175 * the array @a array, according to the ordering defined by @a compare_func. 00176 * The array must already be sorted in the ordering defined by @a compare_func. 00177 * @a compare_func is defined as for the C stdlib function bsearch(). 00178 * 00179 * @note Private. For use by Subversion's own code only. 00180 */ 00181 int 00182 svn_sort__bsearch_lower_bound(const void *key, 00183 const apr_array_header_t *array, 00184 int (*compare_func)(const void *, const void *)); 00185 00186 /* Insert a shallow copy of @a *new_element into the array @a array at the index 00187 * @a insert_index, growing the array and shuffling existing elements along to 00188 * make room. 00189 * 00190 * @note Private. For use by Subversion's own code only. 00191 */ 00192 void 00193 svn_sort__array_insert(const void *new_element, 00194 apr_array_header_t *array, 00195 int insert_index); 00196 00197 00198 /* Remove @a elements_to_delete elements starting at @a delete_index from the 00199 * array @a arr. If @a delete_index is not a valid element of @a arr, 00200 * @a elements_to_delete is not greater than zero, or 00201 * @a delete_index + @a elements_to_delete is greater than @a arr->nelts, 00202 * then do nothing. 00203 * 00204 * @note Private. For use by Subversion's own code only. 00205 */ 00206 void 00207 svn_sort__array_delete(apr_array_header_t *arr, 00208 int delete_index, 00209 int elements_to_delete); 00210 00211 /* Reverse the order of elements in @a array, in place. 00212 * 00213 * @note Private. For use by Subversion's own code only. 00214 */ 00215 void 00216 svn_sort__array_reverse(apr_array_header_t *array, 00217 apr_pool_t *scratch_pool); 00218 00219 #ifdef __cplusplus 00220 } 00221 #endif /* __cplusplus */ 00222 00223 #endif /* SVN_SORTS_H */