hilfe zu malloc und free bei verketter liste

[husten (Gast)]

ich brauch mal eine hilfe zu malloc( calloc )  und free

MCU ist ein Cortex M3


es soll eine einfach verkettete liste sein ..
dazu wird bei bedarf ein elemet erstellt
später irgendwann wieder gelöscht.

Frage an die PROFIS ..
geht das "FREE(" hier so ?

das calloc funktioniert hier prima ..

__attribute__((packed)) struct data_struct{
  struct data_struct  *next;
  uint32_t       data[12];
};

struct data_struct*   data_table = NULL;

void data_remove( struct data_struct* block ){
  struct data_struct* tmp;
  if(data_table == block) {
    tmp = block->next;
    memset( block ,0, sizeof(struct data_struct) );
    free(block);
    data_table = tmp;
  }else{
    for(tmp = data_table; tmp != NULL; tmp = tmp->next) {
      if(tmp->next == block) {
        tmp->next = block->next;
        memset( block ,0, sizeof(struct data_struct) );
        free( block );
        break;
      }
    }
  }
}

struct data_struct* data_new( void ){
  struct data_struct *new_block;

  new_block = calloc( sizeof(struct data_struct) , sizeof(char) );
  if( new_block == NULL ){
    return NULL;
  }
  if(data_table == NULL) {
    new_block->next = NULL;
  }else{
    new_block->next = data_table;
  }
  data_table = new_block;  // new element to first position in list
  return new_block;
}

int main(void){
        struct data_struct*   data;
  SystemInit();

  data = data_new();
  data->data[0] = 5 ;
  data_remove( data );

        for(;;);
}

[Jay (Gast)]

Das ist zu kompliziert gemacht, bzw. zum Teil sinnloser Code. Nur ein 
Beispiel:

  if(data_table == NULL) {
    new_block->next = NULL;
  }else{
    new_block->next = data_table;
  }

kann man zu einer Zeile eindampfen:

 new_block->next = data_table;

So geht das dann weite. calloc() macht keinen Sinn. Die Sonderbehandlung 
des ersten Blocks beim remove macht keinen Sinn, usw.

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

Blöcke vor dem free() ausnullen ist, sofern es sich nicht gerade um
sensitive Daten (Passwörter etc.) handelt, auch eher überflüssig.

Aber im Prinzip müsste das mit dem free() so passen.

[husten (Gast)]

Jay schrieb:
> Das ist zu kompliziert gemacht, bzw. zum Teil sinnloser Code. Nur ein
> Beispiel:
>   if(data_table == NULL) {
>     new_block->next = NULL;
>   }else{
>     new_block->next = data_table;
>   }
>
> kann man zu einer Zeile eindampfen:
>  new_block->next = data_table;
>
> So geht das dann weite. calloc() macht keinen Sinn. Die Sonderbehandlung
> des ersten Blocks beim remove macht keinen Sinn, usw.

ja optimieren kann man dies sicher ..
nur gehts ertsmal grob um die funktion ...

calloc weil ich alles "0" haben will
sonst müsste ich malloc und memset machen

diese sonderbehaldlung keinen sinn ?
es gibt bei dieser liste keinen listenkopf
die fängt eben mit einem pointer auf NULL an und endet genau in diesem
mal schauenw as er dazu sagt wenn ich das auslasse

[Peter D. (peda)]

Auf einem MC kann man in der Regel keine Anwendung schließen, wenn der 
Speicher knapp wird.
Daher reserviert man einfach fest eine sinnvolle Größe an RAM für die 
Liste und gut.

Auch hat man oft auf einem MC keinen Garbage-Collector. D.h. wenn man 
extensiv malloc und free benutzt, kann es passieren, daß irgendwann der 
RAM so sehr fragmentiert ist, daß malloc fehlschlägt.

[husten (Gast)]

Jörg Wunsch schrieb:
> Blöcke vor dem free() ausnullen ist, sofern es sich nicht gerade um
> sensitive Daten (Passwörter etc.) handelt, auch eher überflüssig.
>
> Aber im Prinzip müsste das mit dem free() so passen.

OK
dachte das sollte man lieber nullen ...

das free passt soweit ..
habe meinen fehler gefunden.

im timer war nach dem remove die liste natürlich nicht mehr aktuell und 
der ->next zeigte nun ggf ins nichts


danke

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

Peter Dannegger schrieb:
> Auf einem MC kann man in der Regel keine Anwendung schließen, wenn der
> Speicher knapp wird.

Doch.  Reboot. :-)

> Daher reserviert man einfach fest eine sinnvolle Größe an RAM für die
> Liste und gut.

Welche Größe ist denn sinnvoll, wenn du sie vorher nicht kennst?

Was passiert, wenn dann mehr Daten vorliegen, als diese „sinnvolle“
Größe handhaben kann?

Wenn man ein dynamisches Problem hat, hat man immer die Po-Karte
gezogen, wenn mehr Daten anfallen, als man gerade Speicher hat.
Eine „Exit-Strategie“ benötigt man in diesem Falle immer, egal, ob
man nun das verfemte malloc() benutzt oder irgendwas Präalloziertes.

Wenn man kein dynamisches Problem hat, braucht man auch keine
Klimmzüge mit Listen und dergleichen anstellen.

> Auch hat man oft auf einem MC keinen Garbage-Collector. D.h. wenn man
> extensiv malloc und free benutzt, kann es passieren, daß irgendwann der
> RAM so sehr fragmentiert ist, daß malloc fehlschlägt.

Da er nur gleich große Strukturen alloziert, passiert das nicht: in
einen freigegebenen Bereich muss dann immer wieder eine neue Struktur
dieser Größe reinpassen, alles andere wäre unlogisch.

Bei ungleich großen Datenelementen kommt es darauf an, inwiefern deren
Größe beim Datenanfall gut genug statistisch verteilt ist.  Ab einer
bestimmten Speicherreserve (ähnlich der 10-%-Reserve beim Berkeley
UFS [Unix FileSystem]) dürfte ein derartiges System langzeitstabil
werden, d. h. die Fragmentierung erreicht irgendwann einfach einen
Maximalwert.

Hängt aber natürlich alles auch von der malloc()-Implementierung
selbst ab.  Keine Ahnung, was da bei der Newlib dabei ist.

Auch ist natürlich „Cortex M3“ nur eine sehr grobe Hausnummer.  Da
kann von wenigen Kilobyte RAM bis zu mehreren Megabyte alles dran
hängen.  Es gab Zeiten, da liefen mit 2 x 64 KiB RAM (sogar noch
etwas weniger wegen der System IO Register Page) ganze UNIX-Systeme …

[Karl H. (kbuchegg)]

husten schrieb:

> OK
> dachte das sollte man lieber nullen ...

Zu Debug Zwecken ist das sicher nicht schlecht.
Wobei es manchmal besser ist, ein anderes Muster zu benutzen. 0 kommt in 
den Daten schon recht häufig vor. Alles mit 0xFF vollzukleistern wäre zb 
eine Möglichkeit. Stösst du während der Entwicklung je auf einen Block, 
der lauter 0xFF enthält, dann weißt du, dass du einen ungültigen Pointer 
im System hast und daher noch irgendwo mindestens 1 Fehler im Programm 
sein muss.

> diese sonderbehaldlung keinen sinn ?

Die Sonderbehandlung im remove ist schon ok. Solange du einen 
Root-Pointer hast und nicht ein komplettes Objekt als Root-Objekt 
vorsiehst geht das nicht anders.

Allerdings solltest du deinen Code trotzdem schnell streamlinen. Gerade 
bei derartigen Funktionalitäten verliert man schnell den Überblick, wenn 
man es zu lange hinauszögert. Und dann läuft man Fehlern nach, die man 
nicht sieht, weil man sich in den Sonderfällen verhaspelt, die 
eigentlich gar nicht notwendig sind. Gerade bei dynamischen 
Datenstrukturen ist sauberer und übersichtlicher Code sehr wichtig.

[Karl H. (kbuchegg)]

Tip: bei dynamischen Listen benötigt man auch oft eine 'Previous' 
Funktion, die zu einem Node seinen Vorgänger raussucht. Deine Remove 
Funktion basiert genau darauf. Machst du dir eine entsprechende Funktion 
dann vereinfacht sich die Funktion zu

void data_remove( struct data_struct* block ){

  if( data_table == block )
    data_table = block->next;
  else {
    struct data_struct* previous = data_previous( block );
    if( previous )
      previous->next = block->next;
  }

#ifdef DEBUG
  memset( block, MAGIC_PATTERN_BYTE, sizeof(struct data_struct) );
#endif
  free( block );
}

und das ist schon wieder leichter zu überblicken bzw. zu verstehen. 
Insbesonder letzteres, die leichte Erfassbarkeit beim Lesen eines Codes, 
ist ein wichtiges Kriterium in der Entwicklung. Je besser lesbar du dir 
den Code machst, umso weniger dumme Fehler machst du.

[Amateur (Gast)]

Auch wenn der Speicher theoretisch reichen sollte:
Malloc und free sind bei geringem Gesamtspeicher problematisch.
Vor allem dann, wenn unterschiedlich große Häppchen abgebissen werden.

[husten (Gast)]

hi

Danke erstmal für die gute erklärung

Karl Heinz schrieb:
> Allerdings solltest du deinen Code trotzdem schnell streamlinen.

das ist mein problem...
ich bekomm das nicht so schick hin.

Karl Heinz schrieb:
> Tip: bei dynamischen Listen benötigt man auch oft eine 'Previous'
> Funktion, die zu einem Node seinen Vorgänger raussucht.

stimmt.
Vielen dank werde das so übernehmen :-)

[flobber (Gast)]

Die "übliche" Methode, ein Element aus einer einfach verketteten Liste 
zu löschen:

void data_remove(struct data *block)
{
    struct data *p, **pp;

    for (pp = &data_table; (p = *pp) != NULL; pp = &p->next)
        if (p == block)
        {
            *pp = p->next;
            free(p);
            break;
        }
}

Warum das funktioniert, solltest du zu Übungszwecken selbst 
herausknobeln ;-)

[husten (Gast)]

flobber schrieb:
> Warum das funktioniert, solltest du zu Übungszwecken selbst
> herausknobeln ;-)


hi

danke dafür.
aber ich hab so meine problemchen mit **pp ...
ich habs jetzt probiert  .. und ja es geht ...

struct data *p, **pp;
*p is ein pointer
**pp ein pointer auf einen pointer

ich komm mit verdröselten for() nicht klar
for (pp = &data_table; (p = *pp) != NULL; pp = &p->next)


pp ist ein pointer auf den anfang
*pp ist ein pointer auf den ->next

insgesammt versteh ich es nicht wirklich ...

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

husten schrieb:
> ich komm mit verdröselten for() nicht klar

Immer dran denken, dass man ein for() auch als while() schreiben
kann:

for (x; y; z) {
  ...
}

=>

x;
while (y) {
  ...
  z;
}

(Es gibt geringfügige Unterschiede zwischen beiden, wenn man ein
continue macht, aber die spielen hier keine Rolle.)

[Karl H. (kbuchegg)]

husten schrieb:

> *pp ist ein pointer auf den ->next

wobei du das mit dem 'next' unter den Tisch kehren solltest.
*pp ist einfach die Adresse jenes Speicherortes, an der der Pointer zu 
finden ist, der auf diesen Knoten zeigt.

Denn

Das können ja 2 verschiedene Dinge sind.
Im NOrmalfall ist es der next Pointer vom Vorgängerknoten.
Aber!
Beim ersten Knoten in der Liste gibt es keinen Vorgängerknoten, sondern 
in diesem Fall steht diese Adresse ja in data_table drinne.

Mit dem 2-Stern Pointer spielt das aber keine Rolle mehr. Denn dort 
steht ja die Adresse drinn, wo der Pointer auf diesen Knoten gespeichert 
ist. Und das kann natürlich auch genau dieses data_table sein.

D.h. mit dem 2-Stern Pointer hast du den Sonderfall des ersten Knotens 
bzw. des Root-Pointers umschifft. Das ist dann kein Sonderfall mehr.

[flobber (Gast)]

> aber ich hab so meine problemchen mit **pp ...

Nicht durch die vielen Sternchen verwirren lassen ;-)  Wie du schon 
erkannt hast, ist es ein Pointer.  Auf was für einen Typ der Pointer 
zeigt, ist erstmal egal.  Schau lieber, wohin er zeigt - am Anfang und 
nach jedem Iterationsschritt.  Ein Blatt Papier kann da evtl hilfreich 
sein :-)

[flobber (Gast)]

Schade, jetzt hat KH fast alles erklärt - mMn lernt man viel intensiver, 
wenn man sich so etwas selbst herausknobelt.

[Karl H. (kbuchegg)]

flobber schrieb:

> Ein Blatt Papier kann da evtl hilfreich
> sein :-)

Das unterstütze ich ungemein.
Gerade bei dymaischen Datenstrukturen kann einem mitzeichnen der 
Operationen regelrecht die Augen öffnen.

[huhu (Gast)]

Jörg Wunsch schrieb:
> Immer dran denken, dass man ein for() auch als while() schreiben
> kann:


OK  ds die beiden  grob das selbe machen war mir klar ...
aber SO hab ich das noch nicht betrachtet

Vielen Dank

Karl Heinz schrieb:
> Das können ja 2 verschiedene Dinge sind.
> Im NOrmalfall ist es der next Pointer vom Vorgängerknoten.
> Aber!
> Beim ersten Knoten in der Liste gibt es keinen Vorgängerknoten, sondern
> in diesem Fall steht diese Adresse ja in data_table drinne.
>
> Mit dem 2-Stern Pointer spielt das aber keine Rolle mehr. Denn dort
> steht ja die Adresse drinn, wo der Pointer auf diesen Knoten gespeichert
> ist. Und das kann natürlich auch genau dieses data_table sein.
>
> D.h. mit dem 2-Stern Pointer hast du den Sonderfall des ersten Knotens
> bzw. des Root-Pointers umschifft. Das ist dann kein Sonderfall mehr.

stimmt
beim steppen ist der anfangswert die adresse der tabelle
dann wird die adresse immer durchgeschoben
also vom aktuellen und dem vorgänger

flobber schrieb:
> Nicht durch die vielen Sternchen verwirren lassen ;-)  Wie du schon
> erkannt hast, ist es ein Pointer.  Auf was für einen Typ der Pointer
> zeigt, ist erstmal egal.  Schau lieber, wohin er zeigt - am Anfang und
> nach jedem Iterationsschritt.  Ein Blatt Papier kann da evtl hilfreich
> sein :-)

jaaa  die ** verwirren mich ^^



naja wieder etwas gelernt :-)
vielen dank nochmal an alle beteiligten

pointer und ihre eigenheiten ...
ich mag ja funktionszeger und so ..
aber das ** und solche konstrukte bereiten mir noch kopfschmerzen
hab mir aber schon diverse sachen parat gelegt um das mal weiter zu 
testen