comparison mercurial/util.py @ 16803:107a3270a24a

cleanup: use the deque type where appropriate

There have been quite a few places where we pop elements off the
front of a list.  This can turn O(n) algorithms into something more
like O(n**2).  Python has provided a deque type that can do this
efficiently since at least 2.4.

As an example of the difference a deque can make, it improves
perfancestors performance on a Linux repo from 0.50 seconds to 0.36.

16802:7e5d94381cd1

This contains helper routines that are independent of the SCM core and
hide platform-specific details from the core.
"""

from i18n import _
import error, osutil, encoding
import errno, re, shutil, sys, tempfile, traceback
import os, time, datetime, calendar, textwrap, signal
import imp, socket, urllib

if os.name == 'nt':

    return f

def lrucachefunc(func):
    '''cache most recent results of function calls'''
    cache = {}
    order = []
    if func.func_code.co_argcount == 1:
        def f(arg):
            if arg not in cache:
                if len(cache) > 20:
                    del cache[order.pop(0)]
                cache[arg] = func(arg)
            else:
                order.remove(arg)
            order.append(arg)
            return cache[arg]
    else:
        def f(*args):
            if args not in cache:
                if len(cache) > 20:
                    del cache[order.pop(0)]
                cache[args] = func(*args)
            else:
                order.remove(args)
            order.append(args)
            return cache[args]

    def read(self, l):
        """Read L bytes of data from the iterator of chunks of data.
        Returns less than L bytes if the iterator runs dry."""
        left = l
        buf = ''
        queue = self._queue
        while left > 0:
            # refill the queue
            if not queue:
                target = 2**18
                for chunk in self.iter:

                    if target <= 0:
                        break
                if not queue:
                    break

            chunk = queue.pop(0)
            left -= len(chunk)
            if left < 0:
                queue.insert(0, chunk[left:])
                buf += chunk[:left]
            else:
                buf += chunk

        return buf

def filechunkiter(f, size=65536, limit=None):
    """Create a generator that produces the data in the file size

16803:107a3270a24a

This contains helper routines that are independent of the SCM core and
hide platform-specific details from the core.
"""

from i18n import _
import error, osutil, encoding, collections
import errno, re, shutil, sys, tempfile, traceback
import os, time, datetime, calendar, textwrap, signal
import imp, socket, urllib

if os.name == 'nt':

    return f

def lrucachefunc(func):
    '''cache most recent results of function calls'''
    cache = {}
    order = collections.deque()
    if func.func_code.co_argcount == 1:
        def f(arg):
            if arg not in cache:
                if len(cache) > 20:
                    del cache[order.popleft()]
                cache[arg] = func(arg)
            else:
                order.remove(arg)
            order.append(arg)
            return cache[arg]
    else:
        def f(*args):
            if args not in cache:
                if len(cache) > 20:
                    del cache[order.popleft()]
                cache[args] = func(*args)
            else:
                order.remove(args)
            order.append(args)
            return cache[args]

    def read(self, l):
        """Read L bytes of data from the iterator of chunks of data.
        Returns less than L bytes if the iterator runs dry."""
        left = l
        buf = ''
        queue = collections.deque(self._queue)
        while left > 0:
            # refill the queue
            if not queue:
                target = 2**18
                for chunk in self.iter:

                    if target <= 0:
                        break
                if not queue:
                    break

            chunk = queue.popleft()
            left -= len(chunk)
            if left < 0:
                queue.appendleft(chunk[left:])
                buf += chunk[:left]
            else:
                buf += chunk
        self._queue = list(queue)

        return buf

def filechunkiter(f, size=65536, limit=None):
    """Create a generator that produces the data in the file size