\documentclass[11pt,a4paper]{article} % save as utf-8-emacs-unix % 2006-07-07 EW Adventures-1.tex % 2006-07-22 EW Adventures-2.tex % 2006-08-14 EW Adventures-2a.tex % 2007-01-10 EW Adventures-3.tex % 2007-01-13 EW Adventures-4.tex % 2008-11-14 EW Adventures-5.tex % 2011-01-07 EW Adventures-6.tex: rs485+mpc % 2011-02-14 EW Adventures-7.tex: list % % Aufgebessert nachdem ich 'ne Reihe Optimierungen gemacht hatte % Und dann nochmal komplett umgeräumt! % % language support \usepackage[german]{babel} %\usepackage{german} \usepackage[utf8]{inputenc} % can use Umlauts now ü instead of "u %\usepackage{lmodern} % better fonts %\usepackage{pslatex} % use native PostScript fonts %\usepackage{cm-super} \usepackage{url} % \url{} \path{} with correct "hyphenation" %\usepackage{fancyvrb} % for code examples % \voffset-10mm % \pagestyle{empty} % \pagestyle{plain} % \pagestyle{headings} % \renewcommand{\baselinestretch}{1.08} %\usepackage{xspace} \parindent=0pt %\newcommand{\amforth}{\texttt{amforth}} %\newcommand{\zB}{z.\,B.\ } \begin{document} \title{Adventures in \texttt{\textbf{am}}Forth 7: Eine einfache Liste} \author{Erich Wälde} \maketitle %\begin{multicols}{2} % -------------------------------------------------------------------- %\section{Intro} %\label{sec:intro} \begin{abstract}\itshape Auf meinen Messstationen wollte ich die Information über die angeschlossenen Sensoren so verwalten, dass ich jederzeit neue Sensoren dazuhängen kann, ohne den Kontroller neu zu programmieren. Ich wollte eine einfach verkettete Liste, auch wenn ein Vektor mit zehn Einträgen wahrscheinlich weit gereicht hätte. Ich habe mich für eine sehr simple, einfach verkettete Liste entschieden. Der gezeigte Quelltext bezieht sich auf \texttt{\textbf{am}}Forth $4.2$. \end{abstract} \begin{multicols}{2} % -------------------------------------------------------------------- \section{Paarweise Zellen} \label{sec:intro} Der Eintrag in einer einfach verketteten Liste besteht nur aus zwei Feldern: \begin{enumerate} \item die Adresse des nächsten Eintrags (\texttt{next}) \item der zu speichernde Wert (\texttt{value}) \end{enumerate} Das Ende der Liste markiere ich, indem das erste Feld den Wert null erhält. Der Kopf (Anfang) der Liste (\texttt{head}) wird in einer Variablen aufbewahrt, am besten in einer nicht--flüchtigen Variablen vom Typ \texttt{value}. {\small \begin{verbatim} 0 value LISTE \ define head \end{verbatim} } Um einen Eintrag am Anfang der Liste einzufügen, definiere ich das Wort \texttt{list.add}, welches auch \textit{unshift} heißen könnte. {\small \begin{verbatim} : list.add ( value head -- new.head ) dp >r \ save new.head , \ store head as "next" , \ store "value" r> \ new.head on stack ; \end{verbatim} } An der nächsten freien Adresse im Flash-Speicher (\texttt{dp}) werden der Zeiger auf den nächsten Eintrag und der zu speichernde Wert eingetragen. Der Wert kann natürlich ebenfalls eine Adresse sein, z.B.\ die Adresse einer Funktion oder eines weiteren Datenfelds. Die beiden Felder sind von der Größe \texttt{cell}, also $2$\,Byte. Die Adresse des Eintrags verbleibt auf dem Stack und kann dann in \texttt{head} eingetragen werden. \textbf{Vorsicht:} Die Worte \texttt{dp} und \texttt{here} heißen in den \texttt{\textbf{am}}Forth--Versionen vor $4.0$ \texttt{here} und \texttt{heap}. Im ersten Eintrag der Liste soll die Zahl \texttt{\$0042} gespeichert werden: {\small \begin{verbatim} > 0 value LISTE LISTE hex . 0 ok > $0042 LISTE list.add to LISTE ok > LISTE . 11B9 ok > \end{verbatim} } Das bei jedem Eintrag benötigte Quelltext--Fragment lässt sich auch schöner schreiben. Noch schöner wäre allerdings ein Wort, welches zum Namen eines Listenkopfs das zugehörige Wort definiert. {\small \begin{verbatim} : >LISTE ( value -- ) LISTE list.add to LISTE ; \end{verbatim} } Um den Inhalt der Liste auszugeben, definieren wir drei Worte: {\small \begin{verbatim} : list.next ( addr -- addr' ) i@ ; : list.value ( addr -- value ) 1+ i@ ; : list.show ( 'head -- ) dup 0= if drop exit then begin dup 4 u0.r space \ flash addr dup list.next 4 u0.r space dup list.value 4 u0.r cr list.next dup 0= until drop ; \end{verbatim} } {\small \begin{verbatim} > LISTE list.show 11B9 0000 0042 ok > $08FF >LISTE ok > LISTE list.show 11BB 11B9 08FF 11B9 0000 0042 ok > \end{verbatim} } Diese Liste ist sehr einfach. Man kann nur am Anfang neue Werte hinzufügen und die ganze Liste ausgeben. Die Werte werden in umgekehrter Reihenfolge des Speicherns ausgegeben, was u.U.\ stört. Immerhin muss die Liste nicht am Stück im Speicher liegen. Man kann bequem noch ein paar Worte definieren, und danach weitere Einträge für die Liste. Mit der Liste will man irgendwann etwas Konkretes anfangen, sonst bräuchte man sie nicht. Also schreibe ich eine Funktion, die einen Zeiger auf eine weitere Funktion und den Kopf einer Liste als Argumente bekommt und dann die übergebene Funktion auf alle gespeicherten Werte anwendet. {\small \begin{verbatim} : list.walk ( xt head -- ) dup 0= if drop drop exit then begin \ -- xt item over over \ -- xt item xt 'list.item list.value \ -- xt item xt value swap \ -- xt item value xt execute \ -- xt item list.next \ -- xt next dup 0= until drop drop ; \end{verbatim} } Die übergebene Funktion verbraucht den obersten Wert auf dem Stack (\texttt{value}), produziert aber keine Rückgabewerte. {\small \begin{verbatim} > : doit ( value -- ) 6 u0.r cr ; ok > ' doit LISTE list.walk 0008FF 000042 ok \end{verbatim} } Ausgerüstet mit diesen Worten, erzeuge ich eine Liste, in der die Werte weitere Adressen sind. Sie verweisen auf Datenstrukturen, in denen alles Wissenswerte über einen bestimmten Sensor zu finden ist, etwa wie man einen aktuellen Wert beschaffen kann, oder wie der beschaffte Wert weiterverarbeitet wird. Eine regelmäßig aufgerufene Funktion (\texttt{data.collect}) arbeitet dann die Liste ab. Die Werte werden im RAM abgelegt und nicht auf dem Stapel behalten. Kommen jetzt neue Sensoren an den Kontroller, dann erzeuge ich für jeden eine neue Datenstruktur und verlinke sie zusätzlich in der Liste der Sensoren. Mit dem nächsten Aufruf von \texttt{data.collect} werden auch die neuen Sensoren gelesen. Weitere Funktionen \texttt{data.ls} und \texttt{data.reset} versenden die gesammelten Daten bzw.\ löschen die entsprechenden Speicherbereiche. Für eine ordentliche Liste fehlen weitere Funktionen, die einen bestimmten Eintrag aufsuchen, löschen, oder einen zusätzlichen Eintrag dazwischen verlinken. Für meine Anwendung habe ich das allerdings nicht gebraucht. % -------------------------------------------------------------------- \section{Referenzen} \begin{enumerate} %\item \label{Adv1} E. Wälde, Adventures in Forth, Die 4. Dimension 3/2006, Jahrgang 22 % gforth-ec r8c, i2c von Hand, Thermometer %\item \label{Adv2} E. Wälde, Adventures in Forth 2, Die 4. Dimension 4/2006, Jahrgang 22 % timeup Uhr und Kalender, twotask %\item \label{Adv3} E. Wälde, Adventures in Forth 3, Die 4. Dimension 1/2007, Jahrgang 23 % usart0, redirection %\item \label{Adv4} E. Wälde, Adventures in Forth 4, Die 4. Dimension 1/2007, Jahrgang 23 % dcf-77 Uhr %\item \label{Adv5} E. Wälde, Adventures in Forth 5, Die 4. Dimension 4/2008, Jahrgang 24 % Umstieg auf amforth, bit flags, sensor:, filter_mean: %\item \label{r8c-ds} Renesas R8C/13 datasheet auf \url{www.renesas.com} %\item \label{Koenig} A.\ König und M.\ König, Das PICmicro Profi Buch, Franzis % Verlag 1999, ISBN 3-7723-4284-1 %\item \label{SPelc} Stephen Pelc, Programming Forth, \\ \url{http://www.mpeforth.com/arena/ProgramForth.pdf} %\item \label{Deliano} \url{http://www.embeddedforth.de/emb3.pdf} S.\ 9 %\item \label{dcf} \url{http://de.wikipedia.org/wiki/DCF77} und Verweise darin %\item \label{willem} ByteForth von Willem Ouwerkerk,\\ \url{http://www.forth.hccnet.nl/byteforth.htm} \item \label{amforth} \url{http://amforth.sourceforge.net/} %\item \label{ron} Ron Minke, Forth von der Pike auf Die 4. Dimension 3+4/2005 \ldots 4/2006, sowie Sonderheft AVR und 3+4/2007 %\item \label{namedbits} M. Kalus, M. Trute, Named Bits, Die 4. Dimension 2/2007, Jahrgang 23 %\item \label{lubos} Lubo\v{s} P\v{e}kn\'{y}s Seite: \url{http://www.forth.cz} %\item \label{RS485} Wikipedia (RS485) \url{de.wikipedia.org/wiki/RS485} %\item \label{RS485a} \url{www.mikrocontroller.net/articles/RS-485} %\item \label{g4.fs} Michael Kalus: g4.fs \url{www.forth-ev.de/repos/g4/g4.fs} %\item \label{atmega32} atmega32 Datenblatt (doc2503.pdf) \url{www.atmel.com} \end{enumerate} \end{multicols} %\newpage % -------------------------------------------------------------------- \section{Listings} \begin{quote} \begin{small} \begin{multicols}{2} \listinginput[1]{1}{2011-02/list.fs} \end{multicols} \end{small} \end{quote} \end{document}