svn commit: r1460579 - in /subversion/branches/fsfs-format7/subversion: include/svn_sorts.h libsvn_subr/sorts.c

[st...@apache.org]

Author: stefan2
Date: Mon Mar 25 10:06:48 2013
New Revision: 1460579

URL: http://svn.apache.org/r1460579
Log:
On the fsfs-format7 branch: Introduce a libsvn_subr API for priority queues.
We will soon use it in the new FSFS pack code.

* subversion/include/svn_sorts.h
  (svn__priority_queue_t): declare new data type
  (svn__priority_queue_create,
   svn__priority_queue_size,
   svn__priority_queue_peek,
   svn__priority_queue_pop,
   svn__priority_queue_push): declare new API functions

* subversion/libsvn_subr/sorts.c
  (svn__priority_queue_t): define data type
  (heap_is_less,
   heap_swap,
   heap_bubble_down,
   heap_bubble_up): new utility functions
  (svn__priority_queue_create,
   svn__priority_queue_size,
   svn__priority_queue_peek,
   svn__priority_queue_pop,
   svn__priority_queue_push): implement new API

Modified:
    subversion/branches/fsfs-format7/subversion/include/svn_sorts.h
    subversion/branches/fsfs-format7/subversion/libsvn_subr/sorts.c

Modified: subversion/branches/fsfs-format7/subversion/include/svn_sorts.h
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/include/svn_sorts.h?rev=1460579&r1=1460578&r2=1460579&view=diff
==============================================================================
--- subversion/branches/fsfs-format7/subversion/include/svn_sorts.h (original)
+++ subversion/branches/fsfs-format7/subversion/include/svn_sorts.h Mon Mar 25 10:06:48 2013
@@ -214,6 +214,71 @@ 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);
+
+/**
+ * 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/fsfs-format7/subversion/libsvn_subr/sorts.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/libsvn_subr/sorts.c?rev=1460579&r1=1460578&r2=1460579&view=diff
==============================================================================
--- subversion/branches/fsfs-format7/subversion/libsvn_subr/sorts.c (original)
+++ subversion/branches/fsfs-format7/subversion/libsvn_subr/sorts.c Mon Mar 25 10:06:48 2013
@@ -306,3 +306,142 @@ 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 - 1; i > 0; --i)
+    heap_bubble_down(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_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