-/* PSPP - computes sample statistics.
- Copyright (C) 2006 Free Software Foundation, Inc.
- Written by Ben Pfaff <blp@gnu.org>
+/* PSPP - a program for statistical analysis.
+ Copyright (C) 2006, 2009, 2011 Free Software Foundation, Inc.
- This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License as
- published by the Free Software Foundation; either version 2 of the
- License, or (at your option) any later version.
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
- This program is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
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., 51 Franklin Street, Fifth Floor, Boston, MA
- 02110-1301, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
/* External, circular doubly linked list. */
#include <config.h>
#endif
-#include <libpspp/llx.h>
+#include "libpspp/llx.h"
+#include "libpspp/compiler.h"
#include <assert.h>
#include <stdlib.h>
-#if __GNUC__ >= 2 && !defined UNUSED
-#define UNUSED __attribute__ ((unused))
-#else
-#define UNUSED
-#endif
-
/* Destroys LIST and frees all of its nodes using MANAGER.
If DESTRUCTOR is non-null, each node in the list will be
passed to it in list order, with AUX as auxiliary data, before
that node is destroyed. */
void
llx_destroy (struct llx_list *list, llx_action_func *destructor, void *aux,
- const struct llx_manager *manager)
+ const struct llx_manager *manager)
{
struct llx *llx, *next;
- for (llx = llx_head (list); llx != llx_null (list); llx = next)
+ for (llx = llx_head (list); llx != llx_null (list); llx = next)
{
next = llx_next (llx);
if (destructor != NULL)
destructor (llx_data (llx), aux);
manager->release (llx, manager->aux);
- }
+ }
}
/* Returns the number of nodes in LIST (not counting the null
node). Executes in O(n) time in the length of the list. */
size_t
-llx_count (const struct llx_list *list)
+llx_count (const struct llx_list *list)
{
return llx_count_range (llx_head (list), llx_null (list));
}
pointer if memory allocation failed. */
struct llx *
llx_push_head (struct llx_list *list, void *data,
- const struct llx_manager *manager)
+ const struct llx_manager *manager)
{
return llx_insert (llx_head (list), data, manager);
}
pointer if memory allocation failed. */
struct llx *
llx_push_tail (struct llx_list *list, void *data,
- const struct llx_manager *manager)
+ const struct llx_manager *manager)
{
return llx_insert (llx_null (list), data, manager);
}
and returns the data that the node contained.
Frees the node removed with MANAGER. */
void *
-llx_pop_head (struct llx_list *list, const struct llx_manager *manager)
+llx_pop_head (struct llx_list *list, const struct llx_manager *manager)
{
struct llx *llx = llx_from_ll (ll_head (&list->ll_list));
void *data = llx_data (llx);
llx_insert (struct llx *before, void *data, const struct llx_manager *manager)
{
struct llx *llx = manager->allocate (manager->aux);
- if (llx != NULL)
+ if (llx != NULL)
{
llx->data = data;
- ll_insert (&before->ll, &llx->ll);
+ ll_insert (&before->ll, &llx->ll);
}
return llx;
}
/* Removes R0...R1 from their current list
and inserts them just before BEFORE. */
void
-llx_splice (struct llx *before, struct llx *r0, struct llx *r1)
+llx_splice (struct llx *before, struct llx *r0, struct llx *r1)
{
ll_splice (&before->ll, &r0->ll, &r1->ll);
}
/* Exchanges the positions of A and B,
which may be in the same list or different lists. */
void
-llx_swap (struct llx *a, struct llx *b)
+llx_swap (struct llx *a, struct llx *b)
{
ll_swap (&a->ll, &b->ll);
}
overlap. */
void
llx_swap_range (struct llx *a0, struct llx *a1,
- struct llx *b0, struct llx *b1)
+ struct llx *b0, struct llx *b1)
{
ll_swap_range (&a0->ll, &a1->ll, &b0->ll, &b1->ll);
}
and returns the node that formerly followed it.
Frees the node removed with MANAGER. */
struct llx *
-llx_remove (struct llx *llx, const struct llx_manager *manager)
+llx_remove (struct llx *llx, const struct llx_manager *manager)
{
struct llx *next = llx_next (llx);
ll_remove (&llx->ll);
Frees the removed nodes with MANAGER. */
void
llx_remove_range (struct llx *r0, struct llx *r1,
- const struct llx_manager *manager)
+ const struct llx_manager *manager)
{
struct llx *llx;
/* Removes from R0...R1 all the nodes that equal TARGET
according to COMPARE given auxiliary data AUX.
- Frees the removed nodes with MANAGER.
+ Frees the removed nodes with MANAGER.
Returns the number of nodes removed. */
size_t
llx_remove_equal (struct llx *r0, struct llx *r1, const void *target,
llx_compare_func *compare, void *aux,
- const struct llx_manager *manager)
+ const struct llx_manager *manager)
{
struct llx *x;
size_t count;
count = 0;
for (x = r0; x != r1; )
- if (compare (llx_data (x), target, aux) == 0)
+ if (compare (llx_data (x), target, aux) == 0)
{
x = llx_remove (x, manager);
count++;
count = 0;
for (x = r0; x != r1; )
- if (predicate (llx_data (x), aux))
+ if (predicate (llx_data (x), aux))
{
x = llx_remove (x, manager);
count++;
return count;
}
+/* Returns the first node in R0...R1 that has data TARGET.
+ Returns NULL if no node in R0...R1 equals TARGET. */
+struct llx *
+llx_find (const struct llx *r0, const struct llx *r1, const void *target)
+{
+ const struct llx *x;
+
+ for (x = r0; x != r1; x = llx_next (x))
+ if (llx_data (x) == target)
+ return CONST_CAST (struct llx *, x);
+
+ return NULL;
+}
+
/* Returns the first node in R0...R1 that equals TARGET
according to COMPARE given auxiliary data AUX.
Returns R1 if no node in R0...R1 equals TARGET. */
struct llx *
llx_find_equal (const struct llx *r0, const struct llx *r1,
const void *target,
- llx_compare_func *compare, void *aux)
+ llx_compare_func *compare, void *aux)
{
const struct llx *x;
-
+
for (x = r0; x != r1; x = llx_next (x))
if (compare (llx_data (x), target, aux) == 0)
break;
- return (struct llx *) x;
+ return CONST_CAST (struct llx *, x);
}
/* Returns the first node in R0...R1 for which PREDICATE returns
R0...R1 . */
struct llx *
llx_find_if (const struct llx *r0, const struct llx *r1,
- llx_predicate_func *predicate, void *aux)
+ llx_predicate_func *predicate, void *aux)
{
const struct llx *x;
-
+
for (x = r0; x != r1; x = llx_next (x))
if (predicate (llx_data (x), aux))
break;
- return (struct llx *) x;
+ return CONST_CAST (struct llx *, x);
}
/* Compares each pair of adjacent nodes in R0...R1
{
const struct llx *x, *y;
- for (x = r0, y = llx_next (x); y != r1; x = y, y = llx_next (y))
+ for (x = r0, y = llx_next (x); y != r1; x = y, y = llx_next (y))
if (compare (llx_data (x), llx_data (y), aux) == 0)
- return (struct llx *) x;
+ return CONST_CAST (struct llx *, x);
}
- return (struct llx *) r1;
+ return CONST_CAST (struct llx *, r1);
}
/* Returns the number of nodes in R0...R1.
llx_compare_func *compare, void *aux)
{
const struct llx *max = r0;
- if (r0 != r1)
+ if (r0 != r1)
{
struct llx *x;
-
+
for (x = llx_next (r0); x != r1; x = llx_next (x))
if (compare (llx_data (x), llx_data (max), aux) > 0)
max = x;
}
- return (struct llx *) max;
+ return CONST_CAST (struct llx *, max);
}
/* Returns the least node in R0...R1 according to COMPARE given
llx_compare_func *compare, void *aux)
{
const struct llx *min = r0;
- if (r0 != r1)
+ if (r0 != r1)
{
struct llx *x;
-
+
for (x = llx_next (r0); x != r1; x = llx_next (x))
if (compare (llx_data (x), llx_data (min), aux) < 0)
min = x;
}
- return (struct llx *) min;
+ return CONST_CAST (struct llx *, min);
}
/* Lexicographically compares A0...A1 to B0...B1.
positive if A0...A1 > B0...B1
according to COMPARE given auxiliary data AUX. */
int
-llx_lexicographical_compare_3way (const struct llx *a0, const struct llx *a1,
- const struct llx *b0, const struct llx *b1,
+llx_lexicographical_compare_3way (const struct llx *a0, const struct llx *a1,
+ const struct llx *b0, const struct llx *b1,
llx_compare_func *compare, void *aux)
{
- for (;;)
+ for (;;)
if (b0 == b1)
return a0 != a1;
else if (a0 == a1)
return -1;
- else
+ else
{
int cmp = compare (llx_data (a0), llx_data (b0), aux);
if (cmp != 0)
if (r0 != r1)
{
struct llx *i = llx_prev (r1);
- while (i != r0)
+ while (i != r0)
{
i = llx_prev (i);
if (compare (llx_data (i), llx_data (llx_next (i)), aux) < 0)
llx_swap (i, j);
llx_reverse (llx_next (j), r1);
return true;
- }
+ }
}
-
+
llx_reverse (r0, r1);
}
-
+
return false;
}
if (r0 != r1)
{
struct llx *i = llx_prev (r1);
- while (i != r0)
+ while (i != r0)
{
i = llx_prev (i);
if (compare (llx_data (i), llx_data (llx_next (i)), aux) > 0)
llx_swap (i, j);
llx_reverse (llx_next (j), r1);
return true;
- }
+ }
}
-
+
llx_reverse (r0, r1);
}
-
+
return false;
}
order. */
struct llx *
llx_find_run (const struct llx *r0, const struct llx *r1,
- llx_compare_func *compare, void *aux)
+ llx_compare_func *compare, void *aux)
{
- if (r0 != r1)
+ if (r0 != r1)
{
- do
+ do
{
r0 = llx_next (r0);
}
while (r0 != r1 && compare (llx_data (llx_prev (r0)),
llx_data (r0), aux) <= 0);
}
-
- return (struct llx *) r0;
+
+ return CONST_CAST (struct llx *, r0);
}
/* Merges B0...B1 into A0...A1 according to COMPARE given
Runs in O(n) time in the total number of nodes in the ranges. */
struct llx *
llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *b1,
- llx_compare_func *compare, void *aux)
+ llx_compare_func *compare, void *aux)
{
- if (a0 != a1 && b0 != b1)
+ if (a0 != a1 && b0 != b1)
{
a1 = llx_prev (a1);
b1 = llx_prev (b1);
- for (;;)
- if (compare (llx_data (a0), llx_data (b0), aux) <= 0)
+ for (;;)
+ if (compare (llx_data (a0), llx_data (b0), aux) <= 0)
{
if (a0 == a1)
{
}
else
{
- if (b0 != b1)
+ if (b0 != b1)
{
struct llx *x = b0;
b0 = llx_next (b0);
- llx_splice (a0, x, b0);
+ llx_splice (a0, x, b0);
}
- else
+ else
{
llx_splice (a0, b0, llx_next (b0));
return llx_next (a1);
}
- }
+ }
}
- else
+ else
{
llx_splice (a0, b0, b1);
return b1;
false otherwise. */
bool
llx_is_sorted (const struct llx *r0, const struct llx *r1,
- llx_compare_func *compare, void *aux)
+ llx_compare_func *compare, void *aux)
{
return llx_find_run (r0, r1, compare, aux) == r1;
}
size_t
llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
llx_compare_func *compare, void *aux,
- const struct llx_manager *manager)
+ const struct llx_manager *manager)
{
size_t count = 0;
for (;;)
{
struct llx *y = llx_next (x);
- if (y == r1)
+ if (y == r1)
{
count++;
- break;
+ break;
}
- if (compare (llx_data (x), llx_data (y), aux) == 0)
+ if (compare (llx_data (x), llx_data (y), aux) == 0)
{
- if (dups != NULL)
+ if (dups != NULL)
llx_splice (dups, y, llx_next (y));
else
llx_remove (y, manager);
}
- else
+ else
{
x = y;
- count++;
+ count++;
}
}
}
void
llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
llx_compare_func *compare, void *aux,
- const struct llx_manager *manager)
+ const struct llx_manager *manager)
{
struct llx *pre_r0 = llx_prev (r0);
llx_sort (r0, r1, compare, aux);
- llx_unique (llx_next (pre_r0), r1, dups, compare, aux, manager);
+ llx_unique (llx_next (pre_r0), r1, dups, compare, aux, manager);
}
/* Inserts DATA in the proper position in R0...R1, which must
struct llx *
llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
llx_compare_func *compare, void *aux,
- const struct llx_manager *manager)
+ const struct llx_manager *manager)
{
struct llx *x;
{
struct llx *t0, *t1;
- for (;;)
+ for (;;)
{
if (r0 == r1)
return r0;
r0 = llx_next (r0);
}
- for (t0 = r0;; t0 = t1)
+ for (t0 = r0;; t0 = t1)
{
do
{
return r0;
}
while (!predicate (llx_data (t0), aux));
-
+
t1 = t0;
do
{
t1 = llx_next (t1);
- if (t1 == r1)
+ if (t1 == r1)
{
llx_splice (r0, t0, t1);
return r0;
if PREDICATE is true for every node in R0...R1. */
struct llx *
llx_find_partition (const struct llx *r0, const struct llx *r1,
- llx_predicate_func *predicate, void *aux)
+ llx_predicate_func *predicate, void *aux)
{
const struct llx *partition, *x;
-
+
for (partition = r0; partition != r1; partition = llx_next (partition))
if (!predicate (llx_data (partition), aux))
break;
if (predicate (llx_data (x), aux))
return NULL;
- return (struct llx *) partition;
+ return CONST_CAST (struct llx *, partition);
}
\f
/* Allocates and returns a node using malloc. */
/* Releases node LLX with free. */
static void
-malloc_release_node (struct llx *llx, void *aux UNUSED)
+malloc_release_node (struct llx *llx, void *aux UNUSED)
{
free (llx);
}
/* Manager that uses the standard malloc and free routines. */
-const struct llx_manager llx_malloc_mgr =
+const struct llx_manager llx_malloc_mgr =
{
malloc_allocate_node,
malloc_release_node,
projects / pspp-builds.git / blobdiff