svn_sorts_private.h revision 362181
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_private.h 24 * @brief all sorts of sorts. 25 */ 26 27 28#ifndef SVN_SORTS_PRIVATE_H 29#define SVN_SORTS_PRIVATE_H 30 31#include "../svn_sorts.h" 32 33#ifdef __cplusplus 34extern "C" { 35#endif /* __cplusplus */ 36 37 38 39/** This structure is used to hold a key/value from a hash table. 40 * @note Private. For use by Subversion's own code only. See issue #1644. 41 */ 42struct svn_sort__item_t { 43 /** pointer to the key */ 44 const void *key; 45 46 /** size of the key */ 47 apr_ssize_t klen; 48 49 /** pointer to the value */ 50 void *value; 51}; 52 53/** Sort @a ht according to its keys, return an @c apr_array_header_t 54 * containing @c svn_sort__item_t structures holding those keys and values 55 * (i.e. for each @c svn_sort__item_t @a item in the returned array, 56 * @a item.key and @a item.size are the hash key, and @a item.value points to 57 * the hash value). 58 * 59 * Storage is shared with the original hash, not copied. 60 * 61 * @a comparison_func should take pointers to two items and return an 62 * integer greater than, equal to, or less than 0, according as the first item 63 * is greater than, equal to, or less than the second. 64 * 65 * @note Private. For use by Subversion's own code only. See issue #1644. 66 * 67 * @note This function and the @c svn_sort__item_t should go over to APR. 68 */ 69apr_array_header_t * 70svn_sort__hash(apr_hash_t *ht, 71 int (*comparison_func)(const svn_sort__item_t *, 72 const svn_sort__item_t *), 73 apr_pool_t *pool); 74 75/* Sort APR array @a array using ordering defined by @a comparison_func. 76 * @a comparison_func is defined as for the C stdlib function qsort(). 77 */ 78void 79svn_sort__array(apr_array_header_t *array, 80 int (*comparison_func)(const void *, 81 const void *)); 82 83/* Return the lowest index at which the element @a *key should be inserted into 84 * the array @a array, according to the ordering defined by @a compare_func. 85 * The array must already be sorted in the ordering defined by @a compare_func. 86 * @a compare_func is defined as for the C stdlib function bsearch(); the 87 * @a key will always passed to it as the second parameter. 88 * 89 * @note Private. For use by Subversion's own code only. 90 */ 91int 92svn_sort__bsearch_lower_bound(const apr_array_header_t *array, 93 const void *key, 94 int (*compare_func)(const void *, const void *)); 95 96/* Find the lowest index at which the element @a *key should be inserted into 97 * the array @a array, according to the ordering defined by @a compare_func. 98 * The array must already be sorted in the ordering defined by @a compare_func. 99 * @a compare_func is defined as for the C stdlib function bsearch(); the 100 * @a key will always passed to it as the second parameter. 101 * 102 * Returns a reference to the array element at the insertion location if 103 * that matches @a key and return NULL otherwise. If you call this function 104 * multiple times for the same array and expect the results to often be 105 * consecutive array elements, provide @a hint. It should be initialized 106 * with -1 for the first call and receives the array index if the returned 107 * element. If the return value is NULL, @a *hint is the location where 108 * the respective key would be inserted. 109 * 110 * @note Private. For use by Subversion's own code only. 111 */ 112void * 113svn_sort__array_lookup(const apr_array_header_t *array, 114 const void *key, 115 int *hint, 116 int (*compare_func)(const void *, const void *)); 117 118 119/* Insert a shallow copy of @a *new_element into the array @a array at the index 120 * @a insert_index, growing the array and shuffling existing elements along to 121 * make room. 122 * 123 * Raise an error if @a insert_index is less than 0 or greater than the length 124 * of the array. 125 * 126 * @note Private. For use by Subversion's own code only. 127 */ 128svn_error_t * 129svn_sort__array_insert2(apr_array_header_t *array, 130 const void *new_element, 131 int insert_index); 132 133 134/* Remove @a elements_to_delete elements starting at @a delete_index from the 135 * array @a arr. 136 * 137 * Raise an error if the indexes to delete extends outside the array bounds 138 * or if @a elements_to_delete is not greater than zero. 139 * 140 * @note Private. For use by Subversion's own code only. 141 */ 142svn_error_t * 143svn_sort__array_delete2(apr_array_header_t *arr, 144 int delete_index, 145 int elements_to_delete); 146 147/* Reverse the order of elements in @a array, in place. 148 * 149 * @note Private. For use by Subversion's own code only. 150 */ 151void 152svn_sort__array_reverse(apr_array_header_t *array, 153 apr_pool_t *scratch_pool); 154 155/** Priority queues. 156 * 157 * @defgroup svn_priority_queue__t Priority Queues 158 * @{ 159 */ 160 161/** 162 * We implement priority queues on top of existing ELEMENTS arrays. They 163 * provide us with memory management and very basic element type information. 164 * 165 * The extraction order is being defined by a comparison function similar 166 * to the ones used with qsort. The first element in the queue is always 167 * on with COMPARISON_FUNC(first,element) <= 0, for all elements in the 168 * queue. 169 */ 170 171/** 172 * Opaque data type for priority queues. 173 */ 174typedef struct svn_priority_queue__t svn_priority_queue__t; 175 176/** 177 * Return a priority queue containing all provided @a elements and prioritize 178 * them according to @a compare_func. 179 * 180 * @note The priority queue will use the existing @a elements array for data 181 * storage. So, you must not manipulate that array while using the queue. 182 * Also, the lifetime of the queue is bound to that of the array. 183 */ 184svn_priority_queue__t * 185svn_priority_queue__create(apr_array_header_t *elements, 186 int (*compare_func)(const void *, const void *)); 187 188/** 189 * Returns the number of elements in the @a queue. 190 */ 191apr_size_t 192svn_priority_queue__size(svn_priority_queue__t *queue); 193 194/** 195 * Returns a reference to the first element in the @a queue. The queue 196 * contents remains unchanged. If the @a queue is empty, NULL will be 197 * returned. 198 */ 199void * 200svn_priority_queue__peek(svn_priority_queue__t *queue); 201 202/** 203 * Notify the @a queue after modifying the first item as returned by 204 * #svn_priority_queue__peek. 205 */ 206void 207svn_priority_queue__update(svn_priority_queue__t *queue); 208 209/** 210 * Remove the first element from the @a queue. This is a no-op for empty 211 * queues. 212 */ 213void 214svn_priority_queue__pop(svn_priority_queue__t *queue); 215 216/** 217 * Append the new @a element to the @a queue. @a element must neither be 218 * NULL nor the first element as returned by #svn_priority_queue__peek. 219 */ 220void 221svn_priority_queue__push(svn_priority_queue__t *queue, const void *element); 222 223/** @} */ 224 225 226#ifdef __cplusplus 227} 228#endif /* __cplusplus */ 229 230#endif /* SVN_SORTS_PRIVATE_H */ 231