MG Mud User | 88f1247 | 2016-06-24 23:31:02 +0200 | [diff] [blame^] | 1 | // 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 | */ |
| 41 | struct 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 | */ |
| 59 | protected 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 | */ |
| 80 | protected 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 | */ |
| 115 | protected 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 | */ |
| 154 | protected 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 | |
| 172 | protected 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 | |
| 181 | protected 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 | |
| 194 | protected 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 | |
| 209 | protected mixed test() {return rbuffer;} |
| 210 | */ |