RingBuffer

Hallo Bitsy, kannst du mir sagen woher du dich so gut mit Datenstrukturen auskennst? Woher hast du dein ganzen Wissen? Du scheinst ja echt Experte auf diesem Gebiet zu sein.

D*niel *chumann

Original erstellt von Bitsy:
Ein Ringbuffer bleibt für meine Begriffe immer ein Array

Wenn ein Ringbuffer ein Array ist, was ist dann eine Verkettete Liste, deren Ende wieder auf den Anfang zeigt? Ausserdem was hat ein Array mit einem Ring zu zun?

Daniel E.

Das scheint man ringverkettete Liste o.ä. zu nennen.
Dummerweise gibt's keine einheitlichen Bezeichnungen für derartige Datenstrukturen. Ich hatte bei Ringpuffer auch mehr obiges im Kopf. Die Mehrzahl der Leute versteht darunter allerdings etwas anderes (Siehe Linux-Kernel `printk').

Ich nehme also alles zurück :).

Der Vorteil eines 'althergebrachten' Ringbuffers ist einfach, dass er keine Dynamik hat, also nicht die vergleichsweise langsamen new/malloc-Dinge rufen muss. Oftmals wird er nämlich in zeitkritischen Interrupts eingesetzt. Und in Multitasking (nicht Multithreading!)-Environment muss man das Ein- und Austragen der Daten extrem vorsichtig programmieren.

@Schlange:
Aus der Praxis, für die Theorie sind andere zuständig

Bashar

Original erstellt von Daniel E.:
Eine Schlange kann man auch als verkettete Liste implementieren, allerdings muss man sich entscheiden, ob man lieber O(n) für 'get' haben will, oder doch eine doppelt verkettete Liste will. Wenn man keine Monsterdaten verwaltet würde ich trotzdem `realloc' nehmen.

Eine Queue kann auch mittels einfach verketteter Listen so implementiert werden, dass einfügen und entfernen in konstanter Zeit möglich sind.

Shade Of Mine

Original erstellt von <NasenMann>:
*Ringbuffer: Im Sinne eines FIFO ("vorne" sequentiell reinschreiben, "hinten" sequentiell rauslesen)

Hallo Leute!

Diese Zeile liest sich fuer mich, wie die Definition einer normalen deque oder list...

vorne und hinten, das schliesst (IMHO) einen echten Ring aus...

Bashar

Shade: Normale Queue, keine Deque (double-ended queue)

Daniel E.

Original erstellt von Bashar:
Eine Queue kann auch mittels einfach verketteter Listen so implementiert werden, dass einfügen und entfernen in konstanter Zeit möglich sind.

Also, wenn ich das Ende der Liste finden will, so muss ich alle Listenelemente betrachten.
Wenn ich einen Zeiger auf das Ende der Liste habe, dann kann ich zwar das letzte Element in konstanter Zeit löschen, aber um das 'neue letzte' Element herauszufinden muss ich doch wieder über alle Listenelemente laufen. Das klingt nicht sehr konstant für das Entfernen, finde ich.

Hab ich irgendwas verpasst?

Bashar

Umgekehrt: Entfernen am Kopf, Einfügen am Ende.

[ Dieser Beitrag wurde am 09.10.2002 um 15:01 Uhr von Bashar editiert. ]

Daniel E.

Autsch. Danke.
[Hat das vielleicht irgendeinen tieferen Sinn, dass ich ausgerechnet jetzt zum Augenarzt muss? :)]

[QB]Der Vorteil eines 'althergebrachten' Ringbuffers ist einfach, dass er keine Dynamik hat, also nicht die vergleichsweise langsamen new/malloc-Dinge rufen muss. Oftmals wird er nämlich in zeitkritischen Interrupts eingesetzt. Und in Multitasking (nicht Multithreading!)-Environment muss man das Ein- und Austragen der Daten extrem vorsichtig programmieren.

Genau das ist es. Mein Problem ist: embedded Umgebung, wenig Speicher, noch weniger Zeit. Bei verketteten Listen tritt folgendes Problem auf: wenn ich Daten an eine andere Task übergebe, will diese einen zusammenhängenden Speicherbereich haben. Bei verketteten Listen müsste ich dann wieder umkopieren, falls der Bereich sich über mehrere Beriche erstreckt. ANSI C scheint mir in Sachen Speichermanagement leider bereits zu virtuell angelegt zu sein und keine Kontrolle zu ermöglichen.

Bei weiteren Projekten werde ich sicherlich eine Library für verkettete Listen verwenden, wenn ich mein Team überzeugen kann, sie durchgängig in absolut allen Bereichen des Projektes zu verwenden (sonst ist der Vorteil wieder dahin). Allein bei senden auf's host controller interface (die Schnittstelle zur Hardware) müsste dann noch einmal zusammenkopiert werden).

Danke an alle für die Diskussion!

O.

Bashar

Man kann verkettete Listen natürlich auch in einem geschlossenen Speicherbereich implementieren. Einfach ein großes Array allozieren und eigene Funktionen für malloc/free implementieren (je nach Einsatzzweck auch extrem versimplifiziert).
U.u. auch die Verkettungen durch Array-Indizes ersetzen, kostet u.U. weniger Speicherplatz.

Hi,

was ist unter diese Aufgaben stellung zu verstehen ?

******************************************************
Bei jedem Aufruf des Programms werden die neuen Runtime Parameter den bereits vorhandenen hinzugef�gt.Der Ringpuffer soll eine max. Anzahl (N=10) von Elementen speichern k�nnen. Sie m�ssen diese zu Beginn des Programms einlesen und am Ende wieder speichern. Solange der max. F�llungsgrad noch nicht erreicht ist, sollen die neuen Werte in der Reihenfolge des Einlesens gespeichert werden. Ist der max. F�llungsgrad erreicht, werden die jeweils �ltesteten Werte �berschrieben.
******************************************************

Also werte einlesen nach programm start und beim nächsten Start sollen die Daten wieder da sein. Wie geht das ? Oder ist was anderes damit gemeint ?

mfg
Latzi

TheTester

latzi
*****

vielleicht ist ja sowas gemeint hier mal eine einfache idee, nur für ints sollte aber für chars und "pointer auf arrays" genauso funktionieren

EDIT: ach ja das mit dem einlesen und speichern erfordert dann natürlich arbeit mit datein

int const n = 10;
	int anz = 15;

	int a[n];

	int i;
	for(i=0; i < anz; i++)
		a[i%n]= i;

	for(i=0; i < n; i++)
		printf("%d ",a[i]);

bye

tt

PAD

@tester was hat das mit einem Fifo-Ringspeicher zu tun,
- wie werden Daten eingetragen?
- wie werden Daten entnommen?
- wie stellt man sicher die Ausgabe nicht die Eingabe überholt?
- Soll man wissen das eine Eingangs-Überlauf stattgefunden hat?
- wie stelle ich sicher das ich nicht gerade an der Stelle eintrage, die gerade
ausgegeben wird?

@Nasenmann kannst du das mit dem beliebig großwerden noch etwas genauer spezifizieren, weil die beiden Informationen dynamisch beliebig groß und Ringbuiffer meiner Ansicht nach ausschließen.

Ein Ringbuffer lebt meiner Ansicht nach von einer festen Tiefe, die wenn er voll ist entweder einen Fehler meldet oder die ältesten Elemente überschreibt.
ein dynamisch wachsender Buffer legt davon das ich an einem Ende reinschreiben kann soviel ich will und am anderen Ende soviel entnehmen kann wie ich will.

Oder suchst du eine System welches nur in einem definierten Memory-Areal z.B 64 KB agiert und sich dort wie ein Ringbuffer verhält. in diesem Falle hängt es von deinen Daten ab. sind sie von vorher definierte Größe kann man durch die Wahl der Fifo-Tiefe diese Areal optimal nutzen. Sind die Daten von unterschiedlicher Größe sollte man prüfen ob man nicht das längste Datenpaket als als Standardgröße definieren kann. Geht das nicht mauß man sich eine eigne Datenverwaltung schreiben.
Ich würde den zur Verfügung Stehenden Speicher in 2 Teile teilen
- einen statischen Teil der den Fifo verwaltet, Schreibpointer Lesepointer ein Array von FIFO-Tiefe
die für das Element die Information voll/leer/overwriten enthält einen Zeiger in den zweiten Teil des Memories und die Größpeninformation der gespeicherten Daten.
- den dynamischen Teil eigentlich eine Array of Byte wird vom Anfang her beschreiben, neue Informationen knüpfen unmittelbar an die letzte Information an. werden Informationen entmommen so geschieht dies auch vom Anfang her - da keine Informationen in der Mitte entnommen werden dürfen (FIFO) kann keine Fragmentirung auftreten - somit wandert immer einen unfragmentierter Block von Informationen durch den zweiten Speicherbereich. Interessant wird es wenn man am Ende des Speicherberichs ankommt den Wrap around zu schaffen. Mein Vorschlag wäre, am Ende lieber ein paar Bytes verlieren in dem man fordert das in einem Eintrag keine Umbruch stattfindet.

Ich hoffe das hat geholfen

TheTester

pad
***

- wie werden Daten eingetragen?

einfach so wie ich sie eingetragen hab...

- wie werden Daten entnommen?

einfach so wie ich drauf zugreife

- wie stellt man sicher die Ausgabe nicht die Eingabe überholt?

versteh ich nich ganz, da bei latzi am anfang eingelesen wir und am ende gespeichert wird und da zwischen entweder das ding nur fast voll, voll oder überschrieben wird

- Soll man wissen das eine Eingangs-Überlauf stattgefunden hat?

kannst ja ein flag setzen

- wie stelle ich sicher das ich nicht gerade an der Stelle eintrage, die
gerade ausgegeben wird?

kannst ja readwrite funktionen schreiben die geflaggt werden, eine funktion flaggt die andere, und in der aufgabenstellung von latzi war nix von ausgabe zu lesen...ich wiederhole noch mal am anfang werden die parameter eingelesen am ende gespeichert ich sehe da keine schreib/lese fehler

aber ich weiß gar nicht was du hast es erfüllt schließlich alle Bedingungen die latzi gestellt hat und für mich ist ein Ringpuffer nun mal ein Ring und kein Fifo, dh. für mich wäre das eine verkette liste wo anfang == ende ist das ich jetzt scherzeshalber mal ein array genommen hab...meine güte...

bye

tt

PAD

Sorry meine Antworten haben sich auf die ursprüngliche Augfgabenstellung von NasenMann bezogen

TheTester

jo kein problem, wobei ich ja nasenmanns problem nicht so richtig verstehe ;), weil wenn er schon einen FIFO will warum schreibt er dann keinen

bye

tt

Hi,

thx erst mal an alle, aber das problem hat sich gelöst. Dachte wir sollen das erst ohne dateien schreiben mit dem zwischenspeichern der werte, aber da wir jetzt mit Dateien arbeiten ist es doch schon um einiges einfacher. THX.

mfg
Latzi

Hi,

habe den ringbuffer jetzt geschrieben allerdings habe ich folgende Irrsinnigen Fehler.

Also bis zum einlesen der datei stimmen die Werte noch. Während des Push-Vorganges ändert sich aber erst nach dem 3-4 mal der org. Wert in 4. Bei der Variable Bart. Lass ich sie weg passiert das bei nout, welche ich ja benötige. Woran liegt das ?

PS: Hauptprogramm ist einfach eine aufruf der Funktion mit übergabe der Runtime Argumente und den nötigen Includes ... Größe vom Ringbuffer = 10 Werte.

mfg Latzi

static int count = 0;

typedef struct element
{
   char nutzlast[20];
   int zelle;
   struct element * next;
}Element;

static Element * first;

Element* createStructElement(char* nutzlast)
{
   Element * neu;
   neu = (Element *) malloc (sizeof(Element));

   sprintf(neu->nutzlast,"%s", nutzlast);
   neu->zelle = count;
   neu->next = NULL;

   return (neu);
}

void push(char* Nutzlast)
{
   static Element * tmp;
   static Element * prelast;
   int tmpcount, i;

   if (count == 0)
   {
      tmp = createStructElement(Nutzlast);
      first = tmp;
   }
   else if (count >= 10)
   {
      tmpcount = count - 10;
      tmp = first;
      for (i = 0; i < tmpcount; i++)
      {
         tmp = tmp->next;
      }
      sprintf(tmp->nutzlast,"%s", Nutzlast);
      if (count == 19) count = count - 10;
   }
   else
   {
      prelast = tmp;
      tmp = createStructElement(Nutzlast);
      prelast->next = tmp;
   }
   count++;
}

int info1h2 (int argc, char *argv[])
{
   Element * prelast;
   Element * tmp;
   FILE *datei;
   int i = 0;
   int anfang = 0;
   int nout = atoi(argv[1]);
   int bart = nout; // Unnötige Variable, trotzdem wichtig
   char q[20];
   char *w = q;

   datei = fopen("info1h2.dat", "r");

   if (datei != NULL)
   {
      fscanf(datei,"%d %d\n", &i, &anfang);
      while ((fscanf(datei,"%s\n", q)) != EOF)
      {
         push(w);
      }
      fclose(datei);
      remove("info1h2.dat");
      count = i;
   }
   datei = fopen("info1h2.dat", "a+");

   for (i = 2; i < argc; i++)
   {
      push(argv[i]);
   }

   for (i = 0, tmp = first; i < anfang; i++) tmp = tmp->next;

   for (i = 0; i < nout; i++)
   {
      printf("%2d. Zelle: %s \n", tmp->zelle, tmp->nutzlast);
      if (tmp->next == NULL) tmp = first;
      else tmp = tmp->next;
   }

   fprintf(datei, "%d %d\n", count, tmp->zelle);
   tmp = first;
   while (tmp->next!=NULL)
   {
      fprintf(datei, "%s\n", tmp->nutzlast);
      tmp = tmp->next;
   }
   fprintf(datei, "%s\n", tmp->nutzlast);
   fclose(datei);

   tmp = first;

   while (tmp->next!=NULL)
   {
      prelast = tmp;
      tmp = prelast->next;
      free(prelast);
   }
   free(tmp);

   return 0;
}