r5942 - trunk/eda/fped
werner at docs.openmoko.org
werner at docs.openmoko.org
Mon Apr 26 17:18:01 CEST 2010
Author: werner
Date: 2010-04-26 17:18:01 +0200 (Mon, 26 Apr 2010)
New Revision: 5942
Added:
trunk/eda/fped/tsort.c
trunk/eda/fped/tsort.h
Modified:
trunk/eda/fped/Makefile
trunk/eda/fped/README
trunk/eda/fped/TODO
trunk/eda/fped/fpd.l
trunk/eda/fped/fpd.y
Log:
Added a topological sort algorithm, for use when dumping.
- tsort.h, tsort.c, Makefile: stable topological sort with priorities
- fpd.l, fpd.y: added directive %tsort to test-drive the sort algorithm
- README: documented %tsort
Modified: trunk/eda/fped/Makefile
===================================================================
--- trunk/eda/fped/Makefile 2010-04-25 15:27:27 UTC (rev 5941)
+++ trunk/eda/fped/Makefile 2010-04-26 15:18:01 UTC (rev 5942)
@@ -16,7 +16,7 @@
OBJS = fped.o expr.o coord.o obj.o delete.o inst.o util.o error.o \
unparse.o file.o dump.o kicad.o postscript.o meas.o \
- layer.o overlap.o hole.o \
+ layer.o overlap.o hole.o tsort.o \
cpp.o lex.yy.o y.tab.o \
gui.o gui_util.o gui_style.o gui_inst.o gui_status.o gui_canvas.o \
gui_tool.o gui_over.o gui_meas.o gui_frame.o gui_frame_drag.o
Modified: trunk/eda/fped/README
===================================================================
--- trunk/eda/fped/README 2010-04-25 15:27:27 UTC (rev 5941)
+++ trunk/eda/fped/README 2010-04-26 15:18:01 UTC (rev 5942)
@@ -582,14 +582,15 @@
Experimental: debugging directives
----------------------------------
-For debugging and regression tests, fped supports the following commands
-that mimick the effect of GUI operations:
+For debugging and regression tests, fped supports the following commands,
+most of which mimick the effect of GUI operations:
%del <identifier>
%move <identifier> [<number>] <identifier>
%print <expression>
%dump
%exit
+%tsort { -<id> | +<id> | <id-before> <id-after> [<number>] ... }
%del and %move take as their first argument the name of the vector or
object to manipulate. For this purpose, also objects can be labeled.
@@ -608,3 +609,8 @@
%dump writes the footprint definition in the fped language to standard
output. %exit immediately exits fped, without invoking the GUI.
+
+%tsort is used to test-drive the topological sort algorithm. The items
+in the curly braces are declarations of nodes with (-<id>) or without
+(+<id>) decay or edges in the partial order. The optional number is
+the edge's priority. See tsort.c for details.
Modified: trunk/eda/fped/TODO
===================================================================
--- trunk/eda/fped/TODO 2010-04-25 15:27:27 UTC (rev 5941)
+++ trunk/eda/fped/TODO 2010-04-26 15:18:01 UTC (rev 5942)
@@ -69,7 +69,6 @@
- live update of value when entering strings and expressions ?
- advanced: non-standard solder mask
- advanced: solder paste exceptions (subtractive, additive)
-- advanced: holes
- advanced: silk line width
- future: consider editing non-canvas items (e.g., variable names/values) in
place
Modified: trunk/eda/fped/fpd.l
===================================================================
--- trunk/eda/fped/fpd.l 2010-04-25 15:27:27 UTC (rev 5941)
+++ trunk/eda/fped/fpd.l 2010-04-26 15:18:01 UTC (rev 5942)
@@ -133,6 +133,8 @@
return TOK_DBG_DUMP; }
<INITIAL>"%exit" { BEGIN(NOKEYWORD);
return TOK_DBG_EXIT; }
+<INITIAL>"%tsort" { BEGIN(NOKEYWORD);
+ return TOK_DBG_TSORT; }
<INITIAL>[a-zA-Z_][a-zA-Z_0-9]*: { *strchr(yytext, ':') = 0;
yylval.id = unique(yytext);
Modified: trunk/eda/fped/fpd.y
===================================================================
--- trunk/eda/fped/fpd.y 2010-04-25 15:27:27 UTC (rev 5941)
+++ trunk/eda/fped/fpd.y 2010-04-26 15:18:01 UTC (rev 5942)
@@ -22,6 +22,7 @@
#include "meas.h"
#include "gui_status.h"
#include "dump.h"
+#include "tsort.h"
#include "fpd.h"
@@ -46,7 +47,9 @@
static const char *id_sin, *id_cos, *id_sqrt;
+static struct tsort *tsort;
+
static struct frame *find_frame(const char *name)
{
struct frame *f;
@@ -289,7 +292,7 @@
%token TOK_MEAS TOK_MEASX TOK_MEASY TOK_UNIT
%token TOK_NEXT TOK_NEXT_INVERTED TOK_MAX TOK_MAX_INVERTED
%token TOK_DBG_DEL TOK_DBG_MOVE TOK_DBG_PRINT TOK_DBG_DUMP
-%token TOK_DBG_EXIT
+%token TOK_DBG_EXIT TOK_DBG_TSORT
%token <num> NUMBER
%token <str> STRING
@@ -481,8 +484,41 @@
{
exit(0);
}
+ | TOK_DBG_TSORT '{'
+ {
+ tsort = begin_tsort();
+ }
+ sort_items '}'
+ {
+ void **sort, **walk;
+
+ sort = end_tsort(tsort);
+ for (walk = sort; *walk; walk++)
+ printf("%s\n", (char *) *walk);
+ free(sort);
+ }
;
+sort_items:
+ | sort_items '+' ID
+ {
+ add_node(tsort, (void *) $3, 0);
+ }
+ | sort_items '-' ID
+ {
+ add_node(tsort, (void *) $3, 1);
+ }
+ | sort_items ID ID opt_num
+ {
+ struct node *a, *b;
+
+ /* order is important here ! */
+ a = add_node(tsort, (void *) $2, 0);
+ b = add_node(tsort, (void *) $3, 0);
+ add_edge(a, b, $4.n);
+ }
+ ;
+
table:
TOK_TABLE
{
Added: trunk/eda/fped/tsort.c
===================================================================
--- trunk/eda/fped/tsort.c (rev 0)
+++ trunk/eda/fped/tsort.c 2010-04-26 15:18:01 UTC (rev 5942)
@@ -0,0 +1,160 @@
+/*
+ * tsort.c - Topological sort
+ *
+ * Written 2010 by Werner Almesberger
+ * Copyright 2010 by Werner Almesberger
+ *
+ * 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.
+ */
+
+/*
+ * We use a slight variation of Kahn's algorithm. The difference is that we add
+ * a priority. Edges with the highest priority get selected before edges with
+ * lower priority.
+ *
+ * We maintain the initial list of nodes in the order in which they were added.
+ * Therefore, the first node with inbound edges will always be sorted first.
+ * E.g., the root frame.
+ *
+ * add_node and add_edge can be invoked multiple times with the same
+ * parameters. In the case of add_node, simply the existing node is returned.
+ * In the case of add_edge, the new edge's priority is added to the priority of
+ * the previous edges.
+ *
+ * Priority is accumulated in a node until the node is output. If a node has
+ * the "decay" flag set, it resets the priorities of all other nodes when
+ * output. E.g., when outputting a vector, all priorities accumulated from
+ * previous vectors (towards referencing them with ".") lose their effect.
+ *
+ * Last but not least, the algorithm is stable: a pre-existing order that
+ * conflicts neither with the partial order nor the priorities is preserved.
+ *
+ * Thus, we have the following sorting criteria, in decreasing importance:
+ * - the destination if an edge never precedes its origin
+ * - higher priority comes before lower priority
+ * - earlier add_node comes before later
+ */
+
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <limits.h>
+
+#include "util.h"
+#include "tsort.h"
+
+
+struct edge {
+ struct node *to;
+ int priority; /* edge priority */
+ struct edge *next;
+};
+
+struct node {
+ void *user;
+ struct edge *edges; /* outbound edges */
+ int incoming; /* number of incoming edges */
+ int priority; /* cumulative node priority */
+ int decay; /* all node prio. decay after issuing this */
+ struct node *next;
+};
+
+struct tsort {
+ struct node *nodes;
+ struct node **next_node;
+ int n_nodes;
+};
+
+
+void add_edge(struct node *from, struct node *to, int priority)
+{
+ struct edge **edge;
+
+ for (edge = &from->edges; *edge; edge = &(*edge)->next)
+ if ((*edge)->to == to) {
+ (*edge)->priority += priority;
+ return;
+ }
+ *edge = alloc_type(struct edge);
+ (*edge)->to = to;
+ (*edge)->priority = priority;
+ (*edge)->next = NULL;
+ to->incoming++;
+}
+
+
+struct node *add_node(struct tsort *tsort, void *user, int decay)
+{
+ struct node *node;
+
+ for (node = tsort->nodes; node; node = node->next)
+ if (node->user == user)
+ return node;
+ node = alloc_type(struct node);
+ node->user = user;
+ node->edges = NULL;
+ node->incoming = 0;
+ node->priority = 0;
+ node->decay = decay;
+ node->next = NULL;
+ *tsort->next_node = node;
+ tsort->next_node = &node->next;
+ tsort->n_nodes++;
+ return node;
+}
+
+
+struct tsort *begin_tsort(void)
+{
+ struct tsort *tsort;
+
+ tsort = alloc_type(struct tsort);
+ tsort->nodes = NULL;
+ tsort->next_node = &tsort->nodes;
+ tsort->n_nodes = 0;
+ return tsort;
+}
+
+
+void **end_tsort(struct tsort *tsort)
+{
+ struct node **walk, **first, *node;
+ struct edge *edge;
+ void **res;
+ int n = 0;
+
+ res = alloc_size(sizeof(void *)*(tsort->n_nodes+1));
+ while (1) {
+ first = NULL;
+ for (walk = &tsort->nodes; *walk; walk = &(*walk)->next) {
+ if ((*walk)->incoming)
+ continue;
+ if (!first || (*first)->priority < (*walk)->priority)
+ first = walk;
+ }
+ if (!first)
+ break;
+ if ((*first)->decay)
+ for (node = tsort->nodes; node; node = node->next)
+ node->priority = 0;
+ node = *first;
+ *first = node->next;
+ res[n++] = node->user;
+ while (node->edges) {
+ edge = node->edges;
+ edge->to->incoming--;
+ edge->to->priority += edge->priority;
+ node->edges = edge->next;
+ free(edge);
+ }
+ free(node);
+ }
+ if (tsort->nodes) /* we have at least one cycle */
+ abort();
+ free(tsort);
+ res[n] = NULL;
+ return res;
+}
Added: trunk/eda/fped/tsort.h
===================================================================
--- trunk/eda/fped/tsort.h (rev 0)
+++ trunk/eda/fped/tsort.h 2010-04-26 15:18:01 UTC (rev 5942)
@@ -0,0 +1,25 @@
+/*
+ * tsort.h - Topological sort
+ *
+ * Written 2010 by Werner Almesberger
+ * Copyright 2010 by Werner Almesberger
+ *
+ * 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.
+ */
+
+#ifndef TSORT_H
+#define TSORT_H
+
+struct node;
+struct tsort;
+
+struct node *add_node(struct tsort *tsort, void *user, int decay);
+void add_edge(struct node *from, struct node *to, int priority);
+
+struct tsort *begin_tsort(void);
+void **end_tsort(struct tsort *tsort);
+
+#endif /* !TSORT_H */
More information about the commitlog
mailing list
