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 <gsl/gsl_rng.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include "alloc.h"
-#include "random.h"
-/* Some of the assertions in this file are very expensive. If
- we're optimizing, don't include them. */
-#if __OPTIMIZE__
-#define NDEBUG
+/* Some of the assertions in this file are very expensive. We
+ don't use them by default. */
+#ifdef EXTRA_CHECKS
+#define expensive_assert(X) assert(X)
+#else
+#define expensive_assert(X) ((void) 0)
#endif
#include "error.h"
\f
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)
first += size;
if (first >= last)
{
- assert (adjacent_find_equal (array, count, size, compare, aux) == NULL);
+ assert (adjacent_find_equal (array, count,
+ size, compare, aux) == NULL);
return count;
}
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)
-{
- return rng_get_unsigned (pspp_rng ()) % 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)
return nonzero_cnt;
}
+/* Removes N elements starting at IDX from ARRAY, which consists
+ of COUNT elements of SIZE bytes each, by shifting the elements
+ following them, if any, into its position. */
+void
+remove_range (void *array_, size_t count, size_t size,
+ size_t idx, size_t n)
+{
+ char *array = array_;
+
+ assert (array != NULL);
+ assert (idx <= count);
+ assert (idx + n <= count);
+
+ if (idx + n < count)
+ memmove (array + idx * size, array + (idx + n) * size,
+ size * (count - idx - n));
+}
+
+/* Removes element IDX from ARRAY, which consists of COUNT
+ elements of SIZE bytes each, by shifting the elements
+ following it, if any, into its position. */
+void
+remove_element (void *array, size_t count, size_t size,
+ size_t idx)
+{
+ 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)
}
}
- assert (find (array, count, size, value, compare, aux) == NULL);
+ expensive_assert (find (array, count, size, value, compare, aux) == NULL);
return NULL;
}
\f
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. */
-#include <alloca.h>
#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;
- assert (count < 1 || is_heap (array, count - 1, size, compare, aux));
+ 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
break;
}
- assert (is_heap (array, count, size, compare, aux));
+ expensive_assert (is_heap (array, count, size, compare, aux));
}
/* ARRAY contains COUNT elements of SIZE bytes each. Initially
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;
- assert (is_heap (array, count, size, compare, aux));
+ expensive_assert (is_heap (array, count, size, compare, aux));
SWAP (first, first + (count - 1) * size, size);
heapify (first, count - 1, size, 1, compare, aux);
- assert (count < 1 || is_heap (array, count - 1, size, compare, aux));
+ expensive_assert (count < 1 || is_heap (array, count - 1,
+ size, compare, aux));
}
/* Turns ARRAY, which contains COUNT elements of SIZE bytes, into
for (idx = count / 2; idx >= 1; idx--)
heapify (array, count, size, idx, compare, aux);
- assert (count < 1 || is_heap (array, count, size, compare, aux));
+ expensive_assert (count < 1 || is_heap (array, count, size, compare, aux));
}
/* ARRAY contains COUNT elements of SIZE bytes each. Initially
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;
- assert (is_heap (array, count, size, compare, aux));
+ expensive_assert (is_heap (array, count, size, compare, aux));
for (idx = count; idx >= 2; idx--)
{
SWAP (first, first + (idx - 1) * size, size);
heapify (array, idx - 1, size, 1, compare, aux);
}
- assert (is_sorted (array, count, size, compare, aux));
+ expensive_assert (is_sorted (array, count, size, compare, aux));
}
/* ARRAY contains COUNT elements of SIZE bytes each. This
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++)
projects / pspp-builds.git / blobdiff