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  * 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;
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 int
86  const svn_sort__item_t *b);
87 
88 
89 /** Compare two @c svn_sort__item_t's, returning an integer greater than,
90  * equal to, or less than 0, according as @a a is greater than, equal to,
91  * or less than @a b according to a lexical key comparison. The keys are
92  * not required to be zero-terminated.
93  */
94 int
96  const svn_sort__item_t *b);
97 
98 /** Compare two @c svn_revnum_t's, returning an integer greater than, equal
99  * to, or less than 0, according as @a b is greater than, equal to, or less
100  * than @a a. Note that this sorts newest revision to oldest (IOW, descending
101  * order).
102  *
103  * This function is compatible for use with qsort().
104  *
105  * This is useful for converting an array of revisions into a sorted
106  * @c apr_array_header_t. You are responsible for detecting, preventing or
107  * removing duplicates.
108  */
109 int
110 svn_sort_compare_revisions(const void *a,
111  const void *b);
112 
113 
114 /**
115  * Compare two @c const char * paths, returning an integer greater
116  * than, equal to, or less than 0, using the same comparison rules as
117  * are used by svn_path_compare_paths().
118  *
119  * This function is compatible for use with qsort().
120  *
121  * @since New in 1.1.
122  */
123 int
124 svn_sort_compare_paths(const void *a,
125  const void *b);
126 
127 /**
128  * Compare two @c svn_merge_range_t *'s, returning an integer greater
129  * than, equal to, or less than 0 if the first range is greater than,
130  * equal to, or less than, the second range.
131  *
132  * Both @c svn_merge_range_t *'s must describe forward merge ranges.
133  *
134  * If @a a and @a b intersect then the range with the lower start revision
135  * is considered the lesser range. If the ranges' start revisions are
136  * equal then the range with the lower end revision is considered the
137  * lesser range.
138  *
139  * @since New in 1.5
140  */
141 int
142 svn_sort_compare_ranges(const void *a,
143  const void *b);
144 
145 /** Sort @a ht according to its keys, return an @c apr_array_header_t
146  * containing @c svn_sort__item_t structures holding those keys and values
147  * (i.e. for each @c svn_sort__item_t @a item in the returned array,
148  * @a item->key and @a item->size are the hash key, and @a item->data points to
149  * the hash value).
150  *
151  * Storage is shared with the original hash, not copied.
152  *
153  * @a comparison_func should take two @c svn_sort__item_t's and return an
154  * integer greater than, equal to, or less than 0, according as the first item
155  * is greater than, equal to, or less than the second.
156  *
157  * @note Private. For use by Subversion's own code only. See issue #1644.
158  *
159  * @note This function and the @c svn_sort__item_t should go over to APR.
160  */
161 apr_array_header_t *
162 svn_sort__hash(apr_hash_t *ht,
163  int (*comparison_func)(const svn_sort__item_t *,
164  const svn_sort__item_t *),
165  apr_pool_t *pool);
166 
167 /* Return the lowest index at which the element *KEY should be inserted into
168  the array ARRAY, according to the ordering defined by COMPARE_FUNC.
169  The array must already be sorted in the ordering defined by COMPARE_FUNC.
170  COMPARE_FUNC is defined as for the C stdlib function bsearch(). */
171 int
172 svn_sort__bsearch_lower_bound(const void *key,
173  const apr_array_header_t *array,
174  int (*compare_func)(const void *, const void *));
175 
176 /* Insert a shallow copy of *NEW_ELEMENT into the array ARRAY at the index
177  INSERT_INDEX, growing the array and shuffling existing elements along to
178  make room. */
179 void
180 svn_sort__array_insert(const void *new_element,
181  apr_array_header_t *array,
182  int insert_index);
183 
184 
185 /* Remove ELEMENTS_TO_DELETE elements starting at DELETE_INDEX from the
186  array ARR. If DELETE_INDEX is not a valid element of ARR,
187  ELEMENTS_TO_DELETE is not greater than zero, or
188  DELETE_INDEX + ELEMENTS_TO_DELETE is greater than ARR->NELTS, then do
189  nothing. */
190 void
191 svn_sort__array_delete(apr_array_header_t *arr,
192  int delete_index,
193  int elements_to_delete);
194 
195 #ifdef __cplusplus
196 }
197 #endif /* __cplusplus */
198 
199 #endif /* SVN_SORTS_H */
apr_ssize_t klen
size of the key
Definition: svn_sorts.h:60
int svn_sort_compare_items_lexically(const svn_sort__item_t *a, const svn_sort__item_t *b)
Compare two svn_sort__item_t&#39;s, returning an integer greater than, equal to, or less than 0...
This structure is used to hold a key/value from a hash table.
Definition: svn_sorts.h:55
int svn_sort_compare_paths(const void *a, const void *b)
Compare two const char * paths, returning an integer greater than, equal to, or less than 0...
const void * key
pointer to the key
Definition: svn_sorts.h:57
int svn_sort_compare_ranges(const void *a, const void *b)
Compare two svn_merge_range_t *&#39;s, returning an integer greater than, equal to, or less than 0 if the...
int svn_sort_compare_revisions(const void *a, const void *b)
Compare two svn_revnum_t&#39;s, returning an integer greater than, equal to, or less than 0...
apr_array_header_t * svn_sort__hash(apr_hash_t *ht, int(*comparison_func)(const svn_sort__item_t *, const svn_sort__item_t *), apr_pool_t *pool)
Sort ht according to its keys, return an apr_array_header_t containing svn_sort__item_t structures ho...
void * value
pointer to the value
Definition: svn_sorts.h:63
int svn_sort_compare_items_as_paths(const svn_sort__item_t *a, const svn_sort__item_t *b)
Compare two svn_sort__item_t&#39;s, returning an integer greater than, equal to, or less than 0...
struct svn_sort__item_t svn_sort__item_t
This structure is used to hold a key/value from a hash table.