contrib/subversion/subversion/include/private/svn_sorts_private.h

   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
  34 extern "C" {
  35 #endif /* __cplusplus */
  36
  37 \f
  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  */
  42 struct 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 two @c svn_sort__item_t's 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  */
  69 apr_array_header_t *
  70 svn_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  */
  78 void
  79 svn_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  */
  91 int
  92 svn_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  */
 112 void *
 113 svn_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  * @note Private. For use by Subversion's own code only.
 124  */
 125 void
 126 svn_sort__array_insert(apr_array_header_t *array,
 127                        const void *new_element,
 128                        int insert_index);
 129
 130
 131 /* Remove @a elements_to_delete elements starting at @a delete_index from the
 132  * array @a arr. If @a delete_index is not a valid element of @a arr,
 133  * @a elements_to_delete is not greater than zero, or
 134  * @a delete_index + @a elements_to_delete is greater than @a arr->nelts,
 135  * then do nothing.
 136  *
 137  * @note Private. For use by Subversion's own code only.
 138  */
 139 void
 140 svn_sort__array_delete(apr_array_header_t *arr,
 141                        int delete_index,
 142                        int elements_to_delete);
 143
 144 /* Reverse the order of elements in @a array, in place.
 145  *
 146  * @note Private. For use by Subversion's own code only.
 147  */
 148 void
 149 svn_sort__array_reverse(apr_array_header_t *array,
 150                         apr_pool_t *scratch_pool);
 151
 152 /** Priority queues.
 153  *
 154  * @defgroup svn_priority_queue__t Priority Queues
 155  * @{
 156  */
 157
 158 /**
 159  * We implement priority queues on top of existing ELEMENTS arrays.  They
 160  * provide us with memory management and very basic element type information.
 161  *
 162  * The extraction order is being defined by a comparison function similar
 163  * to the ones used with qsort.  The first element in the queue is always
 164  * on with COMPARISON_FUNC(first,element) <= 0, for all elements in the
 165  * queue.
 166  */
 167
 168 /**
 169  * Opaque data type for priority queues.
 170  */
 171 typedef struct svn_priority_queue__t svn_priority_queue__t;
 172
 173 /**
 174  * Return a priority queue containing all provided @a elements and prioritize
 175  * them according to @a compare_func.
 176  *
 177  * @note The priority queue will use the existing @a elements array for data
 178  * storage.  So, you must not manipulate that array while using the queue.
 179  * Also, the lifetime of the queue is bound to that of the array.
 180  */
 181 svn_priority_queue__t *
 182 svn_priority_queue__create(apr_array_header_t *elements,
 183                            int (*compare_func)(const void *, const void *));
 184
 185 /**
 186  * Returns the number of elements in the @a queue.
 187  */
 188 apr_size_t
 189 svn_priority_queue__size(svn_priority_queue__t *queue);
 190
 191 /**
 192  * Returns a reference to the first element in the @a queue.  The queue
 193  * contents remains unchanged.  If the @a queue is empty, #NULL will be
 194  * returned.
 195  */
 196 void *
 197 svn_priority_queue__peek(svn_priority_queue__t *queue);
 198
 199 /**
 200  * Notify the @a queue after modifying the first item as returned by
 201  * #svn_priority_queue__peek.
 202  */
 203 void
 204 svn_priority_queue__update(svn_priority_queue__t *queue);
 205
 206 /**
 207  * Remove the first element from the @a queue.  This is a no-op for empty
 208  * queues.
 209  */
 210 void
 211 svn_priority_queue__pop(svn_priority_queue__t *queue);
 212
 213 /**
 214  * Append the new @a element to the @a queue.  @a element must neither be
 215  * #NULL nor the first element as returned by #svn_priority_queue__peek.
 216  */
 217 void
 218 svn_priority_queue__push(svn_priority_queue__t *queue, const void *element);
 219
 220 /** @} */
 221
 222
 223 #ifdef __cplusplus
 224 }
 225 #endif /* __cplusplus */
 226
 227 #endif /* SVN_SORTS_PRIVATE_H */