All computer source code presented on this page, unless it includes attribution to another author, is provided by Ed Halley under the Artistic License. Use such code freely and without any expectation of support. I would like to know if you make anything cool with the code, or need questions answered.
python/
    bindings.py
    boards.py
    buzz.py
    caches.py
    cards.py
    constraints.py
    csql.py
    english.py
    getch.py
    getopts.py
    gizmos.py
    goals.py
    improv.py
    interpolations.py
    namespaces.py
    nihongo.py
    nodes.py
    octalplus.py
    patterns.py
    physics.py
    pids.py
    pieces.py
    quizzes.py
    recipes.py
    relays.py
    romaji.py
    ropen.py
    sheets.py
    stores.py
    strokes.py
    subscriptions.py
    svgbuild.py
    testing.py
    things.py
    timing.py
    ucsv.py
    useful.py
    uuid.py
    vectors.py
    weighted.py
java/
    CSVReader.java
    CSVWriter.java
    GlobFilenameFilter.java
    RegexFilenameFilter.java
    StringBufferOutputStream.java
    ThreadSet.java
    Throttle.java
    TracingThread.java
    Utf8ConsoleTest.java
    droid/
        ArrangeViewsTouchListener.java
        DownloadFileTask.java
perl/
    CVQM.pm
    Kana.pm
    Typo.pm
cxx/
    CCache.h
    equalish.cpp
Download CCache.h

// CCache<>: MFC style C++ template class
//
// A template class implementing a generic cache.  Any key type, any value
// type.  Give the key and it retrieves the known value, or uses a fetch
// callback to generate the value.  When over-capacity, it can throw out
// some known values.
//
// Part of Ed Halley's EdhLib MFC extension library.

template <class KEY, class VALUE>
class CCache : public CObject
{
protected:
        struct CCD
        {
                VALUE m_value;
                int m_nUsage;
                int m_nTouch;
        };
public:
        CCache(int nBlockSize = 10, int nHashPrime = 17);

// Attributes
protected:
        CMap<KEY,KEY&,CCD*,CCD*&> m_d;
        BOOL m_bCommitOnFlush;
        int m_nOptimal;
        int m_nTouch;
public:
        int GetCount() const { return m_d.GetCount(); }
        BOOL IsEmpty() const { return m_d.IsEmpty(); }
        //
        POSITION GetStartPosition() const;
        KEY GetNext(POSITION& pos) const;
        //
        int GetOptimalCount() const { return m_nOptimal; }
        void SetOptimalCount(int nElements)
                {       ASSERT(nElements >= 0);
                        m_nOptimal = nElements;
                }
        //
        BOOL IsAutoCommit() const { return m_bCommitOnFlush; }
        void SetAutoCommit(BOOL bAuto)
                {       m_bCommitOnFlush = bAuto;
                }

// Operations
public:
        BOOL IsCached(KEY& key) const;

        BOOL Fetch(KEY& key, VALUE& rValue);
        BOOL Unfetch(KEY& key, BOOL bCommit = (int)-1);
        BOOL Commit(KEY& key);
        BOOL CommitAll();
        BOOL Flush(KEY& key, BOOL bCommit = (int)-1);
        BOOL FlushAll(BOOL bKeepOptimal = FALSE);

// Overridables
public:
        virtual void OnTry(KEY& key);
        virtual void OnHit(KEY& key);
        virtual void OnMiss(KEY& key);

        virtual BOOL OnFetch(KEY& key, VALUE& rValue);
        virtual BOOL OnFlush(KEY& key, VALUE& rValue);
        virtual BOOL OnCommit(KEY& key, VALUE& rValue);

// Implementation
public:
        virtual ~CCache();
protected:
        CCD* _FindData(KEY& key) const;
};

template<class KEY, class VALUE>
CCache<KEY, VALUE>::CCache(int nBlockSize /* = 10 */,
                           int nHashPrime /* = 17 */)
        : m_d(nBlockSize)
{
        m_d.InitHashTable(nHashPrime);
        m_bCommitOnFlush = FALSE;
        m_nOptimal = 0;
        m_nTouch = 0;
}

template<class KEY, class VALUE>
CCache<KEY, VALUE>::~CCache()
{
        FlushAll();
        ASSERT(0 == m_d.GetCount());
}

template<class KEY, class VALUE>
CCache<KEY, VALUE>::CCD* CCache<KEY, VALUE>::_FindData(KEY& key) const
{
        CCD* pData = NULL;
        if (!m_d.Lookup(key, pData))
                return NULL;

        ASSERT(pData);
        return pData;
}

template<class KEY, class VALUE>
POSITION CCache<KEY, VALUE>::GetStartPosition() const
{
        return m_d.GetStartPosition();
}

template<class KEY, class VALUE>
KEY CCache<KEY, VALUE>::GetNext(POSITION& pos) const
{
        KEY key;
        CCD* data;
        m_d.GetNextAssoc(pos, key, data);
        return key;
}

template<class KEY, class VALUE>
BOOL CCache<KEY, VALUE>::IsCached(KEY& key) const
{
        return TRUE && _FindData(key);
}

template<class KEY, class VALUE>
BOOL CCache<KEY, VALUE>::Fetch(KEY& key, VALUE& value)
{
        CCD* pData = NULL;

        // If not in the cache, try to create the data.
        // If that fails, out of luck.
        //
        OnTry(key);
        if (m_d.Lookup(key, pData))
        {
                OnHit(key);
        }
        else
        {
                // Quietly flush some entries if possible to get back
                // below optimal size.
                //
                if (m_nOptimal > 0)
                        FlushAll(TRUE);

                pData = new CCD;
                memset(pData, 0, sizeof(CCD));
                if (!OnFetch(key, pData->m_value))
                {
                        delete pData;
                        return FALSE;
                }
                m_d.SetAt(key, pData);
                OnMiss(key);
        }

        // Now we know the data.
        // Increase its usage.
        // Touch this data.
        //
        ASSERT(pData);
        value = pData->m_value;
        pData->m_nUsage++;
        pData->m_nTouch = m_nTouch++;
        return TRUE;
}

template<class KEY, class VALUE>
BOOL CCache<KEY, VALUE>::Unfetch(KEY& key, BOOL bCommit /* = (int)-1 */)
{
        // If not in the cache, it's a warning.
        //
        CCD* pData = _FindData(key);
        if (!pData)
        {
                TRACE("CCache: unfetch of non-present key\n");
                return FALSE;
        }

        // If already zero usage, it's an error.
        //
        if (0 >= pData->m_nUsage)
        {
                TRACE("CCache: too many unfetches of key\n");
                ASSERT(0);
                return FALSE;
        }

        // Now we know the data.
        // Drop its usage.
        // Touch this data.
        //
        pData->m_nUsage--;
        pData->m_nTouch = m_nTouch++;

        // If it drops to zero, it may be flushed if we're crowded.
        //
        if (pData->m_nUsage <= 0 &&
            0 < m_nOptimal && m_nOptimal < m_d.GetCount())
        {
                Flush(key, bCommit);
        }

        return TRUE;
}

template<class KEY, class VALUE>
BOOL CCache<KEY, VALUE>::Commit(KEY& rKey)
{
        // If it's not in the cache, there's nothing to do.
        CCD* pData = _FindData(key);
        if (!pData)
                return FALSE;

        // Now we know the data.
        // Touch this data.
        //
        pData->m_nUsage--;
        pData->m_nTouch = m_nTouch++;

        // Call the helper to commit this data.
        //
        OnCommit(rKey, pData->m_value);

        return TRUE;
}

template<class KEY, class VALUE>
BOOL CCache<KEY, VALUE>::CommitAll()
{
        POSITION pos = m_d.GetStartPosition();
        while (pos)
        {
                KEY key;
                CCD* pData = NULL;
                m_d.GetNextAssoc(pos, key, pData);
                ASSERT(pData);
                if (!pData)
                        continue;
                OnCommit(key, pData->m_value);
        }
}

template<class KEY, class VALUE>
BOOL CCache<KEY, VALUE>::Flush(KEY& key, BOOL bCommit /* = (int)-1 */)
{
        // If not in the cache, there's nothing to do.
        // Sometimes an unfetch tries to flush, so a subsequent flush is okay.
        CCD* pData = _FindData(key);
        if (!pData)
                return FALSE;

        // If not at zero usage, it's an error.
        //
        if (0 < pData->m_nUsage)
        {
                ASSERT(0);
                TRACE("CCache: trying to flush key in use; unfetch first\n");
                return FALSE;
        }

        // Now we know the data.
        // Trigger the OnCommit() if required.
        // Trigger the OnFlush().
        // Destroy it.
        //
        if (bCommit == (int)-1)
                bCommit = IsAutoCommit();
        if (bCommit)
                OnCommit(key, pData->m_value);
        OnFlush(key, pData->m_value);
        m_d.RemoveKey(key);
        delete pData;
        return TRUE;
}

template<class KEY, class VALUE>
BOOL CCache<KEY, VALUE>::FlushAll(BOOL bKeepOptimal /* = FALSE */)
{
        int nOptimal = m_nOptimal;
        if (!bKeepOptimal)
                nOptimal = 0;

        // Loop until we've gotten back down to optimal or empty.
        //
        int nDeleted = 0;
        while (nOptimal < GetCount())
        {
                // Loop through every element in the cache.
                KEY keyOldest;
                CCD* pOldestData = NULL;
                int nOldestTouch = m_nTouch;
                POSITION pos = m_d.GetStartPosition();
                while (pos)
                {
                        KEY key;
                        CCD* pData = NULL;
                        m_d.GetNextAssoc(pos, key, pData);
                        ASSERT(pData);
                        if (!pData)
                                continue;
                        if (pData->m_nUsage <= 0 &&
                            nOldestTouch > pData->m_nTouch)
                        {
                                // Keep the best candidate so far.
                                keyOldest = key;
                                pOldestData = pData;
                                nOldestTouch = pData->m_nTouch;

                                // Shortcut the rest of the search
                                // if we're flushing every candidate.
                                if (!bKeepOptimal)
                                        break;
                        }
                }

                if (pOldestData)
                {
                        // Found a candidate to flush.
                        // Commit and free it from the cache.
                        //
                        if (m_bCommitOnFlush)
                                OnCommit(keyOldest, pOldestData->m_value);
                        OnFlush(keyOldest, pOldestData->m_value);
                        m_d.RemoveKey(keyOldest);
                        delete pOldestData;
                        nDeleted++;
                }
                else
                {
                        // Found no candidates to flush;
                        // we're forced to keep any remaining keys.
                        //
                        break;
                }
        }

        return (0 != nDeleted);
}

template<class KEY, class VALUE>
void CCache<KEY, VALUE>::OnTry(KEY& key)
{
}

template<class KEY, class VALUE>
void CCache<KEY, VALUE>::OnHit(KEY& key)
{
}

template<class KEY, class VALUE>
void CCache<KEY, VALUE>::OnMiss(KEY& key)
{
}

template<class KEY, class VALUE>
BOOL CCache<KEY, VALUE>::OnFetch(KEY& key, VALUE& value)
{
        return FALSE;
}

template<class KEY, class VALUE>
BOOL CCache<KEY, VALUE>::OnFlush(KEY& key, VALUE& value)
{
        return FALSE;
}

template<class KEY, class VALUE>
BOOL CCache<KEY, VALUE>::OnCommit(KEY& key, VALUE& value)
{
        return FALSE;
}


Contact Ed Halley by email at ed@halley.cc.
Text, code, layout and artwork are Copyright © 1996-2013 Ed Halley.
Copying in whole or in part, with author attribution, is expressly allowed.
Any references to trademarks are illustrative and are controlled by their respective owners.
Make donations with PayPal - it's fast, free and secure!