1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/graphite2/src/SegCache.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,224 @@
1.4 +/* GRAPHITE2 LICENSING
1.5 +
1.6 + Copyright 2010, SIL International
1.7 + All rights reserved.
1.8 +
1.9 + This library is free software; you can redistribute it and/or modify
1.10 + it under the terms of the GNU Lesser General Public License as published
1.11 + by the Free Software Foundation; either version 2.1 of License, or
1.12 + (at your option) any later version.
1.13 +
1.14 + This program is distributed in the hope that it will be useful,
1.15 + but WITHOUT ANY WARRANTY; without even the implied warranty of
1.16 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1.17 + Lesser General Public License for more details.
1.18 +
1.19 + You should also have received a copy of the GNU Lesser General Public
1.20 + License along with this library in the file named "LICENSE".
1.21 + If not, write to the Free Software Foundation, 51 Franklin Street,
1.22 + Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
1.23 + internet at http://www.fsf.org/licenses/lgpl.html.
1.24 +
1.25 +Alternatively, the contents of this file may be used under the terms of the
1.26 +Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
1.27 +License, as published by the Free Software Foundation, either version 2
1.28 +of the License or (at your option) any later version.
1.29 +*/
1.30 +
1.31 +#include "inc/Main.h"
1.32 +#include "inc/TtfTypes.h"
1.33 +#include "inc/TtfUtil.h"
1.34 +#include "inc/SegCache.h"
1.35 +#include "inc/SegCacheEntry.h"
1.36 +#include "inc/SegCacheStore.h"
1.37 +#include "inc/CmapCache.h"
1.38 +
1.39 +
1.40 +using namespace graphite2;
1.41 +
1.42 +#ifndef GRAPHITE2_NSEGCACHE
1.43 +
1.44 +SegCache::SegCache(const SegCacheStore * store, const Features & feats)
1.45 +: m_prefixLength(ePrefixLength),
1.46 + m_maxCachedSegLength(eMaxSpliceSize),
1.47 + m_segmentCount(0),
1.48 + m_features(feats),
1.49 + m_totalAccessCount(0l), m_totalMisses(0l),
1.50 + m_purgeFactor(1.0f / (ePurgeFactor * store->maxSegmentCount()))
1.51 +{
1.52 + m_prefixes.raw = grzeroalloc<void*>(store->maxCmapGid() + 2);
1.53 + m_prefixes.range[SEG_CACHE_MIN_INDEX] = SEG_CACHE_UNSET_INDEX;
1.54 + m_prefixes.range[SEG_CACHE_MAX_INDEX] = SEG_CACHE_UNSET_INDEX;
1.55 +}
1.56 +
1.57 +void SegCache::freeLevel(SegCacheStore * store, SegCachePrefixArray prefixes, size_t level)
1.58 +{
1.59 + for (size_t i = 0; i < store->maxCmapGid(); i++)
1.60 + {
1.61 + if (prefixes.array[i].raw)
1.62 + {
1.63 + if (level + 1 < ePrefixLength)
1.64 + freeLevel(store, prefixes.array[i], level + 1);
1.65 + else
1.66 + {
1.67 + SegCachePrefixEntry * prefixEntry = prefixes.prefixEntries[i];
1.68 + delete prefixEntry;
1.69 + }
1.70 + }
1.71 + }
1.72 + free(prefixes.raw);
1.73 +}
1.74 +
1.75 +void SegCache::clear(SegCacheStore * store)
1.76 +{
1.77 + freeLevel(store, m_prefixes, 0);
1.78 + m_prefixes.raw = NULL;
1.79 +}
1.80 +
1.81 +SegCache::~SegCache()
1.82 +{
1.83 + assert(m_prefixes.raw == NULL);
1.84 +}
1.85 +
1.86 +SegCacheEntry* SegCache::cache(SegCacheStore * store, const uint16* cmapGlyphs, size_t length, Segment * seg, size_t charOffset)
1.87 +{
1.88 + uint16 pos = 0;
1.89 + if (!length) return NULL;
1.90 + assert(length < m_maxCachedSegLength);
1.91 + SegCachePrefixArray pArray = m_prefixes;
1.92 + while (pos + 1 < m_prefixLength)
1.93 + {
1.94 + uint16 gid = (pos < length)? cmapGlyphs[pos] : 0;
1.95 + if (!pArray.array[gid].raw)
1.96 + {
1.97 + pArray.array[gid].raw = grzeroalloc<void*>(store->maxCmapGid() + 2);
1.98 + if (!pArray.array[gid].raw)
1.99 + return NULL; // malloc failed
1.100 + if (pArray.range[SEG_CACHE_MIN_INDEX] == SEG_CACHE_UNSET_INDEX)
1.101 + {
1.102 + pArray.range[SEG_CACHE_MIN_INDEX] = gid;
1.103 + pArray.range[SEG_CACHE_MAX_INDEX] = gid;
1.104 + }
1.105 + else
1.106 + {
1.107 + if (gid < pArray.range[SEG_CACHE_MIN_INDEX])
1.108 + pArray.range[SEG_CACHE_MIN_INDEX] = gid;
1.109 + else if (gid > pArray.range[SEG_CACHE_MAX_INDEX])
1.110 + pArray.range[SEG_CACHE_MAX_INDEX] = gid;
1.111 + }
1.112 + }
1.113 + pArray = pArray.array[gid];
1.114 + ++pos;
1.115 + }
1.116 + uint16 gid = (pos < length)? cmapGlyphs[pos] : 0;
1.117 + SegCachePrefixEntry * prefixEntry = pArray.prefixEntries[gid];
1.118 + if (!prefixEntry)
1.119 + {
1.120 + prefixEntry = new SegCachePrefixEntry();
1.121 + pArray.prefixEntries[gid] = prefixEntry;
1.122 + if (pArray.range[SEG_CACHE_MIN_INDEX] == SEG_CACHE_UNSET_INDEX)
1.123 + {
1.124 + pArray.range[SEG_CACHE_MIN_INDEX] = gid;
1.125 + pArray.range[SEG_CACHE_MAX_INDEX] = gid;
1.126 + }
1.127 + else
1.128 + {
1.129 + if (gid < pArray.range[SEG_CACHE_MIN_INDEX])
1.130 + pArray.range[SEG_CACHE_MIN_INDEX] = gid;
1.131 + else if (gid > pArray.range[SEG_CACHE_MAX_INDEX])
1.132 + pArray.range[SEG_CACHE_MAX_INDEX] = gid;
1.133 + }
1.134 + }
1.135 + if (!prefixEntry) return NULL;
1.136 + // if the cache is full run a purge - this is slow, since it walks the tree
1.137 + if (m_segmentCount + 1 > store->maxSegmentCount())
1.138 + {
1.139 + purge(store);
1.140 + assert(m_segmentCount < store->maxSegmentCount());
1.141 + }
1.142 + SegCacheEntry * pEntry = prefixEntry->cache(cmapGlyphs, length, seg, charOffset, m_totalAccessCount);
1.143 + if (pEntry) ++m_segmentCount;
1.144 + return pEntry;
1.145 +}
1.146 +
1.147 +void SegCache::purge(SegCacheStore * store)
1.148 +{
1.149 + unsigned long long minAccessCount = static_cast<unsigned long long>(m_totalAccessCount * m_purgeFactor + 1);
1.150 + if (minAccessCount < 2) minAccessCount = 2;
1.151 + unsigned long long oldAccessTime = m_totalAccessCount - store->maxSegmentCount() / eAgeFactor;
1.152 + purgeLevel(store, m_prefixes, 0, minAccessCount, oldAccessTime);
1.153 +}
1.154 +
1.155 +void SegCache::purgeLevel(SegCacheStore * store, SegCachePrefixArray prefixes, size_t level,
1.156 + unsigned long long minAccessCount, unsigned long long oldAccessTime)
1.157 +{
1.158 + if (prefixes.range[SEG_CACHE_MIN_INDEX] == SEG_CACHE_UNSET_INDEX) return;
1.159 + size_t maxGlyphCached = prefixes.range[SEG_CACHE_MAX_INDEX];
1.160 + for (size_t i = prefixes.range[SEG_CACHE_MIN_INDEX]; i <= maxGlyphCached; i++)
1.161 + {
1.162 + if (prefixes.array[i].raw)
1.163 + {
1.164 + if (level + 1 < ePrefixLength)
1.165 + purgeLevel(store, prefixes.array[i], level + 1, minAccessCount, oldAccessTime);
1.166 + else
1.167 + {
1.168 + SegCachePrefixEntry * prefixEntry = prefixes.prefixEntries[i];
1.169 + m_segmentCount -= prefixEntry->purge(minAccessCount,
1.170 + oldAccessTime, m_totalAccessCount);
1.171 + }
1.172 + }
1.173 + }
1.174 +}
1.175 +
1.176 +uint32 SegCachePrefixEntry::purge(unsigned long long minAccessCount,
1.177 + unsigned long long oldAccessTime,
1.178 + unsigned long long currentTime)
1.179 +{
1.180 + // ignore the purge request if another has been done recently
1.181 + //if (m_lastPurge > oldAccessTime)
1.182 + // return 0;
1.183 +
1.184 + uint32 totalPurged = 0;
1.185 + // real length is length + 1 in this loop
1.186 + for (uint16 length = 0; length < eMaxSpliceSize; length++)
1.187 + {
1.188 + if (m_entryCounts[length] == 0)
1.189 + continue;
1.190 + uint16 purgeCount = 0;
1.191 + uint16 newIndex = 0;
1.192 + for (uint16 j = 0; j < m_entryCounts[length]; j++)
1.193 + {
1.194 + SegCacheEntry & tempEntry = m_entries[length][j];
1.195 + // purge entries with a low access count which haven't been
1.196 + // accessed recently
1.197 + if (tempEntry.accessCount() <= minAccessCount &&
1.198 + tempEntry.lastAccess() <= oldAccessTime)
1.199 + {
1.200 + tempEntry.clear();
1.201 + ++purgeCount;
1.202 + }
1.203 + else
1.204 + {
1.205 + memcpy(m_entries[length] + newIndex++, m_entries[length] + j, sizeof(SegCacheEntry));
1.206 + }
1.207 + }
1.208 + if (purgeCount == m_entryCounts[length])
1.209 + {
1.210 + assert(newIndex == 0);
1.211 + m_entryCounts[length] = 0;
1.212 + m_entryBSIndex[length] = 0;
1.213 + free(m_entries[length]);
1.214 + m_entries[length] = NULL;
1.215 + }
1.216 + else if (purgeCount > 0)
1.217 + {
1.218 + assert(m_entryCounts[length] == newIndex + purgeCount);
1.219 + m_entryCounts[length] = newIndex;
1.220 + }
1.221 + totalPurged += purgeCount;
1.222 + }
1.223 + m_lastPurge = currentTime;
1.224 + return totalPurged;
1.225 +}
1.226 +
1.227 +#endif
