/***************************************************************************/ /* */ /* ftccache.h */ /* */ /* FreeType internal cache interface (specification). */ /* */ /* Copyright 2000-2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010, */ /* 2011 by */ /* David Turner, Robert Wilhelm, and Werner Lemberg. */ /* */ /* This file is part of the FreeType project, and may only be used, */ /* modified, and distributed under the terms of the FreeType project */ /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ /* this file you indicate that you have read the license and */ /* understand and accept it fully. */ /* */ /***************************************************************************/ #ifndef __FTCCACHE_H__ #define __FTCCACHE_H__ #include "ftcmru.h" FT_BEGIN_HEADER #define _FTC_FACE_ID_HASH( i ) \ ((FT_PtrDist)(( (FT_PtrDist)(i) >> 3 ) ^ ( (FT_PtrDist)(i) << 7 ))) /* handle to cache object */ typedef struct FTC_CacheRec_* FTC_Cache; /* handle to cache class */ typedef const struct FTC_CacheClassRec_* FTC_CacheClass; /*************************************************************************/ /*************************************************************************/ /***** *****/ /***** CACHE NODE DEFINITIONS *****/ /***** *****/ /*************************************************************************/ /*************************************************************************/ /*************************************************************************/ /* */ /* Each cache controls one or more cache nodes. Each node is part of */ /* the global_lru list of the manager. Its `data' field however is used */ /* as a reference count for now. */ /* */ /* A node can be anything, depending on the type of information held by */ /* the cache. It can be an individual glyph image, a set of bitmaps */ /* glyphs for a given size, some metrics, etc. */ /* */ /*************************************************************************/ /* structure size should be 20 bytes on 32-bits machines */ typedef struct FTC_NodeRec_ { FTC_MruNodeRec mru; /* circular mru list pointer */ FTC_Node link; /* used for hashing */ FT_PtrDist hash; /* used for hashing too */ FT_UShort cache_index; /* index of cache the node belongs to */ FT_Short ref_count; /* reference count for this node */ } FTC_NodeRec; #define FTC_NODE( x ) ( (FTC_Node)(x) ) #define FTC_NODE_P( x ) ( (FTC_Node*)(x) ) #define FTC_NODE__NEXT( x ) FTC_NODE( (x)->mru.next ) #define FTC_NODE__PREV( x ) FTC_NODE( (x)->mru.prev ) #ifdef FTC_INLINE #define FTC_NODE__TOP_FOR_HASH( cache, hash ) \ ( ( cache )->buckets + \ ( ( ( ( hash ) & ( cache )->mask ) < ( cache )->p ) \ ? ( ( hash ) & ( ( cache )->mask * 2 + 1 ) ) \ : ( ( hash ) & ( cache )->mask ) ) ) #else FT_LOCAL( FTC_Node* ) ftc_get_top_node_for_hash( FTC_Cache cache, FT_PtrDist hash ); #define FTC_NODE__TOP_FOR_HASH( cache, hash ) \ ftc_get_top_node_for_hash( ( cache ), ( hash ) ) #endif #ifdef FT_CONFIG_OPTION_OLD_INTERNALS FT_BASE( void ) ftc_node_destroy( FTC_Node node, FTC_Manager manager ); #endif /*************************************************************************/ /*************************************************************************/ /***** *****/ /***** CACHE DEFINITIONS *****/ /***** *****/ /*************************************************************************/ /*************************************************************************/ /* initialize a new cache node */ typedef FT_Error (*FTC_Node_NewFunc)( FTC_Node *pnode, FT_Pointer query, FTC_Cache cache ); typedef FT_Offset (*FTC_Node_WeightFunc)( FTC_Node node, FTC_Cache cache ); /* compare a node to a given key pair */ typedef FT_Bool (*FTC_Node_CompareFunc)( FTC_Node node, FT_Pointer key, FTC_Cache cache, FT_Bool* list_changed ); typedef void (*FTC_Node_FreeFunc)( FTC_Node node, FTC_Cache cache ); typedef FT_Error (*FTC_Cache_InitFunc)( FTC_Cache cache ); typedef void (*FTC_Cache_DoneFunc)( FTC_Cache cache ); typedef struct FTC_CacheClassRec_ { FTC_Node_NewFunc node_new; FTC_Node_WeightFunc node_weight; FTC_Node_CompareFunc node_compare; FTC_Node_CompareFunc node_remove_faceid; FTC_Node_FreeFunc node_free; FT_Offset cache_size; FTC_Cache_InitFunc cache_init; FTC_Cache_DoneFunc cache_done; } FTC_CacheClassRec; /* each cache really implements a dynamic hash table to manage its nodes */ typedef struct FTC_CacheRec_ { FT_UFast p; FT_UFast mask; FT_Long slack; FTC_Node* buckets; FTC_CacheClassRec clazz; /* local copy, for speed */ FTC_Manager manager; FT_Memory memory; FT_UInt index; /* in manager's table */ FTC_CacheClass org_class; /* original class pointer */ } FTC_CacheRec; #define FTC_CACHE( x ) ( (FTC_Cache)(x) ) #define FTC_CACHE_P( x ) ( (FTC_Cache*)(x) ) /* default cache initialize */ FT_LOCAL( FT_Error ) FTC_Cache_Init( FTC_Cache cache ); /* default cache finalizer */ FT_LOCAL( void ) FTC_Cache_Done( FTC_Cache cache ); /* Call this function to look up the cache. If no corresponding * node is found, a new one is automatically created. This function * is capable of flushing the cache adequately to make room for the * new cache object. */ #ifndef FTC_INLINE FT_LOCAL( FT_Error ) FTC_Cache_Lookup( FTC_Cache cache, FT_PtrDist hash, FT_Pointer query, FTC_Node *anode ); #endif FT_LOCAL( FT_Error ) FTC_Cache_NewNode( FTC_Cache cache, FT_PtrDist hash, FT_Pointer query, FTC_Node *anode ); /* Remove all nodes that relate to a given face_id. This is useful * when un-installing fonts. Note that if a cache node relates to * the face_id but is locked (i.e., has `ref_count > 0'), the node * will _not_ be destroyed, but its internal face_id reference will * be modified. * * The final result will be that the node will never come back * in further lookup requests, and will be flushed on demand from * the cache normally when its reference count reaches 0. */ FT_LOCAL( void ) FTC_Cache_RemoveFaceID( FTC_Cache cache, FTC_FaceID face_id ); #ifdef FTC_INLINE #define FTC_CACHE_LOOKUP_CMP( cache, nodecmp, hash, query, node, error ) \ FT_BEGIN_STMNT \ FTC_Node *_bucket, *_pnode, _node; \ FTC_Cache _cache = FTC_CACHE(cache); \ FT_PtrDist _hash = (FT_PtrDist)(hash); \ FTC_Node_CompareFunc _nodcomp = (FTC_Node_CompareFunc)(nodecmp); \ FT_Bool _list_changed = FALSE; \ \ \ error = FTC_Err_Ok; \ node = NULL; \ \ /* Go to the `top' node of the list sharing same masked hash */ \ _bucket = _pnode = FTC_NODE__TOP_FOR_HASH( _cache, _hash ); \ \ /* Look up a node with identical hash and queried properties. */ \ /* NOTE: _nodcomp() may change the linked list to reduce memory. */ \ for (;;) \ { \ _node = *_pnode; \ if ( _node == NULL ) \ goto _NewNode; \ \ if ( _node->hash == _hash && \ _nodcomp( _node, query, _cache, &_list_changed ) ) \ break; \ \ _pnode = &_node->link; \ } \ \ if ( _list_changed ) \ { \ /* Update _bucket by possibly modified linked list */ \ _bucket = _pnode = FTC_NODE__TOP_FOR_HASH( _cache, _hash ); \ \ /* Update _pnode by possibly modified linked list */ \ while ( *_pnode != _node ) \ { \ if ( *_pnode == NULL ) \ { \ FT_ERROR(( "FTC_CACHE_LOOKUP_CMP: oops!!! node missing\n" )); \ goto _NewNode; \ } \ else \ _pnode = &((*_pnode)->link); \ } \ } \ \ /* Reorder the list to move the found node to the `top' */ \ if ( _node != *_bucket ) \ { \ *_pnode = _node->link; \ _node->link = *_bucket; \ *_bucket = _node; \ } \ \ /* Update MRU list */ \ { \ FTC_Manager _manager = _cache->manager; \ void* _nl = &_manager->nodes_list; \ \ \ if ( _node != _manager->nodes_list ) \ FTC_MruNode_Up( (FTC_MruNode*)_nl, \ (FTC_MruNode)_node ); \ } \ goto _Ok; \ \ _NewNode: \ error = FTC_Cache_NewNode( _cache, _hash, query, &_node ); \ \ _Ok: \ node = _node; \ FT_END_STMNT #else /* !FTC_INLINE */ #define FTC_CACHE_LOOKUP_CMP( cache, nodecmp, hash, query, node, error ) \ FT_BEGIN_STMNT \ error = FTC_Cache_Lookup( FTC_CACHE( cache ), hash, query, \ (FTC_Node*)&(node) ); \ FT_END_STMNT #endif /* !FTC_INLINE */ /* * This macro, together with FTC_CACHE_TRYLOOP_END, defines a retry * loop to flush the cache repeatedly in case of memory overflows. * * It is used when creating a new cache node, or within a lookup * that needs to allocate data (e.g. the sbit cache lookup). * * Example: * * { * FTC_CACHE_TRYLOOP( cache ) * error = load_data( ... ); * FTC_CACHE_TRYLOOP_END() * } * */ #define FTC_CACHE_TRYLOOP( cache ) \ { \ FTC_Manager _try_manager = FTC_CACHE( cache )->manager; \ FT_UInt _try_count = 4; \ \ \ for (;;) \ { \ FT_UInt _try_done; #define FTC_CACHE_TRYLOOP_END( list_changed ) \ if ( !error || error != FTC_Err_Out_Of_Memory ) \ break; \ \ _try_done = FTC_Manager_FlushN( _try_manager, _try_count ); \ if ( _try_done > 0 && ( list_changed ) ) \ *(FT_Bool*)( list_changed ) = TRUE; \ \ if ( _try_done == 0 ) \ break; \ \ if ( _try_done == _try_count ) \ { \ _try_count *= 2; \ if ( _try_count < _try_done || \ _try_count > _try_manager->num_nodes ) \ _try_count = _try_manager->num_nodes; \ } \ } \ } /* */ FT_END_HEADER #endif /* __FTCCACHE_H__ */ /* END */