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
47extern "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 */
55typedef 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 */
91int
92svn_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 */
101int
102svn_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 */
116int
117svn_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 */
130int
131svn_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 */
148int
149svn_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 */
168apr_array_header_t *
169svn_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 */
181int
182svn_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 */
192void
193svn_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 */
206void
207svn_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 */
215void
216svn_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