X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fllx.c;h=43704e314ea2080c833d4745dc4e6b85e4557604;hb=2a88ed46e4bf5a240b9fe425598edf6bb158d66b;hp=c64393a76010f2bb700e92f90fae058ee5d16c71;hpb=8c8b1ba6eadf4cf533b5cce513a21b48ae06c402;p=pspp diff --git a/src/libpspp/llx.c b/src/libpspp/llx.c index c64393a760..43704e314e 100644 --- a/src/libpspp/llx.c +++ b/src/libpspp/llx.c @@ -1,21 +1,18 @@ -/* PSPP - computes sample statistics. - Copyright (C) 2006 Free Software Foundation, Inc. - Written by Ben Pfaff +/* 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 . */ /* External, circular doubly linked list. */ @@ -31,9 +28,8 @@ #include #endif -#include -#include "compiler.h" -#include +#include "libpspp/llx.h" +#include "libpspp/compiler.h" #include /* Destroys LIST and frees all of its nodes using MANAGER. @@ -42,23 +38,23 @@ 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)); } @@ -68,7 +64,7 @@ llx_count (const struct llx_list *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); } @@ -78,7 +74,7 @@ llx_push_head (struct llx_list *list, void *data, 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); } @@ -87,7 +83,7 @@ llx_push_tail (struct llx_list *list, void *data, 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); @@ -114,10 +110,10 @@ struct 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; } @@ -125,7 +121,7 @@ llx_insert (struct llx *before, void *data, const struct llx_manager *manager) /* 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); } @@ -133,7 +129,7 @@ llx_splice (struct llx *before, struct llx *r0, struct llx *r1) /* 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); } @@ -143,7 +139,7 @@ llx_swap (struct llx *a, struct llx *b) 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); } @@ -152,7 +148,7 @@ llx_swap_range (struct llx *a0, struct llx *a1, 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); @@ -164,29 +160,29 @@ llx_remove (struct llx *llx, const struct llx_manager *manager) 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; - for (llx = r0; llx != r1; ) + for (llx = r0; llx != r1;) llx = llx_remove (llx, manager); } /* 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) + for (x = r0; x != r1;) + if (compare (llx_data (x), target, aux) == 0) { x = llx_remove (x, manager); count++; @@ -210,8 +206,8 @@ llx_remove_if (struct llx *r0, struct llx *r1, size_t count; count = 0; - for (x = r0; x != r1; ) - if (predicate (llx_data (x), aux)) + for (x = r0; x != r1;) + if (predicate (llx_data (x), aux)) { x = llx_remove (x, manager); count++; @@ -222,20 +218,34 @@ llx_remove_if (struct llx *r0, struct llx *r1, 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 @@ -244,14 +254,14 @@ llx_find_equal (const struct llx *r0, const struct llx *r1, 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 @@ -267,12 +277,12 @@ llx_find_adjacent_equal (const struct llx *r0, const struct llx *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. @@ -324,15 +334,15 @@ llx_max (const struct llx *r0, const struct llx *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 @@ -343,15 +353,15 @@ llx_min (const struct llx *r0, const struct llx *r1, 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. @@ -360,16 +370,16 @@ llx_min (const struct llx *r0, const struct llx *r1, 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) @@ -414,7 +424,7 @@ llx_next_permutation (struct llx *r0, struct llx *r1, 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) @@ -427,12 +437,12 @@ llx_next_permutation (struct llx *r0, struct llx *r1, llx_swap (i, j); llx_reverse (llx_next (j), r1); return true; - } + } } - + llx_reverse (r0, r1); } - + return false; } @@ -451,7 +461,7 @@ llx_prev_permutation (struct llx *r0, struct llx *r1, 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) @@ -464,12 +474,12 @@ llx_prev_permutation (struct llx *r0, struct llx *r1, llx_swap (i, j); llx_reverse (llx_next (j), r1); return true; - } + } } - + llx_reverse (r0, r1); } - + return false; } @@ -512,19 +522,19 @@ llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *compare, void *aux) 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 @@ -536,14 +546,14 @@ llx_find_run (const struct llx *r0, const struct llx *r1, 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) { @@ -554,20 +564,20 @@ llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *b1, } 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; @@ -579,7 +589,7 @@ llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *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; } @@ -595,7 +605,7 @@ llx_is_sorted (const struct llx *r0, const struct llx *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; @@ -605,23 +615,23 @@ llx_unique (struct llx *r0, struct llx *r1, struct llx *dups, 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++; } } } @@ -640,11 +650,11 @@ llx_unique (struct llx *r0, struct llx *r1, struct llx *dups, 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 @@ -657,7 +667,7 @@ llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups, 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; @@ -681,7 +691,7 @@ llx_partition (struct llx *r0, struct llx *r1, { struct llx *t0, *t1; - for (;;) + for (;;) { if (r0 == r1) return r0; @@ -691,7 +701,7 @@ llx_partition (struct llx *r0, struct llx *r1, r0 = llx_next (r0); } - for (t0 = r0;; t0 = t1) + for (t0 = r0;; t0 = t1) { do { @@ -700,12 +710,12 @@ llx_partition (struct llx *r0, struct llx *r1, 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; @@ -725,10 +735,10 @@ llx_partition (struct llx *r0, struct llx *r1, 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; @@ -737,7 +747,7 @@ llx_find_partition (const struct llx *r0, const struct llx *r1, if (predicate (llx_data (x), aux)) return NULL; - return (struct llx *) partition; + return CONST_CAST (struct llx *, partition); } /* Allocates and returns a node using malloc. */ @@ -749,13 +759,13 @@ malloc_allocate_node (void *aux UNUSED) /* 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,