Scribd Logo
Upload

Welcome to Scribd!

  • 48 views

    Circular Buffering

    Uploaded by

    Varssha B
    A circular buffer is a data structure that uses a fixed-size buffer as if it were connected end-to-end. It allows for efficient insertion and retrieval of data from both ends of the buffer while only using a finite amount of memory. It maintains separate head and tail indexes to track the oldest and newest elements as they are added and removed from the buffer.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Circular Buffering

    Uploaded by

    Varssha B
    48 views12 pages
    A circular buffer is a data structure that uses a fixed-size buffer as if it were connected end-to-end. It allows for efficient insertion and retrieval of data from both ends of the buffer while only using a finite amount of memory. It maintains separate head and tail indexes to track the oldest and newest elements as they are added and removed from the buffer.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    A circular buffer is a data structure that uses a fixed-size buffer as if it were connected end-to-end. It allows for efficient insertion and retrieval of data from both ends of the buffer while only using a finite amount of memory. It maintains separate head and tail indexes to track the oldest and newest elements as they are added and removed from the buffer.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    48 views12 pages

    Circular Buffering

    Uploaded by

    Varssha B
    A circular buffer is a data structure that uses a fixed-size buffer as if it were connected end-to-end. It allows for efficient insertion and retrieval of data from both ends of the buffer while only using a finite amount of memory. It maintains separate head and tail indexes to track the oldest and newest elements as they are added and removed from the buffer.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 12

    Circular Buffers

    Circular Buffer
    • A circular buffer is a data structure
    consisting of three parts:
    • A fixed-length buffer/array.
    • A head index.
    • A tail index.
    • The general purpose of a Circular
    Buffer is to receive a stream of data
    (usually arbitrarily long or infinite) but
    to only house a finite amount of it in memory at any time.

    01/04/2023 2
    Circular Buffer
    • The primary mechanism for the Circular Buffer is to treat a normal
    buffer as if the next element after the last space in the buffer is going
    to be the first element of the buffer.

    • Take the circular buffer above and count up from 3 to 9.

    01/04/2023 3
    Circular Buffer
    • As you can see, the data rolls around the end of the buffer, back to the
    beginning.

    • However, if we want to retrieve the data in the order in which we


    received it, we need to keep track of where to place the freshest element
    and the locate on the stalest element.
    • When the buffer is full, as seen above, it depends on the application if we should
    replace the stalest element or wait until the stalest element is removed.
    01/04/2023 4
    Circular Buffer
    • Here we include two indexes for the circular buffer: Head and Tail.

    • Head indicates the beginning of stored data, where we have the stalest
    element.
    • Tail indicates the location immediately after stored data, where the freshest
    element will go.
    • In this case, the nine from our last example is the freshest element.
    01/04/2023 5
    Circular Buffer
    • When the buffer is full, both Tail and Head point to the same element
    in the underlying buffer.

    • This means that if we want to accept new data (let's say 10) into the
    buffer, we need to replace the oldest data (3) with the newest data (10).
    • Again, replacing old data with new data may need to wait until the old
    data is used, depending on the application.
    01/04/2023 6
    Circular Buffer
    • When removing the oldest element, the head index moves over to the
    next element.

    • When adding an element, the tail index moves over to the next
    element.

    01/04/2023 7
    Circular Buffer
    • When the buffer is full and you still add an element, the stalest element is
    over written and both head and tail are moved over to the next element.

    • Stalest element (3) is lost in this case.


    01/04/2023 8
    Circular Buffer
    • Accessing the elements of the circular buffer from the underlying
    buffer requires some mathematical tricks.
    • In this case, the head element (the first, the stalest, the oldest) is at
    index 5 in the underlying buffer.

    • The tail space in the buffer is at 4, with the last, stalest element at 3.

    01/04/2023 9
    Circular Buffer – Indexing
    • We need to find a way to associate the following circular buffer
    indexes with the underlying actual indexes.
    i

    • The way we do this is with modular arithmetic:


    i = (head + j) % length; j = (i – head + length) % length;
    01/04/2023 10
    Circular Buffer – Indexing
    • When shifting the head and tail indices, you also need modular
    arithmetic to avoid those indices from falling off the buffer.

    head = (head + 1) % length; tail = (tail + 1) % length;


    01/04/2023 11
    Circular Buffer – Example Code for Circular Buffer of Characters

    int head = tail = 0;


    char poll() {
    int count = 0; char ret = array[head];
    head = (head + 1) % 10;
    char array[10]; count--;
    return ret;
    char get(int j) { }
    int i = (head + j) % 10;

    return array[i];

    void push(char x) {

    array[tail] = x;

    if (head == tail && count == 10) {

    head = (head + 1) % 10;

    tail = (tail + 1) % 10;

    } else {

    tail = (tail + 1) % 10;

    count++;

    01/04/2023 12

    You might also like