C++ Buffer Ideenproblem

najjannaj

alles komplett per Hand Daher keine Libaries und keine malloc oder free oder sowas funktionen.. Geht mir auch hauptsächlich um die Idee dabei..

naja, dann musste dir wohl als speicher erstmal ein fettes char[]-array anlegen und brauchst 'nen fifo-code, der damit arbeitet. beispiele für fifos und ringbuffer gibts ja genug. probier's mal bei google mit 'fifo filetype:c' oder 'ringbuffer filetype:c'. gefundene codes musste natürlich entsprechend umbauen, da du ja auch rückwärts lesen willst. 'normale' fifo-codes geben den gelesenen speicher sofort frei. du darfst den bufferplatz natürlich nicht beim auslesen freigeben, sondern irgendwann später, wenn ganz sicher ist, dass die daten nicht nochmal gelesen werden müssen.

najjannaj

Soweit bin ich mit der Idee und der Programmierung schon, allerdings habe ich das Problem mit dem über die zu lesenden Grenzen und Einfügen noch nicht hinbekommen..

Wenn ich rückwärts lese, springe ich vielleicht über die Grenze bei der Daten neu einzulesen sind, wenn ich dann wieder vorwärtslese werden Daten neu eingelesen, die aber gar nicht eingelesen werden dürften.. Und da hab ich noch keine Idee wie ich das umsetzte..

mcr

Eine Idee:
-- wenn sichergestellt ist, dass du mit den Rückwärtsschritten nie mehr
als 1023 Zeichen am Stück abläufst, kannst du dir ja merken, an welcher
Position die neuen 1024 byte eingelesen werden müssen:
Bsp:

--  du hast die ersten 1024 bytes eingelesen. 
     Also merkst du dir: new_read_in_at = 1024
 --  sobald das 1024 zeichen gelesen wurde, müssen die nächsten Bytes
     eingelesen werden. 
     Also merkst du dir nun: new_read_in_at = 2048
 --  Jedesmal fragst du: if (pos == new_read_in_at), dann liest du
     die nächsten 1024 bytes ein und setzt die Variable new_read_in_at
     auf den nächsten Wert.

Hier kommt nun die obere Einschränkung:
Bsp:

--  new_read_in_at = 2048
     pos = 1024
 --  Wenn nun so viele get_prev kommen, dass du bei 2048 ankommst, 
     geht diese Idee schief.

Aber dann hast du eh ein Problem:

--  Die Daten die du dann bekommst, sind nicht wirklich die Vorgänger-
     daten, sondern ja schon die neuen.

Diesen Fall solltest du abfangen:

--  in deiner get_prev Funktion solltest du so etwas einbauen wie:
     if (pos == new_read_in_at) Fehler
 --  Eine ähnlicher Fehler wäre: er wurde nur einmal 1024 bytes eingelesen
     und du willst mit get_prev auf das 2048 Zeichen zugreifen.

Eine andere Idee:

class {

private:
  char buffer1[1024], buffer2[1024];
  char *cur, *prev;
}

Der Pointer cur zeigt immer auf den neueren der beiden Buffers und prev dann
auf den Vorgänger.

Bei einem read_data passiert dann folgendes:

--  swap(cur, prev); // austauchen der beiden pointer
 --  read data in cur;

Nun hast du einen positionszeiger (buf, pos), der angibt, in welchem
Buffer buf auf welcher Position er sich befindet.

--  Solltest du nun im prev buffer auf position 0 sein und get_prev aufrufen,
     hast du einen Fehler.
 --  Wenn du dich im cur buffer auf position 1023 befindest, musst du
     read_data bei get_next aufrufen.
 --  Wenn du im cur buffer auf position 0 bist, musst du bei get_prev in den
     prev buffer auf position 1023 wechseln.

Nebenbei kannst du dir noch merken, ob die Buffer überhaupt schon gefüllt
sind.

Gruß mcr

najjannaj schrieb:

Wenn ich rückwärts lese, springe ich vielleicht über die Grenze bei der Daten neu einzulesen sind, wenn ich dann wieder vorwärtslese werden Daten neu eingelesen, die aber gar nicht eingelesen werden dürften..

in so'nem ringbuffer gibt's doch einen lese- und einen schreibzeiger. aus der position beider zeiger kannst du berechnen, wieviel platz noch im buffer ist und wieviele daten schon drin sind. die berechnung ist natürlich davon abhängig, ob sich der schreibzeiger hinter dem lesezeiger befindet oder davor. du kannt natürlich auch eine zählvariable verwenden, wenn du mit den zeigern nicht rumrechenen willst. mal dir am besten die verschiedenen szenarien mit stift und papier auf, dann siehst du leicht, wie man over- und underruns ausschliessen kann.

najjannaj

Erstmal Danke an alle.. hab noch keine sichere Lösung aber werde die von "mcr" mal probieren.

Das mit dem Lese und Schreibzeiger hatte ich mir auch schon überlegt.. allerdings habe ich das Problem das der Schreibezeiger nach 2048 schreibzyklen ja auf 0 wechselt da er im Chararray wieder von vorne anfangen, das hieße der Lesezeiger wäre größer als der Schreibezeiger und das wäre nicht so praktisch.. daraufhin hatte ich mir überlegt einfach denn Schreibezeiger weiter auf 2049 laufen zu lassen und mit Modula(%) 2048, die neue Schreibposition im Chararray finde, dadurch wäre der Schreibezeiger immer größer als der Lesezeiger aber es gäbe trotzdem die richtige Position. Ich habe dann nur die Angst das ich über die Grenzen von INT herauslaufe.. wobei ich nie soviel Daten eigentlich einlesen würde..

Weitere Ideen?

najjannaj schrieb:

Das mit dem Lese und Schreibzeiger hatte ich mir auch schon überlegt.. allerdings habe ich das Problem das der Schreibezeiger nach 2048 schreibzyklen ja auf 0 wechselt da er im Chararray wieder von vorne anfangen, das hieße der Lesezeiger wäre größer als der Schreibezeiger und das wäre nicht so praktisch.

das ist nicht schlimm. die neue position für beide zeiger ist immer: (alte_position + x) mod buffergrösse. nur ob diese operation erlaubt ist oder nicht, entscheidet sich (beim einfügen) ob noch genug platz im buffer ist und beim auslesen, ob mindestens x daten im buffer sind (bzw. das x muss entsprechend angepasst werden).

najjannaj

Kannst du deine Beschreibung einen Tick genauer ausführen ich verstehe nicht genau was du damit sagen willst.. Wieso hat der Lesezeiger auch plötzlich eine neue Position?

najjannaj schrieb:

Wieso hat der Lesezeiger auch plötzlich eine neue Position?

na, weil in einem ringbuffer beide zeiger immer vorwärts wandern. beim hineinschreiben wird der schreibzeiger hochgezählt und beim lesen der lesezeiger.

hustbaer

Ich würde hier keinen Ringpuffer verwenden, sondern einen klassischen Cache. Ist IMO viel übersichtlicher, leichter verständlich, leichter zu implementieren etc.
Dazu baust du dir z.B. einfach eine Klasse die N Blöcke mit grösse M gepuffert hält, und mitschreibt wann welcher Block zuletzt gebraucht wurde, und sich natürlich für jeden Block merkt an welcher Stelle in der Datei er anfängt, und wieviel Daten drinstehen (der letzte Block wird ja meist nicht voll sein). Diese Cache-Klasse bietet dann nur Funktionen zum Random-Access, also z.B. nur "read(void* destination_buffer, size_t offset, size_t size)".

Den Lesezeiger verwaltest du dann ausserhalb dieser Cache-Klasse, z.B. in einer weiteren Klasse. Wie du mit dem Lesezeiger herumspringst ist dann vollkommen egal: entweder die nötigen Daten sind noch im Cache, dann werden sie auch nicht nochmal gleaden, oder sie sind nichtmehr im Cache, dann wird nachgeladen, und damit der Block der am längsten nichtmehr gebraucht wurde durch einen neuen ersetzt.