queue like operation on array of structs

[2b|!2b==?]

I have a struct which holds an array of structs like this

struct Struct1
{
struct Struct2* strt2 ;
....
};

I allocate a predetermined size to hold n structs of type Struct2.
However, Struct2 represents data that is coming in from a feed. I want
to have an operation that "shifts" the array elements down by one when a
new packet (of type Struct2) is received, so that Struct1 ALWAYS
contains the latest n values.

memove comes to mind, but I'd appreciate some pointers (pun intended)

 

[Eric Sosman]

I have a struct which holds an array of structs like this

struct Struct1
{
struct Struct2* strt2 ;
....
};

I allocate a predetermined size to hold n structs of type Struct2.
However, Struct2 represents data that is coming in from a feed. I want
to have an operation that "shifts" the array elements down by one when a
new packet (of type Struct2) is received, so that Struct1 ALWAYS
contains the latest n values.

memove comes to mind, but I'd appreciate some pointers (pun intended)

A "circular buffer" comes to mind. Keep the array at
the fixed size n (if n is really truly fixed, you might just
make strt2 an array instead of a pointer), and don't move
things around at all. Instead, keep an index k that tells
where the newest[*] item is. To insert a still newer item,
set k = (k + 1) % n and deposit the newer item there; it
will automatically overwrite the oldest item. To inspect
all the n newest items from newest to oldest, loop through
k, k-1, ..., 0, n-1, ..., k+1 (again, the % operator may
come in handy). To inspect them oldest to newest, loop on
k+1, ..., n-1, 0, ..., k.

[*] Variations: let the index point at the oldest item,
and/or use k = (k - 1) % n to run the index in the opposite
direction. Use whichever convention fits most neatly with
whatever else you're doing to the items.

 

[Bill Pursell]

I have a struct which holds an array of structs like this

struct Struct1
{
struct Struct2* strt2 ;
....

};

I allocate a predetermined size to hold n structs of type Struct2.
However, Struct2 represents data that is coming in from a feed. I want
to have an operation that "shifts" the array elements down by one when a
new packet (of type Struct2) is received, so that Struct1 ALWAYS
contains the latest n values.

memove comes to mind, but I'd appreciate some pointers (pun intended)

The first question comes to mind is: do you really need to move
the data? It's generally easier to implement some sort of
ring buffer:
struct Struct2 *current;
current = ((struct Struct1 *)a)->strt2;
for( ; {
overwrite_current_from_feed( current );
if( current - a->strt2 > N )
current = a->strt2;
else
current += 1;
}

So current always points to the oldest packet in the
buffer (and is probably misnamed).

 

[2b|!2b==?]

I have a struct which holds an array of structs like this

struct Struct1
{
struct Struct2* strt2 ;
....
};

I allocate a predetermined size to hold n structs of type Struct2.
However, Struct2 represents data that is coming in from a feed. I want
to have an operation that "shifts" the array elements down by one when a
new packet (of type Struct2) is received, so that Struct1 ALWAYS
contains the latest n values.

memove comes to mind, but I'd appreciate some pointers (pun intended)

Thanks for the replies guys. However it appears I forgot to mention that
I need to look at the HISTORY of the packets rather than just the
current/latest packet. So that I am able to carry statistical analysis
on the data every time a new packet arrives. This is why I need to
maintain a "window" of the latest N packets. This involves "pushing" all
the elements of the array down by one index when a new packet arrives -
if I correctly understand the suggestions made so far, they do not
address the issue I raised (i.e. maintaining an ordered set of the
latest N items, i.e, in the order recieved) - unless I'm missing
something ??

 

[Flash Gordon]

2b|!2b==? wrote, On 02/05/07 07:59:

Thanks for the replies guys. However it appears I forgot to mention that
I need to look at the HISTORY of the packets rather than just the
current/latest packet. So that I am able to carry statistical analysis
on the data every time a new packet arrives. This is why I need to
maintain a "window" of the latest N packets. This involves "pushing" all
the elements of the array down by one index when a new packet arrives -
if I correctly understand the suggestions made so far, they do not
address the issue I raised (i.e. maintaining an ordered set of the
latest N items, i.e, in the order recieved) - unless I'm missing
something ??

Sounds to me like you need to implement a circular buffer. To do this
you define an array which is large enough (or malloc it if the size is
determined at run time).

Depending on situation you can then handle it one of two ways. Have one
index (or pointer) to the newest entry which is wrapped back to the
start of the array when it reaches the end and a flag to say when you
have got a full buffer. Since you always want the last N elements
available this is probably appropriate.

Alternatively, if something is emptying the data as well, you also keep
a pointer to the tail of the buffer, and you have to obviously check for
when head meets tail (buffer full) or tail meets head (buffer empty).

A search for "circular buffer" should turn up lots of hits with more
detailed explanations and implementations.