Circular buffer (ring buffer) adalah struktur data FIFO dengan kapasitas tetap yang memakai array sebagai storage dan dua indeks berputar (baca dan tulis). Berbeda dari queue sirkular biasa, circular buffer dirancang khusus untuk data streaming—audio, video, serial I/O—di mana producer dan consumer berjalan paralel dengan kecepatan berbeda. Pada chapter ini kita akan mengimplementasikan circular buffer dengan dua varian: dengan field ukuran eksplisit, dan dengan trik sentinel (satu slot kosong).

Konsep Circular Buffer #

Circular buffer adalah array dengan dua indeks berputar. Indeks tulis menandai lokasi elemen baru akan ditulis; indeks baca menandai lokasi elemen berikutnya akan dibaca. Setiap kali indeks mencapai akhir array, ia “berputar” kembali ke indeks 0 lewat operasi modulo.

Tantangan utama: membedakan buffer kosong dari buffer penuh. Dua pendekatan umum:

  1. Field ukuran eksplisit: track jumlah elemen. Kosong saat ukuran == 0, penuh saat ukuran == KAPASITAS. Hemat 1 slot, tetapi butuh sinkronisasi tambahan bila multi-thread.
  2. Sentinel kosong: sisakan 1 slot kosong. Kosong saat baca == tulis, penuh saat (tulis + 1) % KAPASITAS == baca. Tidak butuh field ukuran, tetapi kapasitas efektif berkurang 1.

Implementasi dengan Field ukuran #

Implementasi paling intuitif: struct menyimpan field ukuran yang melacak jumlah elemen aktif.

c 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define KAPASITAS 8

typedef struct {
    int data[KAPASITAS];
    size_t baca;
    size_t tulis;
    size_t ukuran;
} circular_buffer;

void cb_init(circular_buffer *cb) {
    cb->baca = 0;
    cb->tulis = 0;
    cb->ukuran = 0;
}

int cb_penuh(circular_buffer *cb) { return cb->ukuran == KAPASITAS; }
int cb_kosong(circular_buffer *cb) { return cb->ukuran == 0; }

int cb_tulis(circular_buffer *cb, int val) {
    if (cb_penuh(cb)) return -1;
    cb->data[cb->tulis] = val;
    cb->tulis = (cb->tulis + 1) % KAPASITAS;
    cb->ukuran++;
    return 0;
}

int cb_baca(circular_buffer *cb, int *out) {
    if (cb_kosong(cb)) return -1;
    *out = cb->data[cb->baca];
    cb->baca = (cb->baca + 1) % KAPASITAS;
    cb->ukuran--;
    return 0;
}

size_t cb_tersedia(circular_buffer *cb) {
    return KAPASITAS - cb->ukuran;
}

int main(void) {
    circular_buffer cb;
    cb_init(&cb);

    printf("Tulis 5 elemen:\n");
    for (int i = 1; i <= 5; i++) {
        if (cb_tulis(&cb, i * 10) == 0)
            printf("  tulis %d (ukuran=%zu, slot kosong=%zu)\n",
                   i * 10, cb.ukuran, cb_tersedia(&cb));
    }

    printf("\nBaca 3 elemen:\n");
    for (int i = 0; i < 3; i++) {
        int val;
        if (cb_baca(&cb, &val) == 0)
            printf("  baca %d\n", val);
    }

    printf("\nTulis lagi sampai penuh (tes wrap-around):\n");
    for (int i = 6; i <= 12; i++) {
        if (cb_tulis(&cb, i * 10) == 0)
            printf("  tulis %d (ukuran=%zu)\n", i * 10, cb.ukuran);
        else
            printf("  tulis %d gagal: buffer penuh\n", i * 10);
    }

    printf("\nBaca semua (urutan FIFO):\n");
    while (!cb_kosong(&cb)) {
        int val;
        cb_baca(&cb, &val);
        printf("  baca %d\n", val);
    }

    return 0;
}

Output yang Dihasilkan:

text 
Tulis 5 elemen:
  tulis 10 (ukuran=1, slot kosong=7)
  tulis 20 (ukuran=2, slot kosong=6)
  tulis 30 (ukuran=3, slot kosong=5)
  tulis 40 (ukuran=4, slot kosong=4)
  tulis 50 (ukuran=5, slot kosong=3)

Baca 3 elemen:
  baca 10
  baca 20
  baca 30

Tulis lagi sampai penuh (tes wrap-around):
  tulis 60 (ukuran=3)
  tulis 70 (ukuran=4)
  tulis 80 (ukuran=5)
  tulis 90 (ukuran=6)
  tulis 100 (ukuran=7)
  tulis 110 (ukuran=8)
  tulis 120 gagal: buffer penuh

Baca semua (urutan FIFO):
  baca 40
  baca 50
  baca 60
  baca 70
  baca 80
  baca 90
  baca 100
  baca 110

Setelah baca 3 elemen, slot kosong tersedia kembali. Tulis berikutnya mengisi slot dari posisi tulis terakhir (indeks 5, lalu 6, 7, lalu wrap ke 0, 1, 2). Pembacaan menghasilkan urutan FIFO yang benar—elemen tertua dibaca lebih dulu.

Mari kita telaah baris-baris kode di atas:

  1. Baris 7-12 (circular_buffer struct): empat field—array data, indeks baca dan tulis, serta ukuran. Field ukuran melacak jumlah elemen aktif.
  2. Baris 18-23 (cb_tulis): tulis data ke data[tulis], lalu majukan tulis dengan modulo. Increment ukuran. Bila penuh, return -1.
  3. Baris 25-31 (cb_baca): baca data[baca], lalu majukan baca dengan modulo. Decrement ukuran. Bila kosong, return -1.
  4. Baris 33-35 (cb_tersedia): helper untuk hitung slot kosong. Berguna bagi producer untuk tahu berapa banyak elemen bisa ditulis sebelum penuh.
  5. Baris 53-56 (baca 3 elemen): setelah baca, slot kosong bertambah 3. Tetapi elemen 40 dan 50 masih ada di dalam buffer (indeks 3 dan 4) menunggu dibaca.
  6. Baris 60-67 (tulisan ulang): tulis 60, 70, 80, 90, 100, 110—total 6 elemen baru. Setelah 8 elemen aktif (40, 50, 60, 70, 80, 90, 100, 110), buffer penuh. Tulis 120 ditolak.

Implementasi dengan Sentinel #

Pendekatan sentinel tidak menyimpan field ukuran. Trik: sisakan 1 slot kosong sebagai penanda. Bila tulis berada satu posisi sebelum baca, buffer penuh. Kapasitas efektif menjadi KAPASITAS - 1.

c 
#include <stdio.h>

#define KAPASITAS 8

typedef struct {
    int data[KAPASITAS];
    size_t baca;
    size_t tulis;
} cbuf_sentinel;

void cb_init(cbuf_sentinel *cb) {
    cb->baca = 0;
    cb->tulis = 0;
}

int cb_penuh(cbuf_sentinel *cb) {
    return (cb->tulis + 1) % KAPASITAS == cb->baca;
}

int cb_kosong(cbuf_sentinel *cb) {
    return cb->tulis == cb->baca;
}

int cb_tulis(cbuf_sentinel *cb, int val) {
    if (cb_penuh(cb)) return -1;
    cb->data[cb->tulis] = val;
    cb->tulis = (cb->tulis + 1) % KAPASITAS;
    return 0;
}

int cb_baca(cbuf_sentinel *cb, int *out) {
    if (cb_kosong(cb)) return -1;
    *out = cb->data[cb->baca];
    cb->baca = (cb->baca + 1) % KAPASITAS;
    return 0;
}

size_t cb_hitung(cbuf_sentinel *cb) {
    return (cb->tulis + KAPASITAS - cb->baca) % KAPASITAS;
}

int main(void) {
    cbuf_sentinel cb;
    cb_init(&cb);

    printf("Tulis hingga hampir penuh:\n");
    for (int i = 1; i <= 10; i++) {
        if (cb_tulis(&cb, i) == 0)
            printf("  tulis %d (hitung=%zu)\n", i, cb_hitung(&cb));
        else
            printf("  tulis %d gagal: buffer penuh\n", i);
    }

    printf("\nBaca semua (FIFO):\n");
    while (!cb_kosong(&cb)) {
        int val;
        cb_baca(&cb, &val);
        printf("  baca %d\n", val);
    }

    return 0;
}

Output yang Dihasilkan:

text 
Tulis hingga hampir penuh:
  tulis 1 (hitung=1)
  tulis 2 (hitung=2)
  tulis 3 (hitung=3)
  tulis 4 (hitung=4)
  tulis 5 (hitung=5)
  tulis 6 (hitung=6)
  tulis 7 (hitung=7)
  tulis 8 gagal: buffer penuh
  tulis 9 gagal: buffer penuh
  tulis 10 gagal: buffer penuh

Baca semua (FIFO):
  baca 1
  baca 2
  baca 3
  baca 4
  baca 5
  baca 6
  baca 7

Pada KAPASITAS = 8, kapasitas efektif adalah 7 elemen. Tulis ke-8 ditolak karena (tulis + 1) % KAPASITAS == baca. Fungsi cb_hitung() menghitung elemen aktif dengan rumus (tulis - baca + KAPASITAS) % KAPASITAS—rumus ini menangani wrap-around dengan benar.

Aplikasi Circular Buffer #

Circular buffer adalah tulang punggung data streaming. Beberapa use case:

  • Audio/Video streaming: producer (microphone) menulis data audio ke buffer, consumer (speaker) membaca dengan rate tetap. Buffer menyerap ketidaksesuaian rate.
  • Serial I/O: UART driver menulis byte yang diterima ke buffer, aplikasi membaca kapan saja butuh. Buffer mencegah kehilangan data bila aplikasi sibuk.
  • Producer-consumer threading: satu thread producer, satu thread consumer, sharing circular buffer dengan lock ringan (atomic operations). Sering dipakai di embedded systems.