Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

Linked lists in an array of hashes

by biohisham (Priest)
on Oct 20, 2009 at 19:13 UTC ( #802297=perlquestion: print w/replies, xml ) Need Help??
biohisham has asked for the wisdom of the Perl Monks concerning the following question:

Hello Monks, my following code here shows a circular ring buffer simulation that can either be written to or read from using the subs "store" and "retrieve", respectively. I am attempting to teach myself advanced data structures and I lack access to examples so I make my own cases. The ring buffer has a head and a tail to be used for checking the buffer emptiness or fullness.

As long as the head does not "meet" the tail the buffer is not empty and still has data that can be read from, this is technically explained as ($tail != $head), correct?, And to tell whether a buffer is full we do check "$buffer[$tail]{next} !=$head". I failed to put this second case in plain English that is void of technicality for me to understand it better (My background is not entirely IT), I even studied this article from Wikipedia, but yet failed, can anyone do it by drawing my attention to a mnemonic parallel or a correlation between these two conditions or something please?.

My other issue is that, I could not figure out a nice neater way to prepare the data structure to hold the indices, so I need to learn from you how to create this data structure in a more efficient manner. Like, I don't want to have to manually fill the hash keys or fill the array with hashes an index at a time and a key at a time. If possible, how can I automate the array holding the hash so I can give it incrementing values to fill each "next" key without an intervention on my part?,I have tried for the past 2 hours but none of the loops I came up with worked so I'm dry from tricks and open to learn new ones from you :), Here is my code everyone:

use strict; my @buffer=( { data=>'', next=>1 },{ data=>'', next=>2, },{ data=>'', next=>3 }, { data=>'', next=>4 } ); sub store { if($buffer[$tail]{next} !=$head){ $buffer[$tail]{data}=shift; $tail=$buffer[$tail]{next}; return 1 }else{ return "Buffer is full"; } } sub retrieve{ if($tail != $head){ my $data=$buffer[$head]{data}; $head=$buffer[$head]{next}; return $data; }else{ return "Empty\n"; } } store "20"; print retrieve;

Eventually, what are the potential uses of such code, using arrays of hashes in buffers simulation is an example I can think of but what other similar examples of applications there are that such an array of hashes structure use can really save me for the day?!

Excellence is an Endeavor of Persistence. Chance Favors a Prepared Mind.

Replies are listed 'Best First'.
Re: Linked lists in an array of hashes
by ikegami (Pope) on Oct 20, 2009 at 19:47 UTC

    The earlier posts seem to be missing the point of a ring buffer. They require no locks when they have one writer thread and one reader thread. Using push+shift produces a queue, but not specifically a ring buffer.

    For example, the keyboard buffer used to be a ring buffer. The keyboard would place messages into it to be read by the system.

    What the OP is missing is that ring buffers are usually implemented using ever growing indexes into an array, mod the size of the buffer. If you don't want to limit the size of the buffer, you can use a linked list instead of an array. Hashes don't figure into the equation.

    my $head = 0; # Can only be modified by the lone writer thread my $tail = 0; # Can only be modified by the lone reader thread my $size = 4; # Can hold one less than $size my @buf = (undef) x $size; # Can only be called by the lone reader thread sub is_empty { return $tail == $head; } # Can only be called by the lone reader thread sub dequeue { return () if is_empty(); my $val = $buf[$tail]; $tail = ( $tail + 1 ) % @buf; return $val; } # Can only be called by the lone writer thread sub is_full { return ($head + 1) % @buf == $tail; } # Can only be called by the lone writer thread sub enqueue { my ($val) = @_; return 0 if is_full(); $buf[$head] = $val; $head = ( $head + 1 ) % @buf; return 1; }

    If you have more than one writer thread or more than one reader thread, locking is necessary.

    Now, if you want to have multiple buffers going, you can use an object.

    package Data::RingBuffer; sub new { my ($class, $size) = @_; return bless({ head => 0, tail => 0, buf => [ (undef) x $size ], }, $class); } sub is_empty { my ($self) = @_; return $self->{tail} == $self->{head}; } sub dequeue { my ($self) = @_; my $buf = $self->{buf}; return () if $self->is_empty(); my $val = $buf->[$self->{tail}]; $self->{tail} = ( $self->{tail} + 1 ) % @$buf; return $val; } sub is_full { my ($self) = @_; my $buf = $self->{buf}; return ($self->{head} + 1) % @$buf == $self->{tail}; } sub enqueue { my ($self, $val) = @_; my $buf = $self->{buf}; return 0 if $self->is_full(); $buf->[$self->{head}] = $val; $self->{head} = ( $self->{head} + 1 ) % @$buf; return 1; }

    Update: Fixed typos in code. Simplified code.

Re: Linked lists in an array of hashes
by GrandFather (Sage) on Oct 20, 2009 at 20:54 UTC

    Ring buffers are used in performance critical situations, often in embedded code, where a fixed size chunk of memory is allocated and used as a queue for buffering data.

    The usual implementation uses two pointers (indexes). Details vary a little, but by inspecting the pointers you can determine if the buffer is full (incrementing the input pointer would make it match the output pointer), empty (input pointer matches output pointer) or somewhere between. Very often the buffer size is a power of 2 to take advantage binary arithmetic operations to reduce code complexity and increase speed.

    Except as an exercise there is no application I can think of where writing a ring buffer in Perl would be useful. The following may be of interest though:

    use strict; use warnings; my $buffer = new (); print "Buffer has ", $buffer->count (), " values\n"; $buffer->push ($_) for 1 .. 200; print "Buffer has ", $buffer->count (), " values\n"; $buffer->pop () for 1 .. 100; print "Buffer has ", $buffer->count (), " values\n"; $buffer->push ($_ + 200) for 1 .. 150; print "Buffer has ", $buffer->count (), " values\n"; sub new { my @bufferArray; my $buffSize = 256; $#bufferArray = 256; # set buffer size return $buffer = bless { buffer => \@bufferArray, in => 0, out => 0, buffSize => $buffSize, }; } sub count { my ($self) = @_; my $used = $self->{in} - $self->{out}; $used += $self->{buffSize} if $used < 0; return $used; } sub pop { my ($self) = @_; die "Buffer underflow" if $self->{in} == $self->{out}; my $value = $self->{buffer}[$self->{out}]; $self->{out} = ($self->{out} + 1) % $self->{buffSize}; return $value; } sub push { my ($self, $value) = @_; die "Buffer overflow" if $self->count () + 1 == $self->{buffSize}; $self->{buffer}[$self->{in}] = $value; $self->{in} = ($self->{in} + 1) % $self->{buffSize}; }


    Buffer has 0 values Buffer has 200 values Buffer has 100 values Buffer has 250 values

    Update: Fixed reporting error in push - thanks ikegami!

    True laziness is hard work
Re: Linked lists in an array of hashes
by pemungkah (Priest) on Oct 20, 2009 at 21:32 UTC
    First: big kudos for seeing that data structures are important and working to learn about them. I think some of the other posters may be missing what you're trying to do here: use a language that you're comfortable in to try to understand computer science concepts, not solve a particular problem.

    The comments that note that arrays manage themselves in Perl are certainly true, it's that, if I'm interpreting your question correctly, you want to learn about traditional data structure management.

    So - you have then empty condition correct: if the head and tail point to the same node, the buffer is empty. A clearer statement of the "full" state is "If the next of the tail node points to the head, then the buffer is full".

    First: setting up a ring buffer programatically rather than declaratively. You want an array (fixed size) of hashes, each one "pointing" to the next except for the last, which should point to the first. So let's do that:

    my @ring; use constant RING_SIZE => 10; for my $buffer_pointer (0..RING_SIZE) { my $next_element = ($buffer_pointer + 1) % RING_SIZE; $ring[$buffer_pointer] = { data =>'', next => $next_element }; }
    I initially also had put together an example of using references to build a "real" circular buffer, but really there's no reason to do it: way too much overhead. (Aside: it showed me my pointer manipulation skills are a little stale! Worth trying yourself for that reason.) Ring buffers generally are used when you've got the following situation:
    1. You have one thread or process reading a buffer, and a second one writing it.
    2. You are memory-constrained and can only afford to devote a controlled, relatively small amount of storage to the process
    3. You want relatively fast response time from both processes.
    So the writer gets characters from somewhere, and puts them into the buffer. If the buffer fills, it blocks until there is room in the buffer again. The reader of course does the opposite: if the buffer is empty, it blocks until something appears there.

    You do, as others have also mentioned, need a lock to serialize access to the buffer, since the operations to manage the buffer are not atomic - it takes more than one step to decide that there's something in it (or room available) and then alter the buffer accordingly. If you were really planning on implementing this for some reason (a pool of reusable database handles?), you'd need the locking. And they're also right that implementing the put/get management with shift and push would probably be far more efficient and easier to debug.

Re: Linked lists in an array of hashes
by gmargo (Hermit) on Oct 20, 2009 at 19:31 UTC

    Can't you just use "push" and "shift"? Why the big complication with "circular ring buffers"?

Re: Linked lists in an array of hashes
by zwon (Abbot) on Oct 20, 2009 at 19:35 UTC

    What are you're doing doesn't look good for me. You can do the same much simpler:

    my @buffer; sub store { return "Buffer is full" if @buffer >= 4; push @buffer, $_[0]; } sub retrieve { shift @buffer; }

    Update: ikegami is right, if you have reader and writer threads ring buffer is quite useful. And my code would require some synchronization.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://802297]
Approved by AnomalousMonk
and the rats come out to play...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (2)
As of 2018-05-23 00:19 GMT
Find Nodes?
    Voting Booth?