1

I have an array x of constant size (usually around 100-200 entries) and would like to add an array y of constant smaller size (usually between 2-10 entries) to the head, while removing the same size at the end. For example:

Buffer: x = [6 5 4 3 2 1]

New array to add in front: y = [8 7]

Resulting buffer: x = [8 7 6 5 4 3]

And so on...

Note: I need to use a regular C array and need to be able to access the whole array, not only the head or tail. The array is rather small, but the function is called very often, so I am looking for a solution that does not require any excessive memory tasks. Arrays x and y are always of the same size in each step.

Is this a buffer, circular / ring buffer, queue or FIFO? I don't really know what the right search term is for this application.

Language is C.

Improve this question
6
  • Sounds like you're describing a circular buffer. Search away! Commented Dec 14, 2015 at 21:53
  • 1
    Rather than shift a lot of data, use a ring buffer and overwrite the obsolete elements. Commented Dec 14, 2015 at 21:54
  • 1
    Possible duplicate of Queue using Arrays Commented Dec 14, 2015 at 21:59
  • it's a circular / ring buffer queue, or FIFO. Just research the terms you've already come up with. Commented Dec 14, 2015 at 22:00
  • It's difficult to say much without more details. Will a ring-buffer do, or do you need that array explicitly in-ine, eg. for passing to an i/O function by start address/length? Commented Dec 14, 2015 at 22:00

4 Answers 4

Reset to default
2

If you require linear access to the array contents, and you want to not perform frequent memcpy operations, a possible solution for this is a flip buffer or sliding buffer.

The flip buffer is twice as large as the array needs to be (or even more, if you like), so that you can can just move a tail pointer when adding to the end without any wraparound, keeping the data linear.

When you hit the hard limit of the underlying buffer, then you do a slide operation: you move the upper half of the array to the lower half, and subtract the same delta from all the indices.

When this slide operation happens, you know that all data and indices are in the upper partition now, because the buffer, which is 2 * N, wide never contains more than N entries: it is simulating an N sized ring buffer. That is to say, a situation never arises that the tail has hit the end of the buffer, but the head is still in the lower partition (there are more than N items).

Since you'd like to add to the front, we start by filling the upper partition, and we flip in the upward direction:

 [x x x x x x | 6 5 4 3 2 1 ]   -- six-element queue, twelve el. buffer
            H             T

 Add 8 7, remove 2 1:

 [x x x x 8 7 | 6 5 4 3 x x ]
        H             T

 Add 2 1 0 9, remove 6 5 4 3:

 [2 1 0 9 8 7 | x x x x x x ]
H           T

Head has hit -1! Flip to upper partition with memcpy, add 6 to head and tail:

 [x x x x x x | 2 1 0 9 8 7 ]
            H             T

Note that since the two partitions don't overlap, we don't have to use memmove: we can use memcpy.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

What about using memmove() from <string.h> to move slices of the array around? That's not something to exclude without having actually measured the performance. Any solution using linked lists or so might involve operations that take longer than a highly optimized memmove() (that the compiler might even inline).

It really depends on

  • the number of elements in the array
  • the size of the element type
  • the frequency of the operations
  • the time spent modifying the array with respect to everything else
Improve this answer

1 Comment

For small data sets with not too many inserts this is often faster than anything else even with the memmove.
0

What you need is index offset. So, every time you "insert" values, you simply write them where you virtual tail is and update index offset. That is how circular buffers work.

Improve this answer

Comments

0

This is a duplicate. Here's a Java implementation in full on code review https://codereview.stackexchange.com/questions/64258/array-implementation-of-queue and one of the questions in C here Queue using Arrays.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.