Subversion 1.6.16

svn_sorts.h

Go to the documentation of this file.
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 */
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines