Linear search. Performance is O(n^2).

def linear_insert(self, item, priority):
    """Linear search. Performance is O(n^2)."""

    with self.lock:
        self_data = self.data
        rotate = self_data.rotate
        maxlen = self._maxlen
        length = len(self_data)
        count = length

        # in practice, this is better than doing a rotate(-1) every
        # loop and getting self.data[0] each time only because deque
        # implements a very efficient iterator in C
        for i in self_data:
            if priority > i[1]:
                break
            count -= 1

        rotate(-count)
        self_data.appendleft((item, priority))
        rotate(length-count)

        try:
            self.items[item] += 1
        except TypeError:
            self.items[repr(item)] += 1

        if maxlen is not None and maxlen < len(self_data):
                self._poplast()