Doubts about how implementing asynchronous timeouts through a heap

[Giampaolo Rodola']

Hi,
I'm trying to implement an asynchronous scheduler for asyncore to call
functions at a later time without blocking the main loop.
The logic behind it consists in:

- adding the scheduled functions into a heapified list
- calling a "scheduler" function at every loop which checks the scheduled
functions due to expire soonest

Note that, by using a heap, the first element of the list is always supposed
to be the one with the lower timeout.
The support class used to reset() and cancel() the scheduled functions is
very similar to the DelayedCall class defined in /twisted/internet/base.py.
Here's the code I wrote:


<--- snippet --->
import heapq
import time
import sys

delayed_map = []

class delayed_call:
    """Calls a function at a later time.

    The instance returned is an object that can be used to cancel the
    scheduled call, by calling its cancel() method.
    It also may be rescheduled by calling delay() or reset()} methods.
    """

    def __init__(self, delay, target, *args, **kwargs):
        """
        - delay: the number of seconds to wait
        - target: the callable object to call later
        - args: the arguments to call it with
        - kwargs: the keyword arguments to call it with
        """
        assert callable(target), "%s is not callable" %target
        assert sys.maxint >= delay >= 0, "%s is not greater than or equal "
\
                                           "to 0 seconds" % (delay)
        self.__delay = delay
        self.__target = target
        self.__args = args
        self.__kwargs = kwargs
        # seconds from the epoch at which to call the function
        self.timeout = time.time() + self.__delay
        self.cancelled = False
        heapq.heappush(delayed_map, self)

    def __le__(self, other):
        return self.timeout <= other.timeout

    def active(self):
        """Return True if this scheduler has not been cancelled."""
        return not self.cancelled

    def call(self):
        """Call this scheduled function."""
        self.__target(*self.__args, **self.__kwargs)

    def reset(self):
        """Reschedule this call resetting the current countdown."""
        assert not self.cancelled, "Already cancelled"
        self.timeout = time.time() + self.__delay
        if delayed_map[0] is self:
            heapq.heapify(delayed_map)

    def delay(self, seconds):
        """Reschedule this call for a later time."""
        assert not self.cancelled, "Already cancelled."
        assert sys.maxint >= seconds >= 0, "%s is not greater than or equal
" \
                                           "to 0 seconds" %(seconds)
        self.__delay = seconds
        self.reset()

    def cancel(self):
        """Unschedule this call."""
        assert not self.cancelled, "Already cancelled"
        del self.__target, self.__args, self.__kwargs
        if self in delayed_map:
            if delayed_map[0] is self:
                delayed_map.remove(self)
                heapq.heapify(delayed_map)
            else:
                delayed_map.remove(self)
        self.cancelled = True


def fun(arg):
    print arg

a = delayed_call(0.6, fun, '0.6')
b = delayed_call(0.5, fun, '0.5')
c = delayed_call(0.4, fun, '0.4')
d = delayed_call(0.3, fun, '0.3')
e = delayed_call(0.2, fun, '0.2')
f = delayed_call(0.1, fun, '0.1')


while delayed_map:
    now = time.time()
    while delayed_map and now >= delayed_map[0].timeout:
        delayed = heapq.heappop(delayed_map)
        try:
            delayed.call()
        finally:
            if not delayed.cancelled:
                delayed.cancel()
    time.sleep(0.01)
</--- snippet --->


Here comes the questions.
Since that the timeouts of the scheduled functions contained in the list can
change when I reset() or cancel() them I don't know WHEN the list needs to
be heapified().
By doing some tests I came to the conclusion that I need the heapify() the
list only when the function I  reset() or cancel() is the *first of the
list* but I'm not absolutely sure about it.
When do you think it would be necessary calling heapify()?
I wrote a short test suite which tests the code above and I didn't notice
strange behaviors but since that I don't know much about the logic behind
heaps I'd need some help.
Thanks in advance.


--- Giampaolo
http://code.google.com/p/pyftpdlib/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20080709/111d8da1/attachment-0001.html>