summaryrefslogtreecommitdiff
path: root/libbanshee/engine/term-sort.c
diff options
context:
space:
mode:
Diffstat (limited to 'libbanshee/engine/term-sort.c')
-rw-r--r--libbanshee/engine/term-sort.c291
1 files changed, 291 insertions, 0 deletions
diff --git a/libbanshee/engine/term-sort.c b/libbanshee/engine/term-sort.c
new file mode 100644
index 00000000000..7503f296338
--- /dev/null
+++ b/libbanshee/engine/term-sort.c
@@ -0,0 +1,291 @@
+/*
+ * Copyright (c) 2000-2001
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ */
+
+#include <regions.h>
+#include <assert.h>
+#include <ansidecl.h>
+#include "term-sort.h"
+
+struct term_constant_ /* extends gen_e */
+{
+#ifdef NONSPEC
+ sort_kind sort;
+#endif
+ int type;
+ stamp st;
+ char *name;
+};
+
+typedef struct term_constant_ *term_constant_;
+
+region term_sort_region;
+term_hash term_sort_hash;
+bool flag_occurs_check = FALSE;
+
+struct term_stats term_stats;
+
+stamp term_get_stamp(gen_e e)
+{
+ if ( ((gen_term)e)->type == VAR_TYPE )
+ return ((gen_term)term_get_ecr(e))->st;
+ else
+ return ((gen_term)e)->st;
+}
+
+gen_e term_fresh(const char *name)
+{
+ term_stats.fresh++;
+ return (gen_e)tv_fresh(term_sort_region,name);
+}
+
+gen_e term_fresh_large(const char *name)
+{
+ term_stats.fresh_large++;
+ return (gen_e)tv_fresh_large(term_sort_region,name);
+}
+
+gen_e term_fresh_small(const char *name)
+{
+ term_stats.fresh_small++;
+ return (gen_e)tv_fresh_small(term_sort_region,name);
+}
+
+
+#ifdef NONSPEC
+static struct gen_term zero = {ZERO_TYPE,term_sort,ZERO_TYPE};
+static struct gen_term one = {ONE_TYPE,term_sort,ONE_TYPE};
+#else
+static struct gen_term zero = {ZERO_TYPE,ZERO_TYPE};
+static struct gen_term one = {ONE_TYPE,ONE_TYPE};
+#endif /* NONSPEC */
+
+gen_e term_zero(void)
+{
+ return (gen_e)&zero;
+}
+
+gen_e term_one(void)
+{
+ return (gen_e)&one;
+}
+
+
+gen_e term_constant(const char *str)
+{
+ stamp st[2];
+ gen_e result;
+ char *name = rstrdup(term_sort_region,str);
+
+ assert (str != NULL);
+
+ st[0] = CONSTANT_TYPE;
+ st[1] = stamp_string(name);
+
+ if ( (result = term_hash_find(term_sort_hash,st,2)) == NULL)
+ {
+ term_constant_ c = ralloc(term_sort_region, struct term_constant_);
+ c->type = CONSTANT_TYPE;
+ c->st = stamp_fresh();
+ c->name = name;
+
+ result = (gen_e) c;
+ term_hash_insert(term_sort_hash,result,st,2);
+
+ return result;
+ }
+
+ else
+ {
+ return result;
+ }
+
+}
+
+static bool term_is_bottom(gen_e e)
+{
+ return (term_is_zero(e) || term_is_var(e));
+}
+
+bool term_is_zero(gen_e e)
+{
+ return ( ((gen_term)term_get_ecr(e))->type == ZERO_TYPE);
+}
+
+bool term_is_one(gen_e e)
+{
+ return ( ((gen_term)term_get_ecr(e))->type == ONE_TYPE);
+}
+
+bool term_is_var(gen_e e)
+{
+ return ( ((gen_term)term_get_ecr(e))->type == VAR_TYPE);
+}
+
+bool term_is_constant(gen_e e)
+{
+ return ( ((gen_term)term_get_ecr(e))->type == CONSTANT_TYPE);
+}
+
+char *term_get_constant_name(gen_e e)
+{
+ gen_e ecr = term_get_ecr(e);
+ if(! term_is_constant(ecr))
+ return NULL;
+ else
+ return ((term_constant_)ecr)->name;
+}
+
+gen_e term_get_ecr(gen_e e)
+{
+ if (((gen_term)e)->type == VAR_TYPE)
+ return tv_get_ecr((term_var)e);
+ else return e;
+}
+
+static void fire_pending(term_var v, gen_e e,
+ con_match_fn_ptr con_match,
+ occurs_check_fn_ptr occurs)
+{
+ gen_e_list_scanner scan;
+ gen_e temp;
+
+ gen_e_list_scan(tv_get_pending(v),&scan);
+ while (gen_e_list_next(&scan,&temp))
+ {
+ term_unify(con_match,occurs,temp,e);
+ }
+}
+
+static bool eq(gen_e e1, gen_e e2)
+{
+ return term_get_ecr(e1) == term_get_ecr(e2);
+}
+
+void term_unify(con_match_fn_ptr con_match, occurs_check_fn_ptr occurs,
+ gen_e a, gen_e b)
+{
+ gen_e e1 = term_get_ecr(a),
+ e2 = term_get_ecr(b);
+
+ if ( eq(e1,e2) )
+ {
+ return;
+ }
+ if (term_is_constant(e1) && term_is_constant(e2))
+ {
+ failure("Inconsistent system of constraints\n");
+ }
+ else if (term_is_var(e1))
+ {
+ term_var v = (term_var)e1;
+
+
+ if (! term_is_bottom(e2))
+ fire_pending(v,e2,con_match,occurs);
+
+ if (term_is_var(e2))
+ tv_unify_vars(v,(term_var)e2);
+ else /* v = e2, e2 is not a var */
+ {
+ if (occurs(v,e2))
+ failure("Unify terms: occurs check failed\n");
+ tv_unify(v,e2);
+ }
+ }
+ else if (term_is_var(e2))
+ {
+ term_var v = (term_var)e2;
+
+ if (! term_is_bottom(e2))
+ fire_pending(v,e1,con_match,occurs);
+
+ /* v = e1, e1 is not a var */
+ if (occurs(v,e1))
+ failure("Unify terms: occurs check failed\n");
+ tv_unify(v,e1);
+
+ }
+ else con_match(e1,e2);
+}
+
+void term_cunify(con_match_fn_ptr con_match, occurs_check_fn_ptr occurs,
+ gen_e e1, gen_e e2)
+{
+ if (term_is_bottom(e1) && term_is_var(e1))
+ {
+ term_var v1 = (term_var)e1;
+ tv_add_pending(v1,e2);
+ }
+ else
+ {
+ term_unify(con_match,occurs,e1,e2);
+ }
+}
+
+static void term_reset_stats(void)
+{
+ term_stats.fresh = 0;
+ term_stats.fresh_small = 0;
+ term_stats.fresh_large = 0;
+}
+
+void term_print_stats(FILE *f)
+{
+ fprintf(f,"\n========== Term Var Stats ==========\n");
+ fprintf(f,"Fresh : %d\n",term_stats.fresh);
+ fprintf(f,"Fresh Small : %d\n",term_stats.fresh_small);
+ fprintf(f,"Fresh Large : %d\n",term_stats.fresh_large);
+ fprintf(f,"=====================================\n");
+}
+
+/* TODO */
+void term_print_constraint_graph(FILE *f ATTRIBUTE_UNUSED)
+{
+}
+
+void term_init(void)
+{
+ term_sort_region = newregion();
+ term_sort_hash = make_term_hash(term_sort_region);
+}
+
+void term_reset(void)
+{
+ term_hash_delete(term_sort_hash);
+ deleteregion_ptr(&term_sort_region);
+
+ term_reset_stats();
+
+ term_sort_region = newregion();
+ term_sort_hash = make_term_hash(term_sort_region);
+}
+
+
+
View Lorry Controller Status