Ring buffer, linked list, etc.

Christopher R. Hertel crh at ubiqx.mn.org
Sun Aug 7 03:43:43 GMT 2005

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

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

More information about the samba-technical mailing list