You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
- 02111-1307, USA. */
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA. */
/* Copyright (C) 2001 Free Software Foundation, Inc.
You should have received a copy of the GNU General Public License along
with this library; see the file COPYING. If not, write to the Free
- Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
USA.
As a special exception, you may use this file as part of a free software
You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, write to the Free
- Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
- 02111-1307 USA. */
+ Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301 USA. */
#include <config.h>
#include "algorithm.h"
#include <stdlib.h>
#include <string.h>
#include "alloc.h"
-#include "settings.h"
/* Some of the assertions in this file are very expensive. We
don't use them by default. */
const void *target,
algo_compare_func *compare, void *aux)
{
- const unsigned char *element = array;
+ const char *element = array;
while (count-- > 0)
{
const void *element,
algo_compare_func *compare, void *aux)
{
- const unsigned char *first = array;
+ const char *first = array;
size_t equal_cnt = 0;
while (count-- > 0)
count_if (const void *array, size_t count, size_t size,
algo_predicate_func *predicate, void *aux)
{
- const unsigned char *first = array;
+ const char *first = array;
size_t nonzero_cnt = 0;
while (count-- > 0)
size_t nonzero_cnt,
algo_predicate_func *predicate, void *aux)
{
- const unsigned char *first = array;
+ const char *first = array;
size_t idx;
assert (nonzero_cnt <= count);
return 1;
}
\f
-/* A algo_random_func that uses random.h. */
-unsigned
-algo_default_random (unsigned max, void *aux UNUSED)
-{
- unsigned long r_min = gsl_rng_min (get_rng ());
- return (gsl_rng_get (get_rng ()) - r_min) % max;
-}
-
-/* Randomly reorders ARRAY, which contains COUNT elements of SIZE
- bytes each. Uses RANDOM as a source of random data, passing
- AUX as the auxiliary data. RANDOM may be null to use a
- default random source. */
-void
-random_shuffle (void *array_, size_t count, size_t size,
- algo_random_func *random, void *aux)
-{
- unsigned char *array = array_;
- int i;
-
- if (random == NULL)
- random = algo_default_random;
-
- for (i = 1; i < count; i++)
- SWAP (array + i * size, array + random (i + 1, aux) * size, size);
-}
-\f
/* Copies the COUNT elements of SIZE bytes each from ARRAY to
RESULT, except that elements for which PREDICATE is false are
not copied. Returns the number of elements copied. AUX is
void *result,
algo_predicate_func *predicate, void *aux)
{
- const unsigned char *input = array;
- const unsigned char *last = input + size * count;
- unsigned char *output = result;
+ const char *input = array;
+ const char *last = input + size * count;
+ char *output = result;
size_t nonzero_cnt = 0;
while (input < last)
remove_range (array, count, size, idx, 1);
}
+/* Moves an element in ARRAY, which consists of COUNT elements of
+ SIZE bytes each, from OLD_IDX to NEW_IDX, shifting around
+ other elements as needed. Runs in O(abs(OLD_IDX - NEW_IDX))
+ time. */
+void
+move_element (void *array_, size_t count, size_t size,
+ size_t old_idx, size_t new_idx)
+{
+ assert (array_ != NULL || count == 0);
+ assert (old_idx < count);
+ assert (new_idx < count);
+
+ if (old_idx != new_idx)
+ {
+ char *array = array_;
+ char *element = xmalloc (size);
+ char *new = array + new_idx * size;
+ char *old = array + old_idx * size;
+
+ memcpy (element, old, size);
+ if (new < old)
+ memmove (new + size, new, (old_idx - new_idx) * size);
+ else
+ memmove (old, old + size, (new_idx - old_idx) * size);
+ memcpy (new, element, size);
+
+ free (element);
+ }
+}
+
/* A predicate and its auxiliary data. */
struct pred_aux
{
void *element,
algo_compare_func *compare, void *aux)
{
- unsigned char *first = array;
- unsigned char *last = first + count * size;
- unsigned char *result;
+ char *first = array;
+ char *last = first + count * size;
+ char *result;
for (;;)
{
if (count != 0)
{
- const unsigned char *first = array;
+ const char *first = array;
int low = 0;
int high = count - 1;
while (low <= high)
{
int middle = (low + high) / 2;
- const unsigned char *element = first + middle * size;
+ const char *element = first + middle * size;
int cmp = compare (value, element, aux);
if (cmp > 0)
size_t size,
algo_compare_func *compare, void *aux)
{
- const unsigned char *first1 = array1;
- const unsigned char *first2 = array2;
+ const char *first1 = array1;
+ const char *first2 = array2;
size_t min_count = count1 < count2 ? count1 : count2;
while (min_count > 0)
Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
-#ifdef HAVE_ALLOCA_H
-#include <alloca.h>
-#endif
-
#include <limits.h>
#include <stdlib.h>
#include <string.h>
is_sorted (const void *array, size_t count, size_t size,
algo_compare_func *compare, void *aux)
{
- const unsigned char *first = array;
+ const char *first = array;
size_t idx;
for (idx = 0; idx + 1 < count; idx++)
void *result_,
algo_compare_func *compare, void *aux)
{
- const unsigned char *first1 = array1;
- const unsigned char *last1 = first1 + count1 * size;
- const unsigned char *first2 = array2;
- const unsigned char *last2 = first2 + count2 * size;
- unsigned char *result = result_;
+ const char *first1 = array1;
+ const char *last1 = first1 + count1 * size;
+ const char *first2 = array2;
+ const char *last2 = first2 + count2 * size;
+ char *result = result_;
size_t result_count = 0;
while (first1 != last1 && first2 != last2)
adjacent_find_equal (const void *array, size_t count, size_t size,
algo_compare_func *compare, void *aux)
{
- const unsigned char *first = array;
- const unsigned char *last = first + count * size;
+ const char *first = array;
+ const char *last = first + count * size;
while (first < last && first + size < last)
{
push_heap (void *array, size_t count, size_t size,
algo_compare_func *compare, void *aux)
{
- unsigned char *first = array;
+ char *first = array;
size_t i;
expensive_assert (count < 1 || is_heap (array, count - 1,
size, compare, aux));
for (i = count; i > 1; i /= 2)
{
- unsigned char *parent = first + (i / 2 - 1) * size;
- unsigned char *element = first + (i - 1) * size;
+ char *parent = first + (i / 2 - 1) * size;
+ char *element = first + (i - 1) * size;
if (compare (parent, element, aux) < 0)
SWAP (parent, element, size);
else
size_t idx,
algo_compare_func *compare, void *aux)
{
- unsigned char *first = array;
+ char *first = array;
for (;;)
{
pop_heap (void *array, size_t count, size_t size,
algo_compare_func *compare, void *aux)
{
- unsigned char *first = array;
+ char *first = array;
expensive_assert (is_heap (array, count, size, compare, aux));
SWAP (first, first + (count - 1) * size, size);
sort_heap (void *array, size_t count, size_t size,
algo_compare_func *compare, void *aux)
{
- unsigned char *first = array;
+ char *first = array;
size_t idx;
expensive_assert (is_heap (array, count, size, compare, aux));
is_heap (const void *array, size_t count, size_t size,
algo_compare_func *compare, void *aux)
{
- const unsigned char *first = array;
+ const char *first = array;
size_t child;
for (child = 2; child <= count; child++)