Subversion 1.6.16
|
00001 /** 00002 * @copyright 00003 * ==================================================================== 00004 * Copyright (c) 2000-2004, 2008 CollabNet. All rights reserved. 00005 * 00006 * This software is licensed as described in the file COPYING, which 00007 * you should have received as part of this distribution. The terms 00008 * are also available at http://subversion.tigris.org/license-1.html. 00009 * If newer versions of this license are posted there, you may use a 00010 * newer version instead, at your option. 00011 * 00012 * This software consists of voluntary contributions made by many 00013 * individuals. For exact contribution history, see the revision 00014 * history and logs, available at http://subversion.tigris.org/. 00015 * ==================================================================== 00016 * @endcopyright 00017 * 00018 * @file svn_sorts.h 00019 * @brief all sorts of sorts. 00020 */ 00021 00022 00023 #ifndef SVN_SORTS_H 00024 #define SVN_SORTS_H 00025 00026 #include <apr.h> /* for apr_ssize_t */ 00027 #include <apr_pools.h> /* for apr_pool_t */ 00028 #include <apr_tables.h> /* for apr_array_header_t */ 00029 #include <apr_hash.h> /* for apr_hash_t */ 00030 00031 /* Define a MAX macro if we don't already have one */ 00032 #ifndef MAX 00033 #define MAX(a, b) ((a) < (b) ? (b) : (a)) 00034 #endif 00035 00036 /* Define a MIN macro if we don't already have one */ 00037 #ifndef MIN 00038 #define MIN(a, b) ((a) < (b) ? (a) : (b)) 00039 #endif 00040 00041 #ifdef __cplusplus 00042 extern "C" { 00043 #endif /* __cplusplus */ 00044 00045 00046 00047 /** This structure is used to hold a key/value from a hash table. 00048 * @note Private. For use by Subversion's own code only. See issue #1644. 00049 */ 00050 typedef struct svn_sort__item_t { 00051 /** pointer to the key */ 00052 const void *key; 00053 00054 /** size of the key */ 00055 apr_ssize_t klen; 00056 00057 /** pointer to the value */ 00058 void *value; 00059 } svn_sort__item_t; 00060 00061 00062 /** Compare two @c svn_sort__item_t's, returning an integer greater than, 00063 * equal to, or less than 0, according to whether the key of @a a is 00064 * greater than, equal to, or less than the key of @a b as determined 00065 * by comparing them with svn_path_compare_paths(). 00066 * 00067 * The key strings must be NULL-terminated, even though klen does not 00068 * include the terminator. 00069 * 00070 * This is useful for converting a hash into a sorted 00071 * @c apr_array_header_t. For example, to convert hash @a hsh to a sorted 00072 * array, do this: 00073 * 00074 * @verbatim 00075 apr_array_header_t *hdr; 00076 hdr = svn_sort__hash (hsh, @c svn_sort_compare_items_as_paths, pool); 00077 @endverbatim 00078 */ 00079 int 00080 svn_sort_compare_items_as_paths(const svn_sort__item_t *a, 00081 const svn_sort__item_t *b); 00082 00083 00084 /** Compare two @c svn_sort__item_t's, returning an integer greater than, 00085 * equal to, or less than 0, according as @a a is greater than, equal to, 00086 * or less than @a b according to a lexical key comparison. The keys are 00087 * not required to be zero-terminated. 00088 */ 00089 int 00090 svn_sort_compare_items_lexically(const svn_sort__item_t *a, 00091 const svn_sort__item_t *b); 00092 00093 /** Compare two @c svn_revnum_t's, returning an integer greater than, equal 00094 * to, or less than 0, according as @a b is greater than, equal to, or less 00095 * than @a a. Note that this sorts newest revision to oldest (IOW, descending 00096 * order). 00097 * 00098 * This function is compatible for use with qsort(). 00099 * 00100 * This is useful for converting an array of revisions into a sorted 00101 * @c apr_array_header_t. You are responsible for detecting, preventing or 00102 * removing duplicates. 00103 */ 00104 int 00105 svn_sort_compare_revisions(const void *a, 00106 const void *b); 00107 00108 00109 /** 00110 * Compare two @c const char * paths, returning an integer greater 00111 * than, equal to, or less than 0, using the same comparison rules as 00112 * are used by svn_path_compare_paths(). 00113 * 00114 * This function is compatible for use with qsort(). 00115 * 00116 * @since New in 1.1. 00117 */ 00118 int 00119 svn_sort_compare_paths(const void *a, 00120 const void *b); 00121 00122 /** 00123 * Compare two @c svn_merge_range_t *'s, returning an integer greater 00124 * than, equal to, or less than 0 if the first range is greater than, 00125 * equal to, or less than, the second range. 00126 * 00127 * Both @c svn_merge_range_t *'s must describe forward merge ranges. 00128 * 00129 * If @a a and @a b intersect then the range with the lower start revision 00130 * is considered the lesser range. If the ranges' start revisions are 00131 * equal then the range with the lower end revision is considered the 00132 * lesser range. 00133 * 00134 * @since New in 1.5 00135 */ 00136 int 00137 svn_sort_compare_ranges(const void *a, 00138 const void *b); 00139 00140 /** Sort @a ht according to its keys, return an @c apr_array_header_t 00141 * containing @c svn_sort__item_t structures holding those keys and values 00142 * (i.e. for each @c svn_sort__item_t @a item in the returned array, 00143 * @a item->key and @a item->size are the hash key, and @a item->data points to 00144 * the hash value). 00145 * 00146 * Storage is shared with the original hash, not copied. 00147 * 00148 * @a comparison_func should take two @c svn_sort__item_t's and return an 00149 * integer greater than, equal to, or less than 0, according as the first item 00150 * is greater than, equal to, or less than the second. 00151 * 00152 * @note Private. For use by Subversion's own code only. See issue #1644. 00153 * 00154 * @note This function and the @c svn_sort__item_t should go over to APR. 00155 */ 00156 apr_array_header_t * 00157 svn_sort__hash(apr_hash_t *ht, 00158 int (*comparison_func)(const svn_sort__item_t *, 00159 const svn_sort__item_t *), 00160 apr_pool_t *pool); 00161 00162 /* Return the lowest index at which the element *KEY should be inserted into 00163 the array ARRAY, according to the ordering defined by COMPARE_FUNC. 00164 The array must already be sorted in the ordering defined by COMPARE_FUNC. 00165 COMPARE_FUNC is defined as for the C stdlib function bsearch(). */ 00166 int 00167 svn_sort__bsearch_lower_bound(const void *key, 00168 apr_array_header_t *array, 00169 int (*compare_func)(const void *, const void *)); 00170 00171 /* Insert a shallow copy of *NEW_ELEMENT into the array ARRAY at the index 00172 INSERT_INDEX, growing the array and shuffling existing elements along to 00173 make room. */ 00174 void 00175 svn_sort__array_insert(const void *new_element, 00176 apr_array_header_t *array, 00177 int insert_index); 00178 00179 00180 #ifdef __cplusplus 00181 } 00182 #endif /* __cplusplus */ 00183 00184 #endif /* SVN_SORTS_H */