UT/UT_LimitedCache.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:
 *      Side Effects Software Inc
 *      123 Front Street West, Suite 1401
 *      Toronto, Ontario
 *      Canada   M5J 2M2
 *      416-504-9876
 *
 * NAME:        UT_LimitedCache.h ( UT Library, C++)
 *
 * COMMENTS:
 */

#ifndef __UT_LimitedCache__
#define __UT_LimitedCache__

#include "UT_API.h"
#include "UT_Cache.h"
#include "UT_SpinLock.h"
#include "UT_Lock.h"
#include "UT_RefArray.h"
#include "UT_ThreadSafeCache.h"
#include "UT_ConcurrentHashMap.h"
#include "UT_String.h"
#include "UT_SharedPtr.h"

/// The limited cache uses a UT_ThreadSafeCache to maintain the LRU behaviour.
typedef UT_ThreadSafeCache<UT_RecursiveSpinLock>        UT_LimitedLRUCache;

/// @brief Key class - used to query or add objects to the limited cache.
///
/// The key object is used to lookup UT_LimitedCacheItem objects.  The key is
/// stored in the LRU cache and thus, must conform to the requirements of the
/// LRU Cache Item
class UT_API UT_LimitedCacheKey : public UT_LimitedLRUCache::UT_CacheItem
{
public:
             UT_LimitedCacheKey();
    virtual ~UT_LimitedCacheKey();

    /// Return a duplicate new key
    virtual UT_LimitedCacheKey  *duplicate() const = 0;

    /// Return a hash for the key
    virtual unsigned    getHash() const = 0;

    /// Comparison between another key
    virtual bool        isEqual(const UT_LimitedCacheKey &key) const = 0;

    /// Return the memory size of the the key object @b and the size of an
    /// item object.  i.e. @code
    ///    return sizeof(UT_LimitedCacheKey) + sizeof(UT_LimitedCacheItem);
    /// @endcode
    virtual int64       getTotalMemory() const = 0;

    /// @{
    /// API for the LRU cache item
    virtual int64       allocate(void *)
                        { return getTotalMemory(); }
    virtual void        deallocate(void *cache);
    /// @}
};
typedef UT_SharedPtr<UT_LimitedCacheKey>        UT_LimitedCacheKeyHandle;

/// A base class for items stored in the limited cache.  This is required so
/// that the cache can delete items when needed.
class UT_API UT_LimitedCacheItem {
public:
             UT_LimitedCacheItem();
    virtual ~UT_LimitedCacheItem();
};

/// @brief A memory limited cache
///
/// The memory limited cache allows you to put objects into the cache.  The
/// cache will automatically throw objects away based on memory usage.
/// You can put as many objects into the cache as you want, but don't count on
/// always being able to find them in the cache since they may get thrown out.
/// 
/// Example: @code
///   class Item : public UT_LimitedCacheItem {
///   public:
///              Item() : UT_LimitedCacheItem() {}
///     virtual ~Item();
///     Data    myData;         // Data in item
///   };
///   class Key : public UT_LimitedCacheKey {
///     Key(const char *str)    { myString.harden(str); }
///     Key(const Key &key)     { myString.harden(key.myString); }
///     
///     virtual UT_LimitedCacheKey      *duplicate() const
///                                         { return new Key(*this); }
///     virtual unsigned        getHash() const
///                             {
///                                 return myString.hash();
///                             }
///     virtual bool            isEqual(const UT_LimitedCacheKey &src) const
///                             {
///                                 const Key &k = static_cast<Key &>(src);
///                                 return k.myString == myString;
///                             }
///     virtual int64           getTotalMemory() const
///                             {
///                                 return myString.getMemoryUsage() }
///                                         sizeof(Item) +
///                                         sizeof(*this);
///                             }
///   };
///
///   static bool
///   testLookup(const UT_LimitedCache &cache, const char *str)
///   {
///     UT_LimitedCache::Lookup         found;
///
///     found = cache[Key(str)];
///     if (found.isValid())
///         processItem(found.getItem());
///   }
///    
///   testCache(const UT_StringArray &strings)
///   {
///     UT_LimitedCache cache("Test-Cache", 8); // An 8 MB cache
///     for (int i = 0; i < strings.entries(); i++)
///         cache.addItem(Key(strings(i)), new Item());
///     testLookup("foo");
///     testLookup("bar");
///   }
/// @endcode
class UT_API UT_LimitedCache : public UT_Cache
{
public:
     UT_LimitedCache(const char *cache_name,
                    int64 size_in_mb=32);
    ~UT_LimitedCache();

    /// The lookup class is used to return query/add results.  Using the lookup
    /// class, you are guaranteed that the item will not be destroyed while the
    /// lookup exists.  When the lookup is destroyed, the item becomes fair
    /// game for deletion.
    class Lookup {
    public:
        Lookup()
            : myCache(NULL)
            , myKey(NULL)
            , myItem(NULL)
        { }
        /// Copy c-tor
        Lookup(const Lookup &src)
            : myCache(src.myCache)
            , myKey(src.myKey)
            , myItem(src.myItem)
        {
            access();
        }
        ~Lookup()
        {
            release();
        }
        /// Assignment operator
        const Lookup    &operator=(const Lookup &src)
                         {
                             if (this != &src)
                             {
                                 // inc ref count on source
                                 const_cast<Lookup &>(src).access();
                                 // Now release my count
                                 release();
                                 myCache = src.myCache;
                                 myKey = src.myKey;
                                 myItem = src.myItem;
                             }
                             return *this;
                         }
        /// @{
        /// Accessors
        bool                      isValid() const { return myKey; }
        const UT_LimitedCacheKey *getKey() const { return myKey; }
        UT_LimitedCacheItem      *getItem() const { return myItem; }
        /// @}

        /// If you manually delete the object from the cache, you must call
        /// @c clear() so that release() isn't called in the destructor.
        /// Alternatively, if the cache is destructed before the query, it
        /// should also be cleared.
        void            clear() { release(); }
    private:
        Lookup(UT_LimitedCache *cache,
                UT_LimitedCacheKey *key,
                UT_LimitedCacheItem *item)
            : myCache(cache)
            , myKey(key)
            , myItem(item)
        {
            // In this case, the cache has already performed the access on the
            // key.
        }
        void    access()
                {
                    if (myCache && myKey)
                        myCache->referenceItem(myKey);
                }
        void    release()
                {
                    if (myCache && myKey)
                    {
                        myCache->unreferenceItem(myKey);
                        myCache = NULL;
                        myKey = NULL;
                        myItem = NULL;
                    }
                }
        UT_LimitedCacheKey              *myKey;
        UT_LimitedCache                 *myCache;
        UT_LimitedCacheItem             *myItem;
        friend class UT_LimitedCache;
    };

    /// @{
    /// Convenience array operators to lookup objects based on the key
    Lookup      operator()(const UT_LimitedCacheKey &key)
                    { return findItem(key); }
    Lookup      operator[](const UT_LimitedCacheKey &key)
                    { return findItem(key); }
    /// @}

    /// Find out the number of entries being stored in the cache
    int64       entries() const { return myTable.size(); }

    /// Find out the number of entries being stored in the cache
    int64       lru_entries() const     { return myLRUCache.entries(); }


    /// Clear all elements out of the cache
    void        clearCache();

    /// Find an item in the cache.  If there's nothing found, the lookup info
    /// returned will be empty.
    Lookup      findItem(const UT_LimitedCacheKey &key);

    /// Add an item to the cache.  Due to concurrency, the lookup info returned
    /// may not contain the object added.  The item passed in may be deleted by
    /// this method and should not be used once passed in.
    /// @warning The item passed in may be deleted.  The value in the @c Lookup
    /// should be used.
    Lookup      addItem(const UT_LimitedCacheKey &key,
                                UT_LimitedCacheItem *item);

    /// Forcibly delete an item from the cache.  This will delete the item from
    /// the LRU cache and the table.
    void                deallocateItem(const UT_LimitedCacheKey &key);

    /// @{
    /// API defined on UT_Cache
    virtual const char  *utGetCacheName() const
                            { return myName; }
    virtual int64        utGetCurrentSize()
                            { return myLRUCache.getMemoryUsage(); }
    virtual bool         utHasMaxSize() const
                            { return true; }
    virtual int64        utGetMaxSize()
                            { return myLRUCache.getMaxMemoryBytes(); }
    virtual void         utSetMaxSize(int64 bytes)
                             { myLRUCache.setMaxMemoryBytes(bytes); }
    virtual int64        utReduceCacheSizeBy(int64 amount)
                         {
                            int64 used = myLRUCache.getMemoryUsage();
                            myLRUCache.pruneItems(used - amount);
                            return used - myLRUCache.getMemoryUsage();
                         }
    /// @}

    /// Debug and dump the cache -- this may not work properly in threaded code
    void                dumpCache() const;

protected:
    /// @{
    /// Needed for the concurrent map
    class ut_KeyCompare {
    public:
        static size_t   hash(const UT_LimitedCacheKey *a)
                            { return (size_t)a->getHash(); }
        static bool     equal(const UT_LimitedCacheKey *a,
                                const UT_LimitedCacheKey *b)
                            { return a->isEqual(*b); }
    };
    typedef UT_ConcurrentHashMap<UT_LimitedCacheKey *,
                                UT_LimitedCacheItem *,
                                ut_KeyCompare>  ut_StorageMap_t;
    class ut_StorageTable
        : public ut_StorageMap_t
    {
    public:
        static int64    getMemoryUsage() { return sizeof(ut_StorageTable); }
    };
    /// @}

public:
    /// @{
    /// Thread unsafe traversal of the cache contents
    ///   - it->first is a pointer to the UT_LimitedCacheKey
    ///   - it->second is a pointer to the UT_LimitedCacheItem
    typedef ut_StorageMap_t::const_iterator     unsafe_traverser;
    unsafe_traverser    unsafe_begin() const    { return myTable.begin(); }
    unsafe_traverser    unsafe_end() const      { return myTable.end(); }
    /// @}

private:
    void        setMRU(UT_LimitedCacheKey *key);
    void        referenceItem(UT_LimitedCacheKey *key);
    void        unreferenceItem(UT_LimitedCacheKey *key);
    void        destroyItem(const UT_LimitedCacheKey *key, bool del_from_lru);

    UT_LimitedLRUCache          myLRUCache;     // LRU Cache
    ut_StorageTable             myTable;        // Storage
    UT_String                   myName;

    friend class        Lookup;         // For reference/unreference
};

#endif

---