[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
gEDA-cvs: gaf.git: branch: master updated (1.5.0-20080706-437-gd8cc920)
The branch, master has been updated
via d8cc920d932f1557f3d93da6abd1d99e690f39ef (commit)
from 8b171391d26ee79ecccff732ff9ccb257460b815 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
=========
Summary
=========
gnetlist/include/prototype.h | 1 -
gnetlist/src/s_traverse.c | 85 +++++++++++++++++++++++++++---------------
libgeda/include/struct.h | 2 -
libgeda/src/s_basic.c | 2 -
4 files changed, 55 insertions(+), 35 deletions(-)
=================
Commit Messages
=================
commit d8cc920d932f1557f3d93da6abd1d99e690f39ef
Author: Peter TB Brett <peter@xxxxxxxxxxxxx>
Date: Sat Dec 20 21:47:12 2008 +0000
gnetlist: Optimise connection traversal algorithm
Increase performance for traversing schematic connections by
optimising tracking of how many times objects have been visited.
:100644 100644 cc19689... fdf9529... M gnetlist/include/prototype.h
:100644 100644 0c61d19... 3970adc... M gnetlist/src/s_traverse.c
:100644 100644 e686716... 50e0cc5... M libgeda/include/struct.h
:100644 100644 4c008bb... 24822f9... M libgeda/src/s_basic.c
=========
Changes
=========
commit d8cc920d932f1557f3d93da6abd1d99e690f39ef
Author: Peter TB Brett <peter@xxxxxxxxxxxxx>
Date: Sat Dec 20 21:47:12 2008 +0000
gnetlist: Optimise connection traversal algorithm
Increase performance for traversing schematic connections by
optimising tracking of how many times objects have been visited.
diff --git a/gnetlist/include/prototype.h b/gnetlist/include/prototype.h
index cc19689..fdf9529 100644
--- a/gnetlist/include/prototype.h
+++ b/gnetlist/include/prototype.h
@@ -110,7 +110,6 @@ void s_traverse_init(void);
void s_traverse_start(TOPLEVEL *pr_current);
void s_traverse_sheet(TOPLEVEL *pr_current, GList *obj_list, char *hierarchy_tag);
CPINLIST *s_traverse_component(TOPLEVEL *pr_current, OBJECT *component, char *hierarchy_tag);
-void s_traverse_clear_all_visited(GList *obj_list);
NET *s_traverse_net(TOPLEVEL *pr_current, OBJECT *previous_object, NET *nets, OBJECT *object, char *hierarchy_tag);
/* vams_misc.c */
SCM vams_get_attribs_list(OBJECT *object);
diff --git a/gnetlist/src/s_traverse.c b/gnetlist/src/s_traverse.c
index 0c61d19..3970adc 100644
--- a/gnetlist/src/s_traverse.c
+++ b/gnetlist/src/s_traverse.c
@@ -35,6 +35,51 @@
#include <dmalloc.h>
#endif
+/*! Tracks which OBJECTs have been visited so far, and how many times.
+ *
+ * The keys of the table are the OBJECT pointers, and the visit count
+ * is stored directly in the value pointers.
+ */
+static GHashTable *visit_table = NULL;
+
+/*! Trivial function used when clearing #visit_table. */
+static gboolean
+returns_true (gpointer key, gpointer value, gpointer user_data)
+{
+ return TRUE;
+}
+
+/*! Retrieve the current visit count for a particular OBJECT. */
+static inline gint
+is_visited(OBJECT *obj)
+{
+ gpointer val;
+ gpointer orig_key;
+ gboolean exist = g_hash_table_lookup_extended (visit_table,
+ obj,
+ &orig_key,
+ &val);
+ return exist ? GPOINTER_TO_INT(val) : 0;
+}
+
+/*! Increment the current visit count for a particular OBJECT. */
+static inline gint
+visit(OBJECT *obj)
+{
+ gpointer val = GINT_TO_POINTER(is_visited (obj) + 1);
+ g_hash_table_replace (visit_table, obj, val);
+ return GPOINTER_TO_INT (val);
+}
+
+/*! Reset all visit counts. Simply clears the hashtable completely. */
+static inline void
+s_traverse_clear_all_visited (GList *obj_list)
+{
+ g_hash_table_foreach_remove (visit_table,
+ (GHRFunc) returns_true,
+ NULL);
+}
+
void s_traverse_init(void)
{
netlist_head = s_netlist_add(NULL);
@@ -62,6 +107,11 @@ void s_traverse_init(void)
("------------------------------------------------------\n\n");
}
+
+ /* Initialise the hashtable which contains the visit
+ count. N.b. no free functions are required. */
+ visit_table = g_hash_table_new (g_direct_hash,
+ g_direct_equal);
}
void s_traverse_start(TOPLEVEL * pr_current)
@@ -235,7 +285,7 @@ CPINLIST *s_traverse_component(TOPLEVEL * pr_current, OBJECT * component,
verbose_print("p");
- o_current->visited = 1;
+ visit(o_current);
/* add cpin node */
cpins = s_cpinlist_add(cpins);
@@ -271,7 +321,7 @@ CPINLIST *s_traverse_component(TOPLEVEL * pr_current, OBJECT * component,
printf("c_current other_object, not NULL\n");
#endif
- if (!c_current->other_object->visited &&
+ if (!is_visited (c_current->other_object) &&
c_current->other_object != o_current) {
nets = s_net_add(nets);
@@ -328,31 +378,6 @@ CPINLIST *s_traverse_component(TOPLEVEL * pr_current, OBJECT * component,
return (cpinlist_head);
}
-
-void s_traverse_clear_all_visited (GList *obj_list)
-{
- GList *iter;
-
- for (iter = obj_list; iter != NULL; iter = g_list_next (iter)) {
- OBJECT *o_current = iter->data;
-
-#if DEBUG
- if (o_current->visited) {
- printf("%s\n", o_current->name);
- }
-#endif
-
- o_current->visited = 0;
-
- if (o_current->type == OBJ_COMPLEX
- && o_current->complex->prim_objs) {
- s_traverse_clear_all_visited(o_current->complex->prim_objs);
- }
-
- }
-
-}
-
NET *s_traverse_net(TOPLEVEL * pr_current, OBJECT * previous_object,
NET * nets, OBJECT * object, char *hierarchy_tag)
{
@@ -431,10 +456,10 @@ NET *s_traverse_net(TOPLEVEL * pr_current, OBJECT * previous_object,
/*printf("Found net %s\n", object->name); */
verbose_print("n");
- object->visited++;
+ visit(object);
/* this is not perfect yet and won't detect a loop... */
- if (object->visited > 100) {
+ if (is_visited(object) > 100) {
fprintf(stderr, "Found a possible net/pin infinite connection\n");
exit(-1);
}
@@ -452,7 +477,7 @@ NET *s_traverse_net(TOPLEVEL * pr_current, OBJECT * previous_object,
c_current->other_object->visited);
#endif
- if (!c_current->other_object->visited &&
+ if (!is_visited(c_current->other_object) &&
c_current->other_object != o_current &&
c_current->other_object->type != OBJ_BUS) {
diff --git a/libgeda/include/struct.h b/libgeda/include/struct.h
index e686716..50e0cc5 100644
--- a/libgeda/include/struct.h
+++ b/libgeda/include/struct.h
@@ -259,8 +259,6 @@ struct st_object {
int fill_angle1, fill_pitch1;
int fill_angle2, fill_pitch2;
- int visited; /* used in gnetlist for travesal purposes */
-
gboolean complex_embedded; /* is embedded component? */
gchar *complex_basename; /* Component Library Symbol name */
OBJECT *complex_parent; /* Complex parent object pointer */
diff --git a/libgeda/src/s_basic.c b/libgeda/src/s_basic.c
index 4c008bb..24822f9 100644
--- a/libgeda/src/s_basic.c
+++ b/libgeda/src/s_basic.c
@@ -102,8 +102,6 @@ OBJECT *s_basic_init_object(OBJECT *new_node, int type, char const *name)
new_node->conn_list = NULL;
- new_node->visited = 0;
-
new_node->complex_basename = NULL;
new_node->complex_parent = NULL;
_______________________________________________
geda-cvs mailing list
geda-cvs@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-cvs