CODEWITHSUNDEEP
ccircular-buffer
neolith
neolith

Reputation: 819

How to solve this with a circular buffer?

What is the most efficient way of accomplishing the insertion of one element before others in an array without having to rearrange all elements with a for loop. I have tried a circular buffer implementation, but it doesn't work and I am getting frustrated. I made the question simpler, so it will hopefully be easier for everyone.

int * buffer = (int *) calloc(L_buffer, sizeof(int));
int i, j, K, out;

while(1) {

    i = rand();
    K = 3;

    /* Calculate output */

    out = buffer[i]  buffer[i+1]  + buffer[K];

    /* Shift array elements by one and insert new value */

    for(j = 0; j < L_buffer-1; j++) 
        buffer[j+1] = buffer[j];

    buffer[0] = new_value;
}

Solution: I edited the solution of @Eric Postpischil to suit my needs. By extending the function to the following, I can advance the current index in both directions and always wrap around.

int * cb_element(CircularBuffer *cb, ptrdiff_t i) {

    if ( cb->current < 0)
        cb->current += cb->size;

    ptrdiff_t index = cb->current + i;

    if ((size_t) index >= cb->size)
        index -= cb->size;


    return &cb->array[index];
}

So I can

out = *cb_element(&cb, i) + *cb_element(&cb, i+1);

cb.current--;
*cb_element(&cb, 0) = new_value;

Really neat!

Upvotes: -4

Views: 390

Answers (2)

chux
chux

Reputation: 154169

There is probably a more elegant way than doing it with so many lines.

"mod" the array index access with % L_array using unsigned math. Further, if L_array is an unsigned power-of-2, % L_array results in simply emitted and code.

output = p_dynamic[i] + p_dynamic[(i+1)% L_array] + p_dynamic[(i+2)% L_array];

Note: --p_dynamic < p_start is never true unless code relies on undefined behavior. The valid values to compare p_dynamic against are array[0]...array[length], That does not include array[-1].

Insertion looks suspicious for a circular buffer. There should be no reason for a for loop to shift. Instead adjust references to the ends of the buffer.

Consider using below:

array = calloc(L_array, sizeof *array);
size_t length = 0; // current length
size_t begin = 0;  // Index of eldest sample
size_t end = 0;    // Index to store the next sample

To insert

if (length < L_array) {
  length++;
  array[end] = new_value;
  end = (end+1)%L_array;
}

To extract

if (length > 0) {
  length--;
  sample = array[begin];
  begin = (begin+1)%L_array;
}

To sample 3 elements starting at i

if (length >= 3) {
  output = array[(begin+i) % L_array] + array[(begin+i+1) % L_array] +
      array[(begin+i+2) % L_array];
}

Upvotes: 0

Eric Postpischil
Eric Postpischil

Reputation: 223795

int *p_dynamic = array[0]; int *p_start = array[0]; int *p_end = array[L_array - 1];

You have not told us what these variables are intended to do, so we do not know if you are using them in a sensible way for their intended purposes.

if (--p_dynamic < p_start)

When p_dynamic points to array[0], the behavior of --p_dynamic is not defined by the C standard. The standard defines pointer arithmetic only from elements 0 of an array to just beyond the last element of the array.

int K = 3; int i = some_int; int output; output = array[i] + array[i+1] + array[K];

Again, you have not told us the intent, so we do not know what you are trying to achieve here. Why is K 3? Is that a fixed constant in every use of your code or just an example? Does it have any relationship to i? Do you mean array[K] to mean the actual element array[3] will always be added, or do you mean that the element at offset 3 from the current start of the circular buffer will be added?

if (p_dynamic[K] > p_end && p_dynamic[i] < p_end && p_dynamic[i+1] < p_end)

This makes no sense because p_dynamic is a pointer to an int, so p_dynamic[K] is an int, but p_end is a pointer to an int, so p_dynamic[K] > p_end attempts to compare an int to a pointer. I suspect you are attempting to ask whether the element p_dynamic[K] would be beyond the end of the array. You might do that with p_dynamic + K > p_end except, as with --p_dynamic, if it is beyond the end of the array, the pointer arithmetic is not defined by the C standard.

Simplify your code by making a function to help you access array elements. Make a structure that describes the circular buffer. To start simply, I will assume you have a fixed buffer size of Size eleemnts.

typedef struct
{
    int array[Size];
    ptrdiff_t current;
} CircularBuffer;

The member current will be the index (subscript) of the element that is currently oldest in the buffer, the current “start” of the circular buffer. (The ptrdiff_t type is defined in the header <stddef.h>. It may be used for array subscripts.

Then make a function that gives you a pointer to the element with index i:

int *CBElement(CircularBuffer *cb, ptrdiff_t i)
{
    ptrdiff_t index = i + current;
    if (Size <= index) index -= Size;
    return &cb->array[index];
}

Then you can refer to array element K, for example, as *CBElement(&cb, K):

output = *CBElement(&cb, i) + *CBElement(&cb, i+1) + *CBElement(&cb, K);

You can also put new values in the array:

*CBElement(&cb, i) = NewValue;

To advance the buffer, update the current member in the obvious way and put a new value in the new last element (*CBElement(&cb, Size-1)).

This should simplify the task of getting the code working. After it is working, you can consider optimizations and refinements of the buffer implementation.

Upvotes: 0

Related Questions