doppelt verkettete List mit AVR?

[Bjoern (Gast)]

Hallo, ich möchte um den Speicher meines AVR's zu schonen gerne eine 
doppelt verkettete List schreiben, jedoch gehts das irgendwie ständig 
schief. Ich komme eigentlich aus der C++ Programmierung und habe die 
befürchtung, dass ich irgendeinen blöden Denkfehler zwischen C++ und C 
habe, da ich mit structs eher weniger Arbeite.

Ich hoffe ihr könnt mir da ein wenig weiterhelfen...
Das Problem fängt direkt bei dem

addr->back;
addr->next; usw. an

Als fehlermeldung bekomme ich:
error: dereferencing pointer to incomplete type
irgendwie verstehe ich die fehlermeldung so direkt nicht, daher habe ich 
alle erforderlichen Structs einfach mal mit eingepostet, ich hoffe mal 
das der Code einigermaßen übersichtlich ist...

/*****************************************************************
*      Structs fuer alle:
*      wichtigen Kenngroessen
*****************************************************************/
typedef struct {

  unsigned  Licht:1;
  unsigned   DimmWert:4;
  unsigned  AmbientLights:1;
  uint8_t   EinschaltVerz;  
  uint8_t    AusschaltVerz;  
  uint8_t    Grp;  
}Light;

typedef struct {

  unsigned   State:1;    
  unsigned   StateBevor:1;          
  unsigned   Timer:3;
  unsigned   Klicks:2;    
  uint8_t    Grp;      
  

}Switch;

/*****************************************************************
*    Structs fuer verkettete List:
*    ist teil von Switch und Light
*****************************************************************/

typedef struct {
  struct SwitchList *back;
  struct SwitchList *next;
  Switch switchData;  
  
}SwitchList;

typedef struct {
  struct LightList *back;
  struct LightList *next;
  Light  lightData;

}LightList;

/*****************************************************************
*      Funktionenfuer verkettete List:
*          
*****************************************************************/

struct SwitchList* newList( uint8_t Schalter){
  struct SwitchList *addr = ( struct SwitchList* ) malloc(sizeof( SwitchList ));
  addr->back=NULL;
  addr->next=NULL;
  ldHandlerSchalter(Schalter, & (addr->switchData));
  return addr;
}

[Jörg W. (dl8dtl) (Moderator)]

In C++ ist der Name eines struct-Typs ein globaler Name, in C dagegen
existiert er nur in einem Namensraum aller structs und muss mit dem
Wort struct qualifiziert werden:

struct foo {
    struct foo *next, *prev;
    int otherdata;
};

Wenn du partout den globalen Namen ohne struct noch brauchst, dann
kannst du danach (oder parallel) auch noch ein typedef machen:

typedef struct foo foo;

Dieses wäre in C++ entbehrlich, ist aber meiner Meinung nach in
dieser Form (d. h. beide Namen sind gleich) dort aus Kompatibilitäts-
gründen zulässig.

[Bjoern (Gast)]

ahh ok, habe auch gerade meinen Fehler gefunden:
ich poste diesen einfach mal vollständigkeitshalber, damit es evtl. 
anderen weiterhilft.
PS: danke für die schnelle Antwort...

struct SwitchList* newList( uint8_t Schalter){
  SwitchList *addr = ( SwitchList* ) malloc(sizeof( SwitchList ));
  addr->back=NULL;
  addr->next=NULL;
  ldHandlerSchalter(Schalter, & (addr->switchData));
  return addr;
}

[Klaus F. (kfalser)]

Wobei noch anzumerken wäre, dass malloc() in einem AVR eigentlich nichts 
zu suchen hat.

[Jörg W. (dl8dtl) (Moderator)]

Klaus Falser wrote:
> Wobei noch anzumerken wäre, dass malloc() in einem AVR eigentlich nichts
> zu suchen hat.

Humbug.  Prinzipienreiterei.

Zeig mir eine Variante, wie du mit statisch alloziertem Speicher
ein dynamisches Problem so angehst, dass du nicht in vergleichbare
Probleme reinläufst, in die du (bei Vorliegen von mehr
Danteanforderungen als Speicherkapazität, also "overcommittment")
mit malloc() geraten würdest.

Eine doppelt verkettete Liste implementiert man ja nicht, weil man
gerade mal lange Weile hat.

[Bjoern (Gast)]

Ich muss Jörg recht geben, das problem das ich habe, ist, das ich einen 
größeren aber sehr langsamen ausgelagerten Speicher habe. Ich habe 
leider bei der Anwendung extreme Speicher knappheit, meine Idee war es 
nun einfach eine Liste zu implementieren, damit würde sich für mich 
mehrere Vorteile ergeben:
a.) das ständige lesen und schreiben im langsamen Speicher würde 
aufhören.
b.) der Speicher bedarf des programms sinkt
c.) ich muss keine Liste durchlaufen welchen Ausgang ich schalten muss, 
und anschließend nochmal schauen wie der Ausgang nun genau geschaltet 
werden muss.
d.) aufgrund von c. und a. habe ich eine leicht verbesserte laufzeit

[Klaus F. (kfalser)]

@Jörg
Nun, Du kennst den C-Compiler sicher besser als ich, aber ich stelle mir 
vor, dass man die ganzen Routinen zur Heap-Verwaltung sparen kann, wenn 
man malloc nicht verwendet.
Die klassischen Vorurteile betreffen dann weiterhin garbage collection, 
wenn man free verwendet, usw.
Ich muß mir überlegen, wie groß der Heap ist, wie ich das einstelle, 
wieviel Stack mir übrigbleibt ...
Da lege ich lieber eine gewisse Anzahl von Strukturen an. Wenn ich schon 
das Spielchen mit Zeigern und doppelt verketteten Listen (fehlerfrei) 
spielen kann, dann ist der Aufwand einer Liste für freie Objekte auch 
nicht mehr groß.

[Jörg W. (dl8dtl) (Moderator)]

Klaus Falser wrote:

> Nun, Du kennst den C-Compiler sicher besser als ich, aber ich stelle mir
> vor, dass man die ganzen Routinen zur Heap-Verwaltung sparen kann, wenn
> man malloc nicht verwendet.

Nun, meist ist der RAM schneller voll als der Flash-ROM, insbesondere
wenn man Probleme mit dynamischer Datenerfassung hat.  Dir Heap-
Verwaltung belegt in erster Linie Flash-ROM, der erhöhte RAM-Verbrauch
ist gering (wobei du natürlich Recht hast, was die Zeiger in der Liste
angeht, die sind auch Overhead).

> Die klassischen Vorurteile betreffen dann weiterhin garbage collection,
> wenn man free verwendet, usw.

Wenn man malloc() nur dafür nimmt, eine einzige Sorte von struct
damit zu allozieren, ist das überhaut kein Thema.  Da gibt's keine
Chance für irgendeine Fragmentierung.

> Da lege ich lieber eine gewisse Anzahl von Strukturen an. Wenn ich schon
> das Spielchen mit Zeigern und doppelt verketteten Listen (fehlerfrei)
> spielen kann, dann ist der Aufwand einer Liste für freie Objekte auch
> nicht mehr groß.

Womit du mehr oder weniger schlecht malloc() und free() reimplementiert
hättest...

[Klaus F. (kfalser)]

> Womit du mehr oder weniger schlecht malloc() und free() reimplementiert
> hättest...
Wobei ich bei der hausgemachten Implementierung GENAU weiß, was sie tut.

Klassische Paranoia eines embedded Programmierers ...

[Karl H. (kbuchegg)]

  SwitchList *addr = ( SwitchList* ) malloc(sizeof( SwitchList ));

Nimm, den Cast da ganz schnell wieder raus.

1) in C brauchst du ihn nicht, da ein void Pointer allen anderen 
Pointertypen zugewiesen werden kann

2) Gut, spielt auf einem AVR weniger die Rolle, aber im Allgemeinen ist 
es möglich, dass dir dieser Cast einen bösen Fehler verstecken kann.
Nämlich den, dass du vergessen hast, ein Headerfile zu inkludieren, 
welches malloc deklariert. In dem Fall muss der Compiler davon ausgehen, 
dass malloc einen int retourniert (als Standardannahme). Wenn nun auf 
deinem System  sizeof(void*) != sizeof(int), dann geht das böse in die 
Hose.

[Bjoern (Gast)]

ja habe ich gemacht aber ich bekomme grad ein paar kleinere probleme mit 
meinem insertSwitchList und deletSwitchList, wobei deleteSwitchList mir 
2 Errors verursacht...

bei insertNextSwitch bekomme ich folgende Warnings:
assignment from incompatible pointer type

und bei dem deleteSwitchList kommt folgender Error:
error: dereferencing pointer to incomplete Type...

SwitchList* insertNextSwitch( SwitchList *list, uint8_t Schalter ){
  SwitchList *addr = malloc( sizeof ( SwitchList ) );
  addr->back   = list;
  addr->next = NULL;
  list->next = addr;
  ldHandlerSchalter( Schalter, & ( addr->switchData ) );
  return addr;
}

SwitchList* deleteSwitchList( SwitchList *list ){
  list->next->back = list->back;
  list->next->back = list->next;
  return list->back;
}

[Jörg W. (dl8dtl) (Moderator)]

Klaus Falser wrote:

> Wobei ich bei der hausgemachten Implementierung GENAU weiß, was sie tut.

Es hindert dich niemand, dir das malloc() der Bibliothek genauso genau
anzusehen.

[Karl H. (kbuchegg)]

> meinem insertSwitchList und deletSwitchList, wobei deleteSwitchList mir
> 2 Errors verursacht...

Es wäre einfacher, wenn du für uns die fehlerhaften Zeilen markierst.

>
> bei insertNextSwitch bekomme ich folgende Warnings:
> assignment from incompatible pointer type

Wo kriegst du den?

> und bei dem deleteSwitchList kommt folgender Error:
> error: dereferencing pointer to incomplete Type...

dereferencing to incomplete type
bedeutet, dass du über einen Pointer auf eine Struktur zugreifst, der 
Compiler aber die Details der Struktur noch nicht gesehen hat. Daher 
incomplete: er weiß zwar, dass es diese Struktur gibt, sonst hättest du 
keinen Pointer bilden können. Aber der Compiler weiß nicht wie diese 
Struktur aussieht. Daher tut er sich schwer auf eine Komponente der 
Struktur zuzugreifen. Einfach deswegen, weil er nicht weiß an welchem 
Byteoffset innerhalb der STruktur der Member liegt bzw. ob der von dir 
angegebene Komponentenname überhaupt in der STruktur enthalten ist.


> SwitchList* deleteSwitchList( SwitchList *list ){
>   list->next->back = list->back;
>   list->next->back = list->next;

Diese Pointermanipulationen solltest du dir mal aufmalen


    +------+           +-------+        +------+
    |   o------------->|    o---------->|      |
    |      |           |       |        |      |
    |      |<---------------o  |<----------o   |
    +------+           +-------+        +------+
                           ^
                      list |
                       +---|---+
                       |   o   |
                       +-------+

erste Anweisung:     list->next->back = list->back;

    +------+           +-------+        +------+
    |   o------------->|    o---------->|      |
    |      |           |       |        |      |
    |      |<---------------o  |     +-----o   |
    +------+<----+     +-------+     |  +------+
                 |         ^         |
                 +---------|---------+
                           |
                           |
                      list |
                       +---|---+
                       |   o   |
                       +-------+

zweite Anweisung:     list->next->back = list->next;


    +------+           +-------+        +------+
    |   o------------->|    o---------->|      |
    |      |           |       |        |      |
    |      |<---------------o  |     +-----o   |
    +------+           +-------+     |  +------+
                           ^         |      ^
                           |         +------+
                           |
                           |
                      list |
                       +---|---+
                       |   o   |
                       +-------+


Nicht ganz das erhoffte Resultat. Der Node, auf den list zeigt ist nicht 
ausgehängt und freistehend.

Auch die Behandlung der Sonderfälle für erstes und letztes Element nicht 
vergessen. Wenn list auf den letzten Knoten der Liste zeigt, dann 
existiert list->next ganz einfach nicht.

[Stefan E. (sternst)]

Es ist immer noch das gleiche Problem, wie auch schon bei der 
ursprünglichen Fehlermeldung. Der Typ "struct SwitchList" wird nirgendwo 
definiert.

typedef struct {
...
}SwitchList;

->

typedef struct SwitchList{
...
}SwitchList;

PS: Ich vermisse bei deleteSwitchList ein "free".

PPS: Bei insertNextSwitch finde ich, dass der Name ungünstig gewählt 
ist. Schließlich wird das neue Element ja nicht irgendwo eingefügt, 
sondern ans Ende angehängt.

[P. S. (Gast)]

Mal mein Senf dazu: Eine generelle Aussage, dass malloc() auf einem AVR 
falsch waere, ist natuerlich falsch. Aber die Wahrscheinlichkeit, dass 
sich der Entwickler damit mehr Aerger schafft als Nutzen, ist recht 
hoch. Ich rege mich regelmaessig darueber auf, wenn ich in Unix- oder 
Windows-Code statische Arrays finde, aber es gibt nunmal einen 
Unterschied zwischen einer Platform mit MMU, VM und x GB Addressraum und 
einer mit x kB. Speicherfragmentierung sollte man nicht unterschaetzen, 
die reisst auch Systeme mit wesentlich mehr Speicher bei laengeren 
Laufzeiten. Und wenn man wirklich nur eine Strukturgroesse hat, braucht 
man malloc() erst recht nicht...

Wo der OP das Speichersparpotential sieht, ist mir nicht ganz klar. Die 
Listenverwaltung braucht selbst auch Speicher und malloc() selbst 
duerfte auch noch was brauchen. Fragt sich, ob am Ende nicht eher mehr 
verbraucht wird. Da muesste man aber mehr ueber das eigentliche Problem 
wissen.

Wenn dir C++ besser liegt, dann nimm doch einfach C++. Du brauchst nur 
new- und delete-Operatoren, die auf malloc() mappen und schon hast du 
das Gleiche in schoen.

Und vor Allem: Da du anscheinend noch nie eine Listenverwaltung 
geschrieben hast, wuerde ich das erstmal auf dem PC durchexerzieren, bis 
es wirklich sitzt.

P.S: Kann es sein, dass du da die Listenverwaltung fuer jeden konkreten 
Typ nochmal implementierst, statt zu "vererben"?

[Klaus F. (kfalser)]

Vielleicht könnte jemand die STL auf AVR portieren? :-)

[P. S. (Gast)]

Klaus Falser wrote:

> Vielleicht könnte jemand die STL auf AVR portieren? :-)

IMO ist die STL und die "Idee" viele Autoren, C++ muesste frei von C und 
"altmodischen" Methoden gelehrt werden, zu einem grossen Teil schuld 
daran, dass selbst Profis heute oft keine einfachen Datenstrukturen mehr 
implementieren koennen. Du willst gar nicht wissen, was fuer Klopfer man 
im professionellen Umfeld so sieht...

[Klaus F. (kfalser)]

> schuld daran, dass selbst Profis heute oft keine einfachen Datenstrukturen
> mehr implementieren koennen.
So schlimm finde ich das eigentlich nicht, das ist ja genau die Idee 
dahinter. Ob es dann dazu führt, dass die sogenannten Profis nicht mehr 
weissen was sie tun, kann ich nicht beurteilen.
Ich habe eigentlich nichts gegen die STL, ich finde sogar dass sie 
manchman zu wenig verwendet wird.

Aber C/C++ für embeddebed, bzw. Kleinstprozessoren ist eben ganz eine 
andere Geschichte. Der Unterschied zu "normalen" Applikationen ist ja 
die Übersichtlichkeit des Ganzen, da will und muß ich jedes Detail 
verstehen.

Aber der Thread driftet ab ...

[Bjoern (Gast)]

Hallo, ja das delete usw. gefehlt hatte, ist mir aufgefallen. structs 
vererben geht das? ich kanne das nur mit klassen :).
Und ja das ist meine erste Liste und vor allem vll. das 2.te oder 3.te 
mal das ich einen Mikrocontroller Porgrammiere, habe vorher mit VHDL 
halte mealy und moore Automaten "definiert" usw.
so da mehr infos benötigt werden, werde ich einfach mal erzählen wofür 
das ganze nacher da sein soll.

ein Freund von mir baut sich gerade ein Haus und möchte gerne eine 
Haussteuerung haben. es gibt vorerst eine Übergangslösung, die erstmal 
die Lichter normal ein und ausschaltet. diese ist soweit fertig aber in 
meinen Augen recht ineffizient :).
Die Schalter haben drei Funktionen:
1 Klicken => eine Lampe an
2 Klicken => eine gruppe von Lampen an
gedrückt halten => Dimmen

wobei mir das Dimmen extreme Kopfschmerzen bereitet ;) das problem ist, 
das ich ein Signal bekomme, wenn die 230 V ca. +- 10 V vor dem 
nulldurchgang ankommen, dann sollen die (elektronischen) Relais nach 
einer bestimmten Zeit eingeschaltet werden, und so eine Dimmung 
stattfinden.
Wobei ich glaube das mein Programmcode für sowas zulangsam wäre... daher 
muss ich mir evtl. später was anderes einfallen lassen...

Der AVR bzw. das soll später der "Haupt"AVR sein, soll dann anfangen 
diese Dinge zu interpretieren, da die Ausgänge gemultiplext sind, wollte 
ich diese Schalter Abfrage und das ausgeben der Lampen Signale einfach 
in jeweilige Funktionen einbauen.
Es soll einen Speicher geben mit 64kB der dann standard werte ausgibt 
dafür die Funktion ldHandlerSwitch.
Im späteren verlauf, soll dann ein embedded Webserver + eine Controll 
Unit angeschlossen werden, über den man dann zentral Lichter ein/aus 
schalten kann. Eine extra Karte ist für einen rnd Generator gedacht. 
Ausserdem sollen evtl. später noch ein Serieller Bus sowie ein Funkmodul 
mit eingebracht werden jeweils wieder extra Karten.

PS: ich habe die Liste komplett neu geschrieben und eine einfach 
verkettete Liste gemacht. Diese funktioniert auf meinem Rechner bisher 
wunderbar.
Habe auch hier den befehl Free() eingebaut. Es sollen nun noch 3 
Funktionen hinein kommen, die eine Sucht nach einem bestimmten Schalter, 
die andere nach einer Gruppe und last but not least sucht die dritte 
Funktion nach abgelaufenen Timern und Löscht ggF. dieses Element der 
Liste.

PPS: Ich weiß für einen Anfänger in der AVR Programmierung habe ich mir 
ein ganz großen Batzen Arbeit eingeholt. Was denke ich nicht unbedingt 
immer ganz vom Vorteil ist, aber ich möchte es dennoch versuchen dies zu 
programmieren und ich denke mal wenn ich genug Zeit investiere, habe ich 
frühher oder später das gewünschte Ergebnis - auch wenn es nicht gleich 
perfekt ist :).

[P. S. (Gast)]

Bjoern wrote:
> Hallo, ja das delete usw. gefehlt hatte, ist mir aufgefallen. structs
> vererben geht das? ich kanne das nur mit klassen :).

Du musst OO mehr als Philosophie auffassen ;-)

Hier hast du also

struct Node { ...};

und hast, sagen wir mal, Light, was du in der Liste verwalten willst. 
Light soll also von Node erben. Das geht am einfachsten so:

struct Light
{
  struct Node listNode;

  ...
};

Willst du dein Light an eine Listenfunktion uebergeben, uebergibst eben 
Light.listNode oder castest du einfach auf Node  - das passt, da Light 
ja mit dem Node anfaengt. Zurueck geht es nur mit dem Cast, man muss nur 
wissen, was fuer Typen man da in der Hand hat ;-)

Problematisch wird es, wenn dein Light von mehr als einer Sache erben 
soll, dann reicht ein einfacher cast nicht mehr. Erbt Light z.B. noch 
von "Something":

struct Light
{
  struct Node listNode;
  struct Something something;

  ...
};

Dann kannst du nicht einfach von Something auf Light casten - da 
braeuchte man eine kleine Hilfsfunktion oder ein Makro um das halbwegs 
ordentlich zu machen.

Da sieht man gleich, wieso hier C++ praktischer ist, selbst wenn die 
Klassen nicht mal Methoden, Konstruktoren, etc, pp. haben. Du brauchst 
uebrigens nicht mal new und delete, du kannst die Klassen immer noch 
verwenden wie Strukturen, sie einfach per malloc() anlegen - es wird 
dann halt kein Konstruktor aufgerufen und keine Initialisierung gemacht.

> Und ja das ist meine erste Liste und vor allem vll. das 2.te oder 3.te
> mal das ich einen Mikrocontroller Porgrammiere, habe vorher mit VHDL
> halte mealy und moore Automaten "definiert" usw. so da mehr infos
> benötigt werden, werde ich einfach mal erzählen wofür das ganze nacher
> da sein soll.

Wenn du dich eine Weile mit Listen geplagt hast, deren Elemente von Node 
erben (wie auch immer implementiert), faellt dir wahrscheinlich auf, 
dass es unschoen ist eine Klasse von Node erben zu lassen, nur weil man 
sie in einer Liste verwalten will. Vor allem geht das schnell schief, 
wenn man die Elemente in 2 verschiedenen Listen verwenden will... 
deshalb arbeiten eigentlich die meissten mir bekannten Listen mit 
Zeigern auf die zu verwaltetenden Objekte (oder wie STL mit Kopien von 
Typen, die auch Zeiger sein koennen, aber lassen wir mal STL beiseite), 
z.B. so:

struct Node
{
  struct Node next, prev;

  void* content;
};

Die Geschichte koennte man noch lange weiter fuehren, nicht umsonste 
gibt es zu Algorithmen und Datenstrukturen dicke Buecher...

> PS: ich habe die Liste komplett neu geschrieben und eine einfach
> verkettete Liste gemacht. Diese funktioniert auf meinem Rechner bisher
> wunderbar.

Zeig doch mal deine AddNode und RemoveNode Funktionen, dann haben wir 
was zum Zerpfluecken ;-)

> Habe auch hier den befehl Free() eingebaut. Es sollen nun noch 3
> Funktionen hinein kommen, die eine Sucht nach einem bestimmten Schalter,
> die andere nach einer Gruppe und last but not least sucht die dritte
> Funktion nach abgelaufenen Timern und Löscht ggF. dieses Element der
> Liste.

Ich wuerde mir trotzdem ueberlegen, ob's ein Array mit limitierter 
Groesse nicht auch tut ;-)

[Björn C. (bjoernc)]

So hier einfach mal insertNextSwitch und deleteSwitchList, wobei ich mir 
für deleteSwitchList nochmal einen neuen Namen überlegen sollte - der 
ist recht irreführend :)

void insertNextSwitch( struct SwitchList *list, uint8_t Light ){
  struct SwitchList *addr;
  if( list == NULL ){
    list = malloc ( sizeof ( struct SwitchList ) );
    addr->next = NULL;
  }//endif
  else{
  /*************************************
  *  nach Ende suchen
  *************************************/
    while( addr->next != NULL ){
      addr=addr->next;
    }//endwhile
    addr->next = malloc ( sizeof ( struct SwitchList ) );
    addr->next->next=NULL;
  //  ldHandlerSchalter( Light, & (addr->next->switchData) );
  }//end else
}
void deleteSwitchList( struct SwitchList *list ){
                //nur ein Element vorhanden?
    if( list->next==NULL ){
      free(list);
                        list=NULL;
    }//end if
                //wird letztes Element geloescht?
     else if ( list->next->next == NULL ){
      free(list->next);
      list->next=NULL;
    }//end else if
                // rechts neben mir befindliches Element loeschen
    else 
      list->next=list->next->next->next;
      free(list->next);
}

[P. S. (Gast)]

Björn Cassens wrote:
> So hier einfach mal insertNextSwitch und deleteSwitchList, wobei ich mir
> für deleteSwitchList nochmal einen neuen Namen überlegen sollte - der
> ist recht irreführend :)

Interessanter Ansatz, die Liste gleich ganz zu loeschen, wenn sie leer 
ist - also ohne Listenkopf oder so zu arbeiten.

Du hast hier nur 2 Probleme, einmal beim Anlagen der Liste, da du das 
erste Element nur im lokalen Zeiger "list" speicherst. Genauso beim 
Loeschen, du setzt auch hier nur den lokalen Zeiger auf NULL.

Schnellster Fix waere, die Referenz auf diesen Zeiger zu uebergeben.

[Björn C. (bjoernc)]

Ja ähm habe mir grad den Programmcode nochmal angeschaut ich übergebe 
immer (&ptr) damit eine call by reference hat auch den Vorteil, das 
keine Kopie des Zeigers angelegt werden muss, und so wieder ein bissl 
Speicher eingespart wird :)
wie ist das überhaupt in C muss ich um einen void* zu dereferenzieren 
diesen vorher mit *(static_cast<ZielTyp>(void*ptr)) casten, ich glaub in 
C sieht der Cast so aus (ZielTyp*) oder?
[edit] ich dachte vorher immer das ich mich als fortgeschrittener 
Programmierer sehen darf aber irgendwie kommt in mir gerade das gefühl 
hoch, das ich mich sehr überschätzt habe ...
[/edit]

[Klaus F. (kfalser)]

Bjoern wrote:

> wobei mir das Dimmen extreme Kopfschmerzen bereitet ;) das problem ist,
> das ich ein Signal bekomme, wenn die 230 V ca. +- 10 V vor dem
> nulldurchgang ankommen, dann sollen die (elektronischen) Relais nach
> einer bestimmten Zeit eingeschaltet werden, und so eine Dimmung
> stattfinden.
> Wobei ich glaube das mein Programmcode für sowas zulangsam wäre... daher
> muss ich mir evtl. später was anderes einfallen lassen...

Ich glaube, Du denkst viel zu komplizert.
Wenn ich dich richtig verstanden habe, dann möchtest du eine Art 
Phasenanschnittssteuerung bauen. Je nachdem wieviele Lampen du 
unterschiedlich dimmen möchtest wird der Rechenleistungsbedarf 
unterschiedlich groß sein, sollte aber locker ausreichen.
Du muß nur die Eigenheiten eines Microcontrollers ausnützen, also z.B. 
die Timer und die Interrupts. Versuche dir zu überlegen, welche Teile 
häufig, also wiederkehrend ausgeführt werden müssen und welche eher 
selten.
Z.B. wird die Neuberechnung des Einschaltzeitpunkts eher selten nötig 
sein, und wenn der Benutzer den Schalter drückt, dann genügt es alle 50 
- 100 ms die Lichtleistung anzupassen, das ist schnell genug.
Für die Phasenanschnittsteuerung könntest du z.B. Timer verwenden. Wenn 
Du das Intervall der 10 ms Halbperiode in 100 Stufen teilst (sollte 
ausreichen), dann hast du alle 100 us einen Interrupt. In dieser Routine 
machst Du nichts anderes, als aus einer vorberechneten Tabelle von 100 
Einträgen die Ports mit den Ausgängen zu aktualisieren. Bei jedem 
0-Durchgang beginnt die Tabelle von vorne. Das ist schnell braucht kaum 
Resourcen.
Ändert der Benutzer den Dimm-Wert, wird die Tabelle neu berechnet. Das 
kann auch langsam erfolgen.

[Björn C. (bjoernc)]

ja also ich hatte mir folgendes überlegt, ich habe ja 3 Timer, einer 
davon wird dann über den Interrupt getriggert - sofern das geht.
dieser soll dann die Zeit 20ms/Schritte wiederrum einen Interrupt 
erzeugen, so das ich dann weiß, das evtl. etwas geschaltet werden muss 
anhand eines Zaehlers weiß ich dann ungefähr bei welchem Zeit Abschnitt 
ich bin und kann dann mittels DimmWert herausfinden welchen Ausgang ich 
schalten muss :)
Ein anderer Timer (erzeugt auch interrupt) soll mir dann die 
Hold/GetTime für die Ausgänge/Eingänge bereitstellen.
Und der dritte soll mir dann wiederum einen eine Hold/Get Time für den 
Speicher Baustein bereitstellen, ich habe zwei Get/Holdtimes weil diese 
sich extrem unterscheiden bauteilbedingt - aber evtl. finde ich später 
eine Lösung dafür, so das ich dann mit nur ncoh 2 Timern auskomme ;).
achja und der 2 Timer wird auchnoch dazu benutzt, zu triggern, wann ich 
schalterwerte hole und wann ich Ausgängeschalten ich dachte so eine 
Abtastrate von 0.1 s würde ausreichen, aber das hast du schon vorher 
geschrieben :) von daher ist meine Annahme dann richtig denke ich :)

[Michael Wilhelm (Gast)]

Björn, das funktioniert aber nur, wenn ale Lampen an der gleichen Phase 
hängen.

MW

[Klaus F. (kfalser)]

Das mit den Hold/Get Time habe ich zwar nicht nicht verstanden, aber als 
Tipp für die verschieden schnellen Dinge die zu erledigen sind :
Wie wäre es mit einem Mini RTOS? AvrX läuft wunderbar mit Taktrate 1ms 
und kann man dazu verwenden periodische Aufgaben auszuführen, die jetzt 
nicht 100% auf die Microsekunde laufen müssen. Der große Vorteil ist 
dass die einzelnen Tasks (logische Funktionen) von der Beschreibung her 
sauber getrennt sind. Wartbarkeit und Verständis des Programms erhöht 
sich gewaltig.

[Björn C. (bjoernc)]

ähm ja das stimmt wohl ;), aber da die Phasenverschiebung zu Jeder Phase 
120° beträgt, kann man wenn man weiß das Phase 1 gerade den 0 Durchgang 
hat, ja die anderen Phasen diesen Delay später schalten - aber gut das 
du mich darauf hinweist, ansonsten hätte ich das total vergessen und es 
wäre dann total in die Hose gegangen :) - Danke dh. ich muss dann 
ncohmal die Phasen miteinbringen irgendwo :)

So die Delete Funktion funktioniert soweit auch - muss sie nur noch 
ausgiebig mit dem Compiler quälen :)

ich habe mir mal gedacht das eine art Garbage collektor vielleicht recht 
sinnvoll ist, die sich am Ende der Endlos-Whileschleife befindet...
dieser sucht nun nach ausgeschalteten Schaltern bei denen das TTL Feld 
abgelaufen ist und löscht dieses Element.
Die Liste ansich funktioniert soweit ganz gut, habs grad nochmals mit 
dem  Compiler und fprint ausprobiert - dabei sind mir ncoh sehr viele 
Fehler in der Pointer dereferenzierung aufgefallen :) - diese habe ich 
jetzt behoben.

[Michael A. (micha54)]

Peter Stegemann wrote:
> Ich wuerde mir trotzdem ueberlegen, ob's ein Array mit limitierter
> Groesse nicht auch tut ;-)

Hallo,

also so einfach wie Du sehe ich das nicht.
Auch für Microcontroller wie einen Mega8 mit seinen geringen Resourcen 
benutze ich das dynamische malloc - allerdings ohne free.

Damit erzeuge ich generische fifos unterschiedlicher Grösse, und der 
Code kann sie alle bearbeiten, also 4 Zeichen für Tastaturpuffer, und 32 
für das Display 2x16 oder 128 Zeichen für das grosse 4x40 auf einem 
Mega32.

Zur Zeit gehe ich ebenso mit I2C-Request-Puffern um, die je nach 
Zieladdresse unterschiedliche - aber feste - Grössen haben, also 
Keybord=1, Display=16, EEprom=2

Die mallocs laufen alle im Init, oder es wird bedarfsweise etwas meist 
kurz nach dem Start nachgeneriert.

Gruß,
Michael

[pst (Gast)]

Und das ist alles zur Compilezeit noch nicht bekannt?

[Björn C. (bjoernc)]

was ist zur Compilerzeit nicht bekannt?

[Karl H. (kbuchegg)]

Björn Cassens wrote:
> So hier einfach mal insertNextSwitch und deleteSwitchList, wobei ich mir
> für deleteSwitchList nochmal einen neuen Namen überlegen sollte - der
> ist recht irreführend :)

Tut mir leid. Aber deine Funktionen sind sowas von fehlerhaft! Ich geb 
dir den dringenden Rat, die Funktionen mit Papier, Bleistift und 
Radiergummi durchzuspielen. Du bist der Computer, das Papier ist dein 
Speicher und mit dem Belistift, machst du genau die Manipulationen, die 
dir deine Anweisungen vorschreiben. Nicht das was du denkst was 
passieren soll, sondern das ausführen was dort steht.

Für Variablen machst du dir eine Rechteck (das zb. beim Betreten einer 
Funktion erzeugt wird) und schreibst den Namen neben das Rechteck. Bei 
einem malloc malst du einfach ein neues Rechteck aufs Papier.
Adressen sind in deiner Grafik Pfeile. Ein malloc oder eine & Operation 
gibt dir so einen Pfeil auf ein die Hand und du kannst zb den 
Ausgangspunkt des Pfeiles in einr Variablen, einem Rechteck verankern.

  char* Ptr4;

führt zb dazu, dass du auf deinem Papier ein Rechteck malst, dem du den 
Namen Ptr4 gibts. Da keine Initialisierung angegeben ist, bleibt das 
Rechteck leer.


     Ptr4
     +---------+
     |         |
     +---------+

kommt dann irgendwann in deinem Code die Anweisung vor

  Ptr4 = malloc( 5 );

dann malst du für die Allokierung ein neues Rechteck aufs Papier (Wenn 
du willst, kannst du auch noch die Unterteilung in die 5 Bytes 
einzeichnen). malloc gibt der eine Adresse in die Hand, also einen 
Pfeil, der in dem neuen Rechteck endet und die Zuweisung an die Pointer 
Variable wird graphisch so umgestzt, dass der Pfeil in Ptr4 beginnt


     Ptr4
     +---------+
     |   o-----------------------------+
     +---------+                       |
                                       |     +---+---+---+---+---+
                                       +---->|   |   |   |   |   |
                                             +---+---+---+---+---+

So könnte das zb auf deinem Papier aussehen.

Wenn du einen free machst, dann radierst du das zugehörige Rechteck aus. 
Nicht aber die Pfeile! free verändert den übergebenen Pointer nicht und 
du darfst als menschlicher Computer nur das tun, was dein µC auch machen 
wird.

für die Anweisung

     free( Ptr4 );

verändert sich dein Papier also so

     Ptr4
     +---------+
     |   o-----------------------------+
     +---------+                       |
                                       |
                                       +---->


Bei einer Derferenzierung, also einer * oder -> Operation folgst du, 
ausgehend von der bekannten Variablen immer den Pfeilen auf deinem 
Papier. Wenn so ein Pfeil im Nirwana, also im Nichts, endet: bingo, du 
hast einen Programmfehler live in Action gesehen. Wenn irgendwo 
plötzlich ein Rechteck auftaucht, zu dem kein Pfeil mehr hinführt: 
Gratulation du hast soeben ein memory leak entdeckt. Wenn du aus einem 
leeren Rechteck einen Wert ablesen sollst: Super, du hast soeben eine 
nicht initialisierte Variable gefunden.

Die Anweisung

    *Ptr4 = 7;

führt daher unmittelbar dazu, dass du Ptr4 auf dem Papier suchst, 
aufgrund des * dem Pfeil folgst (der Pfeil existiert auf deinem Papier) 
und in dem dort vorgefundenen Rechteck den Wert 7 reinschreibst. Nur: Am 
Ende des Pfeiles existiert jetzt kein Rechteck mehr. Da war mal eins, 
aber jetzt ist es nicht mehr da: Der Speicher wurde bereits freigegeben 
und du beshreibst gerade Speicher, der dir nicht mehr gehört!

Gehen wir das mal an einem Beispiel durch.
Ich geh mal von der Annahme aus, das ein korrekte Liste existiert. 2 
Einträge sind miteinander verknüpft und im letzten Knoten sei der next 
Pointer NULL (wie es sich gehört). Und jetzt nehmen wir mal deine Add 
Funktion und sehen nach, was passiert, wenn du einen neuen Knoten 
anlegen willst.

Hier ist die eingehende Liste, der funktionslokale Pointer list ist beim 
Aufruf der Funktion schon so eingerichtet worden, dass er auf den Anfang 
der Liste zeigt

  list
  +------+
  |   o  |
  +---|--+
      |
      |
  +--------+         +---------+
  |        |         |         |
  |   o------------->|  NULL   |
  +--------+         +---------+

Die Funktion beginnt .... damit, dass eine neue Variable addr erzeugt 
wird. Machen wir gleich mal. Da keine Initialisierung angegeben ist, 
bleibt das Rechteck leer


  list
  +------+
  |   o  |
  +---|--+
      |
      |
  +--------+         +---------+
  |        |         |         |
  |   o------------->|  NULL   |
  +--------+         +---------+



   addr
   +-------+
   |       |
   +-------+

>   if( list == NULL ){

Sieh auf deinem Papier nach: Ist list NULL? Nein ist es nicht, aus list 
kommt ein Pfeil raus, kann also nicht NULL sein. Weiter gehts also mit 
dem else


>   else{
>   /*************************************
>   *  nach Ende suchen
>   *************************************/
>     while( addr->next != NULL ){


Aha. Ausgehend von addr also das next Feld aufsuchen. Du suchst also auf 
deinem Papier das Rechteck addr, folgst dem Pfeil der aus dem Rechteck 
rauskommt und in der Struktur in der der Pfeil endet holst du das next 
Feld und siehst nach ob dort NULL drinnen steht.

Nur: Bei dir kommt aus addr kein Pfeil raus! Die Variable ist 
uninitialisiert!

Nochmal: Ich rate dir dringend deine Funktionen mit solchen graphischen 
Debug-Mitteln auf dem Papier zu testen! Deine Funktionen sind, so wie 
sie gepostet wurden, voller Fehler. Was deine Delete Funktion zb. 
konkret an Durcheinander in deiner Datenstruktur anstellen wird, wage 
ich ohne eine derartige graphische Simulation noch nicht mal ansatzweise 
vorherzusagen. Dass sie jedoch die Datenstruktur komplett durcheinander 
bringen wird, steht absolut 100%-ig fest.

[Björn C. (bjoernc)]

ja das habe ich gemerkt... bin gerade dabei die delete Funktion zu 
debuggen... aber ich glaub ich setze mich morgen nochmal dran...
das ist mittlerweile die einzigste Funktion die noch fehlerhaft ist, die 
anderen habe ich soweit fertig und funktionieren - aber ich geb dir 
recht die hier geposteten waren noch sehr fehlerhaft, aber im laufe des 
Nachmittags habe ich das nun hinbekommen...
auf wunsch kann ich den Code auch noch gern posten...

[Karl H. (kbuchegg)]

Noch ein Hinweis:
delete ist bei einer einfach verketteten Liste gar nicht so trivial. Das 
Problem besteht darin, dass du einen Zeiger auf den Knoten unmittelbar 
vor dem zu löschenden benötigst. Den kriegst du aber nicht so einfach. 
Das ist auch der Grund für eine doppelte Verkettung: da hat man dann 
einen Pointer drauf.
Bei einer einfach verketteten Liste gibt es 2 Möglichkeiten:
Man geht die Liste von vorne durch und sucht aktiv nach dem zu 
löschenenden Knoten, wobei man einen Knoten zuvor aufhört. -> Man hat 
einen Pointer auf den Knoten vor dem zu löschenden
Trick 2 ist wirklich trickreich. Man löscht gar nicht den zu löschenden 
Knoten, sondern seinen Nachfolger. Von dem kennt man seinen Vorgänger 
und seinen Nachfolger. Bevor aber die Daten des Knoten gelöscht werden, 
werden sie in den ursprünglich zu löschenden Knoten umkopiert. Wenn die 
Daten nicht allzu umfangreich sind und die Liste hinreichend lang ist, 
dann geht das schneller, als aktiv nach dem zu löschenden Knoten (wegen 
dem Vorgänger) zu suchen. Dieser Trick funktionirt allerdings 
klarerweise nicht, wenn das zu löschende Element der letzte Knoten der 
Liste ist.

[Björn C. (bjoernc)]

genau, also was funktioniert, ist das ich das erste Element gelöscht 
bekomme, das letzte muss wenn ich richtig gedacht habe, auch noch einmal 
extra behandelt werden.
Mein jetziger Code verursacht zZt. eine Speicherbereichs verletzung aber 
in mom habe ihc noch keine Ahnung woran das genau liegt, aber ich werde 
deinen Tipp beherzigen und mich dann mal morgen mit einem Stift 
bewaffnen und dann einfach mal anfangen das problem aufzuzeichnen.
Die erste Variante die du genannt hast, wollte ich auch benutzen, halt 
ein Element vorher stehen bleiben vorher die Adresse des übernächsten 
Elements kopieren usw. :) also vom gedanken her stimmt das nur die 
umsetzung ist halt falsch ^^.
und danke erstmal für die vielen Antworten hier, ohne euch wäre ich 
nicht soweit gekommen :)

[Karl H. (kbuchegg)]

void DeleteFrom( struct SwitchList** list, struct SwitchList* node )
{
  struct SwitchList* prev = NULL;
  struct SwitchList* loop = NULL;

  if( list == NULL || *list == NULL )
    //
    // Benutzer, was machst du nur mit mir!
    // Du musst mir schon eine Liste geben, aus der ich löschen kann
    // und nein, aus einer leeren Liste kann man nichts löschen
    //
    return;

  //
  // suche nach dem zu löschenden Knoten in der Liste um den Vorgänger
  // des Knotens zu bestimmen
  //
  loop = *list;
  while( loop != node && loop ) {
    prev = loop;
    loop = loop->next;
  }

  if( loop == NULL )
    //
    // Oops, das sollte eigentlich nie passieren: Der zu löschende Knoten
    // steckt gar nicht in der Liste
    // Sollte nie passieren, aber sicher ist sicher
    return;

  if( prev == NULL ) {
    //
    // Fall: der zu löschende Knoten ist der erste der Liste. In dem Fall
    // muss list selber geändert werden
    //
    *list = loop->next;
  }

  else {
    //
    // list kann unverändert bleiben, den node freischaufeln indem der
    // next Pointer des Vorgängers umgelegt wird.
    //
    prev->next = loop->next;
  }

  free( node );
}

Habs nicht getestet, aber sollte funktionieren.

[Johann L. (gjlayde)]

So ganz hab ich nihct verstanden, was du eigentlich machen willst. Die 
Nutzdaten dienen dazu, die Dimm-Stati irgendwelcher Leuchten zu halten.

Die Anzahl der Lampen sind aber doch wohl bekannt? Wenn du zB 30 Lampen 
hast, könntest doch statisch ein Array für 30 Lampen erzeugen. Das spart 
den ganzen Listen- und Zeigerkrempel.

Johann

[Björn C. (bjoernc)]

hey super danke, aber mit deinem Tip bin ich schon sehr viel weiter 
gekommen :) nur ist mein Code aufgeblähter :) aber ich werde mir sofern 
ich darf mal ein paar Dinge abguggen :).
Ich bin jetzt erstmal soweit, das alles gelöscht wird, bei dem der Timer 
abgelaufen ist, probleme habe ich nur [EDIT] ok das mit dem letzten 
Segment habe ich jetzt auch hinbekommen :)[/EDIT]sowie bei dem ersten 
Segment ...
[EDIT] für das erste Segment habe ich auch schon eine Idee ich glaube 
morgen bin ich fertig und vor allem per Du mit der Liste :) [/EDIT]
der Source Code sieht folgendermaßen aus:

void deleteDeadSwitch( struct SwitchList **list ){
  struct SwitchList *addr=  *list ;
  struct SwitchList *buff;
  if( ( *list ) != NULL ){
    while ( addr->next->next!=NULL ){
      if( addr->next->switchData.Timer==0){
        printf("loesche Schalter %02d loeschen\n", addr->next->switchData.SwitchNr);
        buff=addr->next;
        addr->next=addr->next->next;
        free(buff);
      }//endif
      else{
        addr=addr->next;
      }
    }//endwhile

  }//endif
}

Die Ausgabe sieht wie folgt aus:

[Karl H. (kbuchegg)]

Johann L. wrote:
> So ganz hab ich nihct verstanden, was du eigentlich machen willst. Die
> Nutzdaten dienen dazu, die Dimm-Stati irgendwelcher Leuchten zu halten.
>
> Die Anzahl der Lampen sind aber doch wohl bekannt? Wenn du zB 30 Lampen
> hast, könntest doch statisch ein Array für 30 Lampen erzeugen. Das spart
> den ganzen Listen- und Zeigerkrempel.

:-)
Seh ich auch so.
Es ist relativ sinnfrei, einen einzigen uint8_t als Knoten in einer 
Liste zu verwalten. Die Verwaltungsdaten sind wesentlich umfangreicher 
als die Nutzdaten.

Und selbst wenn sie nicht konstants sind, ist man mit einem dyamisch 
alokiertem Array besser bedient.

Aber: Des Programmierers Wille ist sein Himmelreich. Und wenigstens 
einmal in seiner Laufbahn eine dynamische Liste implementiert zu haben 
(beides: einfach und doppelt verkettet) gehört für einen 'erfahrenen' 
Programmierer in meinen Augen mit dazu. Das ist so, wie wenn ein 
erfahrener Schlosser kein Gewinde schneiden kann.

[Björn C. (bjoernc)]

hmm naja ganz ehrlich wir sprechen hier von recht vielen Schaltern und 
ziemlich vielen Lampen und die ganzen Dinge die ich berücksichtigen muss 
sprich Einschalt/Ausschalt verzögerung + Dimmwert und Gruppen funktion 
und gruppen Dimmwert usw. usw. da kommt ehrlich gesagt extrem viel 
zusammen ;).
und mit den Listen mein Professor in Software Engineering sagte mir vor 
ein paar Tagen das in seiner ehemaligen Firma die Bewerber verkettete 
Listen schreiben mussten und das dort sehr viele Leute Probleme hatten 
:)

[Karl H. (kbuchegg)]

Björn Cassens wrote:

> Ich bin jetzt erstmal soweit, das alles gelöscht wird, bei dem der Timer
> abgelaufen ist, probleme habe ich nur [EDIT] ok das mit dem letzten
> Segment habe ich jetzt auch hinbekommen :)[/EDIT]sowie bei dem ersten
> Segment ...
> [EDIT] für das erste Segment habe ich auch schon eine Idee ich glaube
> morgen bin ich fertig und vor allem per Du mit der Liste :) [/EDIT]
> der Source Code sieht folgendermaßen aus:

Sieh dir meinen Code an, wie ich die Suchschleife gestaltet habe.
Und nein: bei einer einfach verketteten Liste ist der letzte Knoten kein 
Sonderfall. Lediglich der erste.

Im Grunde kannst du den Code von oben nehmen, lediglich das 
Suchkriterium, nach dem der zu löschende Knoten bestimmt wird ist ein 
anderes. Dafür fällt dann der node aus der Argumentliste raus. Die 
Funktion würde dir dann einen abgelaufenen Knoten aus der Liste 
rausschmeissen. (Aber man kann natürlich in einer Schleife die Funktion 
immer und immer wieder aufrufen, bis die Funktion über einen 
Rückgabewert meldet, dass sie keinen zu löschenden mehr gefunden hat :-)

[Björn C. (bjoernc)]

jo wie gesagt das teil läuft schon fast freu und des erste teil nun zu 
löschen sollte nicht das problem sein. Nochmals vielen lieben dank für 
deine sehr umfangreiche Hilfe :)

[Karl H. (kbuchegg)]

Wenn ich noch was anmerken darf

void deleteDeadSwitch( struct SwitchList **list ){
  struct SwitchList *addr=  *list ;
  struct SwitchList *buff;
  if( ( *list ) != NULL ){
    while ( addr->next->next!=NULL ){

mach das nicht so.
Wenn *list NULL ist, dann ist das ein Fehlerfall. Wenn du in einer 
Funktion mehrere mögliche Fehlerfälle in den Argumenten hast, dann 
kriegst du auf diese Art ratz/fatz eine beeindruckende Einrücktiefe, 
verbunden mit einer }-Orgie am Funktionsende.

Benutz zur Fehlerabfrage lieber die Umkehrung verbunden mit einem 
vorzeitigen Return

void deleteDeadSwitch( struct SwitchList **list ){
  struct SwitchList *addr=  *list ;
  struct SwitchList *buff;

  if( ( *list ) == NULL )
    return;

  while ( addr->next->next!=NULL ){

Auf die Art bleibt die Einrücktiefe für den eigentlich arbeitenden 
Abschnitt klein und mann kann auch sehr schön sehen, dass die erste 
Abfrage eigentlich nur einen Fehlerfall in den Argumenten abfangen soll 
und es keine weitere sinnvolle Aktion in diesem Fall gibt.

Das ist einer der Fälle an der ich nicht der Meinung bin, dass man das 
Paradigma, dass eine Funktion nur einen Eingang und einen Ausgang haben 
soll, zu 100% durchziehen soll.

[Simon K. (simon)]

Noch mal zu dem dynamischen Speicherkrams:

Das Argument war: Wenn Speicherplatz nur für eine Art von Datentyp 
angefordert wird und freigemacht wird, dann findet keine 
Speicherfragmentierung statt.
Ist auch logisch, da der Datentyp ja immer gleich groß ist.

ABER: Wenn man sowieso nur den Heap-Speicher für einen Datentyp 
verwendet, ist doch schon im Voraus bekannt, wieviele Variablen des 
Datentypen man instanzieren kann, bis der Speicher voll ist!

Wenn man diese Anzahl nimmt und statisch den Speicher reserviert, spart 
man (wie schon gesagt) den Verwaltungsoverhead mit der verketteten Liste 
und macht das Programm nicht so fehleranfällig.

Das ist meine Meinung. Ich verzichte lieber auf dynamische 
Speicherverwaltung und sage lieber im Voraus: "Dieses Programm 
funktioniert mit bis zu maximal 30 Leuchten".

EDIT: m.A.W.: Dynamische Speicherverwaltung macht nur Sinn, wenn mehrere 
asynchrone Prozesse den Speicher brauchen. So können sie ihn sich 
aufteilen, je nach aktuellem Bedarf. Bei einem Datentyp aber ist es 
reichlich sinnfrei.
Deswegen ist dynamische Speicherverwaltung auch bei Betriebssystemen so 
nützlich. Denn da macht es wirklich Sinn.

[Björn C. (bjoernc)]

hmm ja ok da ist was dran, ich bin für jegliche Tips immer dankbar. So 
die Liste läuft jetzt komplett, ich kopiere jetzt einfach mal den code 
direkt aus Visual studio, falls jemand ein gleiches Problem hat und 
damit alles zusammen liegt :)

struct Switch{

  unsigned   State:1;  
  unsigned   StateBevor:1;
  unsigned   Timer:3;    
  unsigned   Klicks:2;
  unsigned  SWGrp:1;
  int    Grp;
  int    Light;
  int    SwitchNr;
};
/*****************************************************************
*  Structs fuer verkettete List:
*       ist teil von Switch und Light
*****************************************************************/

struct SwitchList{
  struct SwitchList *next;
  struct Switch switchData;  
  
};

void insertNextSwitch( struct SwitchList **list, int Switch ){
  struct SwitchList *addr;
  if( ( *list ) == NULL ){
    ( *list ) = malloc ( sizeof ( struct SwitchList ) );
    ( *list )->next = NULL;
    ( *list )->switchData.SwitchNr=Switch;
  }//endif
  else{
  /*************************************
  *      nach Ende suchen
  *************************************/
    addr = *list;
    while( addr->next != NULL ){
      addr=addr->next;
    }//endwhile
    addr->next = malloc ( sizeof ( struct SwitchList ) );
    addr->next->next=NULL;
    addr->next->switchData.SwitchNr=Switch;
  }//end else
}
void deleteDeadSwitch( struct SwitchList **list ){
  struct SwitchList *addr=  *list ;
  struct SwitchList *buff;
  if( ( *list ) != NULL ){
    while ( addr->next!=NULL ){
      if( addr->next->switchData.Timer==0 ){
        printf("loesche Schalter %02d \n", addr->next->switchData.SwitchNr);
        buff=addr->next;
        addr->next=addr->next->next;
        free(buff);
      }//endif
      else{
        addr=addr->next;
      }
    }//endwhile
    if( ( *list )->switchData.Timer == 0 ){
      buff = ( *list );
      ( *list ) = ( *list )->next;
      printf("loesche Schalter %02d \n", buff->switchData.SwitchNr);
      free( buff );
    }
  }//endif
}
/*****************************************************************
*  Test Funktionen:
*****************************************************************/
void setSwitchValue ( struct SwitchList *list ){
  int i=1;
  if( list != NULL ){
      list->switchData.Timer=1;
      list->switchData.SwitchNr=0;
    while ( list->next!=NULL ){
      list->next->switchData.Timer=3;
      list->next->switchData.SwitchNr=i;
      list=list->next;
      i++;
    }
  }
}
void dekrementSwitchTTL ( struct SwitchList *list){
  int i=1;
  if( list != NULL ){
      list->switchData.Timer--;
      printf (" Schalter Nr : %02d   \n" , list->switchData.SwitchNr);
      printf (" Schalter TTL: %02d \n\n" , list->switchData.Timer);
    while (list->next!=NULL){
      list->next->switchData.Timer--;
      printf (" Schalter Nr : %02d   \n" , list->next->switchData.SwitchNr);
      printf (" Schalter TTL: %02d \n\n" , list->next->switchData.Timer);
      list=list->next;
      i++;
    }
  }
}

PS: ich habe die printf's ncoh nicht heraus genommen

[Björn C. (bjoernc)]

ähm um auf Simons aussage zukommen:
ich habe nicht nur SwichtList sondern zusätzlich LightList und evtl. 
später eine Group List ich kann aber vorher nicht absehen, ob und 
wieviele Lampen eingeschaltet sind und vor allem wie oft getastet wird 
:)

[Karl H. (kbuchegg)]

Und noch ein Tip:

Bei dynamischen Datenstrukturen schreibt man sich als aller erstes eine 
Funktion, die die komplette Struktur ausdumpen kann. Nichts gegen deine 
Test indem du Funktion für Funktion immer wieder aufrufst, aber ein 
vollständiger Dump der Liste zeigt sofort ob irgendwo Fehler in der 
Datenstruktur sind.

void Dump( struct SwitchList* list )
{
  struct SwitchList* loop = list;

  while( loop ) {
    printf( "*Node at %p\n", loop );
    printf(  ...... hier deine Nutzdaten ausgeben ...
    printf( " next: %p\n", loop->next );
  }
}

Wenn du diesen Dump nach jedem Add bzw. Delete aus deinem Testprogramm 
heraus aufrufst, dann bleiben Fehler in der Datenstruktur nicht länger 
unentdeckt. Dump wird entweder crashen oder Amok laufen, wenn da was 
nicht stimmt. Und falls nicht: kannst du immer noch sehen, ob ein Insert 
auch tatsächlich an der richtigen Stelle gemacht wurde, ob eine 
Umsortieraktion korrekt gemacht wurde etc.

Verzichte niemals auf solche Hilfsmittel! Manchmal muss man sich in der 
Programmierung auch Werkzeuge bauen, die einem bei der weiteren 
Entwicklung helfen. Die dafür investierte Zeit kriegst du vielfach durch 
eingesparte Entwicklungszeit und schnellerer Fehlerfreiheit zurück.

[Björn C. (bjoernc)]

hmm das mit dem Dump macht Sinn :) ich habe was in den Vorlesungen 
gehört das man sowas mit dem Präprozssor machen kann :) aber ok hier 
muss ich ja vorerst "nur" die printf's raussuchen da hat Visualstudio 
recht tolle tools parat ohne jetzt schleichwerbung zu machen :)

[Simon K. (simon)]

Björn Cassens wrote:
> ähm um auf Simons aussage zukommen:
> ich habe nicht nur SwichtList sondern zusätzlich LightList und evtl.
> später eine Group List ich kann aber vorher nicht absehen, ob und
> wieviele Lampen eingeschaltet sind und vor allem wie oft getastet wird
> :)

Na gut, das ist ein Argument. Ich würde trotzdem (sofern jedes der 
Listenelemente gleich groß ist) eine Union aus den Möglichkeiten machen 
und dann daraus ein Array bilden.
Dann kannst du sagen: Dieses Programm unterstützt 30 Aktionen, die 
entweder Switch, Light etc. sein können.
Wenn die Elemente nicht gleich groß sind, hast du u.U. Probleme mit 
Fragmentierung, aber ich denke mal dem bist du dir bewusst.

Das Visual Studi ist tatsächlich nicht schlecht, wenn es Out Of The Box 
funktionieren soll und man sowieso billig an die Software kommt (sei es 
Schule, Uni, FH, ...).

[Johann L. (gjlayde)]

Karl heinz Buchegger wrote:
> Johann L. wrote:
>> So ganz hab ich nihct verstanden, was du eigentlich machen willst. Die
>> Nutzdaten dienen dazu, die Dimm-Stati irgendwelcher Leuchten zu halten.
>>
>> Die Anzahl der Lampen sind aber doch wohl bekannt? Wenn du zB 30 Lampen
>> hast, könntest doch statisch ein Array für 30 Lampen erzeugen. Das spart
>> den ganzen Listen- und Zeigerkrempel.
>
> :-)
> Seh ich auch so.
> Es ist relativ sinnfrei, einen einzigen uint8_t als Knoten in einer
> Liste zu verwalten. Die Verwaltungsdaten sind wesentlich umfangreicher
> als die Nutzdaten.
>
> Und selbst wenn sie nicht konstants sind, ist man mit einem dyamisch
> alokiertem Array besser bedient.

Selbst das lässt sich vermutlich umgehen

Michael Appelt wrote:
>
> also so einfach wie Du sehe ich das nicht.
> Auch für Microcontroller wie einen Mega8 mit seinen geringen Resourcen
> benutze ich das dynamische malloc - allerdings ohne free.
> [...]
> Die mallocs laufen alle im Init, oder es wird bedarfsweise etwas meist
> kurz nach dem Start nachgeneriert.

Hier wäre ein alloca Mittel der Wahl. Wenn man den Puffer in der 
Init-Phase erzeugt und nie wieder freigeben muss. C99 bietet da sowas:

void foo (int x)
{
    int array[x];
    ...
}

array hat den Gültigkeitsbereich einer lokalen Variablen. Mann kann also 
nach dem Start auf die Größe warten (Anzahl Lampen, etc.) und wenn man 
sie zugesandt bekommen hat, sich den Platz nehmen. Vorteil ist, daß das 
keinen Overhead an RAM-Verbrauch bringt. Zudem wird nicht gegen eine 
lib gelinkt wie bei malloc/free. Mit ein paar Bytes Code beschafft der 
Compiler den Speicherplatz. Man könnte den Platz sogar wieder frei geben 
(indem man foo verlässt) und wieder mit einem anderen Wert für x 
betreten. Es ist nicht so komfortabel wie malloc und stellt bestimmte 
Bedingungen an die Verwenung des Arrays -- ist also kein allgemeiner 
Erstz für malloc. Aber wenn es anwendbar ist, ist es ein sehr 
effizienter Weg, sich Speichen zu beschaffen.

> Aber: Des Programmierers Wille ist sein Himmelreich. Und wenigstens
> einmal in seiner Laufbahn eine dynamische Liste implementiert zu haben
> (beides: einfach und doppelt verkettet) gehört für einen 'erfahrenen'
> Programmierer in meinen Augen mit dazu. Das ist so, wie wenn ein
> erfahrener Schlosser kein Gewinde schneiden kann.

Dagegen sag ich ja auch garnix, aus dem Thread-Verlauf wird das je auch 
deutlich: der Weg ist das Ziel. Lernen kann man allemal was dabei.

[Karl H. (kbuchegg)]

Johann L. wrote:

> Dagegen sag ich ja auch garnix, aus dem Thread-Verlauf wird das je auch
> deutlich: der Weg ist das Ziel. Lernen kann man allemal was dabei.

Ich habs auch nur gesagt, weil mitlerweile eine Generation an 
Programmieren hernwächst, die dynamische Datenstrukturen einfach nicht 
mehr gelernt haben.

Ist im Grunde nichts anderes als der 'Streit' vor 30 Jahren, ob man noch 
Assembler lernen muss, wo es doch Compiler gibt. Solange man mit 
Hohsprachen gut zurecht kommt, ist Assembler natürlich unnötig. Aber wie 
man bei der Programmierung in diesem Forum sehr schön sieht, ist es ganz 
gut, wenn man auch mal etwas Assembler gemacht hat, um sich vorstellen 
zu können was es mit Registern so auf sich hat und was dein eigentlich 
im Chip so abgeht.

Mit den dynamischen Strukturen ist es halt ähnlich. Klar in C++, C#, 
Java (ohne Anspruch auf Vollständigkeit) braucht man dieses Wissen so 
nicht mehr. Und leider erlebt man dann halt aber auch, dass für einen 
bestimmten Zweck oft eine wenig geeignete Datenstruktur gewählt wird, 
weil der Programmierer keine Vorstellung davon hat, was da intern 
eigentlich abgeht.

[Björn C. (bjoernc)]

@ Johann klar ist es komfortabler mit malloc oder noch besser new zu 
arbeiten, das generelle Problem wird bei mir garantiert sein, dass ich 
aus der Computer Programmierung komme bzw. von anfang an nur am Computer 
Programmieren gelernt habe und das bei einem Studiengang E-Technik 
rolleyes. Ich denke das mir auch da gerade die Grundlagen in der 
Mikrocontroller Programmierung fehlen, was man machen kann usw. Bei 
einem PC hat man keine Speicher engpässe, daher gewöhnt man sich einen 
ganz anderen Programmier stil an - denke ich.
Also die AVR Programmierung die ich vor habe ist denke ich mal -  und 
damit möchte ich keine Leistung irgendwie in den Schatten stellen - 
nicht unbedingt das einfachste, aber meine meinung ist, entgegend der 
Meinung aus mehreren Lehrbüchern viel ist auch viel, wer viel vor hat 
lernt mehr, aber auch hier ist das nur eine individuelle Meinung und vor 
allem eine individuelle Lernmethodik. Aber ich glaub ich schweife grad 
ab :)
Also ich möchte das halt gern erstmal so ausprobieren auch wenn man 
evtl. mit anderen Methoden bessere ergebnisse erzielen könnte aber aus 
der Computer Programmierung wäre das so ansich die beste methodik - aber 
wie cih festgestellt habe, gibt es hier extreme Unterschiede...

[Karl H. (kbuchegg)]

Björn Cassens wrote:

> der Computer Programmierung wäre das so ansich die beste methodik - aber
> wie cih festgestellt habe, gibt es hier extreme Unterschiede...

... die hauptsächlich daher rühren, dass auf den µC die hier 
normalerweise gang und gäbe sind, ein SRAM Mangel herrscht. Wenn man nur 
1 oder 2KB zur Verfügung hat, muss man öfter auch mal Kompromisse 
schliessen. Es ist besser, wenn ich von vorne herein sage, das Programm 
kann nur 50 Lampen und die sind fest codiert, also von einer dynamischen 
Datenstruktur auszugehen, mit der dann 40(!) Lampen möglich sind, weil 
der Rest des Speichers von der Verwaltungsinfo aufgefressen wird :-)
Zudem hat man dann auch immer das Problem, dass man möglichst wenig 
Unbekannte in so einem Programm haben möchte. Im Speicher liegen: Stack, 
Heap und globale (fix angelegte) Variablen. Da hat man jetzt 2 Dinge, 
deren Größe von vorne herein nicht feststehen: Stack und Heap, wobei man 
den Stack noch einigermassen gut abschätzen kann. Wenn aber beide 
anfangen zu wachsen und sich die Lücke zwischen den beiden immer mehr 
schliesst, dann ist das um einiges schwerer zu beherrschen, als wie wenn 
man nur den Stack wachsen lässt.

Ich will dich nicht davon abhalten, deine Liste zu machen. Mach sie!
Was wir aber sagen wollen ist: Auf einem µC in der Kategorie Mega8, 16, 
32 muss man auch bei vielen Dingen überlegen, ob man Sachen die auf 
einem PC ganz normal sind, einfach so übernehmen möchte.

[Björn C. (bjoernc)]

hmm ok da ist was wahres dran, aber jetzt bin ich grad mit der Liste 
fertig :), von daher versuche ich es erstmal so. Ich denke bei dem 
nächsten Projekt, werde ich das dann evtl. anders verwalten :) da gehts 
dann um einen Bot der einen Raum vermessen soll, und anschließend 
hindernisse suchen soll xD... ^^

[Johann L. (gjlayde)]

Björn Cassens wrote:
> hmm naja ganz ehrlich wir sprechen hier von recht vielen Schaltern und
> ziemlich vielen Lampen und die ganzen Dinge die ich berücksichtigen muss
> sprich Einschalt/Ausschalt verzögerung + Dimmwert und Gruppen funktion
> und gruppen Dimmwert usw. usw. da kommt ehrlich gesagt extrem viel
> zusammen ;).
Genau dann geht es darum, effizient zu sein.

Versteh mich nicht falsch; sich anzuschauen, wie etwas in der "reinen 
Lehre" umgesetzt wird, ist absolute Grundlage später auch angemessen auf 
einem System mit sehr beschränkten Resourcen codieren zu können. Je 
kleiner die Resourcen jedoch sind (RAM, Code-Speicher, Zeit, ...) desto 
weiter wird man von der reinen Lehre abrücken müssen. Tut man das aber 
zu früh, versaut man sich den Stil mit Hacks. Tut man es zu spät, fliegt 
einem alles um die Ohren oder man kann es in die Tonne kloppen, weil es 
mehr als 100% einer wesentlichen Resource (Code, RAM, Zeit, ...) frisst.

Im Gegensatz zum PC sollte man also immer ungefähr eine Vorstellung 
davon haben, wie der Code letztendlich ungefähr umgesetzt wird oder 
aussehen sollte, nachdem er compiliert ist.

Das heisst nicht, am asm-Code zu kleben. Den erzeugt der Compiler. Aber 
genauso, wie man bei einem Auto hin und wieder auf den Ölstand, 
Tankzeiger oder den Tacho schaut und erst ein Gefühl dafür bekommen 
muss, welcher Fahrstil was kostet, ist es mit den Resourcen eines µC. 
Und es ist eben ein Unterschied, ob man den Führerschein auf den 
Ozeandampfer, nem 20-Tonner, nem Porsche oder nem 2CV macht. Un wenn man 
später mal ds Gefährt wechselt -- egal von wo nach wo -- tut sich immer 
ein neues Universum auf.

> und mit den Listen mein Professor in Software Engineering sagte mir vor
> ein paar Tagen das in seiner ehemaligen Firma die Bewerber verkettete
> Listen schreiben mussten und das dort sehr viele Leute Probleme hatten
> :)
Klasse, Idee! Ich werd auch mal Bewerber einladen, und ihnen dann zur 
Aufgabe geben, ein Betriebssystem oder einen Compiler zu schreiben ;-)
Mal im Ernst: Seltsame Firma. Zeugt davon, daß die Bewerbung von 
Angsthasen geleitet wurde, die die Testergebnisse vorzeigen können, wenn 
der Bewerber später mal Mist baut "Aber bei dem Test hat er doch gut 
abgeschnitten..." Lass dich von sowas nicht ins Boxhorn jagen.

[Björn C. (bjoernc)]

hmm das kann ich nicht beurteilen wie die firma war/ist es wurde mir 
einfach nur so erzählt :) wie das im einzelnem abgelaufen ist weiß ich 
selbst nicht :).
Aber ich dachte mir verkettete Liste das ist doch eigentlich genau das, 
was du brauchst davon hast du gehört, deswegen war der schritt gar nicht 
mehr so groß das der wunsch entstanden ist, dies auf einen AVR zu 
implementieren. Wobei cih aber eines bisher gelernt habe: es ist nicht 
alles gold was glänzt - die praxis sieht ab und zu ganz anders aus :)
wobei ich auch dazusagen muss asm Code? keine ahnung was das jetzt genau 
ist, wenn das Assembler sein soll, habe ich nur eine begrenzte 
vorstellung wie das von C nach Assembler portiert werden soll, wobei cih 
früher schon auf dem 8085 in assembler programmiert habe - und so ein 
paar kleinere dinge mir vorstellen kann...

[Peter D. (peda)]

Bjoern wrote:

> ein Freund von mir baut sich gerade ein Haus und möchte gerne eine
> Haussteuerung haben.

Dann solltest Du Dir erstmal die verschiedensten Threads zur 
Hausautomatisierung ansehen und Anregungen entnehmen:

http://www.mikrocontroller.net/forum/hausbus

Eine zentrale Steuerung würde ich auf keinen Fall machen, der 
Verkabelungsaufwand nimmt astronomische Ausmaße an.
Selbst eine Zentrale pro Etage ist immer noch zuviel Kupferverbrauch.

Heutzutage sind riesige Zentral-CPUs out, man verwendet intelligente 
Sensoren/Aktoren.

Ich würde pro Taster einen ATmega88 + MCP2515 + Triac nehmen, d.h. 
Dimmer und Taster lokal steuern.
Der Taster steuert dann entweder den Triac direkt oder schickt ein 
CAN-Paket an die Zentrale, um ne Gruppe zu steuern.
Über den CAN-Bus kann auch bequem ein Softwareupdate eingespielt werden.

Der Verdrahtungsaufwand sinkt drastisch, da ja alle Teilnehmer parallel 
geschaltet werden und an einem Bus hängen.
Und Speicherprobleme gibts damit auch nicht mehr, der interne SRAM 
reicht völlig aus.


Peter

[Chris (Gast)]

Wenn du eine double linked list hast, kannst du die auch mittels Xor
Komprimieren, solltest du Speicherprobleme haben.

[Jörg W. (dl8dtl) (Moderator)]

Simon K. wrote:

> ABER: Wenn man sowieso nur den Heap-Speicher für einen Datentyp
> verwendet, ist doch schon im Voraus bekannt, wieviele Variablen des
> Datentypen man instanzieren kann, bis der Speicher voll ist!

Nein: die Tiefe deines Stacks ist dir vorab nicht bekannt.  malloc()
ermöglicht es, den Heap bis an den Stack heran automatisch
auszunutzen und auch den Kollisionsfall noch einigermaßen sicher zu
erkennen (es gibt dann NULL zurück), sodass man ihn behandeln kann.
Statisch vorbelegten Speicher müsste man für das mögliche Maximum
bei jeglicher Änderung an den übrigen Daten jedesmal neu kalkulieren,
außerdem müsste man sich ständig Gedanken darum machen, welche Tiefe
der Stack zur Laufzeit tatsächlich erreicht, und schließlich würde
man die Kollision nicht bemerken, sondern stattdessen das Ende der
statisch vorbelegten Daten korrumpieren -- was man vermutlich sehr
lange Zeit erst einmal gar nicht bemerkt, d. h. die Wahrscheinlichkeit,
dass die Applikation erst nach Jahren Laufzeit ,,kracht'' ist dort
sogar höher als bei einer dynamischen Implementierung, die von
vornherein einen sauberen Rückzieher macht, falls malloc() ein NULL
zurück gibt.

Dafür muss man natürlich genau sehen, ob der Puffer, den malloc()
bis zum aktuellen Stackpointer noch belässt, auch tatsächlich
ausreichend ist (__malloc_heap_margin).  Das kann man aber ggf. durch
statische Codeanalyse, während das für die komplette Tiefe des Stacks
in einer üblichen Applikation kaum noch möglich sein dürfte.

Solange man mit den statisch vorbelegten Daten sehr sicher unterhalb
des möglichen Maximums bleibt, ist das natürlich auch kein Problem,
aber genau dann ist malloc() halt auch gar kein Problem.

[Karl H. (kbuchegg)]

Jörg Wunsch wrote:

> Dafür muss man natürlich genau sehen, ob der Puffer, den malloc()
> bis zum aktuellen Stackpointer noch belässt, auch tatsächlich
> ausreichend ist (__malloc_heap_margin).

Das klingt interessant. Mit Google hab ich nichts zum Thema 
__malloc_heap_margin gefunden.

Geh ich recht in der Annahme, dass dieser Wert angibt, wieviel Speicher 
der Memory Allocator übrig lassen muss, weil sich dort drinn der Stack 
breit machen darf?  (Wie stellt man den Wert eigentlich ein?)

[Jörg W. (dl8dtl) (Moderator)]

Sorry, heißt nur __malloc_margin.  Ist hier beschrieben:

http://www.nongnu.org/avr-libc/user-manual/malloc.html

[Johann L. (gjlayde)]

Jörg Wunsch wrote:

> Nein: die Tiefe deines Stacks ist dir vorab nicht bekannt.  malloc()
> ermöglicht es, den Heap bis an den Stack heran automatisch
> auszunutzen und auch den Kollisionsfall noch einigermaßen sicher zu
> erkennen (es gibt dann NULL zurück), sodass man ihn behandeln kann.

Das setzt voraus, daß keine weiteren Funktionsaufrufe geschehen, die den 
Stack weiter wachsen lassen können. Gleiches gilt für ISR-Frames.
Wirklich sicher ist eine solche Abfrage also nicht. Wirkliche Sicherheit 
ohne statische Analyse kann nur eine Stack-Overflow-Trap liefern, die es 
für AVR nicht gibt.

Statische Analysen sind alles andere als trivial, und wenn Interrupts 
auftreten können, nochmal komplizierter. Bei AVR werden kaskadierende 
IRQs wenig verwendet, aber auf komplexeren Systemen sind mehrere 
IRQ-Ebenen üblich und sinnvoll.

Wirklich kontrolliert vor einer Fehlfunktion schützen kann nur eine 
statische Analyse; in vielen sicherheitskritischen Systemen ist malloc 
daher obsolet.

Johann

[Simon K. (simon)]

Jörg Wunsch wrote:
> Simon K. wrote:
>
>> ABER: Wenn man sowieso nur den Heap-Speicher für einen Datentyp
>> verwendet, ist doch schon im Voraus bekannt, wieviele Variablen des
>> Datentypen man instanzieren kann, bis der Speicher voll ist!
>
> Nein: die Tiefe deines Stacks ist dir vorab nicht bekannt.  malloc()
> ermöglicht es, den Heap bis an den Stack heran automatisch
> auszunutzen und auch den Kollisionsfall noch einigermaßen sicher zu
> erkennen (es gibt dann NULL zurück), sodass man ihn behandeln kann.

Ja, da hast du schon Recht, allerdings ist die Tiefe des Stacks auch bei 
statischer Speicherallokierung unbekannt.
Das Problem hast du aber dann, wenn du den gesamten Heap allokiert hast 
und der Stack in den Heap wächst.
Ich finde man hat eine bessere Kontrolle über den Speicherüberlauf, wenn 
man von Vornherein den Stack abschätzt und dann einen bestmimten Platz 
für diesen lässt.
Das was gjlayde oben geschrieben hat mit den unbekannten, finde ich, ist 
gerade bei Mikrocontrollern ziemlich wichtig. Da kommt ja kein 
Bluescreen o.ä. was jetzt ein Problem anzeigt, sondern der dreht 
irgendwann einfach unerwartet am Rad ;)

[Björn C. (bjoernc)]

also sofern malloc NULL liefert, so gibt es eine kleine Funktion, die 
mir genau das anzeigen soll, das der Stack wächst kann gut sein aber ich 
bin bemüht bei den ganzen Funktionen auf "call by reference" 
zurückzugreifen, ich weiß jetzt nicht genau, ob das bei C nun das 
gleiche ist, da ich bei C++ einfach nur ein voind func(int &var ) 
schreiben muss und der rest eigentlich gleich bleibt bei C muss ich mehr 
hin und her dereferenzieren aber im ganzen sollte es doch das gleiche 
sein oder? die meisten Variablen und/oder puffer werden zu anfang des 
Programms erstellt so das die funktionsaufrufe eigentlich keine Kopien 
machen und bei Puffer usw. auf globale Variablen zurückgreifen - ich 
hoffe das diese Vorsichtsmaßnahme mich nicht in trügerische Sicherheit 
ziehe oder ich irgendwo einen Denkfehler habe...

[Johann L. (gjlayde)]

Björn Cassens wrote:
> also sofern malloc NULL liefert, so gibt es eine kleine Funktion, die
> mir genau das anzeigen soll, das der Stack wächst kann gut sein aber ich
> bin bemüht bei den ganzen Funktionen auf "call by reference"
> zurückzugreifen, [...]

Damit machst du je nach Fall den Bock zum Gärtner:

Beitrag "Re: Problem SRAM Optimierung AVR-GCC"

Etwa wenn die Adresse einer lokalen Variablen gezogen wird.

Johann

[Björn C. (bjoernc)]

ähm ganz plöd gefragt, was ist denn genau das problem das call by 
reference oder die Funktionen als solches oder die globalen Variablen?

[Michael A. (micha54)]

Johann L. wrote:
> Wirklich kontrolliert vor einer Fehlfunktion schützen kann nur eine
> statische Analyse; in vielen sicherheitskritischen Systemen ist malloc
> daher obsolet.
>
> Johann

Hallo,

eine statische Analyse kann Efekte durch z.B. Rekursion oder lokale 
dynamische Allocation auch nicht berechnen.
EDIT: sollte man in sicherheitsrelevanten System nicht machen.

Recht gut hilft es, in einem meist sowieso laufenden Timer-interrupt den 
minimalen SP in einer Variablen zu übernehmen und diesen Wert per 
Display anzuzeigen - meine paar AVRs haben inzwischen alle den Luxus 
einer RS232-Schnittstelle für genau diesen Zweck.

Gruß,
Michael

[Karl H. (kbuchegg)]

Björn Cassens wrote:

> bin bemüht bei den ganzen Funktionen auf "call by reference"
> zurückzugreifen, ich weiß jetzt nicht genau, ob das bei C nun das
> gleiche ist,

in C gibt es keinen call by reference.
Ganz einfach aus dem Grund, weil es in C keine Referenzen gibt.

> da ich bei C++ einfach nur ein voind func(int &var )
> schreiben muss und der rest eigentlich gleich bleibt bei C muss ich mehr
> hin und her dereferenzieren

Das spielt keine Rolle und darum gehts im Grunde auch gar nicht.
Auch einen Call By Reference gibt es in C++ nicht gratis. Wenn der 
Compiler die Funktion nicht inlinen kann oder will, dann wird ein Call 
By Reference unter der Bettdecke durch eine Pointerübergabe realisiert. 
In diesem Fall ist dann die Referenz nichts anderes als syntactic sugar, 
um die Pointersyntax zu verstecken.

> hoffe das diese Vorsichtsmaßnahme mich nicht in trügerische Sicherheit
> ziehe oder ich irgendwo einen Denkfehler habe...

Doch das tut es.
Jeder Funktionsaufruf belegt Speicher im Stack. Und sei es nur für die 
Returnadresse. Dazu kommen dann noch lokale Variablen. Die Gratwanderung 
besteht darin, Variablen global zu machen, ohne die allzuviel an 
Flexibilität aufzugeben. Eigentlich möchte man möglichst wenig globale 
Variablen haben, allerdings möchte man auch eine gewisse Kontrolle über 
das Stackwachstum haben und lokale Variablen können einem da dann schön 
in die Suppe spucken, wenn eine Funktion über mehrere verschiedene 
Aufrufpfade aufgerufen werden kann. Da ist dann Analysearbeit gefragt um 
alle Möglichkeiten aufzuspüren. Daher geht man dann gerne den 
pragmatischeren Weg und verlagert Variablen ins globale Lager.

[Karl H. (kbuchegg)]

Björn Cassens wrote:
> ähm ganz plöd gefragt, was ist denn genau das problem das call by
> reference oder die Funktionen als solches oder die globalen Variablen?

Ganz einfach: Es ist das geordnete Zusammenspiel dieser einzelnen 
Komponenten. Einzeln für sich betrachtet, gibt es eh in keinem 
Teilbereich ein Problem. Aber im Zusammenspiel liegt die Krux, da alle 3 
um eine gemeinsame limitierte Resource, den SRAM Speicher, in Konkurrenz 
treten.

Peter, Paul und Marie lieben alle 3 Suppe. Jetzt gibt es aber in dieser 
WG nur ein Teller. Solange jeder zu verschiedenen Zeiten Suppe essen 
will, gibt es kein Problem. Probleme gibt es erst dann, wenn jeder der 3 
genau um 20:00 Uhr einen Teller Suppe haben möchte.

[Björn C. (bjoernc)]

soll das dann bedeuten, das meine überlegungen richtig waren, es aber 
trotzdem später zu erheblichen Problemen führen kann weil der Stack in 
den Heap reingewachsen ist und deswegen mein Controller evtl. Sachen 
macht die vorher nicht vorgesehen waren? :) kann man da überhaupt was 
dagegen machen?

[P. S. (Gast)]

Björn Cassens wrote:

> kann man da überhaupt was dagegen machen?

Solange du keine unkontrollierten Rekursionen hast, laesst sich der 
Stackverbrauch ja relativ gut abschaetzen, bzw. austesten. Wie hier 
schon stand, kannst du den Stackpointer ja ausgeben / pruefen. Damit 
kannst du eigentlich recht solide abschaetzen, wie viel Restspeicher dir 
bleibt.

Schau mal hier rein: 
http://www.roboternetz.de/wissen/index.php/Speicherverbrauch_bestimmen_mit_avr-gcc#Flash-_und_statischer_RAM-Verbrauch

[Björn C. (bjoernc)]

hmm dann kann ich ja nach jedem Bereinigen am besten mal nachschauen, 
wieviel Speicher ich dann übrig haben, und diesen Wert dann später 
Richtung Webserver schicken und mir dann den akt. SPeicher Verbrauch 
ansehen... kann ich aber nciht einfach mal so ein bissl in AVR Studio 
bzw. in Harpsim einfach mal herumspielen, und dann einfach nachschauen, 
wie sich der Speicher verhält, so das ich erstmal eine grobe Vorstellung 
des ganzen bekomme?

[Karl H. (kbuchegg)]

Björn Cassens wrote:
> hmm dann kann ich ja nach jedem Bereinigen am besten mal nachschauen,
> wieviel Speicher ich dann übrig haben, und diesen Wert dann später
> Richtung Webserver schicken und mir dann den akt. SPeicher Verbrauch
> ansehen... kann ich aber nciht einfach mal so ein bissl in AVR Studio
> bzw. in Harpsim einfach mal herumspielen, und dann einfach nachschauen,
> wie sich der Speicher verhält, so das ich erstmal eine grobe Vorstellung
> des ganzen bekomme?

Sicher kannst du.
Dich interessiert vor allen Dingen der Stack Verbrauch. Also einfach mal 
dein Programm bedienen und typische Bedienabläufe laufen lassen. Dann im 
Code mal nach Pfaden suchen, die in möglichst vielen geschachtelten 
Funktionsaufrufen münden, mit möglichst vielen lokalen Variablen. Ziel 
der ganzen Sache ist es, den Stackverbrauch möglichst gut abschätzen zu 
können. Im Zweifelsfall lieber noch 10% draufschlagen.

Diesen Wert gibst du dann __malloc_margin vor.
Jörg hat weiter oben einen Link gepostet, wie das geht.

__malloc_margin sorgt dann dafür, dass der Heap-Allocator diesen 
Speicher, den du für den Stack brauchst in Ruhe lässt.

Das ganze ist ein wenig mühsam, zugegeben. Aber das ist dann halt der 
Preis, den du für dynamische Allokierung zu zahlen hast.

[Stefan E. (sternst)]

Karl heinz Buchegger wrote:
> Ziel
> der ganzen Sache ist es, den Stackverbrauch möglichst gut abschätzen zu
> können. Im Zweifelsfall lieber noch 10% draufschlagen.
> Diesen Wert gibst du dann __malloc_margin vor.

Hmm, habe ich __malloc_margin falsch verstanden?
Ich habe das so verstanden, dass malloc die aktuelle Position des Stack 
prüft, und dann bis maximal __malloc_margin daran geht. Wenn man nun 
__malloc_margin auf die maximale Größe des Stack setzt, und malloc 
aufruft während der Stack nahe an seiner maximalen Größe ist (was ja 
relativ wahrscheinlich ist, da das malloc ja in der Regel in einer 
Funktion auf einer ziemlich tiefen Ebene sitzt), dann schlägt das malloc 
möglicherweise fehl, obwohl noch ziemlich viel Platz wäre. Für das 
__malloc_margin müsste man also den Abstand von der Stackposition beim 
malloc bis zur maximalen Ausdehnung ermitteln. Wenn die maximale 
Ausdehnung des Stacks aber sowieso halbwegs bekannt ist, kann man auch 
gleich __malloc_heap_end entsprechend setzen.

[P. S. (Gast)]

Karl heinz Buchegger wrote:

> Das ganze ist ein wenig mühsam, zugegeben. Aber das ist dann halt der
> Preis, den du für dynamische Allokierung zu zahlen hast.

Den Preis muss man immer bezahlen. Auch, wenn man den Speicher statisch 
belegt muss man wissen, ob er ausreicht.

[Karl H. (kbuchegg)]

Stefan Ernst wrote:
> Karl heinz Buchegger wrote:
>> Ziel
>> der ganzen Sache ist es, den Stackverbrauch möglichst gut abschätzen zu
>> können. Im Zweifelsfall lieber noch 10% draufschlagen.
>> Diesen Wert gibst du dann __malloc_margin vor.
>
> Hmm, habe ich __malloc_margin falsch verstanden?

Nein. Ich!

> Ausdehnung des Stacks aber sowieso halbwegs bekannt ist, kann man auch
> gleich __malloc_heap_end entsprechend setzen.

Genau.
Mea culpa. Tschuldigung.

[Karl H. (kbuchegg)]

Peter Stegemann wrote:
> Karl heinz Buchegger wrote:
>
>> Das ganze ist ein wenig mühsam, zugegeben. Aber das ist dann halt der
>> Preis, den du für dynamische Allokierung zu zahlen hast.
>
> Den Preis muss man immer bezahlen. Auch, wenn man den Speicher statisch
> belegt muss man wissen, ob er ausreicht.

Schon klar.
Der einzige Vorteil ist halt, dass du zur Laufzeit den SRAM Verbrauch 
der nicht für den Stack draufgeht, schon kennst, während der bei 
dynamischer Verwaltung auch von Benutzereingaben abhängen kann.

Wenn alles statisch ist, ist die Frage eine andere: Bleibt genug Platz 
für den Stack übrig oder nicht? Nicht das diese Frage wesentlich 
leichter zu beantworten wäre, damit da jetzt kein Misverständnis 
auftaucht. Aber man hat immerhin eine Unbekannte weniger, die man 
abschätzen muss.

[Björn C. (bjoernc)]

also sieht mein Schlachtplan wie folgt aus: erstmal alle Funktionen 
inkl. Variablen halbwegsfertig schreiben, via Harpsim dann anfangen das 
teil zu quälen und mir dann den Stack verbrauch ansehen - kann man auch 
etwas in der art wie eine Testbench bzw. eine Stimuli einrichten wie es 
in VHDL auch geht - bin wie gesagt der totale Anfänger in Sachen 
Mikrocontroller :)

[Johann L. (gjlayde)]

Björn Cassens wrote:
> hmm dann kann ich ja nach jedem Bereinigen am besten mal nachschauen,
> wieviel Speicher ich dann übrig haben, und diesen Wert dann später

Nein. Wie willst du den feien Platz denn bestimen? Die in roboternetz 
verlinkte Routine sagt ausdrücklich, daß sie nicht mit malloc zusammen 
funktioniert.

Johann