subversion/libsvn_subr/sorts.c

   1 /*
   2  * sorts.c:   all sorts of sorts
   3  *
   4  * ====================================================================
   5  * Copyright (c) 2000-2006 CollabNet.  All rights reserved.
   6  *
   7  * This software is licensed as described in the file COPYING, which
   8  * you should have received as part of this distribution.  The terms
   9  * are also available at http://subversion.tigris.org/license-1.html.
  10  * If newer versions of this license are posted there, you may use a
  11  * newer version instead, at your option.
  12  *
  13  * This software consists of voluntary contributions made by many
  14  * individuals.  For exact contribution history, see the revision
  15  * history and logs, available at http://subversion.tigris.org/.
  16  * ====================================================================
  17  */
  18
  19
  20 \f
  21 #include <apr_pools.h>
  22 #include <apr_hash.h>
  23 #include <apr_tables.h>
  24 #include <stdlib.h>       /* for qsort()   */
  25 #include <assert.h>
  26 #include "svn_path.h"
  27 #include "svn_sorts.h"
  28 #include "svn_error.h"
  29
  30
  31 \f
  32 /*** svn_sort__hash() ***/
  33
  34 /* (Should this be a permanent part of APR?)
  35
  36    OK, folks, here's what's going on.  APR hash tables hash on
  37    key/klen objects, and store associated generic values.  They work
  38    great, but they have no ordering.
  39
  40    The point of this exercise is to somehow arrange a hash's keys into
  41    an "ordered list" of some kind -- in this case, a nicely sorted
  42    one.
  43
  44    We're using APR arrays, therefore, because that's what they are:
  45    ordered lists.  However, what "keys" should we put in the array?
  46    Clearly, (const char *) objects aren't general enough.  Or rather,
  47    they're not as general as APR's hash implementation, which stores
  48    (void *)/length as keys.  We don't want to lose this information.
  49
  50    Therefore, it makes sense to store pointers to {void *, size_t}
  51    structures in our array.  No such apr object exists... BUT... if we
  52    can use a new type svn_sort__item_t which contains {char *, size_t, void
  53    *}.  If store these objects in our array, we get the hash value
  54    *for free*.  When looping over the final array, we don't need to
  55    call apr_hash_get().  Major bonus!
  56  */
  57
  58
  59 int
  60 svn_sort_compare_items_as_paths(const svn_sort__item_t *a,
  61                                 const svn_sort__item_t *b)
  62 {
  63   const char *astr, *bstr;
  64
  65   astr = a->key;
  66   bstr = b->key;
  67   assert(astr[a->klen] == '\0');
  68   assert(bstr[b->klen] == '\0');
  69   return svn_path_compare_paths(astr, bstr);
  70 }
  71
  72
  73 int
  74 svn_sort_compare_items_lexically(const svn_sort__item_t *a,
  75                                  const svn_sort__item_t *b)
  76 {
  77   int val;
  78   apr_size_t len;
  79
  80   /* Compare bytes of a's key and b's key up to the common length. */
  81   len = (a->klen < b->klen) ? a->klen : b->klen;
  82   val = memcmp(a->key, b->key, len);
  83   if (val != 0)
  84     return val;
  85
  86   /* They match up until one of them ends; whichever is longer is greater. */
  87   return (a->klen < b->klen) ? -1 : (a->klen > b->klen) ? 1 : 0;
  88 }
  89
  90
  91 int
  92 svn_sort_compare_revisions(const void *a, const void *b)
  93 {
  94   svn_revnum_t a_rev = *(const svn_revnum_t *)a;
  95   svn_revnum_t b_rev = *(const svn_revnum_t *)b;
  96
  97   if (a_rev == b_rev)
  98     return 0;
  99
 100   return a_rev < b_rev ? 1 : -1;
 101 }
 102
 103
 104 int
 105 svn_sort_compare_paths(const void *a, const void *b)
 106 {
 107   const char *item1 = *((const char * const *) a);
 108   const char *item2 = *((const char * const *) b);
 109
 110   return svn_path_compare_paths(item1, item2);
 111 }
 112
 113
 114 int
 115 svn_sort_compare_ranges(const void *a, const void *b)
 116 {
 117   const svn_merge_range_t *item1 = *((const svn_merge_range_t * const *) a);
 118   const svn_merge_range_t *item2 = *((const svn_merge_range_t * const *) b);
 119
 120   if (item1->start == item2->start
 121       && item1->end == item2->end)
 122     return 0;
 123
 124   if (item1->start == item2->start)
 125     return item1->end < item2->end ? -1 : 1;
 126
 127   return item1->start < item2->start ? -1 : 1;
 128 }
 129
 130 apr_array_header_t *
 131 svn_sort__hash(apr_hash_t *ht,
 132                int (*comparison_func)(const svn_sort__item_t *,
 133                                       const svn_sort__item_t *),
 134                apr_pool_t *pool)
 135 {
 136   apr_hash_index_t *hi;
 137   apr_array_header_t *ary;
 138
 139   /* allocate an array with enough elements to hold all the keys. */
 140   ary = apr_array_make(pool, apr_hash_count(ht), sizeof(svn_sort__item_t));
 141
 142   /* loop over hash table and push all keys into the array */
 143   for (hi = apr_hash_first(pool, ht); hi; hi = apr_hash_next(hi))
 144     {
 145       svn_sort__item_t *item = apr_array_push(ary);
 146
 147       apr_hash_this(hi, &item->key, &item->klen, &item->value);
 148     }
 149
 150   /* now quicksort the array.  */
 151   qsort(ary->elts, ary->nelts, ary->elt_size,
 152         (int (*)(const void *, const void *))comparison_func);
 153
 154   return ary;
 155 }