You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by st...@apache.org on 2013/07/29 00:00:44 UTC
svn commit: r1507859 - in /subversion/branches/fsx: ./
subversion/include/svn_sorts.h subversion/libsvn_subr/sorts.c
Author: stefan2
Date: Sun Jul 28 22:00:44 2013
New Revision: 1507859
URL: http://svn.apache.org/r1507859
Log:
On the fsx branch: Merge the patches pertaining to the new
svn__priority_queue_* private API (r1460579,1462904,1467382 )
from /branches/fsfs-format7. There were no conflicts.
Modified:
subversion/branches/fsx/ (props changed)
subversion/branches/fsx/subversion/include/svn_sorts.h
subversion/branches/fsx/subversion/libsvn_subr/sorts.c
Propchange: subversion/branches/fsx/
------------------------------------------------------------------------------
Merged /subversion/branches/fsfs-format7:r1460579,1462904,1467382
Modified: subversion/branches/fsx/subversion/include/svn_sorts.h
URL: http://svn.apache.org/viewvc/subversion/branches/fsx/subversion/include/svn_sorts.h?rev=1507859&r1=1507858&r2=1507859&view=diff
==============================================================================
--- subversion/branches/fsx/subversion/include/svn_sorts.h (original)
+++ subversion/branches/fsx/subversion/include/svn_sorts.h Sun Jul 28 22:00:44 2013
@@ -216,6 +216,78 @@ 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,
+ void *element);
+
+/** @} */
+
+
#ifdef __cplusplus
}
#endif /* __cplusplus */
Modified: subversion/branches/fsx/subversion/libsvn_subr/sorts.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsx/subversion/libsvn_subr/sorts.c?rev=1507859&r1=1507858&r2=1507859&view=diff
==============================================================================
--- subversion/branches/fsx/subversion/libsvn_subr/sorts.c (original)
+++ subversion/branches/fsx/subversion/libsvn_subr/sorts.c Sun Jul 28 22:00:44 2013
@@ -307,3 +307,148 @@ svn_sort__array_reverse(apr_array_header
}
}
}
+
+/* Our priority queue data structure:
+ * Simply remember the constructor parameters.
+ */
+struct svn__priority_queue_t
+{
+ /* the queue elements, ordered as a heap according to COMPARE_FUNC */
+ apr_array_header_t *elements;
+
+ /* predicate used to order the heap */
+ int (*compare_func)(const void *, const void *);
+};
+
+/* Return TRUE, if heap element number LHS in QUEUE is smaller than element
+ * number RHS according to QUEUE->COMPARE_FUNC
+ */
+static int
+heap_is_less(svn__priority_queue_t *queue,
+ apr_size_t lhs,
+ apr_size_t rhs)
+{
+ char *lhs_value = queue->elements->elts + lhs * queue->elements->elt_size;
+ char *rhs_value = queue->elements->elts + rhs * queue->elements->elt_size;
+
+ assert(lhs < queue->elements->nelts);
+ assert(rhs < queue->elements->nelts);
+ return queue->compare_func((void *)lhs_value, (void *)rhs_value) < 0;
+}
+
+/* Exchange elements number LHS and RHS in QUEUE.
+ */
+static void
+heap_swap(svn__priority_queue_t *queue,
+ apr_size_t lhs,
+ apr_size_t rhs)
+{
+ int i;
+ char *lhs_value = queue->elements->elts + lhs * queue->elements->elt_size;
+ char *rhs_value = queue->elements->elts + rhs * queue->elements->elt_size;
+
+ for (i = 0; i < queue->elements->elt_size; ++i)
+ {
+ char temp = lhs_value[i];
+ lhs_value[i] = rhs_value[i];
+ rhs_value[i] = temp;
+ }
+}
+
+/* Move element number IDX to lower indexes until the heap criterion is
+ * fulfilled again.
+ */
+static void
+heap_bubble_down(svn__priority_queue_t *queue,
+ int idx)
+{
+ while (idx > 0 && heap_is_less(queue, idx, (idx - 1) / 2))
+ {
+ heap_swap(queue, idx, (idx - 1) / 2);
+ idx = (idx - 1) / 2;
+ }
+}
+
+/* Move element number IDX to higher indexes until the heap criterion is
+ * fulfilled again.
+ */
+static void
+heap_bubble_up(svn__priority_queue_t *queue,
+ int idx)
+{
+ while (2 * idx + 2 < queue->elements->nelts)
+ {
+ int child = heap_is_less(queue, 2 * idx + 1, 2 * idx + 2)
+ ? 2 * idx + 1
+ : 2 * idx + 2;
+
+ if (heap_is_less(queue, idx, child))
+ return;
+
+ heap_swap(queue, idx, child);
+ idx = child;
+ }
+
+ if ( 2 * idx + 1 < queue->elements->nelts
+ && heap_is_less(queue, 2 * idx + 1, idx))
+ heap_swap(queue, 2 * idx + 1, idx);
+}
+
+svn__priority_queue_t *
+svn__priority_queue_create(apr_array_header_t *elements,
+ int (*compare_func)(const void *, const void *))
+{
+ int i;
+
+ svn__priority_queue_t *queue = apr_pcalloc(elements->pool, sizeof(*queue));
+ queue->elements = elements;
+ queue->compare_func = compare_func;
+
+ for (i = elements->nelts / 2; i >= 0; --i)
+ heap_bubble_up(queue, i);
+
+ return queue;
+}
+
+apr_size_t
+svn__priority_queue_size(svn__priority_queue_t *queue)
+{
+ return queue->elements->nelts;
+}
+
+void *
+svn__priority_queue_peek(svn__priority_queue_t *queue)
+{
+ return queue->elements->nelts ? queue->elements->elts : NULL;
+}
+
+void
+svn__priority_queue_update(svn__priority_queue_t *queue)
+{
+ heap_bubble_up(queue, 0);
+}
+
+void
+svn__priority_queue_pop(svn__priority_queue_t *queue)
+{
+ if (queue->elements->nelts)
+ {
+ memcpy(queue->elements->elts,
+ queue->elements->elts + (queue->elements->nelts - 1)
+ * queue->elements->elt_size,
+ queue->elements->elt_size);
+ --queue->elements->nelts;
+ heap_bubble_up(queue, 0);
+ }
+}
+
+void
+svn__priority_queue_push(svn__priority_queue_t *queue,
+ void *element)
+{
+ /* we cannot duplicate elements due to potential array re-allocs */
+ assert(element && element != queue->elements->elts);
+
+ memcpy(apr_array_push(queue->elements), element, queue->elements->elt_size);
+ heap_bubble_down(queue, queue->elements->nelts - 1);
+}
\ No newline at end of file