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.

3 komentarzy

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 :)