1 | /** |
2 | * @copyright |
3 | * ==================================================================== |
4 | * Licensed to the Apache Software Foundation (ASF) under one |
5 | * or more contributor license agreements. See the NOTICE file |
6 | * distributed with this work for additional information |
7 | * regarding copyright ownership. The ASF licenses this file |
8 | * to you under the Apache License, Version 2.0 (the |
9 | * "License"); you may not use this file except in compliance |
10 | * with the License. You may obtain a copy of the License at |
11 | * |
12 | * http://www.apache.org/licenses/LICENSE-2.0 |
13 | * |
14 | * Unless required by applicable law or agreed to in writing, |
15 | * software distributed under the License is distributed on an |
16 | * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
17 | * KIND, either express or implied. See the License for the |
18 | * specific language governing permissions and limitations |
19 | * under the License. |
20 | * ==================================================================== |
21 | * @endcopyright |
22 | * |
23 | * @file svn_sorts.h |
24 | * @brief all sorts of sorts. |
25 | */ |
26 | |
27 | |
28 | #ifndef SVN_SORTS_H |
29 | #define SVN_SORTS_H |
30 | |
31 | #include <apr.h> /* for apr_ssize_t */ |
32 | #include <apr_pools.h> /* for apr_pool_t */ |
33 | #include <apr_tables.h> /* for apr_array_header_t */ |
34 | #include <apr_hash.h> /* for apr_hash_t */ |
35 | |
36 | /* Define a MAX macro if we don't already have one */ |
37 | #ifndef MAX |
38 | #define MAX(a, b) ((a) < (b) ? (b) : (a)) |
39 | #endif |
40 | |
41 | /* Define a MIN macro if we don't already have one */ |
42 | #ifndef MIN |
43 | #define MIN(a, b) ((a) < (b) ? (a) : (b)) |
44 | #endif |
45 | |
46 | #ifdef __cplusplus |
47 | extern "C" { |
48 | #endif /* __cplusplus */ |
49 | |
50 | |
51 | |
52 | /** This structure is used to hold a key/value from a hash table. |
53 | * @note Private. For use by Subversion's own code only. See issue #1644. |
54 | */ |
55 | typedef struct svn_sort__item_t { |
56 | /** pointer to the key */ |
57 | const void *key; |
58 | |
59 | /** size of the key */ |
60 | apr_ssize_t klen; |
61 | |
62 | /** pointer to the value */ |
63 | void *value; |
64 | } svn_sort__item_t; |
65 | |
66 | |
67 | /** Compare two @c svn_sort__item_t's, returning an integer greater than, |
68 | * equal to, or less than 0, according to whether the key of @a a is |
69 | * greater than, equal to, or less than the key of @a b as determined |
70 | * by comparing them with svn_path_compare_paths(). |
71 | * |
72 | * The key strings must be NULL-terminated, even though klen does not |
73 | * include the terminator. |
74 | * |
75 | * This is useful for converting a hash into a sorted |
76 | * @c apr_array_header_t. For example, to convert hash @a hsh to a sorted |
77 | * array, do this: |
78 | * |
79 | * @code |
80 | apr_array_header_t *array; |
81 | array = svn_sort__hash(hsh, svn_sort_compare_items_as_paths, pool); |
82 | @endcode |
83 | * |
84 | * This function works like svn_sort_compare_items_lexically() except that it |
85 | * orders children in subdirectories directly after their parents. This allows |
86 | * using the given ordering for a depth first walk, but at a performance |
87 | * penalty. Code that doesn't need this special behavior for children, e.g. when |
88 | * sorting files at a single directory level should use |
89 | * svn_sort_compare_items_lexically() instead. |
90 | */ |
91 | int |
92 | svn_sort_compare_items_as_paths(const svn_sort__item_t *a, |
93 | const svn_sort__item_t *b); |
94 | |
95 | |
96 | /** Compare two @c svn_sort__item_t's, returning an integer greater than, |
97 | * equal to, or less than 0, according as @a a is greater than, equal to, |
98 | * or less than @a b according to a lexical key comparison. The keys are |
99 | * not required to be zero-terminated. |
100 | */ |
101 | int |
102 | svn_sort_compare_items_lexically(const svn_sort__item_t *a, |
103 | const svn_sort__item_t *b); |
104 | |
105 | /** Compare two @c svn_revnum_t's, returning an integer greater than, equal |
106 | * to, or less than 0, according as @a b is greater than, equal to, or less |
107 | * than @a a. Note that this sorts newest revision to oldest (IOW, descending |
108 | * order). |
109 | * |
110 | * This function is compatible for use with qsort(). |
111 | * |
112 | * This is useful for converting an array of revisions into a sorted |
113 | * @c apr_array_header_t. You are responsible for detecting, preventing or |
114 | * removing duplicates. |
115 | */ |
116 | int |
117 | svn_sort_compare_revisions(const void *a, |
118 | const void *b); |
119 | |
120 | |
121 | /** |
122 | * Compare two @c const char * paths, @a *a and @a *b, returning an |
123 | * integer greater than, equal to, or less than 0, using the same |
124 | * comparison rules as are used by svn_path_compare_paths(). |
125 | * |
126 | * This function is compatible for use with qsort(). |
127 | * |
128 | * @since New in 1.1. |
129 | */ |
130 | int |
131 | svn_sort_compare_paths(const void *a, |
132 | const void *b); |
133 | |
134 | /** |
135 | * Compare two @c svn_merge_range_t *'s, @a *a and @a *b, returning an |
136 | * integer greater than, equal to, or less than 0 if the first range is |
137 | * greater than, equal to, or less than, the second range. |
138 | * |
139 | * Both @c svn_merge_range_t *'s must describe forward merge ranges. |
140 | * |
141 | * If @a *a and @a *b intersect then the range with the lower start revision |
142 | * is considered the lesser range. If the ranges' start revisions are |
143 | * equal then the range with the lower end revision is considered the |
144 | * lesser range. |
145 | * |
146 | * @since New in 1.5 |
147 | */ |
148 | int |
149 | svn_sort_compare_ranges(const void *a, |
150 | const void *b); |
151 | |
152 | /** Sort @a ht according to its keys, return an @c apr_array_header_t |
153 | * containing @c svn_sort__item_t structures holding those keys and values |
154 | * (i.e. for each @c svn_sort__item_t @a item in the returned array, |
155 | * @a item->key and @a item->size are the hash key, and @a item->value points to |
156 | * the hash value). |
157 | * |
158 | * Storage is shared with the original hash, not copied. |
159 | * |
160 | * @a comparison_func should take two @c svn_sort__item_t's and return an |
161 | * integer greater than, equal to, or less than 0, according as the first item |
162 | * is greater than, equal to, or less than the second. |
163 | * |
164 | * @note Private. For use by Subversion's own code only. See issue #1644. |
165 | * |
166 | * @note This function and the @c svn_sort__item_t should go over to APR. |
167 | */ |
168 | apr_array_header_t * |
169 | svn_sort__hash(apr_hash_t *ht, |
170 | int (*comparison_func)(const svn_sort__item_t *, |
171 | const svn_sort__item_t *), |
172 | apr_pool_t *pool); |
173 | |
174 | /* Return the lowest index at which the element @a *key should be inserted into |
175 | * the array @a array, according to the ordering defined by @a compare_func. |
176 | * The array must already be sorted in the ordering defined by @a compare_func. |
177 | * @a compare_func is defined as for the C stdlib function bsearch(). |
178 | * |
179 | * @note Private. For use by Subversion's own code only. |
180 | */ |
181 | int |
182 | svn_sort__bsearch_lower_bound(const void *key, |
183 | const apr_array_header_t *array, |
184 | int (*compare_func)(const void *, const void *)); |
185 | |
186 | /* Insert a shallow copy of @a *new_element into the array @a array at the index |
187 | * @a insert_index, growing the array and shuffling existing elements along to |
188 | * make room. |
189 | * |
190 | * @note Private. For use by Subversion's own code only. |
191 | */ |
192 | void |
193 | svn_sort__array_insert(const void *new_element, |
194 | apr_array_header_t *array, |
195 | int insert_index); |
196 | |
197 | |
198 | /* Remove @a elements_to_delete elements starting at @a delete_index from the |
199 | * array @a arr. If @a delete_index is not a valid element of @a arr, |
200 | * @a elements_to_delete is not greater than zero, or |
201 | * @a delete_index + @a elements_to_delete is greater than @a arr->nelts, |
202 | * then do nothing. |
203 | * |
204 | * @note Private. For use by Subversion's own code only. |
205 | */ |
206 | void |
207 | svn_sort__array_delete(apr_array_header_t *arr, |
208 | int delete_index, |
209 | int elements_to_delete); |
210 | |
211 | /* Reverse the order of elements in @a array, in place. |
212 | * |
213 | * @note Private. For use by Subversion's own code only. |
214 | */ |
215 | void |
216 | svn_sort__array_reverse(apr_array_header_t *array, |
217 | apr_pool_t *scratch_pool); |
218 | |
219 | #ifdef __cplusplus |
220 | } |
221 | #endif /* __cplusplus */ |
222 | |
223 | #endif /* SVN_SORTS_H */ |
224 | |