third_party/WebKit/Source/platform/fonts/shaping/ShapeCache.h - chromium/src - Git at Google

 /*
  * Copyright (C) 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2015 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */

 #ifndef ShapeCache_h
 #define ShapeCache_h

 #include "platform/fonts/shaping/ShapeResult.h"
 #include "platform/text/TextRun.h"
 #include "wtf/Forward.h"
 #include "wtf/HashFunctions.h"
 #include "wtf/HashSet.h"
 #include "wtf/HashTableDeletedValueType.h"
 #include "wtf/StringHasher.h"
 #include "wtf/WeakPtr.h"

 namespace blink {

 class Font;
 class GlyphBuffer;
 class SimpleFontData;

 struct ShapeCacheEntry {
   DISALLOW_NEW_EXCEPT_PLACEMENT_NEW();
   ShapeCacheEntry() { m_shapeResult = nullptr; }
   RefPtr<const ShapeResult> m_shapeResult;
 };

 class ShapeCache {
   USING_FAST_MALLOC(ShapeCache);
   WTF_MAKE_NONCOPYABLE(ShapeCache);

  private:
   // Used to optimize small strings as hash table keys. Avoids malloc'ing an
   // out-of-line StringImpl.
   class SmallStringKey {
     DISALLOW_NEW_EXCEPT_PLACEMENT_NEW();

    public:
     static unsigned capacity() { return s_capacity; }

     SmallStringKey() : m_length(s_emptyValueLength), m_direction(LTR) {}

     SmallStringKey(WTF::HashTableDeletedValueType)
         : m_length(s_deletedValueLength), m_direction(LTR) {}

     template <typename CharacterType>
     SmallStringKey(CharacterType* characters,
                    unsigned short length,
                    TextDirection direction)
         : m_length(length), m_direction(direction) {
       ASSERT(length <= s_capacity);

       StringHasher hasher;

       bool remainder = length & 1;
       length >>= 1;

       unsigned i = 0;
       while (length--) {
         m_characters[i] = characters[i];
         m_characters[i + 1] = characters[i + 1];
         hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]);
         i += 2;
       }

       if (remainder) {
         m_characters[i] = characters[i];
         hasher.addCharacter(characters[i]);
       }

       m_hash = hasher.hash();
     }

     const UChar* characters() const { return m_characters; }
     unsigned short length() const { return m_length; }
     TextDirection direction() const {
       return static_cast<TextDirection>(m_direction);
     }
     unsigned hash() const { return m_hash; }

     bool isHashTableDeletedValue() const {
       return m_length == s_deletedValueLength;
     }
     bool isHashTableEmptyValue() const {
       return m_length == s_emptyValueLength;
     }

    private:
     static const unsigned s_capacity = 15;
     static const unsigned s_emptyValueLength = s_capacity + 1;
     static const unsigned s_deletedValueLength = s_capacity + 2;

     unsigned m_hash;
     unsigned m_length : 15;
     unsigned m_direction : 1;
     UChar m_characters[s_capacity];
   };

   struct SmallStringKeyHash {
     STATIC_ONLY(SmallStringKeyHash);
     static unsigned hash(const SmallStringKey& key) { return key.hash(); }
     static bool equal(const SmallStringKey& a, const SmallStringKey& b) {
       return a == b;
     }
     // Empty and deleted values have lengths that are not equal to any valid
     // length.
     static const bool safeToCompareToEmptyOrDeleted = true;
   };

   struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> {
     STATIC_ONLY(SmallStringKeyHashTraits);
     static const bool hasIsEmptyValueFunction = true;
     static bool isEmptyValue(const SmallStringKey& key) {
       return key.isHashTableEmptyValue();
     }
     static const unsigned minimumTableSize = 16;
   };

   friend bool operator==(const SmallStringKey&, const SmallStringKey&);

  public:
   ShapeCache() : m_weakFactory(this), m_version(0) {}

   ShapeCacheEntry* add(const TextRun& run, ShapeCacheEntry entry) {
     if (run.length() > SmallStringKey::capacity())
       return 0;

     return addSlowCase(run, entry);
   }

   void clearIfVersionChanged(unsigned version) {
     if (version != m_version) {
       clear();
       m_version = version;
     }
   }

   void clear() {
     m_singleCharMap.clear();
     m_shortStringMap.clear();
   }

   unsigned size() const {
     return m_singleCharMap.size() + m_shortStringMap.size();
   }

   size_t byteSize() const {
     size_t selfByteSize = 0;
     for (auto cacheEntry : m_singleCharMap) {
       selfByteSize += cacheEntry.value.m_shapeResult->byteSize();
     }
     for (auto cacheEntry : m_shortStringMap) {
       selfByteSize += cacheEntry.value.m_shapeResult->byteSize();
     }
     return selfByteSize;
   }

   WeakPtr<ShapeCache> weakPtr() { return m_weakFactory.createWeakPtr(); }

  private:
   ShapeCacheEntry* addSlowCase(const TextRun& run, ShapeCacheEntry entry) {
     unsigned length = run.length();
     bool isNewEntry;
     ShapeCacheEntry* value;
     if (length == 1) {
       uint32_t key = run[0];
       // All current codepointsin UTF-32 are bewteen 0x0 and 0x10FFFF,
       // as such use bit 32 to indicate direction.
       if (run.direction() == RTL)
         key |= (1u << 31);
       SingleCharMap::AddResult addResult = m_singleCharMap.add(key, entry);
       isNewEntry = addResult.isNewEntry;
       value = &addResult.storedValue->value;
     } else {
       SmallStringKey smallStringKey;
       if (run.is8Bit())
         smallStringKey =
             SmallStringKey(run.characters8(), length, run.direction());
       else
         smallStringKey =
             SmallStringKey(run.characters16(), length, run.direction());

       SmallStringMap::AddResult addResult =
           m_shortStringMap.add(smallStringKey, entry);
       isNewEntry = addResult.isNewEntry;
       value = &addResult.storedValue->value;
     }

     if (!isNewEntry)
       return value;

     if (size() < s_maxSize)
       return value;

     // No need to be fancy: we're just trying to avoid pathological growth.
     m_singleCharMap.clear();
     m_shortStringMap.clear();

     return 0;
   }

   typedef HashMap<SmallStringKey,
                   ShapeCacheEntry,
                   SmallStringKeyHash,
                   SmallStringKeyHashTraits>
       SmallStringMap;
   typedef HashMap<uint32_t,
                   ShapeCacheEntry,
                   DefaultHash<uint32_t>::Hash,
                   WTF::UnsignedWithZeroKeyHashTraits<uint32_t>>
       SingleCharMap;

   // Hard limit to guard against pathological growth. The expected number of
   // cache entries is a lot lower given the average word count for a web page
   // is well below 1,000 and even full length books rarely have over 10,000
   // unique words [1]. 1: http://www.mine-control.com/zack/guttenberg/
   // Our definition of a word is somewhat different from the norm in that we
   // only segment on space. Thus "foo", "foo-", and "foo)" would count as
   // three separate words. Given that 10,000 seems like a reasonable maximum.
   static const unsigned s_maxSize = 10000;

   SingleCharMap m_singleCharMap;
   SmallStringMap m_shortStringMap;
   WeakPtrFactory<ShapeCache> m_weakFactory;
   unsigned m_version;
 };

 inline bool operator==(const ShapeCache::SmallStringKey& a,
                        const ShapeCache::SmallStringKey& b) {
   if (a.length() != b.length() || a.direction() != b.direction())
     return false;
   return WTF::equal(a.characters(), b.characters(), a.length());
 }

 }  // namespace blink

 #endif  // ShapeCache_h
	/*
	* Copyright (C) 2012 Apple Inc. All rights reserved.
	* Copyright (C) 2015 Google Inc. All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	*
	* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*/

	#ifndef ShapeCache_h
	#define ShapeCache_h

	#include "platform/fonts/shaping/ShapeResult.h"
	#include "platform/text/TextRun.h"
	#include "wtf/Forward.h"
	#include "wtf/HashFunctions.h"
	#include "wtf/HashSet.h"
	#include "wtf/HashTableDeletedValueType.h"
	#include "wtf/StringHasher.h"
	#include "wtf/WeakPtr.h"

	namespace blink {

	class Font;
	class GlyphBuffer;
	class SimpleFontData;

	struct ShapeCacheEntry {
	DISALLOW_NEW_EXCEPT_PLACEMENT_NEW();
	ShapeCacheEntry() { m_shapeResult = nullptr; }
	RefPtr<const ShapeResult> m_shapeResult;
	};

	class ShapeCache {
	USING_FAST_MALLOC(ShapeCache);
	WTF_MAKE_NONCOPYABLE(ShapeCache);

	private:
	// Used to optimize small strings as hash table keys. Avoids malloc'ing an
	// out-of-line StringImpl.
	class SmallStringKey {
	DISALLOW_NEW_EXCEPT_PLACEMENT_NEW();

	public:
	static unsigned capacity() { return s_capacity; }

	SmallStringKey() : m_length(s_emptyValueLength), m_direction(LTR) {}

	SmallStringKey(WTF::HashTableDeletedValueType)
	: m_length(s_deletedValueLength), m_direction(LTR) {}

	template <typename CharacterType>
	SmallStringKey(CharacterType* characters,
	unsigned short length,
	TextDirection direction)
	: m_length(length), m_direction(direction) {
	ASSERT(length <= s_capacity);

	StringHasher hasher;

	bool remainder = length & 1;
	length >>= 1;

	unsigned i = 0;
	while (length--) {
	m_characters[i] = characters[i];
	m_characters[i + 1] = characters[i + 1];
	hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]);
	i += 2;
	}

	if (remainder) {
	m_characters[i] = characters[i];
	hasher.addCharacter(characters[i]);
	}

	m_hash = hasher.hash();
	}

	const UChar* characters() const { return m_characters; }
	unsigned short length() const { return m_length; }
	TextDirection direction() const {
	return static_cast<TextDirection>(m_direction);
	}
	unsigned hash() const { return m_hash; }

	bool isHashTableDeletedValue() const {
	return m_length == s_deletedValueLength;
	}
	bool isHashTableEmptyValue() const {
	return m_length == s_emptyValueLength;
	}

	private:
	static const unsigned s_capacity = 15;
	static const unsigned s_emptyValueLength = s_capacity + 1;
	static const unsigned s_deletedValueLength = s_capacity + 2;

	unsigned m_hash;
	unsigned m_length : 15;
	unsigned m_direction : 1;
	UChar m_characters[s_capacity];
	};

	struct SmallStringKeyHash {
	STATIC_ONLY(SmallStringKeyHash);
	static unsigned hash(const SmallStringKey& key) { return key.hash(); }
	static bool equal(const SmallStringKey& a, const SmallStringKey& b) {
	return a == b;
	}
	// Empty and deleted values have lengths that are not equal to any valid
	// length.
	static const bool safeToCompareToEmptyOrDeleted = true;
	};

	struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> {
	STATIC_ONLY(SmallStringKeyHashTraits);
	static const bool hasIsEmptyValueFunction = true;
	static bool isEmptyValue(const SmallStringKey& key) {
	return key.isHashTableEmptyValue();
	}
	static const unsigned minimumTableSize = 16;
	};

	friend bool operator==(const SmallStringKey&, const SmallStringKey&);

	public:
	ShapeCache() : m_weakFactory(this), m_version(0) {}

	ShapeCacheEntry* add(const TextRun& run, ShapeCacheEntry entry) {
	if (run.length() > SmallStringKey::capacity())
	return 0;

	return addSlowCase(run, entry);
	}

	void clearIfVersionChanged(unsigned version) {
	if (version != m_version) {
	clear();
	m_version = version;
	}
	}

	void clear() {
	m_singleCharMap.clear();
	m_shortStringMap.clear();
	}

	unsigned size() const {
	return m_singleCharMap.size() + m_shortStringMap.size();
	}

	size_t byteSize() const {
	size_t selfByteSize = 0;
	for (auto cacheEntry : m_singleCharMap) {
	selfByteSize += cacheEntry.value.m_shapeResult->byteSize();
	}
	for (auto cacheEntry : m_shortStringMap) {
	selfByteSize += cacheEntry.value.m_shapeResult->byteSize();
	}
	return selfByteSize;
	}

	WeakPtr<ShapeCache> weakPtr() { return m_weakFactory.createWeakPtr(); }

	private:
	ShapeCacheEntry* addSlowCase(const TextRun& run, ShapeCacheEntry entry) {
	unsigned length = run.length();
	bool isNewEntry;
	ShapeCacheEntry* value;
	if (length == 1) {
	uint32_t key = run[0];
	// All current codepointsin UTF-32 are bewteen 0x0 and 0x10FFFF,
	// as such use bit 32 to indicate direction.
	if (run.direction() == RTL)
	key \|= (1u << 31);
	SingleCharMap::AddResult addResult = m_singleCharMap.add(key, entry);
	isNewEntry = addResult.isNewEntry;
	value = &addResult.storedValue->value;
	} else {
	SmallStringKey smallStringKey;
	if (run.is8Bit())
	smallStringKey =
	SmallStringKey(run.characters8(), length, run.direction());
	else
	smallStringKey =
	SmallStringKey(run.characters16(), length, run.direction());

	SmallStringMap::AddResult addResult =
	m_shortStringMap.add(smallStringKey, entry);
	isNewEntry = addResult.isNewEntry;
	value = &addResult.storedValue->value;
	}

	if (!isNewEntry)
	return value;

	if (size() < s_maxSize)
	return value;

	// No need to be fancy: we're just trying to avoid pathological growth.
	m_singleCharMap.clear();
	m_shortStringMap.clear();

	return 0;
	}

	typedef HashMap<SmallStringKey,
	ShapeCacheEntry,
	SmallStringKeyHash,
	SmallStringKeyHashTraits>
	SmallStringMap;
	typedef HashMap<uint32_t,
	ShapeCacheEntry,
	DefaultHash<uint32_t>::Hash,
	WTF::UnsignedWithZeroKeyHashTraits<uint32_t>>
	SingleCharMap;

	// Hard limit to guard against pathological growth. The expected number of
	// cache entries is a lot lower given the average word count for a web page
	// is well below 1,000 and even full length books rarely have over 10,000
	// unique words [1]. 1: http://www.mine-control.com/zack/guttenberg/
	// Our definition of a word is somewhat different from the norm in that we
	// only segment on space. Thus "foo", "foo-", and "foo)" would count as
	// three separate words. Given that 10,000 seems like a reasonable maximum.
	static const unsigned s_maxSize = 10000;

	SingleCharMap m_singleCharMap;
	SmallStringMap m_shortStringMap;
	WeakPtrFactory<ShapeCache> m_weakFactory;
	unsigned m_version;
	};

	inline bool operator==(const ShapeCache::SmallStringKey& a,
	const ShapeCache::SmallStringKey& b) {
	if (a.length() != b.length() \|\| a.direction() != b.direction())
	return false;
	return WTF::equal(a.characters(), b.characters(), a.length());
	}

	} // namespace blink

	#endif // ShapeCache_h