/*
* Copyright (c) 2005 Nokia Corporation and/or its subsidiary(-ies).
* All rights reserved.
* This component and the accompanying materials are made available
* under the terms of the License "Eclipse Public License v1.0"
* which accompanies this distribution, and is available
* at the URL "http://www.eclipse.org/legal/epl-v10.html".
*
* Initial Contributors:
* Nokia Corporation - initial contribution.
*
* Contributors:
*
* Description: Transformation cache implementation
*
*/


/*!
 * \internal
 * \file
 * \brief Transformation cache implementation
 */

#ifndef M3G_CORE_INCLUDE
#   error included by m3g_core.c; do not compile separately.
#endif

#include "m3g_tcache.h"

/* NOTE size MUST be a power of two! */
#define TCACHE_COMPOSITES 128
#define TCACHE_PATHS 128

/*----------------------------------------------------------------------
 * Data structures
 *--------------------------------------------------------------------*/

/*!
 * \internal
 * \brief Transformation path cache element
 */
typedef struct
{
    M3Gfloat elem[12];  /* NOTE the bottom row is always 0 0 0 1 */
    M3Guint mask;
    M3Guint classified  : 1;
    M3Guint complete    : 1;
    
    const Node *from, *to;
} TCachePath;

M3G_CT_ASSERT2(sizeof(TCachePath) == 64);

/*!
 * \internal
 * \brief Transformation cache data implementation
 */
struct TCacheImpl
{
    Interface *m3g;

    TCachePath paths[TCACHE_PATHS];
    Matrix composites[TCACHE_COMPOSITES];
    const Transformable *compositeObjs[TCACHE_COMPOSITES];
    
    M3Gbool pathsInvalid;
};

/*----------------------------------------------------------------------
 * Private functions
 *--------------------------------------------------------------------*/

static M3G_INLINE M3Gint m3gTransformableHash(const Transformable *t)
{
    M3Guint a = (M3Guint) t;
    M3Guint b = (M3Guint) t;
    
    a += (a >> 3) + (a >> 9) + (a >> 17);
    b  = (b >> 16) | (b << 16);
    b += (b >> 5) + (b >> 10) + (b >> 20);
    return (M3Gint)(a ^ b);
}

static M3Gint m3gPathHash(const Node *from, const Node *to)
{
    M3Guint a = (M3Guint) from;
    M3Guint b = (M3Guint) to;

    a += (a >> 3) + (a >> 9) + (a >> 17);
    b  = (b >> 16) | (b << 16);
    b += (b >> 5) + (b >> 10) + (b >> 20);
    return (M3Gint)(a ^ b);
}

static M3G_INLINE M3Gint m3gGetTransformableSlot(const TCache *tc, const Transformable *t)
{
    M3G_UNREF(tc);
    return m3gTransformableHash(t) & (TCACHE_COMPOSITES - 1);
}

static M3G_INLINE M3Gint m3gGetPathSlot(const TCache *tc, const Node *from, const Node *to)
{
    M3G_UNREF(tc);
    return m3gPathHash(from, to) & (TCACHE_PATHS - 1);
}
    
/*----------------------------------------------------------------------
 * Internal functions
 *--------------------------------------------------------------------*/

/*!
 * \internal
 * \brief
 */
static TCache* m3gCreateTransformCache(Interface *m3g)
{
    TCache *cache = m3gAllocZ(m3g, sizeof(TCache));
    if (cache) {
        cache->m3g = m3g;
        cache->pathsInvalid = M3G_TRUE;
    }
    return cache;
}

/*!
 * \internal
 * \brief
 */
static void m3gDeleteTransformCache(TCache *cache)
{
    if (cache) {
        m3gFree(cache->m3g, cache);
    }
}

/*!
 * \internal
 * \brief
 */
static void m3gCacheComposite(TCache *cache, const Transformable *t, const Matrix *m)
{
    M3Gint idx = m3gGetTransformableSlot(cache, t);

    /* If the matrix being added already exists in the cache, the
     * cache is being used sub-optimally */
    
    M3G_ASSERT(cache->compositeObjs[idx] != t);
    
    /* Just overwrite any existing entries, but keep track of
     * collisions for profiling */
    
    if (cache->compositeObjs[idx]) {
        m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_COLLISIONS, 1);
    }
    else {
        m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_LOAD, 1);
    }
    cache->composites[idx] = *m;
    cache->compositeObjs[idx] = t;
    
    m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_INSERTS, 1);
}

/*!
 * \internal
 * \brief
 */
static void m3gCachePath(TCache *cache, const Node *from, const Node *to, const Matrix *m)
{
    M3G_ASSERT(m3gIsWUnity(m));
    /* These two asserts are not errors in a strict sense, but imply
     * sub-optimal cache use */
    M3G_ASSERT(from || to);
    M3G_ASSERT(from != to);
    
    M3G_BEGIN_PROFILE(cache->m3g, M3G_PROFILE_TCACHE);
    
    /* If the cache has been invalidated, wipe it clean before
     * inserting anything */
    
    if (cache->pathsInvalid) {
        m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_FLUSHES, 1);
        m3gZero(cache->paths, TCACHE_PATHS * sizeof(cache->paths[0]));
        cache->pathsInvalid = M3G_FALSE;
    }

    /* Hash to the cache, then just overwrite anything previously
     * there */
    {
        M3Gint idx = m3gGetPathSlot(cache, from, to);
        TCachePath *c = &cache->paths[idx];

        /* If this assert is hit, the path being added already exists
         * in the cache; this is not an error per se, but implies
         * sub-optimal cache usage */
        M3G_ASSERT(c->from != from || c->to != to);
        
        /* Overwrite the matrix data */
        {
            const M3Gfloat *src = &m->elem[0];
            M3Gfloat *dst = &c->elem[0];
            int row, col;
            for (col = 0; col < 4; ++col) {
                for (row = 0; row < 3; ++row) {
                    *dst++ = *src++;
                }
                ++src;
            }
            c->mask = m->mask;
            c->classified = m->classified;
            c->complete = m->complete;
        }

        /* Register collisions for bookkeeping */

        if (c->from || c->to) {
            m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_COLLISIONS, 1);
        }
        else {
            m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_LOAD, 1);
        }
        
        c->from = from;
        c->to = to;
    }
    M3G_END_PROFILE(cache->m3g, M3G_PROFILE_TCACHE);
    
    m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_INSERTS, 1);
}

/*!
 * \internal
 * \brief
 */
static M3Gbool m3gGetCachedComposite(const TCache *cache, const Transformable *t, Matrix *m)
{
    M3Gint idx = m3gGetTransformableSlot(cache, t);
    if (cache->compositeObjs[idx] == t) {
        *m = cache->composites[idx];
        m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_HITS, 1);
        return M3G_TRUE;
    }
    m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_MISSES, 1);
    return M3G_FALSE;
}

/*!
 * \internal
 * \brief
 */
static M3Gbool m3gGetCachedPath(const TCache *cache, const Node *from, const Node *to, Matrix *m)
{
    M3G_BEGIN_PROFILE(cache->m3g, M3G_PROFILE_TCACHE);
    
    if (!cache->pathsInvalid) {

        /* Hash to the respective cache slot */
        
        M3Gint idx = m3gGetPathSlot(cache, from, to);
        const TCachePath *c = &cache->paths[idx];

        /* If it matches, copy to the output matrix */
        
        if (c->from == from && c->to == to) {
            const M3Gfloat *src = &c->elem[0];
            M3Gfloat *dst = &m->elem[0];
            int col;
            for (col = 0; col < 4; ++col) {
                *dst++ = *src++;
                *dst++ = *src++;
                *dst++ = *src++;
                *dst++ = 0.0f;
            }
            m->elem[15] = 1.0f;
            m->mask = c->mask;
            m->classified = c->classified;
            m->complete = c->complete;

            M3G_END_PROFILE(cache->m3g, M3G_PROFILE_TCACHE);
    
            m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_HITS, 1);
            return M3G_TRUE;
        }
    }
    M3G_END_PROFILE(cache->m3g, M3G_PROFILE_TCACHE);
    
    m3gIncStat(cache->m3g, M3G_STAT_TCACHE_PATH_MISSES, 1);
    return M3G_FALSE;
}

/*!
 * \internal
 * \brief
 */
static void m3gInvalidateCachedPaths(TCache *cache, const Node *n)
{
    M3G_UNREF(n);
    m3gResetStat(cache->m3g, M3G_STAT_TCACHE_PATH_LOAD);
    cache->pathsInvalid = M3G_TRUE;
}

/*!
 * \internal
 * \brief
 */
static void m3gInvalidateCachedTransforms(TCache *cache, const Transformable *t)
{
    /* Look for a composite entry and wipe if found */
    {
        M3Gint idx = m3gGetTransformableSlot(cache, t);
        if (cache->compositeObjs[idx] == t) {
            cache->compositeObjs[idx] = NULL;
            m3gIncStat(cache->m3g, M3G_STAT_TCACHE_COMPOSITE_LOAD, -1);
        }
    }
    
    /* NOTE We just cast the pointer to a Node below -- it's only used
     * for hashing, and every object will still be unique regardless
     * of the class */
    
    m3gInvalidateCachedPaths(cache, (const Node*) t);
}