Subversion
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
svn_sorts.h
Go to the documentation of this file.
1 /**
2  * @copyright
3  * ====================================================================
4  * Copyright (c) 2000-2004, 2008 CollabNet. All rights reserved.
5  *
6  * This software is licensed as described in the file COPYING, which
7  * you should have received as part of this distribution. The terms
8  * are also available at http://subversion.tigris.org/license-1.html.
9  * If newer versions of this license are posted there, you may use a
10  * newer version instead, at your option.
11  *
12  * This software consists of voluntary contributions made by many
13  * individuals. For exact contribution history, see the revision
14  * history and logs, available at http://subversion.tigris.org/.
15  * ====================================================================
16  * @endcopyright
17  *
18  * @file svn_sorts.h
19  * @brief all sorts of sorts.
20  */
21 
22 
23 #ifndef SVN_SORTS_H
24 #define SVN_SORTS_H
25 
26 #include <apr.h> /* for apr_ssize_t */
27 #include <apr_pools.h> /* for apr_pool_t */
28 #include <apr_tables.h> /* for apr_array_header_t */
29 #include <apr_hash.h> /* for apr_hash_t */
30 
31 /* Define a MAX macro if we don't already have one */
32 #ifndef MAX
33 #define MAX(a, b) ((a) < (b) ? (b) : (a))
34 #endif
35 
36 /* Define a MIN macro if we don't already have one */
37 #ifndef MIN
38 #define MIN(a, b) ((a) < (b) ? (a) : (b))
39 #endif
40 
41 #ifdef __cplusplus
42 extern "C" {
43 #endif /* __cplusplus */
44 
45 
46 
47 /** This structure is used to hold a key/value from a hash table.
48  * @note Private. For use by Subversion's own code only. See issue #1644.
49  */
50 typedef struct svn_sort__item_t {
51  /** pointer to the key */
52  const void *key;
53 
54  /** size of the key */
55  apr_ssize_t klen;
56 
57  /** pointer to the value */
58  void *value;
60 
61 
62 /** Compare two @c svn_sort__item_t's, returning an integer greater than,
63  * equal to, or less than 0, according to whether the key of @a a is
64  * greater than, equal to, or less than the key of @a b as determined
65  * by comparing them with svn_path_compare_paths().
66  *
67  * The key strings must be NULL-terminated, even though klen does not
68  * include the terminator.
69  *
70  * This is useful for converting a hash into a sorted
71  * @c apr_array_header_t. For example, to convert hash @a hsh to a sorted
72  * array, do this:
73  *
74  * @verbatim
75  apr_array_header_t *hdr;
76  hdr = svn_sort__hash (hsh, @c svn_sort_compare_items_as_paths, pool);
77  @endverbatim
78  */
79 int
81  const svn_sort__item_t *b);
82 
83 
84 /** Compare two @c svn_sort__item_t's, returning an integer greater than,
85  * equal to, or less than 0, according as @a a is greater than, equal to,
86  * or less than @a b according to a lexical key comparison. The keys are
87  * not required to be zero-terminated.
88  */
89 int
91  const svn_sort__item_t *b);
92 
93 /** Compare two @c svn_revnum_t's, returning an integer greater than, equal
94  * to, or less than 0, according as @a b is greater than, equal to, or less
95  * than @a a. Note that this sorts newest revision to oldest (IOW, descending
96  * order).
97  *
98  * This function is compatible for use with qsort().
99  *
100  * This is useful for converting an array of revisions into a sorted
101  * @c apr_array_header_t. You are responsible for detecting, preventing or
102  * removing duplicates.
103  */
104 int
105 svn_sort_compare_revisions(const void *a,
106  const void *b);
107 
108 
109 /**
110  * Compare two @c const char * paths, returning an integer greater
111  * than, equal to, or less than 0, using the same comparison rules as
112  * are used by svn_path_compare_paths().
113  *
114  * This function is compatible for use with qsort().
115  *
116  * @since New in 1.1.
117  */
118 int
119 svn_sort_compare_paths(const void *a,
120  const void *b);
121 
122 /**
123  * Compare two @c svn_merge_range_t *'s, returning an integer greater
124  * than, equal to, or less than 0 if the first range is greater than,
125  * equal to, or less than, the second range.
126  *
127  * Both @c svn_merge_range_t *'s must describe forward merge ranges.
128  *
129  * If @a a and @a b intersect then the range with the lower start revision
130  * is considered the lesser range. If the ranges' start revisions are
131  * equal then the range with the lower end revision is considered the
132  * lesser range.
133  *
134  * @since New in 1.5
135  */
136 int
137 svn_sort_compare_ranges(const void *a,
138  const void *b);
139 
140 /** Sort @a ht according to its keys, return an @c apr_array_header_t
141  * containing @c svn_sort__item_t structures holding those keys and values
142  * (i.e. for each @c svn_sort__item_t @a item in the returned array,
143  * @a item->key and @a item->size are the hash key, and @a item->data points to
144  * the hash value).
145  *
146  * Storage is shared with the original hash, not copied.
147  *
148  * @a comparison_func should take two @c svn_sort__item_t's and return an
149  * integer greater than, equal to, or less than 0, according as the first item
150  * is greater than, equal to, or less than the second.
151  *
152  * @note Private. For use by Subversion's own code only. See issue #1644.
153  *
154  * @note This function and the @c svn_sort__item_t should go over to APR.
155  */
156 apr_array_header_t *
157 svn_sort__hash(apr_hash_t *ht,
158  int (*comparison_func)(const svn_sort__item_t *,
159  const svn_sort__item_t *),
160  apr_pool_t *pool);
161 
162 /* Return the lowest index at which the element *KEY should be inserted into
163  the array ARRAY, according to the ordering defined by COMPARE_FUNC.
164  The array must already be sorted in the ordering defined by COMPARE_FUNC.
165  COMPARE_FUNC is defined as for the C stdlib function bsearch(). */
166 int
167 svn_sort__bsearch_lower_bound(const void *key,
168  apr_array_header_t *array,
169  int (*compare_func)(const void *, const void *));
170 
171 /* Insert a shallow copy of *NEW_ELEMENT into the array ARRAY at the index
172  INSERT_INDEX, growing the array and shuffling existing elements along to
173  make room. */
174 void
175 svn_sort__array_insert(const void *new_element,
176  apr_array_header_t *array,
177  int insert_index);
178 
179 
180 #ifdef __cplusplus
181 }
182 #endif /* __cplusplus */
183 
184 #endif /* SVN_SORTS_H */