--- /dev/null
+/* PSPP - computes sample statistics.
+ Copyright (C) 2007 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 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. */
+
+#include <config.h>
+
+#include <libpspp/taint.h>
+
+#include <stddef.h>
+
+#include <libpspp/array.h>
+#include <libpspp/assertion.h>
+
+#include "xalloc.h"
+
+/* This code maintains two invariants:
+
+ 1. If a node is tainted, then all of its successors are
+ tainted.
+
+ 2. If a node is tainted, then it and all of its predecessors are
+ successor-tainted. */
+
+/* A list of pointers to taint structures. */
+struct taint_list
+ {
+ size_t cnt;
+ struct taint **taints;
+ };
+
+static void taint_list_init (struct taint_list *);
+static void taint_list_destroy (struct taint_list *);
+static void taint_list_add (struct taint_list *, struct taint *);
+static void taint_list_remove (struct taint_list *, const struct taint *);
+
+/* A taint. */
+struct taint
+ {
+ size_t ref_cnt; /* Number of owners. */
+ struct taint_list successors; /* Successors in graph. */
+ struct taint_list predecessors; /* Predecessors in graph. */
+ bool tainted; /* Is this node tainted? */
+ bool tainted_successor; /* Is/was any derived taint tainted? */
+ };
+
+static void recursively_set_taint (struct taint *);
+static void recursively_set_tainted_successor (struct taint *);
+
+/* Creates and returns a new taint object. */
+struct taint *
+taint_create (void)
+{
+ struct taint *taint = xmalloc (sizeof *taint);
+ taint->ref_cnt = 1;
+ taint_list_init (&taint->successors);
+ taint_list_init (&taint->predecessors);
+ taint->tainted = false;
+ taint->tainted_successor = false;
+ return taint;
+}
+
+/* Returns a clone of the given TAINT.
+ The new and old taint objects are logically indistinguishable,
+ as if they were the same object. (In this implementation,
+ they are in fact the same object, but this is not a guarantee
+ made by the interface.) */
+struct taint *
+taint_clone (const struct taint *taint_)
+{
+ struct taint *taint = (struct taint *) taint_;
+
+ assert (taint->ref_cnt > 0);
+ taint->ref_cnt++;
+ return taint;
+}
+
+/* Destroys the given TAINT.
+ Returns false if TAINT was tainted, true otherwise.
+ Any propagation relationships through TAINT are preserved.
+ That is, if A taints B and B taints C, then destroying B will
+ preserve the transitive relationship, so that tainting A will
+ still taint C. */
+bool
+taint_destroy (struct taint *taint)
+{
+ bool was_tainted = taint_is_tainted (taint);
+ if (--taint->ref_cnt == 0)
+ {
+ size_t i, j;
+
+ for (i = 0; i < taint->predecessors.cnt; i++)
+ for (j = 0; j < taint->successors.cnt; j++)
+ taint_propagate (taint->predecessors.taints[i],
+ taint->successors.taints[j]);
+
+ for (i = 0; i < taint->predecessors.cnt; i++)
+ taint_list_remove (&taint->predecessors.taints[i]->successors, taint);
+ for (i = 0; i < taint->successors.cnt; i++)
+ taint_list_remove (&taint->successors.taints[i]->predecessors, taint);
+
+ taint_list_destroy (&taint->successors);
+ taint_list_destroy (&taint->predecessors);
+ free (taint);
+ }
+ return !was_tainted;
+}
+
+/* Adds a propagation relationship from FROM to TO. This means
+ that, should FROM ever become tainted, then TO will
+ automatically be marked tainted as well. This takes effect
+ immediately: if FROM is currently tainted, then TO will be
+ tainted after the call completes.
+
+ Taint propagation is transitive: if A propagates to B and B
+ propagates to C, then tainting A taints both B and C. Taint
+ propagation is not commutative: propagation from A to B does
+ not imply propagation from B to A. Taint propagation is
+ robust against loops, so that if A propagates to B and vice
+ versa, whether directly or indirectly, then tainting either A
+ or B will cause the other to be tainted, without producing an
+ infinite loop. */
+void
+taint_propagate (const struct taint *from_, const struct taint *to_)
+{
+ struct taint *from = (struct taint *) from_;
+ struct taint *to = (struct taint *) to_;
+
+ if (from != to)
+ {
+ taint_list_add (&from->successors, to);
+ taint_list_add (&to->predecessors, from);
+ if (from->tainted && !to->tainted)
+ recursively_set_taint (to);
+ else if (to->tainted_successor && !from->tainted_successor)
+ recursively_set_tainted_successor (from);
+ }
+}
+
+/* Returns true if TAINT is tainted, false otherwise. */
+bool
+taint_is_tainted (const struct taint *taint)
+{
+ return taint->tainted;
+}
+
+/* Marks TAINT tainted and propagates the taint to all of its
+ successors. */
+void
+taint_set_taint (const struct taint *taint_)
+{
+ struct taint *taint = (struct taint *) taint_;
+ if (!taint->tainted)
+ recursively_set_taint (taint);
+}
+
+/* Returns true if TAINT is successor-tainted, that is, if it or
+ any of its successors is or ever has been tainted. (A
+ "successor" of a taint object X is any taint object that can
+ be reached by following propagation relationships starting
+ from X.) */
+bool
+taint_has_tainted_successor (const struct taint *taint)
+{
+ return taint->tainted_successor;
+}
+
+/* Attempts to reset the successor-taint on TAINT. This is
+ successful only if TAINT currently has no tainted successor. */
+void
+taint_reset_successor_taint (const struct taint *taint_)
+{
+ struct taint *taint = (struct taint *) taint_;
+
+ if (taint->tainted_successor)
+ {
+ size_t i;
+
+ for (i = 0; i < taint->successors.cnt; i++)
+ if (taint->successors.taints[i]->tainted_successor)
+ return;
+
+ taint->tainted_successor = false;
+ }
+}
+\f
+/* Initializes LIST as an empty list of taints. */
+static void
+taint_list_init (struct taint_list *list)
+{
+ list->cnt = 0;
+ list->taints = NULL;
+}
+
+/* Destroys LIST. */
+static void
+taint_list_destroy (struct taint_list *list)
+{
+ free (list->taints);
+}
+
+/* Returns true if TAINT is in LIST, false otherwise. */
+static bool
+taint_list_contains (const struct taint_list *list, const struct taint *taint)
+{
+ size_t i;
+
+ for (i = 0; i < list->cnt; i++)
+ if (list->taints[i] == taint)
+ return true;
+
+ return false;
+}
+
+/* Returns true if X is zero or a power of 2, false otherwise. */
+static bool
+is_zero_or_power_of_2 (size_t x)
+{
+ return (x & (x - 1)) == 0;
+}
+
+/* Adds TAINT to LIST, if it isn't already in the list. */
+static void
+taint_list_add (struct taint_list *list, struct taint *taint)
+{
+ if (!taint_list_contains (list, taint))
+ {
+ /* To save a few bytes of memory per list, we don't store
+ the list capacity as a separate member. Instead, the
+ list capacity is always zero or a power of 2. Thus, if
+ the list count is one of these threshold values, we need
+ to allocate more memory. */
+ if (is_zero_or_power_of_2 (list->cnt))
+ list->taints = xnrealloc (list->taints,
+ list->cnt == 0 ? 1 : 2 * list->cnt,
+ sizeof *list->taints);
+ list->taints[list->cnt++] = taint;
+ }
+}
+
+/* Removes TAINT from LIST (which must contain it). */
+static void
+taint_list_remove (struct taint_list *list, const struct taint *taint)
+{
+ size_t i;
+
+ for (i = 0; i < list->cnt; i++)
+ if (list->taints[i] == taint)
+ {
+ remove_element (list->taints, list->cnt, sizeof *list->taints, i);
+ list->cnt--;
+ return;
+ }
+
+ NOT_REACHED ();
+}
+\f
+/* Marks TAINT as tainted, as well as all of its successors
+ recursively. Also marks TAINT's predecessors as
+ successor-tainted, recursively. */
+static void
+recursively_set_taint (struct taint *taint)
+{
+ size_t i;
+
+ taint->tainted = taint->tainted_successor = true;
+ for (i = 0; i < taint->successors.cnt; i++)
+ {
+ struct taint *s = taint->successors.taints[i];
+ if (!s->tainted)
+ recursively_set_taint (s);
+ }
+ for (i = 0; i < taint->predecessors.cnt; i++)
+ {
+ struct taint *p = taint->predecessors.taints[i];
+ if (!p->tainted_successor)
+ recursively_set_tainted_successor (p);
+ }
+}
+
+/* Marks TAINT as successor-tainted, as well as all of its
+ predecessors recursively. */
+static void
+recursively_set_tainted_successor (struct taint *taint)
+{
+ size_t i;
+
+ taint->tainted_successor = true;
+ for (i = 0; i < taint->predecessors.cnt; i++)
+ {
+ struct taint *p = taint->predecessors.taints[i];
+ if (!p->tainted_successor)
+ recursively_set_tainted_successor (p);
+ }
+}
+
projects / pspp-builds.git / blobdiff