blob: 19338e17e6bf18902557fc97cf7d3ffbb43d6f1e [file] [log] [blame]
MG Mud User88f12472016-06-24 23:31:02 +02001// MorgenGrauen MUDlib
2/** \file /std/util/ringbuffer.c
3* Implmentiert einen Ringbuffer in LPC.
4* Ab und an hat man den Fall, dass man Ereignisse/Meldungen o.ae. hat, von
5* denen man immer genau die letzten x gespeichert und abrufbar vorhalten
6* moechte. Dieses File stellt eine Datenstruktur und dazugehoerige
7* Verwaltungsfunktionen zu Verfuegung, mit denen dies effizient moeglich ist.
8* Insbesondere umgehen diese das staendige Slicing von Arrays, mit denen
9* haeufig Ringpuffer gebaut werden. Hierbei wird das Schreiben in den Puffer
10* billiger, das Abrufen der Daten allerdings teurer. Wird der Puffer haeufiger
11* abgefragt als beschrieben, ist dies keine effiziente Loesung.
12*
13* \author Zesstra
14* \date 22.05.2008
15* \version $Id$
16*/
17/* Changelog:
18*/
19#pragma strong_types
20#pragma save_types
21#pragma no_clone
22#pragma no_inherit
23#pragma no_shadow
24#pragma pedantic
25#pragma range_check
26
27#include <util/ringbuffer.h>
28
29/** Standardgroesse fuer Ringbuffer.
30 */
31#define MAXCOUNT 30
32
33
34/** Struktur, die einen Ringpuffer speichert.
35 Der Puffer selber ist im wesentlichen ein Array. Hinzu kommt noch ein
36 Zaehler, der den naechsten zu ueberschreibenden Wert indiziert sowie einen
37 Modus, der die Reihenfolge beim Abrufen beshreibt:
38 MODE_FIFO: First-in-First-out (default)
39 MODE_LIFO: Last-in-First-out
40 */
41struct std_ringbuffer {
42 mixed rbuffer;
43 int mode;
44 int next;
45};
46
47/** Erzeugt einen neuen Ringbuffer und liefert ihn zurueck.
48 Die Funktion erzeugt einen neuen, leeren Ringbuffer der Groesse \a size
49 und mit Ausgabemodus \a newmode und liefert die entsprechende
50 Ringbuffer-Struktur zurueck.
51 \attention Die zurueckgelieferte Datenstruktur bitte nicht per Hand
52 manipulieren.
53 \param[in] size Groesse des zu erzeugenden Ringbuffers. Default: 30
54 \param[in] newmode Ausgabemodus des Ringbuffers: \a MODE_FIFO oder
55 \a MODE_LIFO. Default: MODE_FIFO
56 \return Der erzeugte Ringbuffer (struct vom Typ std_ringbuffer).
57 \sa ResizeRingBuffer, RingBufferPut, RingBufferGet
58 */
59protected struct std_ringbuffer CreateRingBuffer(int size, int newmode) {
60
61 struct std_ringbuffer buffer = (<std_ringbuffer>
62 rbuffer: allocate(size||MAXCOUNT, 0),
63 mode: newmode || MODE_FIFO,
64 next: 0 );
65
66 // Bei LIFO von oben anfangen.
67 if (newmode==MODE_LIFO)
68 buffer->next = sizeof(buffer->rbuffer);
69
70 return buffer;
71}
72
73/** Schreibt einen neuen Wert in den Ringbuffer.
74 Diese Funktion schreibt einen neuen Wert in den Ringbuffer \a buffer und
75 loescht dabei ggf. den aeltesten Wert im Puffer.
76 \param[in,out] buffer zu aendernder Ringbuffer
77 \param[in] val hinzuzufuegender Wert
78 \sa CreateRingBuffer, ResizeRingBuffer, RingBufferGet
79 */
80protected void RingBufferPut(struct std_ringbuffer buffer, mixed val) {
81 int next = buffer->next;
82 // je nach Ausgabemodus von oben nach unten oder von unten nach oben die
83 // Werte reinschreiben.
84 switch(buffer->mode) {
85 case MODE_LIFO:
86 // next ist hier eigentlich ein 'last'. Dekrementieren und dann zum
87 // Indizieren benutzen.
88 buffer->rbuffer[--next] = val;
89 // wenn man gerade in Element 0 geschrieben hat, ist naechstes Element
90 // sizeof()-1, d.h. sizeof() als next vermerken.
91 next ||= sizeof(buffer->rbuffer);
92 break;
93 default:
94 // Wert schreiben und next inkrementieren.
95 buffer->rbuffer[next++] = val;
96 // wird sizeof() erreicht, ist das naechste Element 0. Etwas schneller
97 // waere ein Modulo mit der Buffergroesse direkt bei der Indizierung
98 // oben, aber dann kann es u.U. durch einen numerischen Overflow buggen.
99 if (next==sizeof(buffer->rbuffer))
100 next = 0;
101 }
102 buffer->next = next;
103}
104
105/** Liefert ein Array mit allen Werten des Ringbuffers \a buffer.
106 Das zurueckgelieferte Array enthaelt alle Daten des Ringbuffers in der
107 beim Erstellen des Puffers gewuenschten Reihenfolge (s. MODE_FIFO,
108 MODE_LIFO).
109 Ist der Puffer noch nicht vollstaendig gefuellt, enthalten die bisher noch
110 nie beschriebenen Elemente 0.
111 \param[in] buffer Ringpuffer, dessen Daten ausgeben werden sollen.
112 \return Array mit Daten des Puffers.
113 \sa CreateRingBuffer, RingBufferPut, ResizeRingBuffer
114 */
115protected mixed RingBufferGet(struct std_ringbuffer buffer) {
116 int size = sizeof(buffer->rbuffer);
117 int next = buffer->next;
118 mixed rbuffer = buffer->rbuffer;
119
120 switch(buffer->mode) {
121 case MODE_LIFO:
122 // der hintere Teil enthaelt die neueren Daten. Die kommen zuerst.
123 // Wenn next == sizeof(), dann kann das interne Array einfach kopiert
124 // werden.
125 if (next == size)
126 return copy(rbuffer);
127 else
128 return rbuffer[next .. size-1] + rbuffer[0 .. next-1];
129 default:
130 // der vordere Teil enthaelt die neueren Daten. Also zuerst den hinteren
131 // ausgeben, dann den vorderen.
132 // Wenn next 0, kann das interne Array einfach kopiert werden. Sonst
133 // muss es zusammengesetzt werden.
134 if (next)
135 return rbuffer[next .. size-1] + rbuffer[0 .. next-1];
136 else
137 return copy(rbuffer);
138 }
139 return 0;
140}
141
142/** Erzeugt einen neuen Ringbuffer der Groesse \a size und dem gleichen Modus
143 * wie \a buf, der dieselben Daten enthaelt wie \a buf.
144 * Diese Funktion erzeugt einen neuen Ringbuffer und kopiert alle Daten aus
145 * dem alten Puffer in den neuen um.
146 \param[in] buf alter Ringbuffer
147 \param[in] size gewuenschte neue Groesse
148 \return Liefert neuen Ringbuffer mit gewuenschten Groesse.
149 \sa CreateRingBuffer, RingBufferPut, RingBufferGet
150 \attention Wird der Ringbuffer verkleinert, kommt es zum Verlust der
151 aeltesten Daten, die nicht mehr in den neuen hineinpassen.
152 \todo Effizientere Implementation.
153 */
154protected struct std_ringbuffer ResizeRingBuffer(struct std_ringbuffer buf,
155 int size) {
156 // neuen Ringbuffer anlegen.
157 struct std_ringbuffer nbuf = CreateRingBuffer(size, buf->mode);
158 // und alle daten aus dem alten wieder reinstopfen.
159 // ja, das geht effizienter, hab ich gerade aber keinen Bock drauf. Die
160 // Funktion wird vermutlich eh sehr selten gerufen.
161 foreach(mixed val: RingBufferGet(buf))
162 RingBufferPut(nbuf, val);
163 // neuen Buffer zurueckgeben. Der alte bleibt unveraendert!
164 return nbuf;
165}
166
167/* halbfertige Implementation mit Arrays.
168#define RBUFFER 0
169#define MODE 1
170#define COUNTER 2
171
172protected mixed CreateRingBuffer(int size, int mode) {
173 mixed buffer = ({ allocate(size||MAXCOUNT, 0),
174 mode || MODE_FIFO,
175 0 });
176 if (mode==MODE_LIFO)
177 buffer[COUNTER] = sizeof(buffer[RBUFFER]);
178 return buffer;
179}
180
181protected void RingBufferPut(mixed buffer, mixed val) {
182 int counter = buffer[COUNTER];
183 switch(mode) {
184 case MODE_LIFO:
185 rbuffer[--counter] = val;
186 counter ||= sizeof(rbuffer);
187 break;
188 default:
189 rbuffer[(counter++)%sizeof(rbuffer)] = val;
190 }
191 buffer[COUNTER]=counter;
192}
193
194protected mixed RingBufferGet(mixed buffer) {
195 int size=sizeof(rbuffer);
196
197 switch(mode) {
198 case MODE_LIFO:
199 return rbuffer[counter..size] + rbuffer[0..counter-1];
200 default:
201 if (counter%size)
202 return rbuffer[(counter%size) .. size-1]
203 + rbuffer[0..(counter%size)-1];
204 else
205 return copy(rbuffer);
206 }
207}
208
209protected mixed test() {return rbuffer;}
210*/