Verkettete Liste für ASURO

[Spacy Bar]

Hallo Community,

Ich habe mal auf dem PC ein Programm geschrieben, dass Zahlenwerte in einer Verketteten Liste speichert. Ich dachte mir, dass kann der Robby auch nur Zahlen sind witzlos, es müssen schon char-Arrays/Strings sein. Das ganze endete in einem Zeigergewirr mit Strukturgewirr verknüpft. Ich hoffe ihr habt eine Lösung für mein Problem, ich habe 'ne ganze menge Zeit rein investiert.

#include "asuro.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct knoten {
char wort[16];
struct knoten *next;
};

typedef struct knoten Knoten_t;
typedef struct knoten* KnotenPtr_t;
KnotenPtr_t anfang = NULL;

void einfuegenknoten( KnotenPtr_t neu ) {
KnotenPtr_t hilfZeiger;
if( anfang == NULL ) {
anfang = neu;
neu->next = NULL;
}
else {
hilfZeiger = anfang;
while(hilfZeiger->next != NULL) hilfZeiger = hilfZeiger->next;
hilfZeiger->next = neu;
neu->next = NULL;
}
}

void neuerKnoten(void){
KnotenPtr_t neu = malloc(sizeof(Knoten_t));
if( neu == NULL){
SerWrite("Speicher ist voll/Kein Speicher vorhanden!\n\r",45);
return;
}
SerWrite("Wert für Knoten eingeben:\n\r",26);
do { SerRead(wort[16] ,15,0);
} while( getchar()!='\n');
}

void loescheKnoten(char txt[]){
KnotenPtr_t hilfZeiger1;
KnotenPtr_t hilfZeiger2;
if(anfang != NULL){
char tmp[] = anfang->wort
else if( strcmp(txt[], tmp[]) == 0 ){
hilfZeiger1 = anfang->next;
free(anfang);
anfang = hilfZeiger1;
}
else {
hilfZeiger1 = anfang;
while(hilfZeiger1->next != NULL){
hilfZeiger2 = hilfZeiger1->next;
char tmp2[] = hilfZeiger2->wort[];
if( strcmp( txt[] , tmp2[]) == 0 ){
hilfZeiger1->next = hilfZeiger2->next;
break;
}
}
}
}
}

void knotenAuflisten(void){
KnotenPtr_t hilfZeiger = anfang;
while( hilfZeiger != NULL ){
char out[16] = hilfZeiger->wort[16];
SerWrite(out, 16);
hilfZeiger = hilfZeiger->next;
}
}

int main(void){
while(1){
char wahl[2] = '\0';
char tmp[16];
SerWrite("-a- Neues Wort hinzufügen\n\r", 28)
SerWrite("-b- Wort löschen\n\r",19);
SerWrite("-c- Alle Worte auflisten\n\r",27);
SerWrite("Ihre Wahl:\n\r",13);
SerRead(wahl, 1,0);
if( strcmp(wahl, 'a') == 0){
neuerKnoten();
break;
}
else if(strcmp(wahl, 'b')==0){
SerWrite("Wort zum löschen:\n\r",20);
SerRead(tmp, 15,0);
loescheKnoten(tmp[16]);
break;
}
else if(strcmp(wahl, 'c')==0){
knotenAuflisten();
break;
}
}
return 0;
}

Nun zur Fehlermeldung:
> "C:\ASURO_src\FirstTry\Test-all.bat"

C:\ASURO_src\FirstTry>make all
set -e; avr-gcc -MM -mmcu=atmega8 -I. -g -Os -funsigned-char -funsigned-bitfields -fpack-struct -fshort-enums -Wall -Wstrict-prototypes -Wa,-ahlms=asuro.lst asuro.c \
| sed 's,\(.*\)\.o[ :]*,\1.o \1.d : ,g' > asuro.d; \
[ -s asuro.d ] || rm -f asuro.d
0 [main] sh 888 sync_with_child: child 5736(0x154) died before initialization with status code 0xC0000142
45612 [main] sh 888 sync_with_child: *** child state waiting for longjmp
/usr/bin/sh: fork: Resource temporarily unavailable
set -e; avr-gcc -MM -mmcu=atmega8 -I. -g -Os -funsigned-char -funsigned-bitfields -fpack-struct -fshort-enums -Wall -Wstrict-prototypes -Wa,-ahlms=test.lst test.c \
| sed 's,\(.*\)\.o[ :]*,\1.o \1.d : ,g' > test.d; \
[ -s test.d ] || rm -f test.d
0 [main] sh 6852 sync_with_child: child 5140(0x154) died before initialization with status code 0xC0000142
6152 [main] sh 6852 sync_with_child: *** child state waiting for longjmp
/usr/bin/sh: fork: Resource temporarily unavailable
-------- begin --------
avr-gcc --version
avr-gcc (WinAVR 20100110) 4.3.3
Copyright (C) 2008 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

avr-gcc -c -mmcu=atmega8 -I. -g -Os -funsigned-char -funsigned-bitfields -fpack-struct -fshort-enums -Wall -Wstrict-prototypes -Wa,-ahlms=test.lst test.c -o test.o
test.c: In function 'neuerKnoten':
test.c:32: warning: pointer targets in passing argument 1 of 'SerWrite' differ in signedness
test.c:35: warning: pointer targets in passing argument 1 of 'SerWrite' differ in signedness
test.c:36: error: 'wort' undeclared (first use in this function)
test.c:36: error: (Each undeclared identifier is reported only once
test.c:36: error: for each function it appears in.)
test.c: In function 'loescheKnoten':
test.c:45: error: invalid initializer
test.c:45: error: expected ',' or ';' before 'else'
test.c:50: error: expected '}' before 'else'
test.c:44: warning: unused variable 'tmp'
test.c:54: error: expected expression before ']' token
test.c:54: error: array subscript is not an integer
test.c:54: error: invalid initializer
test.c:55: error: expected expression before ']' token
test.c:55: error: array subscript is not an integer
test.c:55: error: array subscript is not an integer
test.c: At top level:
test.c:62: error: expected identifier or '(' before '}' token
test.c: In function 'knotenAuflisten':
test.c:67: error: invalid initializer
test.c:68: warning: pointer targets in passing argument 1 of 'SerWrite' differ in signedness
test.c: In function 'main':
test.c:75: error: invalid initializer
test.c:77: warning: pointer targets in passing argument 1 of 'SerWrite' differ in signedness
test.c:78: error: expected ';' before 'SerWrite'
test.c:79: warning: pointer targets in passing argument 1 of 'SerWrite' differ in signedness
test.c:80: warning: pointer targets in passing argument 1 of 'SerWrite' differ in signedness
test.c:81: warning: pointer targets in passing argument 1 of 'SerRead' differ in signedness
test.c:82: warning: passing argument 2 of 'strcmp' makes pointer from integer without a cast
test.c:86: warning: passing argument 2 of 'strcmp' makes pointer from integer without a cast
test.c:87: warning: pointer targets in passing argument 1 of 'SerWrite' differ in signedness
test.c:88: warning: pointer targets in passing argument 1 of 'SerRead' differ in signedness
test.c:89: warning: passing argument 1 of 'loescheKnoten' makes pointer from integer without a cast
test.c:92: warning: passing argument 2 of 'strcmp' makes pointer from integer without a cast
make: *** [test.o] Error 1

> Process Exit Code: 2
> Time Taken: 00:01


So, jetzt seit ihr dran ;)

LG
Spacy Bar

[Wsk8]

Ich hab jetzt ehrlich gesagt keine Lust mich durch die ganzen Fehler zu wuseln, deshalb kriegste meine funktionierende Lösung. Kompiliert fehlerfrei und in meinem Test gabs auch keine Mem Leaks. Kann aber trotzdem Fehler enthalten.

Gespeichert wird hier der Pointer auf einen String.



#ifndef LIST_H
#define LIST_H




typedef struct Node {
char *dirpath;
struct Node *pNext;
} TNode;


void Prepend(TNode **pList, char const *path);
void Append(TNode **pList, char const *path);
void Delete(TNode **pList, char const *path);
void DeleteAll(TNode *pPath);




#endif




#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#include "list.h"




/* Make new node */
static TNode *MakeNode(char const *path) {
TNode *const pNewNode = malloc(sizeof(*pNewNode));


if(pNewNode == 0) {
fprintf(stderr, "MakeNode(): No memory!\n");
}


if(1 > strlen(path)) {
fprintf(stderr, "MakeNode(): Warning! Empty directory is inserted!");
}


pNewNode->dirpath = malloc(strlen(path)+1);
strcpy(pNewNode->dirpath, path);
pNewNode->pNext = 0;


return pNewNode;
}


//add node at start
void Prepend(TNode **pList, char const *path) {
TNode *pNewNode = MakeNode(path);


pNewNode->pNext = *pList;
*pList = pNewNode;
}


//add node at end
void Append(TNode **pList, char const *path) {
TNode *pNewNode = MakeNode(path);
TNode *pNode = *pList;
TNode *pPrev = *pList;


if(*pList == 0) { //empty list
*pList = pNewNode;
}else{
while(pNode != 0) {
pPrev = pNode;
pNode = pNode->pNext;
}
pPrev->pNext = pNewNode; //catenation with the last new node
}
}


void Delete(TNode **pList, char const *path) {
TNode *pPrev = *pList;
TNode *pNode = *pList;


while(pNode != 0) {
if(strcmp(pNode->dirpath, path) == 0) {
pPrev->pNext = pNode->pNext;
free(pNode->dirpath);
free(pNode); pNode = 0;
break;
}
pPrev = pNode;
pNode = pNode->pNext;
}
}


void DeleteAll(TNode *pPath) {
TNode *pNode = 0; //Pointer


while(pPath != 0) { //stop if end of list reached
pNode = pPath;
pPath = pNode->pNext; //next node
free(pNode->dirpath);
free(pNode); pNode = 0; //delete pointer and set to 0
}
}


mfg

[Valen]

Auch ich habe keine Lust das ganzen durch zu gehen. Aber hier solltest du es ein wenig mit reduzieren können.


test.c:36: error: 'wort' undeclared (first use in this function)
test.c:36: error: (Each undeclared identifier is reported only once
test.c:36: error: for each function it appears in.)

...
do { SerRead(wort[16] ,15,0);
} while( getchar()!='\n');
...


Die String "wort" besteht nicht in dem void Funktion "neuerKnoten". Es ist zwar als Teil von den Struktur "knoten" definiert. Aber das ist kein Speicherplatz.



struct knoten {
char wort[16];
struct knoten *next;
};



test.c: In function 'loescheKnoten':
test.c:45: error: invalid initializer
test.c:45: error: expected ',' or ';' before 'else'
test.c:50: error: expected '}' before 'else'
test.c:44: warning: unused variable 'tmp'




void loescheKnoten(char txt[]){
KnotenPtr_t hilfZeiger1;
KnotenPtr_t hilfZeiger2;
if(anfang != NULL){
char tmp[] = anfang->wort //Hmm, gehört hier nicht ein ; und } wenn dannach ein else if-Zweich anfangt?
else if( strcmp(txt[], tmp[]) == 0 ){ // [] ist nicht notwendig wenn du den gesamten Strings bedeutest. Hier oben aber schon.
...

[Spacy Bar]

Tschuldige ich habe meine erste Fehlermeldung geposted. Ein paar Fehler hatte ich schon behoben.
Jedoch Vielen Dank für die schnellen Antworten und die Codes.

LG
Spacy Bar

[Sisor]

Ich dachte mir, dass kann der Robby auch nur Zahlen sind witzlos, es müssen schon char-Arrays/Strings sein. Das ganze endete in einem Zeigergewirr mit Strukturgewirr verknüpft. Ich hoffe ihr habt eine Lösung für mein Problem, ich habe 'ne ganze menge Zeit rein investiert.
...
So, jetzt seit ihr dran

Du schaffst dir ein 'komplexes' Problem, weil eine einfache Lösung witzlos ist?!
Dann bekommst du es nicht gelöst, es endet in einem Gewirr! Jetzt soll das Forum ran?

Der war gut...

[markusj]

Davon abgesehen: malloc zu verwenden ist auf so kleinen Plattformen wie dem AVR in der Regel keine gute Idee. Zum sind malloc und free "teuer" und zum anderen kannst du es früher oder später mit Speicherfragmentierung zu tun bekommen. In der Regel reicht eine statische Speicherreservierung aus, ist dabei einfacher und im Zweifelsfall auch zuverlässiger.

mfG
Markus

[Spacy Bar]

Du schaffst dir ein 'komplexes' Problem, weil eine einfache Lösung witzlos ist?!
Dann bekommst du es nicht gelöst, es endet in einem Gewirr! Jetzt soll das Forum ran?

Der war gut...
Tut mir leid, das ist von dir falsch verstanden worden. Deswegen habe ich den Zwinker-Smiley dahinter gesetzt, damit es als Witz verstanden wird, das gilt in meinem Umfeld als absolute Entschuldigung.


- - - Aktualisiert - - -


Davon abgesehen: malloc zu verwenden ist auf so kleinen Plattformen wie dem AVR in der Regel keine gute Idee. Zum sind malloc und free "teuer" und zum anderen kannst du es früher oder später mit Speicherfragmentierung zu tun bekommen. In der Regel reicht eine statische Speicherreservierung aus, ist dabei einfacher und im Zweifelsfall auch zuverlässiger.[...]

Das kann ich zum einen nachvollziehen, da der µC nur 1 kb RAM hat, zum anderen Funktionierte das Programm als Zahlenspeicher für den PC ebenfalls nur im Bereich unter einem KB (solange man keinen Zahlenwald darein gepflanzt hat).

LG
Spacy Bar

[markusj]

Das kann ich zum einen nachvollziehen, da der µC nur 1 kb RAM hat, zum anderen Funktionierte das Programm als Zahlenspeicher für den PC ebenfalls nur im Bereich unter einem KB (solange man keinen Zahlenwald darein gepflanzt hat).

Das Problem der Speicherfragmentierung hat erst einmal nichts mit dem verfügbaren Speicher zu tun. Speicherfragmentierung entsteht, wenn im Adressraum einzelne Bereiche belegt sind und andere dazwischen frei. Wenn von den 1kB rechnerisch 50% frei sind kann es so trotzdem passieren, dass selbst ein malloc für 100 Bytes fehlschlagen kann, wenn kein zusammenhängender freier Speicherbereich >=100 Byte vorhanden ist. Ein solcher Flickenteppich im RAM entsteht dann, wenn du unterschiedlich große Speicherblöcke anforderst und der allozierte Speicher dann sehr unterschiedliche "Lebensdauern" hat.
Ein Beispiel (Je Zeichen 64 Byte, + entspricht belegtem Speicher, _ entspricht freiem Speicher) bei dem nur noch Speicheranforderungen bis zu zwei Einheiten (128 Byte) möglich sind - Und wenn man das ganze auf Byte-Ebene betrachtet kann die Fragmentierung noch viel schlimmer werden:
_+++__+__+_++_+_

mfG
Markus

[Spacy Bar]

Das Problem der Speicherfragmentierung hat erst einmal nichts mit dem verfügbaren Speicher zu tun. Speicherfragmentierung entsteht, wenn im Adressraum einzelne Bereiche belegt sind und andere dazwischen frei. Wenn von den 1kB rechnerisch 50% frei sind kann es so trotzdem passieren, dass selbst ein malloc für 100 Bytes fehlschlagen kann, wenn kein zusammenhängender freier Speicherbereich >=100 Byte vorhanden ist. Ein solcher Flickenteppich im RAM entsteht dann, wenn du unterschiedlich große Speicherblöcke anforderst und der allozierte Speicher dann sehr unterschiedliche "Lebensdauern" hat.
Ein Beispiel (Je Zeichen 64 Byte, + entspricht belegtem Speicher, _ entspricht freiem Speicher) bei dem nur noch Speicheranforderungen bis zu zwei Einheiten (128 Byte) möglich sind - Und wenn man das ganze auf Byte-Ebene betrachtet kann die Fragmentierung noch viel schlimmer werden:
_+++__+__+_++_+_

Erstmal Danke für die Erklärung, von den Grundsätzen der Heap-Fragmentierung hatte ich zwar im C-Grundkurs von Jürgen Wolf schon gelesen, aber offensichtlich nicht richtig verstanden. Da stand etwas von Heap-Defragmentierung per Funktionsimplimentierung, allerdings kein Beispiel. Wenn du davon was verstehst, würde ich mich sehr über eine Erklärung freuen.
Außerdem wurde die alternative Funktion alloca() erwähnt, mit der Speicher vom Stack angefordert wird. Wird sie genauso verwendet und macht sie in meinem Fall Sinn?
Ich freue mich über jegliche erklärenden Antworten.

LG
Spacy Bar

[shedepe]

Auf einem Mikrocontroller ist es viel sinnvoller sich einen Ringbuffer zu bauen als eine verkettete Liste. Dessen speicher kann man statisch allokieren. Problematisch wird es nur wenn man zwischen drin Daten einfügen will.

[markusj]

Da stand etwas von Heap-Defragmentierung per Funktionsimplimentierung, allerdings kein Beispiel. Wenn du davon was verstehst, würde ich mich sehr über eine Erklärung freuen.
Außerdem wurde die alternative Funktion alloca() erwähnt, mit der Speicher vom Stack angefordert wird. Wird sie genauso verwendet und macht sie in meinem Fall Sinn?
Heap-Defragmentierung über Funktionen: Keine Ahnung was damit gemeint ist, ich vermute das geht Hand in Hand mit alloca und der Nutzung des Stacks.
Grundsätzlich: Wenn alle Speicheranforderungen bis zum Ende einer Funktion wieder vollständig freigegeben wurden, bekommst du kein Problem mit der Fragmentierung des Speichers - Weil es keine "überlebenden" Speicherblöcke gibt die den Adressraum fragmentieren können.
Für solche "kurzlebigen" Speicherobjekte kannst du dann aber auch den Stack verwenden (die beiden Varianten unterschieden sich dann nicht) - Speicher vom Stack wird mit alloca() angefordert. Vorteil: Bei verlassen der Funktion wird er automatisch freigegeben. Vorteil für alloca(): Die Funktion ist deutlich schneller/performanter als malloc/free.

Nochmal zur Defragmentierung: Das wird ohne größere Klimmzüge nicht funktionieren. Dazu würdest du eine zusätzliche Ebene zusätzlicher Indirektion benötigen die es dir erlaubt, Speicherbereiche im Hintergrund zu verschieben ohne die Verweise darauf ungültig zu machen. Direkte Pointer können das nicht leisten, du müsstest also mit Referenzen arbeiten.

mfG
Markus

[Spacy Bar]

@shedepe Ich habe mir soeben ein Beispiel eines Ringbuffers angesehen, aber ihn nicht wirklich verstanden. Könntest du vielleicht ein gut kommentiertes Beispiel posten?

Problematisch wird es nur wenn man zwischen drin Daten einfügen will.
Das habe ich nicht vor, nur notfalls bereits gespeicherte Daten löschen, ohne die gesamte Liste/den gesamten Ringbuffer zu leeren.

LG
Spacy Bar

[shedepe]

Schau mal hier:
https://www.mikrocontroller.net/articles/FIFO

http://rn-wissen.de/wiki/index.php/FIFO_mit_avr-gcc

Prinzip ist wie eine queu (Also First in First out).

[Spacy Bar]

Heap-Defragmentierung über Funktionen: Keine Ahnung was damit gemeint ist, ich vermute das geht Hand in Hand mit alloca und der Nutzung des Stacks.
Grundsätzlich: Wenn alle Speicheranforderungen bis zum Ende einer Funktion wieder vollständig freigegeben wurden, bekommst du kein Problem mit der Fragmentierung des Speichers - Weil es keine "überlebenden" Speicherblöcke gibt die den Adressraum fragmentieren können.
Für solche "kurzlebigen" Speicherobjekte kannst du dann aber auch den Stack verwenden (die beiden Varianten unterschieden sich dann nicht) - Speicher vom Stack wird mit alloca() angefordert. Vorteil: Bei verlassen der Funktion wird er automatisch freigegeben. Vorteil für alloca(): Die Funktion ist deutlich schneller/performanter als malloc/free.

Nochmal zur Defragmentierung: Das wird ohne größere Klimmzüge nicht funktionieren. Dazu würdest du eine zusätzliche Ebene zusätzlicher Indirektion benötigen die es dir erlaubt, Speicherbereiche im Hintergrund zu verschieben ohne die Verweise darauf ungültig zu machen. Direkte Pointer können das nicht leisten, du müsstest also mit Referenzen arbeiten.[...]
Danke, gut dass das geklärt ist. Ich meinte allerdings mit der Verwendung von alloca() hauptsächlich die Syntax. Ist das 1 zu 1 mit malloc() austauschbar und macht das das free() überflüssig?
Bitte um baldige Antwort.

LG
Spacy Bar

[Wsk8]

http://bit.ly/1n8j23N

mfg

[markusj]

Danke, gut dass das geklärt ist. Ich meinte allerdings mit der Verwendung von alloca() hauptsächlich die Syntax. Ist das 1 zu 1 mit malloc() austauschbar und macht das das free() überflüssig?

http://www.nongnu.org/avr-libc/user-manual/group__alloca.html
http://www.nongnu.org/avr-libc/user-manual/group__avr__stdlib.html#ga4996af830ebe744d9678e525 1dfd3ebd

mfG
Markus

[Spacy Bar]

Gut, danke für die Erklärung und das für mich googeln.

LG
Spacy Bar