Ring buffer, linked list, etc.

[Christopher R. Hertel]

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

-- 
"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