UT/UT_ThreadSafeCache.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      Andrew Clinton
 *      Side Effects Software Inc
 *      123 Front Street West, Suite 1401
 *      Toronto, Ontario
 *      Canada   M5J 2M2
 *      416-504-9876
 *
 * NAME:        UT_ThreadSafeCache.h ( UT Library, C++ )
 *
 * COMMENTS:    A fast, thread-safe cache to be used for high-performance
 *              applications.
 */

#ifndef __UT_ThreadSafeCache__
#define __UT_ThreadSafeCache__

#include "UT_API.h"
#include <SYS/SYS_Types.h>
#include <SYS/SYS_AtomicInt.h>
#include <SYS/SYS_AtomicIntImpl.h>
#include "UT_LockUtil.h"

// Explicit instantiations are provided for:
// - UT_Lock
// - UT_RecursiveSpinLock
template <class Lock>
class UT_API UT_ThreadSafeCache {
public:
    // A cache item stub.  You must implement a subclass to provide
    // allocation and deallocation routines.
    class UT_CacheItem
    {
    public:
                 UT_CacheItem()
                     : myPrev(0), myNext(0), myMemory(0)
                     , myRefCount(0), myTimeStamp(0)
                     , myAllocated(false) {}
        virtual ~UT_CacheItem() {}

    protected:
        // Allocate an item and return the total amount of memory consumed
        // by the cache item in bytes.
        virtual int64    allocate(void *parms) = 0;

        // Deallocate the item and free associated memory.
        virtual void     deallocate(void *user_data) = 0;

        // Retrieve the amount of memory consumed by the cache item
        int64            getMemoryUsage() const { return myMemory; }

    private:
        int              getRefCount() const    { return myRefCount; }
        void             incRefCount()          { myRefCount.add(1); }
        void             decRefCount()          { myRefCount.add(-1); }

        bool             isInCache() const      { return myNext; }

    private:
        UT_CacheItem    *myPrev;
        UT_CacheItem    *myNext;
        int64            myMemory;
        uint64           myTimeStamp;
        SYS_AtomicInt32  myRefCount;
        bool             myAllocated;

        friend class     UT_ThreadSafeCache;
        friend class     UT_ThreadSafeCache::unsafe_traverser;
        friend class     UT_LimitedCache;
    };

public:
    // The destroy flag controls whether the cache will clean up its
    // allocated items on destruction.
     UT_ThreadSafeCache(bool destroy = true);
    ~UT_ThreadSafeCache();

    // Set cache size in megabytes
    void                setMaxMemory(int64 size_mb, bool prune = false);
    // Set cache size in bytes
    void                setMaxMemoryBytes(int64 size_bytes, bool prune = false);
    int64               getMaxMemoryBytes() const
                            { return myMemoryLimit; }

    // Get total cache memory usage in bytes, including all allocated item
    // memory.
    int64               getMemoryUsage() const  { return myMemoryUsed; }

    // Get number of cached items
    int64               entries() const         { return myEntries; }

    // Set user data that is passed to allocate()/deallocate()
    void                setUserData(void *data) { myUserData = data; }

    // Control whether we evict items when memory limit is used. Default is
    // true.
    void                setCheckMemoryLimit(bool check)
                            { myCheckMemoryLimit = check; }
    bool                getCheckMemoryLimit() const
                            { return myCheckMemoryLimit; }

    // Access an item in the cache.  If the item is not already in the
    // cache, it will be inserted at the head.  If the lock flag is true,
    // calling this operation acquires an access lock that must be released
    // with release().  parms will be passed directly to the allocate()
    // operation.
    void                access(UT_CacheItem *item, void *parms = 0)
                        {
                            item->incRefCount();
                            // Now, check if we need to reorder
                            accessUnreferenced(item, parms);
                        }
    /// Re-order list because of access
    void                accessUnreferenced(UT_CacheItem *item, void *parms = 0)
                        {
                            // Before moving items in the cache, check whether
                            // the head has been moved a sufficient number of
                            // times to make it useful to move the item back to
                            // the head of the cache.  This way, if the same
                            // set of items are always referenced we never need
                            // to modify the cache.
                            if (item->myAllocated && isNearHead(item))
                            {
                                return;
                            }

                            // Now, reorder the item in the cache
                            accessLockedReorder(item, parms);
                        }
    // Release the access lock an an item.  For every call to access()
    // there must be a corresponding call to release().
    void                release(UT_CacheItem *item);

    // Deallocates and removes an item from the cache.
    void                freeItem(UT_CacheItem *item);

    // Clear all entries from the cache.
    void                freeAllItems();

    // Prune entries from the cache until we hit the given memory usage
    void                pruneItems(int64 memory_limit);

    class UT_API unsafe_traverser
    {
        public:
            unsafe_traverser()
                : myCurr(NULL) {}
            unsafe_traverser(const unsafe_traverser &src)
                : myCurr(src.myCurr) {}
            ~unsafe_traverser() {}

            const UT_CacheItem  *get() const    { return myCurr; }
            int         operator==(const unsafe_traverser &cmp) const
                            { return myCurr == cmp.myCurr; }
            int         operator!=(const unsafe_traverser &cmp) const
                            { return myCurr != cmp.myCurr; }
            bool        atEnd() const
                            { return !myCurr; }
            unsafe_traverser    &operator++()
                            {
                                if (myCurr)
                                    myCurr = myCurr->myNext;
                                return *this;
                            }
            const unsafe_traverser      &operator=(const unsafe_traverser &src)
                            {
                                myCurr = src.myCurr;
                                return *this;
                            }
        private:
            unsafe_traverser(UT_CacheItem *head)
                : myCurr(head) {}
            const UT_CacheItem  *myCurr;
            friend class UT_ThreadSafeCache;
    };

    unsafe_traverser    unsafe_begin() const
                            { return unsafe_traverser(myHead); }
    unsafe_traverser    unsafe_end() const
                            { return unsafe_traverser(); }

    /// Query the cache misses
    int64               getFaults() const       { return myFaults; }

private:
    /// Reorder the list due to access - requires locking
    void                accessLockedReorder(UT_CacheItem *item, void *parms);

    void                pruneItemsNoLock(int64 memory_limit);
    void                addToCache(UT_CacheItem *item);
    void                removeFromCache(UT_CacheItem *item);
    void                allocateItem(UT_CacheItem *item, void *parms)
                        {
                            if (!item->myAllocated)
                            {
                                int handle = myObjLock.lock(item);
                                if (!item->myAllocated)
                                {
                                    item->myMemory = item->allocate(
                                            parms ? parms : myUserData);
                                    item->myAllocated = true;
                                }
                                myObjLock.unlock(item, handle);
                            }
                        }

    // Heuristic to decide when an item is close to the head.  Items can
    // only be moved when this method returns false.
    bool                isNearHead(const UT_CacheItem *item) const
                        { return myHeadTime - item->myTimeStamp <=
                            myQuarterEntries; }

private:
    UT_ObjLockType<Lock>         myObjLock;
    Lock                         myThreadLock;
    UT_CacheItem                *myHead;
    int64                        myMemoryLimit;
    int64                        myMemoryUsed;
    int64                        myEntries;
    int64                        myQuarterEntries;
    int64                        myFaults;
    uint64                       myHeadTime;
    void                        *myUserData;
    bool                         myDestroy;
    bool                         myCheckMemoryLimit;
    friend class        UT_LimitedCache;
};

#endif

---