Are there Python code for a FIFO-like structure?

[Andrew Henshaw]

"Grant Griffin" <g2 at seebelow.org> wrote in message
news:39DE3F0C.984E2187 at seebelow.org...
> Huaiyu Zhu wrote:
> >
> > [Huaiyu Zhu]
> >
> > >> > I need something like a fifo, inplemented in a fixed length list...
> > >> > an IndexError is raised if the tail gets
> > >> > too close to the head.
> >
> > Hi, everyone,
> >
> > Thanks for all these good ideas.
> >
> > [Christian Tismer]
> >
> > >Hmm, why don't you really use a fixed length list, maintain
> > >two rotating pointers, and check that they behave well?
> >
> > Yes, that's what I had in mind when I posted the query.  The real work
is to
> > make the two pointers behave well, of course.  I'm getting there.
> >
>
> If I understand what you're after, here is a description of generic FIFO
> logic (caveat emptor: from memory):
>
> 1. Allocate the fixed-length FIFO buffer (probably as a Python list
> or--maybe better--as a Numeric array.)
> 2. Initialize a read_index and write_index to zero.
> 3. The FIFO is empty whenever read_index == write_index (e.g. when both
> are initialized to zero.)
> 4. The FIFO if full whenever write_index is one less than read_index.
> (Note that a special "modulo" case of full is when write_index == length
> - 1, and read_index == 0.)
> 5. To read, check for FIFO empty (if so, raise error), get data at
> read_index, then increment read_index, modulo the length.  (You can
> quickly implement the modulo by just setting read_index to 0 when the
> incremented read_index == length.)


Note, the modulo function can be made very fast if your list length is a
power of 2.   Modulo then simply becomes 'pointer & (length-1)'.  For
example:

buf_len = 1024
wrap_at = buf_len - 1

buffer = [0] * buf_len
.
.
.
read_index = read_index & wrap_at     # read_index &= wrap_at   with Python
2.0
.
.
.

This should be faster than branching.


> 6. To write, do the same thing: check for FIFO full (if so, raise
> error), put data at write_index, increment, do quick modulo.)
>
> if-i-could-ever-remember-where-i-put-all-those-fifo-implementations
>    -i've-written-over-the-years,-i-wouldn't-ever-have-written
>    -so-many-fifo-implementations-over-the-years-ly y'rs,
>
> =g2
> --
> _____________________________________________________________________
>
> Grant R. Griffin                                       g2 at dspguru.com
> Publisher of dspGuru                           http://www.dspguru.com
> Iowegian International Corporation       http://www.iowegian.com