From 2a2ba142b11466a039c95046ab26f003bc757a9e Mon Sep 17 00:00:00 2001 From: =?utf8?q?G=C3=B6tz=20Lindenmaier?= Date: Wed, 9 Jun 2004 20:27:41 +0000 Subject: [PATCH] functionality to hash types efficiently. [r3045] --- ir/tr/Makefile.in | 4 +- ir/tr/type.h | 2 +- ir/tr/type_identify.c | 94 +++++++++++++++++++++++++++++++++++++++ ir/tr/type_identify.h | 101 ++++++++++++++++++++++++++++++++++++++++++ ir/tr/typegmod.h | 2 +- 5 files changed, 199 insertions(+), 4 deletions(-) create mode 100644 ir/tr/type_identify.c create mode 100644 ir/tr/type_identify.h diff --git a/ir/tr/Makefile.in b/ir/tr/Makefile.in index fed3782d4..eaca6a8e1 100644 --- a/ir/tr/Makefile.in +++ b/ir/tr/Makefile.in @@ -16,13 +16,13 @@ topdir = ../.. subdir := ir/tr INSTALL_HEADERS = entity.h mangle.h tpop.h type.h typewalk.h type_or_entity.h \ - typegmod.h trvrfy.h + typegmod.h trvrfy.h type_identify.h SOURCES = $(INSTALL_HEADERS) SOURCES += Makefile.in \ entity.c entity_t.h mangle.c tpop.c tpop_t.h type.c type_t.h \ - typewalk.c typegmod.c trvrfy.h trvrfy.c + typewalk.c typegmod.c trvrfy.h trvrfy.c type_identify.c include $(topdir)/MakeRules diff --git a/ir/tr/type.h b/ir/tr/type.h index 71321a3a2..4454c5d37 100644 --- a/ir/tr/type.h +++ b/ir/tr/type.h @@ -141,7 +141,7 @@ ident* get_type_ident(type *tp); void set_type_ident(type *tp, ident* id); const char* get_type_name(type *tp); -/** The state of a type layout. */ +/** The state of the type layout. */ typedef enum { layout_undefined, /**< The layout of this type is not defined. Address computation to access fields is not diff --git a/ir/tr/type_identify.c b/ir/tr/type_identify.c new file mode 100644 index 000000000..1905f6c33 --- /dev/null +++ b/ir/tr/type_identify.c @@ -0,0 +1,94 @@ +/* + * Project: libFIRM + * File name: ir/tr/type.c + * Purpose: Representation of types. + * Author: Goetz Lindenmaier + * Modified by: + * Created: + * CVS-ID: $Id$ + * Copyright: (c) 2001-2003 Universität Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + +/** + * + * file type.c - implementation of the datastructure to hold + * type information. + * (C) 2004 by Universitaet Karlsruhe + * Goetz Lindenmaier + * + */ + +#ifdef HAVE_CONFIG_H +# include +#endif + +#include "type_identify.h" + +# include +# include +# include +# include "type_t.h" +# include "tpop_t.h" +# include "irprog_t.h" +# include "typegmod.h" +# include "array.h" +# include "irprog.h" +# include "mangle.h" +#include "pset.h" + +/* The hash set for types. */ +static pset *type_table = NULL; + + +int compare_names (const void *tp1, const void *tp2) { + type *t1 = (type *) tp1; + type *t2 = (type *) tp2; + + return (t1 != t2 && + (t1->type_op != t2->type_op || + t1->name != t2->name ) ); +} + + +/* stuff for comparing two types. */ +//static int compare_strict (type *tp1, type *tp2) { +static int compare_strict (const void *tp1, const void *tp2) { + type *t1 = (type *) tp1; + type *t2 = (type *) tp2; + return t1 != t2; +} + +compare_types_func_tp compare_types_func = compare_strict; + +/* stuff to compute a hash value for a type. */ +int hash_name (type *tp) { + unsigned h = (unsigned)tp->type_op; + h = 9*h + (unsigned)tp->name; + return h; +} + +hash_types_func_tp hash_types_func = hash_name; + + +/* The function that hashes a type. */ +type *mature_type(type *tp) { + type *o; + + assert(type_table); + + o = pset_insert (type_table, tp, hash_types_func(tp) ); + + if (!o || o == tp) return tp; + + exchange_types(tp, o); + return o ; +} + + +void init_type_identify(void) { + //type_table = new_pset ((int (const void *, const void *))compare_types_func, 8); + + type_table = new_pset (compare_types_func, 8); + //type_table = new_pset (compare_names, 8); +} diff --git a/ir/tr/type_identify.h b/ir/tr/type_identify.h new file mode 100644 index 000000000..fbb5eea21 --- /dev/null +++ b/ir/tr/type_identify.h @@ -0,0 +1,101 @@ +/** + * + * @file type.h + * + * Project: libFIRM
+ * File name: ir/tr/type.h
+ * Purpose: Representation of types.
+ * Author: Goetz Lindenmaier
+ * Modified by:
+ * Created:
+ * Copyright: (c) 2001-2003 Universität Karlsruhe
+ * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
+ * CVS-ID: $Id$ + * + * + */ + +# ifndef _TYPE_IDENTIFY_H_ +# define _TYPE_IDENTIFY_H_ + +#ifndef _TYPE_TYPEDEF_ +#define _TYPE_TYPEDEF_ +typedef struct type type; +#endif + +/* ------------------------------------------------------------------------ */ + +/** Type for a function that compares two types. + * + * @param tp1 The first type to compare. + * @param tp2 The second type to compare. + */ +//typedef int (*compare_types_func_tp) (type *tp1, type *tp2); +typedef int (*compare_types_func_tp) (const void *tp1, const void *tp2); + +/** Compares two types by their name. + * + * Compares the opcode and the name of the types. If these are + * equal returns true, else false. + */ +int compare_names (const void *tp1, const void *tp2); + +/** Compares two types strict. + * + * returns true if tp1 == tp2 + */ +int compare_strict (const void *tp1, const void *tp2); + +/** A variable that holds a compare function for types. + * + * The compare function is used to identify equal types. The + * variable is initialized with the function compare_strict(). + * + * The variable must be set before calling init_firm()! Later changes + * have no effect. + */ +extern compare_types_func_tp compare_types_func; + + +/* ------------------------------------------------------------------------ */ + +/** Type for a function that computes a hash value for a type. + * + * @param tp The type to compute a hash for. + */ +typedef int (*hash_types_func_tp)(type *tp); + +/** Computes a hash value by the type name. + * + * Uses the name of the type and the type opcode to compute the hash. + */ +int hash_name (type *tp); + +/** A variable that holds a hash function for a type. + * + * The hash function is used to identify equal types. The + * variable is initialized with the function hash_name(). + * + * The variable must be set before calling init_firm()! Later changes + * have no effect. + */ +extern hash_types_func_tp hash_types_func; + + +/* ------------------------------------------------------------------------ */ + +/** Finalize type construction. + * + * Indicate that a type is so far completed that it can be + * distinguished from other types. Mature_type hashes the type into a + * table. It uses the function in compare_types_func to compare the + * types. If it find a type identical to tp it returns this type. In + * this case it also turns tp into the Id type. The caller should free + * tp if he knows that there are no other references to tp. The memory + * of tp is not lost, but will remain alive for an unknown time. + * + * @param tp The type to mature. + */ +type * mature_type(type *tp); + +# endif /* _TYPE_IDENTIFY_H_ */ diff --git a/ir/tr/typegmod.h b/ir/tr/typegmod.h index a0e610628..d92863bc3 100644 --- a/ir/tr/typegmod.h +++ b/ir/tr/typegmod.h @@ -40,7 +40,7 @@ void exchange_types(type *old_type, type *new_type); /** - * skip id types until a useful type is reached. + * Skip id types until a useful type is reached. * * @param tp - A type of arbitrary kind. * -- 2.20.1