Thread-safe Sorted Collection

Question

Is there an implementation of a thread-safe sorted collection in Python?
Python's docs reference SortedCollection but I'm not sure if it's thread-safe (is it?)
If there is no such implementation - how would you implement it?

Answer 1

Looking through the code, it does not appear to be thread safe. To use it from multiple threads the application code that accesses it should be guarded with semaphore locks.

If you want to make the SortedCollection class thread safe, you could write a decorator function.

It would look something like this:

SortedCollection:

def __init__(self):
    self.mysemaphore = threading.Semaphore()

def guard(func):
    def guarded(*args, **kwds):
        self.mysemaphore.acquire()
        try:
            return func(*args, **kwds)
        finally:
            self.mysemaphore.release()

return guarded

# edit the class, applying the decorator to its methods.
@guard
def unsafeFunc(self, a, b, c):
    ''' do work here'''

EDIT

Don't make the mistake of thinking that a threadsafe data structure will make your application code thread safe. If you perform multiple operations on a SortedCollection, all of those operations need to be guarded by a lock.

Even if SortedCollection is threadsafe, the following code would not be:

slist.insert(1)
slist.insert(2)

It is possible that another thread could insert an item in between those 2 statements. You will need to guard within your application code. If you add this to your application code, you will not need to modify the SortedCollection to be thread safe.

semaphore2.acquire()

try:
    slist.insert(1)
    slist.insert(2)
finally:
    semaphore2.release()

Answer 2

The collections.OrderedDict class is not threadsafe for updates. You can do concurrent reads, but locks are needed for writes. For an example of how to use locks with OrderedDict, see the source for functools.lru_cache().