Just use an array, and a scalar to point into the array.

my @buffer = (0) x 5;
my $pointer = 0;
for (0..30) {
    print "old value: ", $buffer[$pointer % @buffer], "\n";
    print "new value: $_\n";
    $buffer[$pointer % @buffer] = $_;
    $pointer++;
}
[download]

I don't like leaving the $pointer variable grow indefinitely.
This code is equivalent, but keeps $pointer in [0,@buffer). In fact, just gets the remainder after each $pointer change

my @buffer = (0) x 5;
my $pointer = 0;
for (0..30) {
    print "old value: ", $buffer[$pointer], "\n";
    print "new value: $_\n";
    $buffer[$pointer] = $_; 
    $pointer = (++$pointer) % @buffer;
}
[download]

I usually avoid code like $pointer = (++$pointer) % @buffer; where the same variable is modified twice within the same expression. It means that the outcome depends on the order of evaluation, which isn't defined in all cases (it is in the case of assignment though).

Instead I'd just write $pointer = (1 + $pointer) % @buffer.

Perl 6 - second systems done right

No $pointer. @buffer always ordered last to most recent.


my @buffer = (0) x 5;
for (0..30) {
    print "old value: ", $buffer[0], "\n";
    print "new value: $_\n";
    shift @buffer;
    push  @buffer, $_;
}
[download]

A circular buffer is a specific implementation of a queue which has the following features:

• If you have one reader and one writer working in parallel, there is no need for locking.
• No need for memory allocation.
• O(1) insertion at the tail and O(1) removal from the head.

All of these features are offered by a plain array based queue in Perl (see below), so I don't see the point of implementing a circular buffer in Perl unless its faster (but I doubt that).

my @q;
while (@q) {
   my $item = shift(@q);  # Insertion
   ...
   push @q, ...;          # Removal
   ...
}
[download]

For fun, I wrote one.

package Data::CircularBuffer;

use strict;
use warnings;

# This does nothing if 'use threads;' wasn't previously executed.
use threads::shared qw( bless );

sub new {
   my ($class, $n) = @_;
   ++$n;  # Used to differentiate full from empty.
   return bless({
      size => $n,
      buf  => [ (undef) x $n ],
      head => 0,
      tail => 0,
   }, $class);
}

sub is_empty {
   my ($self) = @_;
   return $self->{head} == $self->{tail};
}

# Returns empty list if the buffer is empty. That means the
# following will work even if the buffer contains false elements:
#    while (my ($element) = $cb->shift()) { ... }
sub shift {
   my ($self) = @_;
   return () if $self->is_empty();

   my $val = $self->{buf}[ $self->{head} ];
   $self->{buf}[ $self->{head} ] = undef;
   $self->{head} = ( $self->{head} + 1 ) % $self->{size};
   return $val;
   
}

# Returns number of items successfully inserted.
sub push {
   my $self = shift;

   my $inserted = 0;
   for (@_) {
      my $new_tail = ( $self->{tail} + 1 ) % $self->{size};
      last if $new_tail == $self->{head};

      $self->{buf}[ $self->{tail} ] = $_;
      $self->{tail} = $new_tail;
   }

   return $inserted;
}

1;
[download]

Untested. Should work with a writer in one thread and a reader in another thread without locks.

Update: Now clears elements that have been shifted out of the buffer to ensure timely destruction.

In Perl, a Perl array can be used to implement a FIFO buffer. A Perl array is different from arrays in C or other programming language's ideas of arrays in that it can change size. So to implement a FIFO queue in Perl, just push new entries onto the bottom of the Perl array and shift out "oldest" entries from the top. The size of the Perl array (and the indicies) will adjust themselves without you having to "move" anything. For the idea, this code is untested, but I figure should work...

my @fifo;
my $MAX_FIFO = 53; #max size is optional

sub add_entry
{
   die "Cicular buffer overflow\n" if (@fifo >= $MAX_FIFO);
   my $entry = shift;  #well, $_[0] is ok for syntax too
                       #but I think this is more clear
                       #these simple assignment statements are 
                       #  not "expensive"
   push @fifo, $entry; 
}

sub get_entry
{
   return (shift @fifo);
}
[download]

get_entry() above could be modified to "die" if the @fifo is empty. There are lots of other possibilities. I advise the OP to study the Perl functions: push, pop, shift, unshift and splice.

The Perl version is also very fast - not as fast as C, but much easier to write!

No, it's practically exactly the same, op for op.

So to implement a FIFO queue in Perl, just push new entries onto the bottom of the Perl array and shift out "oldest" entries from the top.

A circular buffer is a queue (FIFO), but a queue is not necessarily a circular buffer. You didn't provide any indication as to whether the code you posted is a suitable solution for the OP or not.

It turns out the code you (and I) posted does exhibit the same characteristics as a circular buffer. See my reply.

The Perl array also can implement essentially the equivalent of a 'C' doubly linked list. [...] But in Perl you can use splice()

If you can use splice, you don't have a linked list. Linked lists take O(1) to remove a previously found element. splice takes O(N).

The more I learn about Perl, the more impressed I become with the performance. Perl codes at about a 3x-5x and sometimes 10x efficiency in terms of source lines vs 'C'. From what I can see, great Perl code runs like 1/3 the speed of average 'C' code which given the coding efficiency is just fine - actually Great! I have become a fan of Perl.

I am curious as to the implementation of splice() in Perl. Does a splice() really result in a copy of an entire array, like a typical 'C' realloc()? If a Perl array has say 1,000 elements and I do an "insert" after element 2, how does the low level Perl deal with this? Does it really do 1,000+ operations?

How does Perl handle the push or unshift operations?