1 /****************************************************************************
5 * The FreeType internal cache interface (body).
7 * Copyright (C) 2000-2023 by
8 * David Turner, Robert Wilhelm, and Werner Lemberg.
10 * This file is part of the FreeType project, and may only be used,
11 * modified, and distributed under the terms of the FreeType project
12 * license, LICENSE.TXT. By continuing to use, modify, or distribute
13 * this file you indicate that you have read the license and
14 * understand and accept it fully.
20 #include <freetype/internal/ftobjs.h>
21 #include <freetype/internal/ftdebug.h>
27 #define FT_COMPONENT cache
30 #define FTC_HASH_MAX_LOAD 2
31 #define FTC_HASH_MIN_LOAD 1
32 #define FTC_HASH_SUB_LOAD ( FTC_HASH_MAX_LOAD - FTC_HASH_MIN_LOAD )
34 /* this one _must_ be a power of 2! */
35 #define FTC_HASH_INITIAL_SIZE 8
38 /*************************************************************************/
39 /*************************************************************************/
41 /***** CACHE NODE DEFINITIONS *****/
43 /*************************************************************************/
44 /*************************************************************************/
46 /* add a new node to the head of the manager's circular MRU list */
48 ftc_node_mru_link( FTC_Node node,
51 void *nl = &manager->nodes_list;
54 FTC_MruNode_Prepend( (FTC_MruNode*)nl,
60 /* remove a node from the manager's MRU list */
62 ftc_node_mru_unlink( FTC_Node node,
65 void *nl = &manager->nodes_list;
68 FTC_MruNode_Remove( (FTC_MruNode*)nl,
76 /* move a node to the head of the manager's MRU list */
78 ftc_node_mru_up( FTC_Node node,
81 FTC_MruNode_Up( (FTC_MruNode*)&manager->nodes_list,
86 /* get a top bucket for specified hash from cache,
87 * body for FTC_NODE_TOP_FOR_HASH( cache, hash )
89 FT_LOCAL_DEF( FTC_Node* )
90 ftc_get_top_node_for_hash( FTC_Cache cache,
96 idx = hash & cache->mask;
97 if ( idx >= cache->p )
98 idx = hash & ( cache->mask >> 1 );
100 return cache->buckets + idx;
103 #endif /* !FTC_INLINE */
106 /* Note that this function cannot fail. If we cannot re-size the
107 * buckets array appropriately, we simply degrade the hash table's
111 ftc_cache_resize( FTC_Cache cache )
115 FTC_Node node, *pnode;
116 FT_UFast p = cache->p;
117 FT_UFast size = cache->mask + 1; /* available size */
118 FT_UFast half = size >> 1;
121 /* do we need to expand the buckets array? */
122 if ( cache->slack < 0 )
124 FTC_Node new_list = NULL;
127 /* try to expand the buckets array _before_ splitting
132 FT_Memory memory = cache->memory;
136 /* if we can't expand the array, leave immediately */
137 if ( FT_QRENEW_ARRAY( cache->buckets, size, size * 2 ) )
140 cache->mask = 2 * size - 1;
144 /* the bucket to split */
145 pnode = cache->buckets + p - half;
153 if ( node->hash & half )
156 node->link = new_list;
163 cache->buckets[p] = new_list;
165 cache->slack += FTC_HASH_MAX_LOAD;
168 FT_TRACE2(( "ftc_cache_resize: cache %u increased to %u hashes\n",
169 cache->index, cache->p ));
172 /* do we need to shrink the buckets array? */
173 else if ( cache->slack > (FT_Long)p * FTC_HASH_SUB_LOAD )
175 FTC_Node old_list = cache->buckets[--p];
178 if ( p < FTC_HASH_INITIAL_SIZE )
183 FT_Memory memory = cache->memory;
187 /* if we can't shrink the array, leave immediately */
188 if ( FT_QRENEW_ARRAY( cache->buckets, size, half ) )
191 cache->mask = half - 1;
194 /* the bucket to merge */
195 pnode = cache->buckets + p - half;
198 pnode = &(*pnode)->link;
202 cache->slack -= FTC_HASH_MAX_LOAD;
205 FT_TRACE2(( "ftc_cache_resize: cache %u decreased to %u hashes\n",
206 cache->index, cache->p ));
209 /* otherwise, the hash table is balanced */
216 /* remove a node from its cache's hash table */
218 ftc_node_hash_unlink( FTC_Node node0,
221 FTC_Node *pnode = FTC_NODE_TOP_FOR_HASH( cache, node0->hash );
226 FTC_Node node = *pnode;
231 FT_TRACE0(( "ftc_node_hash_unlink: unknown node\n" ));
241 *pnode = node0->link;
245 ftc_cache_resize( cache );
249 /* add a node to the `top' of its cache's hash table */
251 ftc_node_hash_link( FTC_Node node,
254 FTC_Node *pnode = FTC_NODE_TOP_FOR_HASH( cache, node->hash );
261 ftc_cache_resize( cache );
265 /* remove a node from the cache manager */
267 ftc_node_destroy( FTC_Node node,
268 FTC_Manager manager )
273 #ifdef FT_DEBUG_ERROR
274 /* find node's cache */
275 if ( node->cache_index >= manager->num_caches )
277 FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
282 cache = manager->caches[node->cache_index];
284 #ifdef FT_DEBUG_ERROR
287 FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
292 manager->cur_weight -= cache->clazz.node_weight( node, cache );
294 /* remove node from mru list */
295 ftc_node_mru_unlink( node, manager );
297 /* remove node from cache's hash table */
298 ftc_node_hash_unlink( node, cache );
300 /* now finalize it */
301 cache->clazz.node_free( node, cache );
304 /* check, just in case of general corruption :-) */
305 if ( manager->num_nodes == 0 )
306 FT_TRACE0(( "ftc_node_destroy: invalid cache node count (%u)\n",
307 manager->num_nodes ));
312 /*************************************************************************/
313 /*************************************************************************/
315 /***** ABSTRACT CACHE CLASS *****/
317 /*************************************************************************/
318 /*************************************************************************/
321 FT_LOCAL_DEF( FT_Error )
322 ftc_cache_init( FTC_Cache cache )
324 FT_Memory memory = cache->memory;
328 cache->p = FTC_HASH_INITIAL_SIZE;
329 cache->mask = FTC_HASH_INITIAL_SIZE - 1;
330 cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD;
332 FT_MEM_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE );
337 FT_LOCAL_DEF( FT_Error )
338 FTC_Cache_Init( FTC_Cache cache )
340 return ftc_cache_init( cache );
345 ftc_cache_done( FTC_Cache cache )
347 FT_Memory memory = cache->memory;
350 if ( cache->buckets )
352 FTC_Manager manager = cache->manager;
353 FT_UFast count = cache->p;
357 for ( i = 0; i < count; i++ )
359 FTC_Node node = cache->buckets[i], next;
367 /* remove node from mru list */
368 ftc_node_mru_unlink( node, manager );
370 /* now finalize it */
371 manager->cur_weight -= cache->clazz.node_weight( node, cache );
373 cache->clazz.node_free( node, cache );
379 FT_FREE( cache->buckets );
388 FTC_Cache_Done( FTC_Cache cache )
390 ftc_cache_done( cache );
395 ftc_cache_add( FTC_Cache cache,
400 node->cache_index = (FT_UShort)cache->index;
403 ftc_node_hash_link( node, cache );
404 ftc_node_mru_link( node, cache->manager );
407 FTC_Manager manager = cache->manager;
410 manager->cur_weight += cache->clazz.node_weight( node, cache );
412 if ( manager->cur_weight >= manager->max_weight )
415 FTC_Manager_Compress( manager );
422 FT_LOCAL_DEF( FT_Error )
423 FTC_Cache_NewNode( FTC_Cache cache,
433 * We use the FTC_CACHE_TRYLOOP macros to support out-of-memory
434 * errors (OOM) correctly, i.e., by flushing the cache progressively
435 * in order to make more room.
438 FTC_CACHE_TRYLOOP( cache )
440 error = cache->clazz.node_new( &node, query, cache );
442 FTC_CACHE_TRYLOOP_END( NULL )
448 /* don't assume that the cache has the same number of buckets, since
449 * our allocation request might have triggered global cache flushing
451 ftc_cache_add( cache, hash, node );
461 FT_LOCAL_DEF( FT_Error )
462 FTC_Cache_Lookup( FTC_Cache cache,
470 FT_Error error = FT_Err_Ok;
471 FT_Bool list_changed = FALSE;
473 FTC_Node_CompareFunc compare = cache->clazz.node_compare;
476 if ( !cache || !anode )
477 return FT_THROW( Invalid_Argument );
479 /* Go to the `top' node of the list sharing same masked hash */
480 bucket = pnode = FTC_NODE_TOP_FOR_HASH( cache, hash );
482 /* Lookup a node with exactly same hash and queried properties. */
483 /* NOTE: _nodcomp() may change the linked list to reduce memory. */
490 if ( node->hash == hash &&
491 compare( node, query, cache, &list_changed ) )
499 /* Update bucket by modified linked list */
500 bucket = pnode = FTC_NODE_TOP_FOR_HASH( cache, hash );
502 /* Update pnode by modified linked list */
503 while ( *pnode != node )
507 FT_ERROR(( "FTC_Cache_Lookup: oops!!! node missing\n" ));
511 pnode = &(*pnode)->link;
515 /* Reorder the list to move the found node to the `top' */
516 if ( node != *bucket )
519 node->link = *bucket;
523 /* move to head of MRU list */
525 FTC_Manager manager = cache->manager;
528 if ( node != manager->nodes_list )
529 ftc_node_mru_up( node, manager );
536 return FTC_Cache_NewNode( cache, hash, query, anode );
539 #endif /* !FTC_INLINE */
543 FTC_Cache_RemoveFaceID( FTC_Cache cache,
546 FTC_Manager manager = cache->manager;
547 FTC_Node frees = NULL;
548 FT_UFast count = cache->p;
552 for ( i = 0; i < count; i++ )
554 FTC_Node* pnode = cache->buckets + i;
559 FTC_Node node = *pnode;
560 FT_Bool list_changed = FALSE;
566 if ( cache->clazz.node_remove_faceid( node, face_id,
567 cache, &list_changed ) )
578 /* remove all nodes in the free list */
587 manager->cur_weight -= cache->clazz.node_weight( node, cache );
588 ftc_node_mru_unlink( node, manager );
590 cache->clazz.node_free( node, cache );
595 ftc_cache_resize( cache );