svn commit: r1664127 - in /subversion/branches/move-tracking-2/subversion: include/svn_iter.h libsvn_subr/iter.c

[ju...@apache.org]

Author: julianfoad
Date: Wed Mar  4 19:46:17 2015
New Revision: 1664127

URL: http://svn.apache.org/r1664127
Log:
On the 'move-tracking-2' branch: Provide convenient array and hash iteration
and accessors.

Simpler iteration over an array or a hash, sharing these features:
  - Convenience prioritized over speed.
  - Easy access to this key and this value as iterator member variables.
  - Templated iterator with parameterized element type.
  - Built-in, managed iterpool as an iterator member variable.
  - Iteration in sorted order (optional).

Array of pointers to objects, with
  - Simpler syntax for operations such as make, get, set, push, pop.
  - Efficient duplicators for an array of simple or compound elements.
  - The get and set and iteration functions avoid the need to use the
    non-type-safe APR_ARRAY_IDX. (It does not assert that the sizeof(type)
    matches, let alone (type) itself. Note: When I inserted
    "assert(sizeof(type)==array->elt_size)" in APR's version, the Subversion
    test suite still passed, so that's good.)

Hash table with
  - C-string keys.

TODO:
  - Implement an efficient 'svn_array_extend' method (what's that?)
  - Try making a templated array type with parameterized element type.
  - Add 'svn_hash_this_key/klen/val' and 'svn_hash_this' functions (for
    compatibility)?

* subversion/include/svn_iter.h,
  subversion/libsvn_subr/iter.c
  (svn_iter_t, SVN_ITER_T, SVN_CONST_ITER_T): New.

  (svn_array_t,
   svn_array_make, svn_array_make_n, svn_array_ensure,
   svn_ptr_array_dup_shallow, SVN_PTR_ARRAY_DUP_SIMPLE,
   svn_ptr_array_dup_simple, svn_ptr_array_dup_compound,
   svn_array_get, svn_array_set,
   svn_array_push, svn_array_pop, SVN_ARRAY_PUSH,
   svn_array__first, svn_array__sorted_first, svn_array__next,
   SVN_ARRAY_ITER, SVN_ARRAY_ITER_SORTED,
   SVN_ARRAY_ITER_NO_POOL, SVN_ARRAY_ITER_SORTED_NO_POOL): New.

  (svn_hash__first, svn_hash__sorted_first, svn_hash__next,
   SVN_HASH_ITER, SVN_HASH_ITER_SORTED,
   SVN_HASH_ITER_NO_POOL, SVN_HASH_ITER_SORTED_NO_POOL): New.

  (test_array,
   test_hash): New test functions.

Modified:
    subversion/branches/move-tracking-2/subversion/include/svn_iter.h
    subversion/branches/move-tracking-2/subversion/libsvn_subr/iter.c

Modified: subversion/branches/move-tracking-2/subversion/include/svn_iter.h
URL: http://svn.apache.org/viewvc/subversion/branches/move-tracking-2/subversion/include/svn_iter.h?rev=1664127&r1=1664126&r2=1664127&view=diff
==============================================================================
--- subversion/branches/move-tracking-2/subversion/include/svn_iter.h (original)
+++ subversion/branches/move-tracking-2/subversion/include/svn_iter.h Wed Mar  4 19:46:17 2015
@@ -132,6 +132,276 @@ svn_iter__break(void);
 #define svn_iter_break(pool) return svn_iter__break()
 
 
+/* ====================================================================== */
+
+/** A hash iterator for iterating over an array or a hash table in
+ * its natural order or in sorted order.
+ *
+ * For an array, the @a i and @a val members provide the index and value
+ * of the current item.
+ *
+ * For a hash table, the @c key, @c klen and @c val members provide the
+ * key, key length (in bytes) and value of the current item.
+ *
+ * The @c iterpool member provides a managed iteration pool. It is cleared
+ * at the start of each iteration and destroyed at the end of iteration.
+ */
+typedef struct svn_iter_t
+{
+  /* private: the original hash for unsorted hash iteration */
+  apr_hash_index_t *apr_hi;
+
+  /* private: the original or sorted array for array iteration, or an array
+     of (svn_sort__item_t) hash items for sorted hash iteration */
+  const apr_array_header_t *array;
+
+  /* current element: iteration order index (array only; undefined for hash) */
+  int i;
+  /* current element: key (hash only; undefined for an array) */
+  const char *key;
+  /* current element: key length (hash only; undefined for an array) */
+  apr_ssize_t klen;
+  /* current element: value (array or hash) */
+  void *val;
+
+  /* iteration pool */
+  apr_pool_t *iterpool;
+} svn_iter_t;
+
+/* Type-templated iterator.
+ * ### Layout must be the same as svn_iter_t.
+ */
+#define SVN_ITER_T(element_target_type) \
+  struct { \
+    apr_hash_index_t *apr_hi; \
+    const apr_array_header_t *array; \
+    int i;  /* the current index into ARRAY */ \
+    const char *key; \
+    apr_ssize_t klen; \
+    element_target_type *val; \
+    apr_pool_t *iterpool; \
+  }
+
+/* Type-templated iterator with pointer to 'const' elements.
+ * ### Layout must be the same as svn_iter_t.
+ * ### One of the main uses should be to iterate over a const collection,
+ *     but the iteration implementation doesn't currently distinguish const
+ *     from non-const collections.
+ */
+#define SVN_CONST_ITER_T(element_target_type) \
+  SVN_ITER_T(element_target_type const)
+
+/* ====================================================================== */
+
+/*
+ * An array of pointers to objects.
+ *
+ *   - (void *) element type
+ *   - an element may not be null
+ *     ### TODO: Allow an element to be null.
+ */
+
+/** An array, assumed to be an array of pointers. */
+typedef apr_array_header_t svn_array_t;
+
+/** Return a new, empty array, allocated in @a pool. */
+svn_array_t *
+svn_array_make(apr_pool_t *pool);
+
+/** Return a new, empty array, with initial space for @a elements elements,
+ * allocated in POOL. The current number of elements is set to 0.
+ *
+ * @note This is for performance optimization.
+ */
+svn_array_t *
+svn_array_make_n(apr_pool_t *pool, int elements);
+
+/** Ensure the array has space for at least @a elements elements in total.
+ * The current number of elements is unchanged.
+ *
+ * @note This is for performance optimization.
+ */
+void
+svn_array_ensure(svn_array_t *array, int elements);
+
+/** Shallow-copy an array of pointers to simple objects.
+ *
+ * Return a duplicate in @a pool of the array @a array of pointers.
+ * Do not duplicate the pointed-to objects.
+ */
+apr_array_header_t *
+svn_array_dup_shallow(const apr_array_header_t *array,
+                      apr_pool_t *pool);
+
+/** Deep-copy an array of pointers to simple objects.
+ *
+ * Return a duplicate in @a pool of the array @a array of pointers to
+ * objects of size @a object_size bytes. Duplicate each object bytewise.
+ */
+apr_array_header_t *
+svn_array_dup_simple(const apr_array_header_t *array,
+                     size_t object_size,
+                     apr_pool_t *pool);
+
+/** Deep-copy an array of pointers to simple objects.
+ *
+ * Return a duplicate in @a pool of the array @a array of pointers to
+ * objects of type @a element_type. Duplicate each object bytewise.
+ */
+#define SVN_ARRAY_DUP_SIMPLE(array, element_type, pool) \
+  svn_array_dup_simple(array, sizeof(element_type), pool)
+
+/** Deep-copy an array of pointers to compound objects.
+ *
+ * Return a duplicate in @a pool of the array @a array of pointers to
+ * compound objects. Use @a element_dup_func to duplicate each element.
+ *
+ * ### A more efficient version could be offered, taking a "copy
+ *     constructor" rather than a "dup" function for the elements,
+ *     and using a hybrid of this implementation and the
+ *     svn_array_dup_simple() implementation. (A copy constructor
+ *     constructs a copy at a specified address.)
+ */
+apr_array_header_t *
+svn_array_dup_compound(const apr_array_header_t *array,
+                       void *(*element_dup_func)(const void *, apr_pool_t *),
+                       apr_pool_t *pool);
+
+/** Get element number @a i in @a array. */
+void *
+svn_array_get(const svn_array_t *array,
+              int i);
+
+/** Set element number @a i in @a array to @a val. */
+void
+svn_array_set(svn_array_t *array,
+              int i,
+              const void *val);
+
+/* These pop/push macros are intended to be similar to the APR ones. */
+#define svn_array_pop(array) ((void **)apr_array_pop(array))
+#define svn_array_push(array) ((const void **)apr_array_push(array))
+#define SVN_ARRAY_PUSH(array) (*(svn_array_push(array)))
+
+/** Start iterating over the array @a array, in arbitrary order.
+ *
+ * Return an iterator, or null if there are no items in @a array.
+ */
+svn_iter_t *
+svn_array__first(apr_pool_t *pool,
+                 const svn_array_t *array);
+
+/** Start iterating over the array @a array, in sorted order according to
+ * @a comparison_func.  Return a pointer to the first element, or NULL if
+ * there are no elements.
+ *
+ * It is permissible to change the original array @a array during the
+ * iteration.  Doing so will not affect the sequence of elements returned
+ * by svn_array__next(), as svn_array__sorted_first() takes a snapshot of
+ * pointers to the original keys and values.  The memory in which the
+ * original keys and values of HT are stored must remain available during
+ * the iteration.
+ */
+svn_iter_t *
+svn_array__sorted_first(apr_pool_t *pool,
+                        const svn_array_t *array,
+                        int (*comparison_func)(const void *,
+                                               const void *));
+
+/** Return a pointer to the next element of the array being iterated by
+ * @a i, or NULL if there are no more elements.
+ */
+svn_iter_t *
+svn_array__next(svn_iter_t *i);
+
+/** Iteration over the array @a array.
+ *
+ * To be used in the parentheses of a for() loop.
+ * @a i is the iterator variable declared with "SVN_[CONST_]ITER_T(type) *i;".
+ */
+#define SVN_ARRAY_ITER(i, array, pool) \
+  i = (void *)svn_array__first(pool, array); \
+  i; \
+  i = (void *)svn_array__next((void *)i)
+
+/** Like SVN_ARRAY_ITER but using the array's own pool. */
+#define SVN_ARRAY_ITER_NO_POOL(i, array) \
+  SVN_ARRAY_ITER(i, array, (array)->pool)
+
+/** Like SVN_ARRAY_ITER but iterating over a copy of the array sorted by
+ * @a comparison_func. */
+#define SVN_ARRAY_ITER_SORTED(i, array, comparison_func, pool) \
+  i = (void *)svn_array__sorted_first(pool, array, comparison_func); \
+  i; \
+  i = (void *)svn_array__next((void *)i)
+
+/** Like SVN_ARRAY_SORTED but using the array's own pool. */
+#define SVN_ARRAY_ITER_SORTED_NO_POOL(i, array, comparison_func) \
+  SVN_ARRAY_ITER_SORTED(i, array, comparison_func, (array)->pool)
+
+/* ====================================================================== */
+
+/*
+ * A hash table in which:
+ *   - keys are assumed to be null-terminated (const char *) strings
+ *   - iteration in sorted order is possible
+ *   - an iteration pool is provided
+ */
+
+struct svn_sort__item_t;
+
+/** Start iterating over the hash table @a ht, in arbitrary order.
+ *
+ * Similar to apr_hash_first().
+ */
+svn_iter_t *
+svn_hash__first(apr_pool_t *pool,
+                apr_hash_t *ht);
+
+/** Start iterating over the hash table @a ht, in sorted order according to
+ * @a comparison_func.  Return a pointer to the first element, or NULL if
+ * there are no elements.
+ *
+ * It is permissible to change the original hash table @a ht during the
+ * iteration.  Doing so will not affect the sequence of elements returned
+ * by svn_hash__next(), as svn_hash__sorted_first() takes a snapshot of
+ * pointers to the original keys and values.  The memory in which the
+ * original keys and values of HT are stored must remain available during
+ * the iteration.
+ */
+svn_iter_t *
+svn_hash__sorted_first(apr_pool_t *pool,
+                       apr_hash_t *ht,
+                       int (*comparison_func)(const struct svn_sort__item_t *,
+                                              const struct svn_sort__item_t *));
+
+/** Return a pointer to the next element of the hash table being iterated by
+ * @a hi, or NULL if there are no more elements.
+ */
+svn_iter_t *
+svn_hash__next(svn_iter_t *hi);
+
+/* Type-templated iteration.
+ * To be used in the parentheses of a for() loop.
+ * I is the iterator variable declared with "SVN_[CONST_]ITER_T(type) *i;".
+ */
+#define SVN_HASH_ITER(i, pool, ht) \
+  i = (void *)svn_hash__first(pool, ht); \
+  i; \
+  i = (void *)svn_hash__next((void *)i)
+
+#define SVN_HASH_ITER_NO_POOL(i, ht) \
+  SVN_HASH_ITER(i, apr_hash_pool_get(ht), ht)
+
+#define SVN_HASH_ITER_SORTED(i, ht, comparison_func, pool) \
+  i = (void *)svn_hash__sorted_first(pool, ht, comparison_func); \
+  i; \
+  i = (void *)svn_hash__next((void *)i)
+
+#define SVN_HASH_ITER_SORTED_NO_POOL(i, ht, comparison_func) \
+  SVN_HASH_ITER_SORTED(i, ht, comparison_func, apr_hash_pool_get(ht))
+
+
 #ifdef __cplusplus
 }
 #endif /* __cplusplus */

Modified: subversion/branches/move-tracking-2/subversion/libsvn_subr/iter.c
URL: http://svn.apache.org/viewvc/subversion/branches/move-tracking-2/subversion/libsvn_subr/iter.c?rev=1664127&r1=1664126&r2=1664127&view=diff
==============================================================================
--- subversion/branches/move-tracking-2/subversion/libsvn_subr/iter.c (original)
+++ subversion/branches/move-tracking-2/subversion/libsvn_subr/iter.c Wed Mar  4 19:46:17 2015
@@ -23,6 +23,8 @@
 
 #include "svn_iter.h"
 #include "svn_pools.h"
+#include "svn_hash.h"
+#include "private/svn_sorts_private.h"
 #include "private/svn_dep_compat.h"
 
 #include "svn_error_codes.h"
@@ -209,3 +211,337 @@ void *apr_hash_this_val(apr_hash_index_t
   return val;
 }
 #endif
+
+
+/* ====================================================================== */
+
+svn_array_t *
+svn_array_make(apr_pool_t *pool)
+{
+  return apr_array_make(pool, 0, sizeof(void *));
+}
+
+svn_array_t *
+svn_array_make_n(apr_pool_t *pool, int elements)
+{
+  return apr_array_make(pool, elements, sizeof(void *));
+}
+
+/* ### inefficient implementation */
+void
+svn_array_ensure(svn_array_t *array, int elements)
+{
+  int old_nelts = array->nelts;
+
+  while (array->nalloc < elements)
+    apr_array_push(array);
+  array->nelts = old_nelts;
+}
+
+apr_array_header_t *
+svn_array_dup_shallow(const apr_array_header_t *array,
+                      apr_pool_t *pool)
+{
+  apr_array_header_t *new_array = apr_array_copy(pool, array);
+
+  return new_array;
+}
+
+/* ### This implementation comes from ptr_array_dup(), a local helper
+ *     for svn_rangelist_dup(). */
+apr_array_header_t *
+svn_array_dup_simple(const apr_array_header_t *array,
+                     size_t object_size,
+                     apr_pool_t *pool)
+{
+  apr_array_header_t *new_array = apr_array_make(pool, array->nelts,
+                                                 sizeof(void *));
+
+  /* allocate target range buffer with a single operation */
+  char *copy = apr_palloc(pool, object_size * array->nelts);
+
+  /* for efficiency, directly address source and target reference buffers */
+  void **source = (void **)(array->elts);
+  void **target = (void **)(new_array->elts);
+  int i;
+
+  /* copy ranges iteratively and link them into the target range list */
+  for (i = 0; i < array->nelts; i++)
+    {
+      target[i] = &copy[i * object_size];
+      memcpy(target[i], source[i], object_size);
+    }
+  new_array->nelts = array->nelts;
+
+  return new_array;
+}
+
+apr_array_header_t *
+svn_array_dup_compound(const apr_array_header_t *array,
+                       void *(*element_dup_func)(const void *, apr_pool_t *),
+                       apr_pool_t *pool)
+{
+  apr_array_header_t *new_array = apr_array_make(pool, array->nelts,
+                                                 sizeof(void *));
+  int i;
+
+  for (i = 0; i < array->nelts; i++)
+    {
+      svn_array_set(new_array, i,
+                    element_dup_func(svn_array_get(array, i), pool));
+    }
+  new_array->nelts = array->nelts;
+
+  return new_array;
+}
+
+void *
+svn_array_get(const svn_array_t *array,
+              int i)
+{
+  return APR_ARRAY_IDX(array, i, void *);
+}
+
+void
+svn_array_set(svn_array_t *array,
+              int i,
+              const void *value)
+{
+  APR_ARRAY_IDX(array, i, const void *) = value;
+}
+
+/* Clean up internal state of IT. */
+static void
+iter_cleanup(svn_iter_t *it)
+{
+  if (it->iterpool)
+    svn_pool_destroy(it->iterpool);
+#ifdef SVN_DEBUG
+  memset(it, 0, sizeof(*it));
+#endif
+}
+
+svn_iter_t *
+svn_array__first(apr_pool_t *pool,
+                 const svn_array_t *array)
+{
+  svn_iter_t *it;
+
+  if (! array->nelts)
+    return NULL;
+
+  it = apr_pcalloc(pool, sizeof(*it));
+  it->array = array;
+  it->i = 0;
+  it->val = svn_array_get(array, 0);
+  it->iterpool = svn_pool_create(pool);
+  return it;
+}
+
+svn_iter_t *
+svn_array__sorted_first(apr_pool_t *pool,
+                        const svn_array_t *array,
+                        int (*comparison_func)(const void *,
+                                               const void *))
+{
+  svn_array_t *new_array = svn_array_dup_shallow(array, pool);
+
+  svn_sort__array(new_array, comparison_func);
+  return svn_array__first(pool, new_array);
+}
+
+svn_iter_t *
+svn_array__next(svn_iter_t *it)
+{
+  it->i++;
+  if (it->i >= it->array->nelts)
+    {
+      iter_cleanup(it);
+      return NULL;
+    }
+
+  it->val = svn_array_get(it->array, it->i);
+  svn_pool_clear(it->iterpool);
+  return it;
+}
+
+
+/* ====================================================================== */
+
+/* Exercise the svn_array API. */
+
+static void *test_dup_cstring(const void *s, apr_pool_t *pool)
+{
+  return apr_pstrdup(pool, s);
+}
+
+static void
+test_array(apr_pool_t *pool)
+{
+  svn_array_t *a = svn_array_make(pool);
+  const char *str;
+  const svn_array_t *b;
+
+  /* get and set and push */
+  SVN_ARRAY_PUSH(a) = "hello";
+  str = svn_array_get(a, 0);
+  svn_array_set(a, 1, str);
+  SVN_ARRAY_PUSH(a) = str;
+
+  /* duplication */
+  b = svn_array_dup_shallow(a, pool);
+  b = SVN_ARRAY_DUP_SIMPLE(b, char *, pool);
+  b = svn_array_dup_compound(b, test_dup_cstring, pool);
+
+  /* iteration with svn_array__[sorted_]first() */
+  {
+    svn_iter_t *i;
+
+    for (i = svn_array__first(pool, a); i; i = svn_array__next(i))
+      printf("%s", (char *)i->val);
+    for (i = svn_array__sorted_first(pool, b, svn_sort_compare_paths);
+         i; i = svn_array__next(i))
+      printf("%s", (char *)i->val);
+  }
+
+  /* iteration, typed, with SVN_ARRAY_ITER[_SORTED]() */
+  {
+    SVN_ITER_T(char) *ia;
+    SVN_CONST_ITER_T(char) *ib;
+
+    for (SVN_ARRAY_ITER(ia, a, pool))
+      printf("%s", ia->val);
+    for (SVN_ARRAY_ITER_SORTED(ib, b, svn_sort_compare_paths, pool))
+      printf("%s", ib->val);
+  }
+}
+
+
+/* ====================================================================== */
+
+svn_iter_t *
+svn_hash__first(apr_pool_t *pool,
+                apr_hash_t *ht)
+{
+  svn_iter_t *hi = apr_pcalloc(pool, sizeof(*hi));
+
+  hi->array = NULL;
+
+  hi->apr_hi = apr_hash_first(pool, ht);
+  if (! hi->apr_hi)
+    return NULL;
+
+  apr_hash_this(hi->apr_hi, (const void **)&hi->key, &hi->klen, &hi->val);
+  hi->iterpool = svn_pool_create(pool);
+  return hi;
+}
+
+svn_iter_t *
+svn_hash__sorted_first(apr_pool_t *pool,
+                       apr_hash_t *ht,
+                       int (*comparison_func)(const svn_sort__item_t *,
+                                              const svn_sort__item_t *))
+{
+  svn_iter_t *hi = apr_palloc(pool, sizeof(*hi));
+
+  hi->apr_hi = NULL;
+
+  if (apr_hash_count(ht) == 0)
+    return NULL;
+
+  hi->array = svn_sort__hash(ht, comparison_func, pool);
+  hi->i = 0;
+  hi->key = APR_ARRAY_IDX(hi->array, hi->i, svn_sort__item_t).key;
+  hi->klen = APR_ARRAY_IDX(hi->array, hi->i, svn_sort__item_t).klen;
+  hi->val = APR_ARRAY_IDX(hi->array, hi->i, svn_sort__item_t).value;
+  hi->iterpool = svn_pool_create(pool);
+  return hi;
+}
+
+svn_iter_t *
+svn_hash__next(svn_iter_t *hi)
+{
+  if (hi->apr_hi)  /* is an unsorted iterator */
+    {
+      hi->apr_hi = apr_hash_next(hi->apr_hi);
+      if (! hi->apr_hi)
+        {
+          iter_cleanup(hi);
+          return NULL;
+        }
+      apr_hash_this(hi->apr_hi, (const void **)&hi->key, &hi->klen, &hi->val);
+    }
+
+  if (hi->array)  /* is a sorted iterator */
+    {
+      hi->i++;
+      if (hi->i >= hi->array->nelts)
+        {
+          iter_cleanup(hi);
+          return NULL;
+        }
+      hi->key = APR_ARRAY_IDX(hi->array, hi->i, svn_sort__item_t).key;
+      hi->klen = APR_ARRAY_IDX(hi->array, hi->i, svn_sort__item_t).klen;
+      hi->val = APR_ARRAY_IDX(hi->array, hi->i, svn_sort__item_t).value;
+    }
+
+  svn_pool_clear(hi->iterpool);
+  return hi;
+}
+
+
+/* ====================================================================== */
+
+/* Exercise the svn_hash API. */
+static void
+test_hash(apr_pool_t *pool)
+{
+  apr_hash_t *hash = apr_hash_make(pool);
+  svn_iter_t *hi;
+  SVN_ITER_T(const char) *it;
+
+  svn_hash_sets(hash, "K1", "V1");
+  svn_hash_sets(hash, "Key2", "Value2");
+  svn_hash_sets(hash, "Key three", "Value three");
+  svn_hash_sets(hash, "Fourth key", "Fourth value");
+
+  printf("Hash iteration, unsorted:");
+  for (hi = svn_hash__first(pool, hash); hi; hi = svn_hash__next(hi))
+    {
+      const char *k = apr_psprintf(hi->iterpool, "[%s]", hi->key);
+      apr_ssize_t l = hi->klen;
+      const char *v = hi->val;
+
+      printf("  key[%d]: %-20s val: %s\n", (int)l, k, v);
+    }
+
+  printf("Hash iteration, sorted:");
+  for (hi = svn_hash__sorted_first(pool, hash, svn_sort_compare_items_lexically);
+       hi; hi = svn_hash__next(hi))
+    {
+      const char *k = apr_psprintf(hi->iterpool, "[%s]", hi->key);
+      apr_ssize_t l = hi->klen;
+      const char *v = hi->val;
+
+      printf("  key[%d]: %-20s val: %s\n", (int)l, k, v);
+    }
+
+  printf("Hash iteration, typed, unsorted:");
+  for (SVN_HASH_ITER(it, pool, hash))
+    {
+      printf("  key[%d]: %-20s val: %s\n",
+             (int)it->klen,
+             apr_psprintf(it->iterpool, "[%s]", it->key),
+             it->val);
+    }
+
+  printf("Hash iteration, typed, sorted:");
+  for (SVN_HASH_ITER_SORTED(it, hash, svn_sort_compare_items_lexically, pool))
+    {
+      printf("  key[%d]: %-20s val: %s\n",
+             (int)it->klen,
+             apr_psprintf(it->iterpool, "[%s]", it->key),
+             it->val);
+    }
+
+}