Циклічний буфер

Циклічний буфер або кільцевий буфер - це структура даних, яка має фіксований розмір і використовується так ніби кінець буферу і початок замкнені в кільце, тобто при досягненні кінця буфера знов переміщуються в його початок. Така структура дає можливість здійснювати буферизацію потоків даних.

Циклічний буфер

Застосування

Перевагою використання циклічного буфера є те, що при зчитуванні не потрібно переміщувати дані в буфері, тому що вказівник на поточну позицію переміщується сам. При використанні не кільцевих буферів було б необхідно переміщувати дані, коли його елементи стають непотрібними. Іншими словами кільцевий буфер добре застосовувати для реалізації буферу типу FIFO ("перший прийшов — першим пішов").

Циклічний буфер добре підходить для реалізації черг фіксованого розміру. Але якщо розмір черги є змінним, операція розширення кільцевого буфера є не ефективною, оскільки вимагає здійснення процедури переміщення пам’яті. В таких випадках краще використовувати зв'язаний список.

Такий тип буферу часто зустрічається при роботі з апаратним обладнанням та мікроконтролерами. При роботі з даними мультимедіа, обмежений циклічний буфер часто реалізує задачу постачальника-споживача, наприклад, при роботі зі звуковими картами. Карта зчитує для відтворення звуку дані з буфера з постійною швидкістю, в той час як постачальник (наприклад, аудіо-генератор) може перезаписувати старі дані.

Принцип роботи

В початковому стані буфер є пустим і має деяку визначену наперед довжину. Наприклад, так виглядає буфер для 7-ми елементів:

Допустимо, що в середину буфера в якійсь позиції записано значення 1 (конкретна початкова позиція не має значення для циклічного буферу):

Потім допустимо ми додали ще два елементи зі значеннями 2 і 3 — в позиції після значення 1:

Якщо необхідно видалити елементи з буферу, видалятимуться ті, що були записані раніше. Допустимо, що треба видалити два елементи, в такому випадку, значення 1 і 2 будуть видалені, а в буфері залишиться значення 3:

Якщо буфер містить 7 елементів тоді він є повністю заповненим:

Особливість кільцевого буфера полягає в тому, що коли він заповнений і відбувається новий запис даний, будуть перезаписані вже існуючі найстаріші елементи по колу. В такому випадку, два нових елементи — A і B — додаються і перезаписують значення 3 і 4:

Як альтернатива, ще одним із способів обробити ситуацію з заповненням буфера це запобігання перезапису шляхом повернення статусу помилки чи генерації винятку. Перезаписувати дані чи ні залишають на розсуд процедури або програмного додатку, які працюють з буфером.

І нарешті, якщо видалити два елементи то видалені будуть не комірки зі значеннями 3 і 4, а 5 і 6 оскільки A і B перезаписали значення 3 і 4 і буфер матиме наступний вміст:

Посилання

• CircularBuffer, Portland Pattern Repository
• Boost: Templated Circular Buffer Container
• http://www.dspguide.com/ch28/2.htm