Ring buffer, linked list, etc.

Stefan Metzmacher metze at samba.org
Wed Aug 10 07:38:41 GMT 2005


Am Sonntag, 7. August 2005 07:06 schrieb Christopher R. Hertel:

Hi Chris,

could you give me a should introducing about what you're talking,
I mean what was the topic of the discusion, and to what code does this 
belong...

thanks!

metze

> We also talked about using skip lists for the event queue, but the problem
> we ran into was:  If we get an arbitrary delete (caused by an event
> actually occuring) the skip list pointers would no longer be valid and
> could mess things up.
>
> So:  If we pre-tallocate blocks of doubly-linked-list nodes (in, say,
>      groups of 128 nodes each), then instead of freeing the memory when a
>      node is deleted we would:
>      = remove it from the event list
>      = add it to a singly-linked free list
>      = set the event timeout value to zero
>
>      In the event queue, only the first node in the linked list will have
>      a NULL previous pointer, so we can ignore skip list pointers that
>      point to nodes with a NULL previous pointer.  We would probably mark
>      them as unused so that they can be re-used (another free list).
>
>      If the free list ever runs out, we would tallocate another 128
>      (or whatever) nodes and rebuild the node free list.
>
>      I'm thinking that we would probably set aside one skip node per 128
>      event nodes.  The skip nodes could also be arranged as a
>      doubly-linked list.
>
> I'd like to code this up.  I have a very full week at work, however, and
> my kids haven't seen me for a week so if anyone else wants to do it please
> go ahead.  :)
>
> Chris -)-----
>
> On Sat, Aug 06, 2005 at 10:43:43PM -0500, Christopher R. Hertel wrote:
> > Tridge, Volker,
> >
> > Once I got home and had my first decent cup of tea in a week, a thought
> > occurred to me regarding the idea of using a ring buffer.
> >
> > As I understand it, f an event is received before the queue entry times
> > out then the entry is removed from the event queue.  This is done by way
> > of a pointer directly to the event queue entry.
> >
> > With a doubly-linked-list or a binary tree, that removal can occur
> > without any traversal of the list.  The pointer to the event node is all
> > you need.
> >
> > If we build a ring buffer, however, and use memmove() to open spaces when
> > we need to insert new nodes, we'll mess up any external pointers.  You'll
> > have to search for the correct node each time.
> >
> > Using a ring buffer, the way to get around this is to mark nodes as
> > "Deleted" if the event arrives before timeout.
> >
> > That still leaves the problem of adding new nodes to the ring buffer.  I
> > have some ideas on how to do that...
> >
> > Let me know first, though, if I've misunderstood the way this code
> > operates.
> >
> > Chris -)-----
> >
> > --
> > "Implementing CIFS - the Common Internet FileSystem" ISBN: 013047116X
> > Samba Team -- http://www.samba.org/     -)-----   Christopher R. Hertel
> > jCIFS Team -- http://jcifs.samba.org/   -)-----   ubiqx development,
> > uninq. ubiqx Team -- http://www.ubiqx.org/     -)-----   crh at ubiqx.mn.org
> > OnLineBook -- http://ubiqx.org/cifs/    -)-----   crh at ubiqx.org

-- 
metze
--
Stefan (metze) Metzmcher <metze at samba dot org>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.samba.org/archive/samba-technical/attachments/20050810/984aefa2/attachment.bin


More information about the samba-technical mailing list