michael@0: /*  GRAPHITE2 LICENSING
michael@0: 
michael@0:     Copyright 2010, SIL International
michael@0:     All rights reserved.
michael@0: 
michael@0:     This library is free software; you can redistribute it and/or modify
michael@0:     it under the terms of the GNU Lesser General Public License as published
michael@0:     by the Free Software Foundation; either version 2.1 of License, or
michael@0:     (at your option) any later version.
michael@0: 
michael@0:     This program is distributed in the hope that it will be useful,
michael@0:     but WITHOUT ANY WARRANTY; without even the implied warranty of
michael@0:     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
michael@0:     Lesser General Public License for more details.
michael@0: 
michael@0:     You should also have received a copy of the GNU Lesser General Public
michael@0:     License along with this library in the file named "LICENSE".
michael@0:     If not, write to the Free Software Foundation, 51 Franklin Street,
michael@0:     Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
michael@0:     internet at http://www.fsf.org/licenses/lgpl.html.
michael@0: 
michael@0: Alternatively, the contents of this file may be used under the terms of the
michael@0: Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
michael@0: License, as published by the Free Software Foundation, either version 2
michael@0: of the License or (at your option) any later version.
michael@0: */
michael@0: 
michael@0: #include "inc/Main.h"
michael@0: #include "inc/TtfTypes.h"
michael@0: #include "inc/TtfUtil.h"
michael@0: #include "inc/SegCache.h"
michael@0: #include "inc/SegCacheEntry.h"
michael@0: #include "inc/SegCacheStore.h"
michael@0: #include "inc/CmapCache.h"
michael@0: 
michael@0: 
michael@0: using namespace graphite2;
michael@0: 
michael@0: #ifndef GRAPHITE2_NSEGCACHE
michael@0: 
michael@0: SegCache::SegCache(const SegCacheStore * store, const Features & feats)
michael@0: : m_prefixLength(ePrefixLength),
michael@0:   m_maxCachedSegLength(eMaxSpliceSize),
michael@0:   m_segmentCount(0),
michael@0:   m_features(feats),
michael@0:   m_totalAccessCount(0l), m_totalMisses(0l),
michael@0:   m_purgeFactor(1.0f / (ePurgeFactor * store->maxSegmentCount()))
michael@0: {
michael@0:     m_prefixes.raw = grzeroalloc<void*>(store->maxCmapGid() + 2);
michael@0:     m_prefixes.range[SEG_CACHE_MIN_INDEX] = SEG_CACHE_UNSET_INDEX;
michael@0:     m_prefixes.range[SEG_CACHE_MAX_INDEX] = SEG_CACHE_UNSET_INDEX;
michael@0: }
michael@0: 
michael@0: void SegCache::freeLevel(SegCacheStore * store, SegCachePrefixArray prefixes, size_t level)
michael@0: {
michael@0:     for (size_t i = 0; i < store->maxCmapGid(); i++)
michael@0:     {
michael@0:         if (prefixes.array[i].raw)
michael@0:         {
michael@0:             if (level + 1 < ePrefixLength)
michael@0:                 freeLevel(store, prefixes.array[i], level + 1);
michael@0:             else
michael@0:             {
michael@0:                 SegCachePrefixEntry * prefixEntry = prefixes.prefixEntries[i];
michael@0:                 delete prefixEntry;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     free(prefixes.raw);
michael@0: }
michael@0: 
michael@0: void SegCache::clear(SegCacheStore * store)
michael@0: {
michael@0:     freeLevel(store, m_prefixes, 0);
michael@0:     m_prefixes.raw = NULL;
michael@0: }
michael@0: 
michael@0: SegCache::~SegCache()
michael@0: {
michael@0:     assert(m_prefixes.raw == NULL);
michael@0: }
michael@0: 
michael@0: SegCacheEntry* SegCache::cache(SegCacheStore * store, const uint16* cmapGlyphs, size_t length, Segment * seg, size_t charOffset)
michael@0: {
michael@0:     uint16 pos = 0;
michael@0:     if (!length) return NULL;
michael@0:     assert(length < m_maxCachedSegLength);
michael@0:     SegCachePrefixArray pArray = m_prefixes;
michael@0:     while (pos + 1 < m_prefixLength)
michael@0:     {
michael@0:         uint16 gid = (pos < length)? cmapGlyphs[pos] : 0;
michael@0:         if (!pArray.array[gid].raw)
michael@0:         {
michael@0:             pArray.array[gid].raw = grzeroalloc<void*>(store->maxCmapGid() + 2);
michael@0:             if (!pArray.array[gid].raw)
michael@0:                 return NULL; // malloc failed
michael@0:             if (pArray.range[SEG_CACHE_MIN_INDEX] == SEG_CACHE_UNSET_INDEX)
michael@0:             {
michael@0:                 pArray.range[SEG_CACHE_MIN_INDEX] = gid;
michael@0:                 pArray.range[SEG_CACHE_MAX_INDEX] = gid;
michael@0:             }
michael@0:             else
michael@0:             {
michael@0:                 if (gid < pArray.range[SEG_CACHE_MIN_INDEX])
michael@0:                     pArray.range[SEG_CACHE_MIN_INDEX] = gid;
michael@0:                 else if (gid > pArray.range[SEG_CACHE_MAX_INDEX])
michael@0:                     pArray.range[SEG_CACHE_MAX_INDEX] = gid;
michael@0:             }
michael@0:         }
michael@0:         pArray = pArray.array[gid];
michael@0:         ++pos;
michael@0:     }
michael@0:     uint16 gid = (pos < length)? cmapGlyphs[pos] : 0;
michael@0:     SegCachePrefixEntry * prefixEntry = pArray.prefixEntries[gid];
michael@0:     if (!prefixEntry)
michael@0:     {
michael@0:         prefixEntry = new SegCachePrefixEntry();
michael@0:         pArray.prefixEntries[gid] = prefixEntry;
michael@0:         if (pArray.range[SEG_CACHE_MIN_INDEX] == SEG_CACHE_UNSET_INDEX)
michael@0:         {
michael@0:             pArray.range[SEG_CACHE_MIN_INDEX] = gid;
michael@0:             pArray.range[SEG_CACHE_MAX_INDEX] = gid;
michael@0:         }
michael@0:         else
michael@0:         {
michael@0:             if (gid < pArray.range[SEG_CACHE_MIN_INDEX])
michael@0:                 pArray.range[SEG_CACHE_MIN_INDEX] = gid;
michael@0:             else if (gid > pArray.range[SEG_CACHE_MAX_INDEX])
michael@0:                 pArray.range[SEG_CACHE_MAX_INDEX] = gid;
michael@0:         }
michael@0:     }
michael@0:     if (!prefixEntry) return NULL;
michael@0:     // if the cache is full run a purge - this is slow, since it walks the tree
michael@0:     if (m_segmentCount + 1 > store->maxSegmentCount())
michael@0:     {
michael@0:         purge(store);
michael@0:         assert(m_segmentCount < store->maxSegmentCount());
michael@0:     }
michael@0:     SegCacheEntry * pEntry = prefixEntry->cache(cmapGlyphs, length, seg, charOffset, m_totalAccessCount);
michael@0:     if (pEntry) ++m_segmentCount;
michael@0:     return pEntry;
michael@0: }
michael@0: 
michael@0: void SegCache::purge(SegCacheStore * store)
michael@0: {
michael@0:     unsigned long long minAccessCount = static_cast<unsigned long long>(m_totalAccessCount * m_purgeFactor + 1);
michael@0:     if (minAccessCount < 2) minAccessCount = 2;
michael@0:     unsigned long long oldAccessTime = m_totalAccessCount - store->maxSegmentCount() / eAgeFactor;
michael@0:     purgeLevel(store, m_prefixes, 0, minAccessCount, oldAccessTime);
michael@0: }
michael@0: 
michael@0: void SegCache::purgeLevel(SegCacheStore * store, SegCachePrefixArray prefixes, size_t level,
michael@0:                           unsigned long long minAccessCount, unsigned long long oldAccessTime)
michael@0: {
michael@0:     if (prefixes.range[SEG_CACHE_MIN_INDEX] == SEG_CACHE_UNSET_INDEX) return;
michael@0:     size_t maxGlyphCached = prefixes.range[SEG_CACHE_MAX_INDEX];
michael@0:     for (size_t i = prefixes.range[SEG_CACHE_MIN_INDEX]; i <= maxGlyphCached; i++)
michael@0:     {
michael@0:         if (prefixes.array[i].raw)
michael@0:         {
michael@0:             if (level + 1 < ePrefixLength)
michael@0:                 purgeLevel(store, prefixes.array[i], level + 1, minAccessCount, oldAccessTime);
michael@0:             else
michael@0:             {
michael@0:                 SegCachePrefixEntry * prefixEntry = prefixes.prefixEntries[i];
michael@0:                 m_segmentCount -= prefixEntry->purge(minAccessCount,
michael@0:                     oldAccessTime, m_totalAccessCount);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: uint32 SegCachePrefixEntry::purge(unsigned long long minAccessCount,
michael@0:                                               unsigned long long oldAccessTime,
michael@0:                                               unsigned long long currentTime)
michael@0: {
michael@0:     // ignore the purge request if another has been done recently
michael@0:     //if (m_lastPurge > oldAccessTime)
michael@0:     //    return 0;
michael@0: 
michael@0:     uint32 totalPurged = 0;
michael@0:     // real length is length + 1 in this loop
michael@0:     for (uint16 length = 0; length < eMaxSpliceSize; length++)
michael@0:     {
michael@0:         if (m_entryCounts[length] == 0)
michael@0:             continue;
michael@0:         uint16 purgeCount = 0;
michael@0:         uint16 newIndex = 0;
michael@0:         for (uint16 j = 0; j < m_entryCounts[length]; j++)
michael@0:         {
michael@0:             SegCacheEntry & tempEntry = m_entries[length][j];
michael@0:             // purge entries with a low access count which haven't been
michael@0:             // accessed recently
michael@0:             if (tempEntry.accessCount() <= minAccessCount &&
michael@0:                 tempEntry.lastAccess() <= oldAccessTime)
michael@0:             {
michael@0:                 tempEntry.clear();
michael@0:                 ++purgeCount;
michael@0:             }
michael@0:             else
michael@0:             {
michael@0:                 memcpy(m_entries[length] + newIndex++, m_entries[length] + j, sizeof(SegCacheEntry));
michael@0:             }
michael@0:         }
michael@0:         if (purgeCount == m_entryCounts[length])
michael@0:         {
michael@0:             assert(newIndex == 0);
michael@0:             m_entryCounts[length] = 0;
michael@0:             m_entryBSIndex[length] = 0;
michael@0:             free(m_entries[length]);
michael@0:             m_entries[length] = NULL;
michael@0:         }
michael@0:         else if (purgeCount > 0)
michael@0:         {
michael@0:             assert(m_entryCounts[length] == newIndex + purgeCount);
michael@0:             m_entryCounts[length] = newIndex;
michael@0:         }
michael@0:         totalPurged += purgeCount;
michael@0:     }
michael@0:     m_lastPurge = currentTime;
michael@0:     return totalPurged;
michael@0: }
michael@0: 
michael@0: #endif