diff options
Diffstat (limited to 'subversion/include/private/svn_sorts_private.h')
| -rw-r--r-- | subversion/include/private/svn_sorts_private.h | 227 |
1 files changed, 227 insertions, 0 deletions
diff --git a/subversion/include/private/svn_sorts_private.h b/subversion/include/private/svn_sorts_private.h new file mode 100644 index 0000000..c358513 --- /dev/null +++ b/subversion/include/private/svn_sorts_private.h @@ -0,0 +1,227 @@ +/** + * @copyright + * ==================================================================== + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + * ==================================================================== + * @endcopyright + * + * @file svn_sorts_private.h + * @brief all sorts of sorts. + */ + + +#ifndef SVN_SORTS_PRIVATE_H +#define SVN_SORTS_PRIVATE_H + +#include "../svn_sorts.h" + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + + + +/** This structure is used to hold a key/value from a hash table. + * @note Private. For use by Subversion's own code only. See issue #1644. + */ +struct svn_sort__item_t { + /** pointer to the key */ + const void *key; + + /** size of the key */ + apr_ssize_t klen; + + /** pointer to the value */ + void *value; +}; + +/** Sort @a ht according to its keys, return an @c apr_array_header_t + * containing @c svn_sort__item_t structures holding those keys and values + * (i.e. for each @c svn_sort__item_t @a item in the returned array, + * @a item->key and @a item->size are the hash key, and @a item->value points to + * the hash value). + * + * Storage is shared with the original hash, not copied. + * + * @a comparison_func should take two @c svn_sort__item_t's and return an + * integer greater than, equal to, or less than 0, according as the first item + * is greater than, equal to, or less than the second. + * + * @note Private. For use by Subversion's own code only. See issue #1644. + * + * @note This function and the @c svn_sort__item_t should go over to APR. + */ +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 APR array @a array using ordering defined by @a comparison_func. + * @a comparison_func is defined as for the C stdlib function qsort(). + */ +void +svn_sort__array(apr_array_header_t *array, + int (*comparison_func)(const void *, + const void *)); + +/* Return the lowest index at which the element @a *key should be inserted into + * the array @a array, according to the ordering defined by @a compare_func. + * The array must already be sorted in the ordering defined by @a compare_func. + * @a compare_func is defined as for the C stdlib function bsearch(); the + * @a key will always passed to it as the second parameter. + * + * @note Private. For use by Subversion's own code only. + */ +int +svn_sort__bsearch_lower_bound(const apr_array_header_t *array, + const void *key, + int (*compare_func)(const void *, const void *)); + +/* Find the lowest index at which the element @a *key should be inserted into + * the array @a array, according to the ordering defined by @a compare_func. + * The array must already be sorted in the ordering defined by @a compare_func. + * @a compare_func is defined as for the C stdlib function bsearch(); the + * @a key will always passed to it as the second parameter. + * + * Returns a reference to the array element at the insertion location if + * that matches @a key and return NULL otherwise. If you call this function + * multiple times for the same array and expect the results to often be + * consecutive array elements, provide @a hint. It should be initialized + * with -1 for the first call and receives the array index if the returned + * element. If the return value is NULL, @a *hint is the location where + * the respective key would be inserted. + * + * @note Private. For use by Subversion's own code only. + */ +void * +svn_sort__array_lookup(const apr_array_header_t *array, + const void *key, + int *hint, + int (*compare_func)(const void *, const void *)); + + +/* Insert a shallow copy of @a *new_element into the array @a array at the index + * @a insert_index, growing the array and shuffling existing elements along to + * make room. + * + * @note Private. For use by Subversion's own code only. + */ +void +svn_sort__array_insert(apr_array_header_t *array, + const void *new_element, + int insert_index); + + +/* Remove @a elements_to_delete elements starting at @a delete_index from the + * array @a arr. If @a delete_index is not a valid element of @a arr, + * @a elements_to_delete is not greater than zero, or + * @a delete_index + @a elements_to_delete is greater than @a arr->nelts, + * then do nothing. + * + * @note Private. For use by Subversion's own code only. + */ +void +svn_sort__array_delete(apr_array_header_t *arr, + int delete_index, + int elements_to_delete); + +/* Reverse the order of elements in @a array, in place. + * + * @note Private. For use by Subversion's own code only. + */ +void +svn_sort__array_reverse(apr_array_header_t *array, + apr_pool_t *scratch_pool); + +/** Priority queues. + * + * @defgroup svn_priority_queue__t Priority Queues + * @{ + */ + +/** + * We implement priority queues on top of existing ELEMENTS arrays. They + * provide us with memory management and very basic element type information. + * + * The extraction order is being defined by a comparison function similar + * to the ones used with qsort. The first element in the queue is always + * on with COMPARISON_FUNC(first,element) <= 0, for all elements in the + * queue. + */ + +/** + * Opaque data type for priority queues. + */ +typedef struct svn_priority_queue__t svn_priority_queue__t; + +/** + * Return a priority queue containing all provided @a elements and prioritize + * them according to @a compare_func. + * + * @note The priority queue will use the existing @a elements array for data + * storage. So, you must not manipulate that array while using the queue. + * Also, the lifetime of the queue is bound to that of the array. + */ +svn_priority_queue__t * +svn_priority_queue__create(apr_array_header_t *elements, + int (*compare_func)(const void *, const void *)); + +/** + * Returns the number of elements in the @a queue. + */ +apr_size_t +svn_priority_queue__size(svn_priority_queue__t *queue); + +/** + * Returns a reference to the first element in the @a queue. The queue + * contents remains unchanged. If the @a queue is empty, #NULL will be + * returned. + */ +void * +svn_priority_queue__peek(svn_priority_queue__t *queue); + +/** + * Notify the @a queue after modifying the first item as returned by + * #svn_priority_queue__peek. + */ +void +svn_priority_queue__update(svn_priority_queue__t *queue); + +/** + * Remove the first element from the @a queue. This is a no-op for empty + * queues. + */ +void +svn_priority_queue__pop(svn_priority_queue__t *queue); + +/** + * Append the new @a element to the @a queue. @a element must neither be + * #NULL nor the first element as returned by #svn_priority_queue__peek. + */ +void +svn_priority_queue__push(svn_priority_queue__t *queue, const void *element); + +/** @} */ + + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* SVN_SORTS_PRIVATE_H */ |