Skiplists

[Einar Indridason]

>>>>>> Ethan Galstad wrote:
>
> >>>>>>> For the event queue, I was thinking that a skip
> >>>>>>> list structure might be best for efficiency
> >>>>>>> (http://en.wikipedia.org/wiki/Skip_list).  The
> >>>>>>> event queue is used in primarily two
> >>>>>>> situations:
> >>>>>>> 1. Popping events from the head of the list to
> >>>>>>>    be executed
> >>>>>>> 2. Inserting events into the list (mid- or
> >>>>>>>    endpoint).



Sorry for butting in so late in this discussion.  But have you considered a
"Heap" (or a priority queue)?
(Or maybe I'm misunderstanding something here?)

http://en.wikipedia.org/wiki/Heap_%28data_structure%29
http://en.wikipedia.org/wiki/Priority_queue

This will allow you, with ease, to get the "lowest" priority.  (It is the
first item on the heap).
Time complexity of retrieval is of order: O(n * log(n))
Adding an item, with assorted priority, is also of order: O(n * log(n))

Cheers,
--
EinarI
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.monitoring-lists.org/archive/developers/attachments/20071016/0ebb95bb/attachment.html>
-------------- next part --------------
-------------------------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc.
Still grepping through log files to find problems?  Stop.
Now Search log events and configuration files using AJAX and a browser.
Download your FREE copy of Splunk now >> http://get.splunk.com/
-------------- next part --------------
_______________________________________________
Nagios-devel mailing list
Nagios-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nagios-devel