Bufor cykliczny jako zapętlona lista jednokierunkowa
furious programming
Wprowadzenie
Artykuł ten ma na celu przedstawienie odmiennego sposobu implementacji bufora cyklicznego, na podstawie struktury wykorzystywanej do tworzenia list jednokierunkowych, a nie jednowymiarowej macierzy. Bufor ten zostanie opakowany w specjalnie przygotowane do tego celu klasy. Jednak zamiast umożliwiać przechowywanie danych typów prostych, będzie pozwalać na dodawanie dowolnych rekordów. Większą część artykułu zajmie opis stworzenia uniwersalnej klasy, implementującej podstawowe mechanizmy bufora cyklicznego. Na podstawie takiej klasy bazowej będzie można stworzyć kolejne klasy buforów cyklicznych, mogących przechowywać dowolne rekordy danych.
Klasa w całości została napisana w środowisku Delphi7 i jest kompatybilna nie tylko z nowszymi środowiskami Delphi, ale także można jej używać w Lazarusie.
Zachęcam do zapoznania się z poniższą treścią.
1 Wprowadzenie
2 Bufor cykliczny
3 Bufor jako lista jednokierunkowa
4 Klasa bazowa bufora cyklicznego
4.1 TBufferElement i PBufferElement
4.2 Klasa TCustomCircularBuffer
4.2.1 Dodatkowe typy i stałe
4.2.2 Pola klasy
4.2.3 Konstruktor
4.2.4 Destruktor
4.2.5 Metody
4.2.5.1 GetBufferState
4.2.5.2 InternalEnqueue
4.2.5.3 InternalDequeue
4.2.6 Właściwości
5 Własna klasa bufora cyklicznego
5.3 TStructBufferData i PStructBufferData
5.4 Klasa TStructCircularBuffer
5.4.7 Dodatkowe typy
5.4.8 Metody
5.4.8.4 Enqueue
5.4.8.5 Dequeue
6 Podsumowanie
Bufor cykliczny
Bufor cykliczny (ang. Circular buffer) to obszar pamięci o statycznym rozmiarze, służący do przechowywania dowolnych danych. Obsługa pamięci bufora zorganizowana jest tak, aby wykluczyć konieczność manipulowania rozmiarem przydzielonej pamięci, stąd struktura bufora cyklicznego jest zapętlona.
Do operacji dodawania danych do bufora i odczytu z niego wykorzystywane są wskaźniki na pierwszy i ostatni element bufora, oraz wskaźniki na aktualny element do odczytu i zapisu danych. Po każdorazowym dodaniu nowego elementu do bufora, wskaźnik zapisu inkrementuje się, a po odczycie danych - inkrementuje się wskaźnik odczytu. Jeśli wskaźnik odczytu lub zapisu po danej operacji wskazuje na ostatni element bufora - ustawia się go z powrotem na pierwszy element i rozpoczyna od początku.
Aby odróżnić bufor pusty od pełnego, jeden element bufora musi zostać zarezerwowany, aby wskaźniki odczytu i zapisu nie mogły wskazywać na ten sam element. Żeby nie tracić jednego elementu bufora, należy przechować ilość aktualnie zajętych elementów bufora i tę ilość sprawdzać zarówno przy zapisie nowych danych do bufora, jak i przy ich odczycie.
Bufor jako lista jednokierunkowa
Implementacja bufora na podstawie struktury listy jednokierunkowej umożliwia wykluczenie konieczności porównania wartości wskaźników odczytu i zapisu ze wskaźnikami na pierwszy i ostatni element bufora. Każdy węzeł (element) bufora musi być strukturą, zawierającą dane oraz wskaźnik na kolejny węzeł. Aby zachować strukturę zapętloną, wskaźnik na ostatni element bufora musi zawierać wskazanie na pierwszy element.
Klasa bazowa bufora cyklicznego
Bazowa klasa powinna imeplementować podstawową mechanikę bufora, służącą do zarządzania jego pamięcią oraz umożliwiająca dodanie i odczyt danych typu ogólnego - Pointer. Dodatkowo może zawierać właściwości informujące np. o rozmiarze bufora, liczbie zajętych elementów czy choćby informująca o stanie bufora - bufor pusty lub pełny.
TBufferElement i PBufferElement
Pojedynczy węzeł bufora musi zawierać co najmniej dwie informacje, dlatego do tego celu zadeklarować należy rekord z polami przechowującymi dane węzła oraz wskaźnik na kolejny węzeł bufora:
type
PBufferElement = ^TBufferElement;
TBufferElement = record
Data: Pointer;
Next: PBufferElement;
end;
Typ PBufferElement
jest wskaźnikiem na rekord z danymi pojedynczego elementu i to on będzie wykorzystywany w klasie bazowej.
Klasa TCustomCircularBuffer
Bazowa klasa bufora musi implementować podstawowe mechanizmy, jak przydzielanie i zwalnianie pamięci bufora, dodawanie nowych danych do bufora i ich odczyt, a także metodę sprawdzającą, czy bufor jest pusty lub pełny. Przykładowa deklaracja bazowej klasy bufora cyklicznego:
type
TCustomCircularBuffer = class(TObject)
private
FFirst: PBufferElement;
FLast: PBufferElement;
FWrite: PBufferElement;
FRead: PBufferElement;
FSize: UInt16;
FCount: UInt16;
private
function GetBufferState(AState: TBufferState): Boolean;
protected
procedure InternalEnqueue(var AData: Pointer);
procedure InternalDequeue(out AData: Pointer);
public
constructor Create(ASize: UInt16);
destructor Destroy(); override;
public
property Size: UInt16 read FSize;
property Count: UInt16 read FCount;
property State[AState: TBufferState]: Boolean read GetBufferState; default;
end;
Dodatkowe typy i stałe
Klasa korzysta także z dodatkowych typów UInt16 (którego brak w Delphi7) dla ustalenia rozmiaru bufora, a także TBufferState
; Deklaracje obu tych typów przedstawiają się następująco:
{$IFNDEF FPC}
type
UInt16 = type Word;
{$ENDIF}
type
TBufferState = (bsEmpty, bsFull);
Metody umożliwiające zapis i odczyt danych do i z bufora wykorzystują własną klasę wyjątku:
type
ECustomBufferException = class(Exception);
Do konstruktora tworzonych wyjątków przekazywane są łańcuchy z dwóch stałych EM_BUFFER_EMPTY
i EM_BUFFER_FULL
:
const
EM_BUFFER_EMPTY = AnsiString('cannot read data from buffer (buffer is empty)');
EM_BUFFER_FULL = AnsiString('cannot write data to buffer (buffer is full)');
Pola klasy
Klasa posiada cztery pola wskaźnikowe oraz dwa liczbowe, wykorzystywane we wszystkich metodach. Opis pól klasy poniżej:
Pole | Typ | Opis |
---|---|---|
FFirst | PBufferElement |
wskaźnik na fizycznie pierwszy element bufora |
FLast | PBufferElement |
wskaźnik na fizycznie ostatni element bufora |
FWrite | PBufferElement |
wskaźnik na element gotowy do zapisu danych |
FRead | PBufferElement |
wskaźnik na element gotowy do odczytu danych |
FSize | UInt16 | rozmiar bufora, liczony w elementach |
FCount | UInt16 | liczba zajętych elementów bufora |
Konstruktor
Konstruktor klasy tworzy odpowiednią listę elementów bufora w pamięci w odpowiedniej kolejności i dba o jej zapętloną strukturę, a także inicjuje wartości wszystkich pól klasy. Definicja konstruktora:
constructor TCustomCircularBuffer.Create(ASize: UInt16);
var
pbeToken: PBufferElement;
begin
inherited Create();
New(FFirst);
pbeToken := FFirst;
FSize := 1;
FCount := 0;
while FSize < ASize do
begin
New(pbeToken^.Next);
pbeToken := pbeToken^.Next;
Inc(FSize);
end;
FLast := pbeToken;
FLast^.Next := FFirst;
FWrite := FFirst;
FRead := FFirst;
end;
Pierwszy element macierzy tworzony jest osobno, a jego referencja zostaje wpisana do pola FFirst
. Następnie inicjowana jest pomocnicza zmienna pbeToken
oraz pola rozmiaru bufora, a także zerowane jest pole z ilością zajętych elementów. Kolejnym krokiem jest utworzenie listy elementów bufora w pętli, na podstawie iteratora pbeToken
; Pole FSize
początkowo przyjmuje wartość 1
, dlatego że pierwszy element został utworzony przed pętlą. Pole to służy także jako iterator pętli tworzącej listę elementów bufora.
Po utworzeniu wszystkich elementów bufora, zmienna pbeToken
zawiera referencję do fizycznie ostatniego elementu bufora, stąd jej wartość zostaje przypisana do pola FLast
; Następnie do pola FLast^.Next
przypisywana jest referencja pierwszego elementu bufora, zawarta w polu FFirst
, dzięki czemu lista zostaje zapętlona. Ostatnim krokiem jest ustawienie wskaźników FWrite
i FRead
na pierwszy element bufora.
Destruktor
Jedynym zadaniem destruktora klasy jest zwolnienie z pamieci wszystkich elementów bufora i zwolnienie klasy z pamięci.
destructor TCustomCircularBuffer.Destroy();
var
pbeToken, pbeNext: PBufferElement;
begin
pbeToken := FFirst;
while FSize > 0 do
begin
pbeNext := pbeToken^.Next;
Dispose(pbeToken);
pbeToken := pbeNext;
Dec(FSize);
end;
inherited Destroy();
end;
Za pomocą zmiennych pomocniczych pbeToken
i pbeNext
zwalniane są kolejne węzły listy. Głównym iteratorem pętli usuwającej jest pole FSize
i dopóki zawiera wartość większą od 0
- elementy wskazywane przez zmienną pbeToken
zostają usunięte z pamięci.
Metody
GetBufferState
Jest to metoda dostępowa, służąca do sprawdzenia czy bufor jest pusty lub pełny. Wykorzystywana jest przez właściwość State
do sprawdzenia stanu zajętości listy.
function TCustomCircularBuffer.GetBufferState(AState: TBufferState): Boolean;
begin
Result := False; // and be quiet, compiler...
case AState of
bsEmpty: Result := FSize = 0;
bsFull: Result := FCount = FSize;
end;
end;
Jeśli argument AState
zawiera wartość bsEmpty
, metoda sprawdza czy bufor jest pusty i zwraca True jeśli tak jest, w przeciwnym razie zwraca False. Natomiast jeżeli argument zawiera wartość bsFull
, metoda sprawdza czy bufor jest pełny i zwraca odpowiednią wartość logiczną.
InternalEnqueue
Prywatna metoda służąca do dodania nowych danych do pojedynczego elementu bufora.
procedure TCustomCircularBuffer.InternalEnqueue(var AData: Pointer);
begin
if FCount = FSize then
raise ECustomBufferException.Create(EM_BUFFER_FULL)
else
begin
FWrite^.Data := AData;
FWrite := FWrite^.Next;
Inc(FCount);
end;
end;
Przed faktycznym dodaniem nowych danych do bufora metoda sprawdza, czy bufor jest już pełny i jeśli tak jest - wywołuje wyjątek ze stosownym komunikatem. Jeżeli bufor nie jest pełny, nowe dane wpisywane są do węzła, na który wskazuje wskaźnik z pola FWrite
, po czym wskaźnik ten ustawiany jest na kolejny element, a wartość pola FCount
zostaje zwiększona o 1
.
InternalDequeue
Ta prywatna metoda służy do odczytu danych z pojedynczego elementu bufora.
procedure TCustomCircularBuffer.InternalDequeue(out AData: Pointer);
begin
if FCount = 0 then
raise ECustomBufferException.Create(EM_BUFFER_EMPTY)
else
begin
AData := FRead^.Data;
FRead := FRead^.Next;
Dec(FCount);
end;
end;
Przed odczytem danych z elementu metoda sprawdza, czy bufor jest pusty i jeśli tak jest - tworzy wyjątek z odpowiednim komunikatem. Jeśli jednak bufor nie jest pusty, dane zostają odczytane z elementu, na który wskazuje wskaźnik z pola FRead
, po czym wskaźnik ten ustawiany jest na kolejny element, a wartość pola FCount
zostaje zmniejszona o 1
;
Właściwości
Właściwości klasy przewidziane są jedynie do pobrania informacji o buforze. Opis właściwości poniżej:
Właściwość | Typ | Opis |
---|---|---|
Size | UInt16 | rozmiar bufora, liczony w elementach |
Count | UInt16 | liczba zajętych elementów bufora |
State | Boolean | stan zajętości bufora (właściwość domyślna) |
Własna klasa bufora cyklicznego
Klasa bazowa została przygotowana tak, aby zawierała najważniejsze algorytmy organizacji pamięci bufora oraz prywatne metody pozwalające na zapis lub odczyt danych typu ogólnego. Klasa pochodna będzie już zawierać metody pozwalające na operacje na konkretnych rekordach lub dowolnych innych danych, do których można uzyskać wskaźnik.
Przykładowa klasa pochodna będzie umożliwiać zapis i odczyt rekordów z dwoma polami - liczbowym i logicznym.
TStructBufferData i PStructBufferData
Dane elementu pojedynczego elementu bufora będą rekordem zawierającym liczbę 16-bitową i i wartość logiczną. Do tego celu przygotować należy typ rekordu:
type
PStructBufferData = ^TStructBufferData;
TStructBufferData = record
Index: UInt16;
State: Boolean;
end;
Typ PStructBufferData
jest wskaźnikiem na rekord typu TStructBufferData
i to on będzie używany podczas dodawania i pobierania danych do i z bufora.
Klasa TStructCircularBuffer
Klasa ta będzie dziedziczyć z klasy bazowej podstawowe mechanizmy zarządzające pamięcią bufora oraz umożliwiające dodanie i pobranie wkaźnika do pojedynczego elementu. Klasa pochodna dodatkowo posiadać będzie własne metody służące do dodania i odczytu całych rekordów danych. Z podanych parametrów będzie tworzyć rekordy w pamięci i wskaźniki do nich dodawać do bufora za pomocą odziedziczonej metody InternalEnqueue
; Podczas pobierania danych elementu bufora będzie pobierać wskaźnik do elementu za pomocą metody InternalDequeue
, po czym dane z tego rekordu przekazywać będzie do parametrów wyjściowych metody odczytującej.
Dodatkowe typy
Klasa pochodna korzysta z własnej klasy wyjątku w metodach do zapisu i odczytu danych z i do bufora. Poniżej deklaracja używanej klasy wyjątku:
type
EStructBufferException = class(Exception);
Metody
Enqueue
Publiczna metoda służąca do dodania rekordu do bufora.
procedure TStructCircularBuffer.Enqueue(const AIndex: UInt16; const AState: Boolean);
var
psbdWrite: PStructBufferData;
begin
New(psbdWrite);
try
psbdWrite^.Index := AIndex;
psbdWrite^.State := AState;
inherited InternalEnqueue(Pointer(psbdWrite));
except
Dispose(psbdWrite);
raise;
end;
end;
W tej metodzie alokowana jest pamięć dla nowego rekordu, po czym rekord ten jest uzupełniany liczbą z parametru AIndex
oraz wartością logiczną, przekazaną w parametrze AState
. Następnie wykonywana zostaje próba dodania wskaźnika na nowy rekord za pomocą metody InternalEnqueue
. Jeśli podczas dodawania nowych danych wystąpi wyjątek, zmienna psbdWrite
zostanie zwolniona z pamięci, dzięki czemu uniknie się wycieku pamięci. Za pomocą słowa kluczowego Raise wyjątek zostanie przekazany do bloku niższego rzędu.
Dequeue
Publiczna metoda umożliwiająca pobranie danych z bieżącego elementu bufora.
procedure TStructCircularBuffer.Dequeue(out AIndex: UInt16; out AState: Boolean);
var
psbdRead: PStructBufferData;
begin
try
inherited InternalDequeue(Pointer(psbdRead));
AIndex := psbdRead^.Index;
AState := psbdRead^.State;
Dispose(psbdRead);
except
raise;
end;
end;
W pierwszej kolejności zostaje wykonana próba pobrania wskaźnika na rekord danych bieżącego elementu. Jeśli wskaźnik zostanie poprawnie pobrany, dane zawarte w rekordzie, na który wskazuje pobrany wskaźnik zostaną przepisane do parametrów wyjściowych metody, po czym rekord danych pobranego elementu zostaje zwolniony z pamięci. W przypadku wystąpienia wyjątku podczas odczytu danych z bufora, zwalnianie rekordu spod wskaźnika psbdRead
zostanie pominięte, a za pomocą słowa kluczowego Raise wyjątek zostanie przekazany do bloku niższego rzędu.
Podsumowanie
Dzięki stworzeniu bazowej klasy bufora cyklicznego mamy możliwość skorzystania z jednego silnika zarządzającego pamięcią bufora oraz na jej podstawie stworzenie wielu klas buforów, umożliwiających zapis różnego typu danych, bez konieczności implementacji wszystkich mechanizmów. Dzięki temu każda nowa klasa będzie musiała posiadać jedynie własne metody służące do dodawania i odczytywania danych do i z bufora.
W załączniku znajduje się moduł StructCircularBuffer.pas z kodem obu przedstawionych w artykule klas buforów, udostępniany na licencji GNU GPL3.
Jak klikniesz na zakładkę "Kompendium wiedzy" tam jest lista nowych artykułów :)
Dzięki Adam :)
Wczoraj jak zobaczyłem na forum wątek dotyczący bufora cyklicznego na zwykłej tablicy to w komentarzu mojej odpowiedzi dodałem, że ciekawsza jest implementacja na liście jednokierunkowej; No i wtedy coś mnie tknęło żeby taką napisać; I tak powstała uniwersalna klasa takiego bufora, do której od razu napisałem artykuł; Czasem trzeba coś wymodzić i opublikować;
Nie myślałem jednak, że bez "zareklamowania się" ktokolwiek tutaj trafi, bo jakoś nie znalazłem listy nowych artykułów; Ale jak widać od nocy ponad 10 odsłon to raczej dobrze; Mam nadzieję, że klasa się komuś przyda i sam sposób realizacji bufora cyklicznego będzie fajną ciekawostką, nie tylko dla mnie.
Brawo, fajny tekst :)