subversion/libsvn_subr/sorts.c - subversion - Git at Google

 /*
  * sorts.c:   all sorts of sorts
  *
  * ====================================================================
  *    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.
  * ====================================================================
  */


 #include <apr_pools.h>
 #include <apr_hash.h>
 #include <apr_tables.h>
 #include <stdlib.h>       /* for qsort()   */
 #include <assert.h>
 #include "svn_hash.h"
 #include "svn_path.h"
 #include "svn_sorts.h"
 #include "svn_error.h"


 /*** svn_sort__hash() ***/

 /* (Should this be a permanent part of APR?)

    OK, folks, here's what's going on.  APR hash tables hash on
    key/klen objects, and store associated generic values.  They work
    great, but they have no ordering.

    The point of this exercise is to somehow arrange a hash's keys into
    an "ordered list" of some kind -- in this case, a nicely sorted
    one.

    We're using APR arrays, therefore, because that's what they are:
    ordered lists.  However, what "keys" should we put in the array?
    Clearly, (const char *) objects aren't general enough.  Or rather,
    they're not as general as APR's hash implementation, which stores
    (void *)/length as keys.  We don't want to lose this information.

    Therefore, it makes sense to store pointers to {void *, size_t}
    structures in our array.  No such apr object exists... BUT... if we
    can use a new type svn_sort__item_t which contains {char *, size_t, void
    *}.  If store these objects in our array, we get the hash value
    *for free*.  When looping over the final array, we don't need to
    call apr_hash_get().  Major bonus!
  */


 int
 svn_sort_compare_items_as_paths(const svn_sort__item_t *a,
                                 const svn_sort__item_t *b)
 {
   const char *astr, *bstr;

   astr = a->key;
   bstr = b->key;
   assert(astr[a->klen] == '\0');
   assert(bstr[b->klen] == '\0');
   return svn_path_compare_paths(astr, bstr);
 }


 int
 svn_sort_compare_items_lexically(const svn_sort__item_t *a,
                                  const svn_sort__item_t *b)
 {
   int val;
   apr_size_t len;

   /* Compare bytes of a's key and b's key up to the common length. */
   len = (a->klen < b->klen) ? a->klen : b->klen;
   val = memcmp(a->key, b->key, len);
   if (val != 0)
     return val;

   /* They match up until one of them ends; whichever is longer is greater. */
   return (a->klen < b->klen) ? -1 : (a->klen > b->klen) ? 1 : 0;
 }


 int
 svn_sort_compare_revisions(const void *a, const void *b)
 {
   svn_revnum_t a_rev = *(const svn_revnum_t *)a;
   svn_revnum_t b_rev = *(const svn_revnum_t *)b;

   if (a_rev == b_rev)
     return 0;

   return a_rev < b_rev ? 1 : -1;
 }


 int
 svn_sort_compare_paths(const void *a, const void *b)
 {
   const char *item1 = *((const char * const *) a);
   const char *item2 = *((const char * const *) b);

   return svn_path_compare_paths(item1, item2);
 }


 int
 svn_sort_compare_ranges(const void *a, const void *b)
 {
   const svn_merge_range_t *item1 = *((const svn_merge_range_t * const *) a);
   const svn_merge_range_t *item2 = *((const svn_merge_range_t * const *) b);

   if (item1->start == item2->start
       && item1->end == item2->end)
     return 0;

   if (item1->start == item2->start)
     return item1->end < item2->end ? -1 : 1;

   return item1->start < item2->start ? -1 : 1;
 }

 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)
 {
   apr_hash_index_t *hi;
   apr_array_header_t *ary;
   svn_boolean_t sorted;
   svn_sort__item_t *prev_item;

   /* allocate an array with enough elements to hold all the keys. */
   ary = apr_array_make(pool, apr_hash_count(ht), sizeof(svn_sort__item_t));

   /* loop over hash table and push all keys into the array */
   sorted = TRUE;
   prev_item = NULL;
   for (hi = apr_hash_first(pool, ht); hi; hi = apr_hash_next(hi))
     {
       svn_sort__item_t *item = apr_array_push(ary);

       apr_hash_this(hi, &item->key, &item->klen, &item->value);

       if (prev_item == NULL)
         {
           prev_item = item;
           continue;
         }

       if (sorted)
         {
           sorted = (comparison_func(prev_item, item) < 0);
           prev_item = item;
         }
     }

   /* quicksort the array if it isn't already sorted.  */
   if (!sorted)
     qsort(ary->elts, ary->nelts, ary->elt_size,
           (int (*)(const void *, const void *))comparison_func);

   return ary;
 }

 /* Return the lowest index at which the element *KEY should be inserted into
    the array at BASE which has NELTS elements of size ELT_SIZE bytes each,
    according to the ordering defined by COMPARE_FUNC.
    0 <= NELTS <= INT_MAX, 1 <= ELT_SIZE <= INT_MAX.
    The array must already be sorted in the ordering defined by COMPARE_FUNC.
    COMPARE_FUNC is defined as for the C stdlib function bsearch().
    Note: This function is modeled on bsearch() and on lower_bound() in the
    C++ STL.
  */
 static int
 bsearch_lower_bound(const void *key,
                     const void *base,
                     int nelts,
                     int elt_size,
                     int (*compare_func)(const void *, const void *))
 {
   int lower = 0;
   int upper = nelts - 1;

   /* Binary search for the lowest position at which to insert KEY. */
   while (lower <= upper)
     {
       int try = lower + (upper - lower) / 2;  /* careful to avoid overflow */
       int cmp = compare_func((const char *)base + try * elt_size, key);

       if (cmp < 0)
         lower = try + 1;
       else
         upper = try - 1;
     }
   assert(lower == upper + 1);

   return lower;
 }

 int
 svn_sort__bsearch_lower_bound(const void *key,
                               const apr_array_header_t *array,
                               int (*compare_func)(const void *, const void *))
 {
   return bsearch_lower_bound(key,
                              array->elts, array->nelts, array->elt_size,
                              compare_func);
 }

 void
 svn_sort__array_insert(const void *new_element,
                        apr_array_header_t *array,
                        int insert_index)
 {
   int elements_to_move;
   char *new_position;

   assert(0 <= insert_index && insert_index <= array->nelts);
   elements_to_move = array->nelts - insert_index;  /* before bumping nelts */

   /* Grow the array, allocating a new space at the end. Note: this can
      reallocate the array's "elts" at a different address. */
   apr_array_push(array);

   /* Move the elements after INSERT_INDEX along. (When elements_to_move == 0,
      this is a no-op.) */
   new_position = (char *)array->elts + insert_index * array->elt_size;
   memmove(new_position + array->elt_size, new_position,
           array->elt_size * elements_to_move);

   /* Copy in the new element */
   memcpy(new_position, new_element, array->elt_size);
 }

 void
 svn_sort__array_delete(apr_array_header_t *arr,
                        int delete_index,
                        int elements_to_delete)
 {
   /* Do we have a valid index and are there enough elements? */
   if (delete_index >= 0
       && delete_index < arr->nelts
       && elements_to_delete > 0
       && (elements_to_delete + delete_index) <= arr->nelts)
     {
       /* If we are not deleting a block of elements that extends to the end
          of the array, then we need to move the remaining elements to keep
          the array contiguous. */
       if ((elements_to_delete + delete_index) < arr->nelts)
         memmove(
           arr->elts + arr->elt_size * delete_index,
           arr->elts + (arr->elt_size * (delete_index + elements_to_delete)),
           arr->elt_size * (arr->nelts - elements_to_delete - delete_index));

       /* Delete the last ELEMENTS_TO_DELETE elements. */
       arr->nelts -= elements_to_delete;
     }
 }

 void
 svn_sort__array_reverse(apr_array_header_t *array,
                         apr_pool_t *scratch_pool)
 {
   int i;

   if (array->elt_size == sizeof(void *))
     {
       for (i = 0; i < array->nelts / 2; i++)
         {
           int swap_index = array->nelts - i - 1;
           void *tmp = APR_ARRAY_IDX(array, i, void *);

           APR_ARRAY_IDX(array, i, void *) =
             APR_ARRAY_IDX(array, swap_index, void *);
           APR_ARRAY_IDX(array, swap_index, void *) = tmp;
         }
     }
   else
     {
       apr_size_t sz = array->elt_size;
       char *tmp = apr_palloc(scratch_pool, sz);

       for (i = 0; i < array->nelts / 2; i++)
         {
           int swap_index = array->nelts - i - 1;
           char *x = array->elts + (sz * i);
           char *y = array->elts + (sz * swap_index);

           memcpy(tmp, x, sz);
           memcpy(x, y, sz);
           memcpy(y, tmp, sz);
         }
     }
 }
	/*
	* sorts.c: all sorts of sorts
	*
	* ====================================================================
	* 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.
	* ====================================================================
	*/



	#include <apr_pools.h>
	#include <apr_hash.h>
	#include <apr_tables.h>
	#include <stdlib.h> /* for qsort() */
	#include <assert.h>
	#include "svn_hash.h"
	#include "svn_path.h"
	#include "svn_sorts.h"
	#include "svn_error.h"



	/* svn_sort__hash() */

	/* (Should this be a permanent part of APR?)

	OK, folks, here's what's going on. APR hash tables hash on
	key/klen objects, and store associated generic values. They work
	great, but they have no ordering.

	The point of this exercise is to somehow arrange a hash's keys into
	an "ordered list" of some kind -- in this case, a nicely sorted
	one.

	We're using APR arrays, therefore, because that's what they are:
	ordered lists. However, what "keys" should we put in the array?
	Clearly, (const char *) objects aren't general enough. Or rather,
	they're not as general as APR's hash implementation, which stores
	(void *)/length as keys. We don't want to lose this information.

	Therefore, it makes sense to store pointers to {void *, size_t}
	structures in our array. No such apr object exists... BUT... if we
	can use a new type svn_sort__item_t which contains {char *, size_t, void
	*}. If store these objects in our array, we get the hash value
	for free. When looping over the final array, we don't need to
	call apr_hash_get(). Major bonus!
	*/


	int
	svn_sort_compare_items_as_paths(const svn_sort__item_t *a,
	const svn_sort__item_t *b)
	{
	const char astr, bstr;

	astr = a->key;
	bstr = b->key;
	assert(astr[a->klen] == '\0');
	assert(bstr[b->klen] == '\0');
	return svn_path_compare_paths(astr, bstr);
	}


	int
	svn_sort_compare_items_lexically(const svn_sort__item_t *a,
	const svn_sort__item_t *b)
	{
	int val;
	apr_size_t len;

	/* Compare bytes of a's key and b's key up to the common length. */
	len = (a->klen < b->klen) ? a->klen : b->klen;
	val = memcmp(a->key, b->key, len);
	if (val != 0)
	return val;

	/* They match up until one of them ends; whichever is longer is greater. */
	return (a->klen < b->klen) ? -1 : (a->klen > b->klen) ? 1 : 0;
	}


	int
	svn_sort_compare_revisions(const void a, const void b)
	{
	svn_revnum_t a_rev = (const svn_revnum_t )a;
	svn_revnum_t b_rev = (const svn_revnum_t )b;

	if (a_rev == b_rev)
	return 0;

	return a_rev < b_rev ? 1 : -1;
	}


	int
	svn_sort_compare_paths(const void a, const void b)
	{
	const char item1 = ((const char * const *) a);
	const char item2 = ((const char * const *) b);

	return svn_path_compare_paths(item1, item2);
	}


	int
	svn_sort_compare_ranges(const void a, const void b)
	{
	const svn_merge_range_t item1 = ((const svn_merge_range_t * const *) a);
	const svn_merge_range_t item2 = ((const svn_merge_range_t * const *) b);

	if (item1->start == item2->start
	&& item1->end == item2->end)
	return 0;

	if (item1->start == item2->start)
	return item1->end < item2->end ? -1 : 1;

	return item1->start < item2->start ? -1 : 1;
	}

	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)
	{
	apr_hash_index_t *hi;
	apr_array_header_t *ary;
	svn_boolean_t sorted;
	svn_sort__item_t *prev_item;

	/* allocate an array with enough elements to hold all the keys. */
	ary = apr_array_make(pool, apr_hash_count(ht), sizeof(svn_sort__item_t));

	/* loop over hash table and push all keys into the array */
	sorted = TRUE;
	prev_item = NULL;
	for (hi = apr_hash_first(pool, ht); hi; hi = apr_hash_next(hi))
	{
	svn_sort__item_t *item = apr_array_push(ary);

	apr_hash_this(hi, &item->key, &item->klen, &item->value);

	if (prev_item == NULL)
	{
	prev_item = item;
	continue;
	}

	if (sorted)
	{
	sorted = (comparison_func(prev_item, item) < 0);
	prev_item = item;
	}
	}

	/* quicksort the array if it isn't already sorted. */
	if (!sorted)
	qsort(ary->elts, ary->nelts, ary->elt_size,
	(int ()(const void , const void *))comparison_func);

	return ary;
	}

	/* Return the lowest index at which the element *KEY should be inserted into
	the array at BASE which has NELTS elements of size ELT_SIZE bytes each,
	according to the ordering defined by COMPARE_FUNC.
	0 <= NELTS <= INT_MAX, 1 <= ELT_SIZE <= INT_MAX.
	The array must already be sorted in the ordering defined by COMPARE_FUNC.
	COMPARE_FUNC is defined as for the C stdlib function bsearch().
	Note: This function is modeled on bsearch() and on lower_bound() in the
	C++ STL.
	*/
	static int
	bsearch_lower_bound(const void *key,
	const void *base,
	int nelts,
	int elt_size,
	int (compare_func)(const void , const void *))
	{
	int lower = 0;
	int upper = nelts - 1;

	/* Binary search for the lowest position at which to insert KEY. */
	while (lower <= upper)
	{
	int try = lower + (upper - lower) / 2; /* careful to avoid overflow */
	int cmp = compare_func((const char )base + try elt_size, key);

	if (cmp < 0)
	lower = try + 1;
	else
	upper = try - 1;
	}
	assert(lower == upper + 1);

	return lower;
	}

	int
	svn_sort__bsearch_lower_bound(const void *key,
	const apr_array_header_t *array,
	int (compare_func)(const void , const void *))
	{
	return bsearch_lower_bound(key,
	array->elts, array->nelts, array->elt_size,
	compare_func);
	}

	void
	svn_sort__array_insert(const void *new_element,
	apr_array_header_t *array,
	int insert_index)
	{
	int elements_to_move;
	char *new_position;

	assert(0 <= insert_index && insert_index <= array->nelts);
	elements_to_move = array->nelts - insert_index; /* before bumping nelts */

	/* Grow the array, allocating a new space at the end. Note: this can
	reallocate the array's "elts" at a different address. */
	apr_array_push(array);

	/* Move the elements after INSERT_INDEX along. (When elements_to_move == 0,
	this is a no-op.) */
	new_position = (char )array->elts + insert_index array->elt_size;
	memmove(new_position + array->elt_size, new_position,
	array->elt_size * elements_to_move);

	/* Copy in the new element */
	memcpy(new_position, new_element, array->elt_size);
	}

	void
	svn_sort__array_delete(apr_array_header_t *arr,
	int delete_index,
	int elements_to_delete)
	{
	/* Do we have a valid index and are there enough elements? */
	if (delete_index >= 0
	&& delete_index < arr->nelts
	&& elements_to_delete > 0
	&& (elements_to_delete + delete_index) <= arr->nelts)
	{
	/* If we are not deleting a block of elements that extends to the end
	of the array, then we need to move the remaining elements to keep
	the array contiguous. */
	if ((elements_to_delete + delete_index) < arr->nelts)
	memmove(
	arr->elts + arr->elt_size * delete_index,
	arr->elts + (arr->elt_size * (delete_index + elements_to_delete)),
	arr->elt_size * (arr->nelts - elements_to_delete - delete_index));

	/* Delete the last ELEMENTS_TO_DELETE elements. */
	arr->nelts -= elements_to_delete;
	}
	}

	void
	svn_sort__array_reverse(apr_array_header_t *array,
	apr_pool_t *scratch_pool)
	{
	int i;

	if (array->elt_size == sizeof(void *))
	{
	for (i = 0; i < array->nelts / 2; i++)
	{
	int swap_index = array->nelts - i - 1;
	void tmp = APR_ARRAY_IDX(array, i, void );

	APR_ARRAY_IDX(array, i, void *) =
	APR_ARRAY_IDX(array, swap_index, void *);
	APR_ARRAY_IDX(array, swap_index, void *) = tmp;
	}
	}
	else
	{
	apr_size_t sz = array->elt_size;
	char *tmp = apr_palloc(scratch_pool, sz);

	for (i = 0; i < array->nelts / 2; i++)
	{
	int swap_index = array->nelts - i - 1;
	char x = array->elts + (sz i);
	char y = array->elts + (sz swap_index);

	memcpy(tmp, x, sz);
	memcpy(x, y, sz);
	memcpy(y, tmp, sz);
	}
	}
	}