1 /***************************************************************************/
5 /* The FreeType internal cache interface (body). */
7 /* Copyright 2000-2016 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. */
16 /***************************************************************************/
21 #include FT_INTERNAL_OBJECTS_H
22 #include FT_INTERNAL_DEBUG_H
28 #define FT_COMPONENT trace_cache
31 #define FTC_HASH_MAX_LOAD 2
32 #define FTC_HASH_MIN_LOAD 1
33 #define FTC_HASH_SUB_LOAD ( FTC_HASH_MAX_LOAD - FTC_HASH_MIN_LOAD )
35 /* this one _must_ be a power of 2! */
36 #define FTC_HASH_INITIAL_SIZE 8
39 /*************************************************************************/
40 /*************************************************************************/
42 /***** CACHE NODE DEFINITIONS *****/
44 /*************************************************************************/
45 /*************************************************************************/
47 /* add a new node to the head of the manager's circular MRU list */
49 ftc_node_mru_link( FTC_Node node
,
52 void *nl
= &manager
->nodes_list
;
55 FTC_MruNode_Prepend( (FTC_MruNode
*)nl
,
61 /* remove a node from the manager's MRU list */
63 ftc_node_mru_unlink( FTC_Node node
,
66 void *nl
= &manager
->nodes_list
;
69 FTC_MruNode_Remove( (FTC_MruNode
*)nl
,
77 /* move a node to the head of the manager's MRU list */
79 ftc_node_mru_up( FTC_Node node
,
82 FTC_MruNode_Up( (FTC_MruNode
*)&manager
->nodes_list
,
87 /* get a top bucket for specified hash from cache,
88 * body for FTC_NODE_TOP_FOR_HASH( cache, hash )
90 FT_LOCAL_DEF( FTC_Node
* )
91 ftc_get_top_node_for_hash( FTC_Cache cache
,
98 idx
= hash
& cache
->mask
;
100 idx
= hash
& ( 2 * cache
->mask
+ 1 );
101 pnode
= cache
->buckets
+ idx
;
105 #endif /* !FTC_INLINE */
108 /* Note that this function cannot fail. If we cannot re-size the
109 * buckets array appropriately, we simply degrade the hash table's
113 ftc_cache_resize( FTC_Cache cache
)
117 FTC_Node node
, *pnode
;
118 FT_UFast p
= cache
->p
;
119 FT_UFast mask
= cache
->mask
;
120 FT_UFast count
= mask
+ p
+ 1; /* number of buckets */
123 /* do we need to shrink the buckets array? */
124 if ( cache
->slack
< 0 )
126 FTC_Node new_list
= NULL
;
129 /* try to expand the buckets array _before_ splitting
134 FT_Memory memory
= cache
->memory
;
138 /* if we can't expand the array, leave immediately */
139 if ( FT_RENEW_ARRAY( cache
->buckets
,
140 ( mask
+ 1 ) * 2, ( mask
+ 1 ) * 4 ) )
144 /* split a single bucket */
145 pnode
= cache
->buckets
+ p
;
153 if ( node
->hash
& ( mask
+ 1 ) )
156 node
->link
= new_list
;
163 cache
->buckets
[p
+ mask
+ 1] = new_list
;
165 cache
->slack
+= FTC_HASH_MAX_LOAD
;
169 cache
->mask
= 2 * mask
+ 1;
176 /* do we need to expand the buckets array? */
177 else if ( cache
->slack
> (FT_Long
)count
* FTC_HASH_SUB_LOAD
)
179 FT_UFast old_index
= p
+ mask
;
183 if ( old_index
+ 1 <= FTC_HASH_INITIAL_SIZE
)
188 FT_Memory memory
= cache
->memory
;
192 /* if we can't shrink the array, leave immediately */
193 if ( FT_RENEW_ARRAY( cache
->buckets
,
194 ( mask
+ 1 ) * 2, mask
+ 1 ) )
203 pnode
= cache
->buckets
+ p
;
205 pnode
= &(*pnode
)->link
;
207 pold
= cache
->buckets
+ old_index
;
211 cache
->slack
-= FTC_HASH_MAX_LOAD
;
215 /* otherwise, the hash table is balanced */
222 /* remove a node from its cache's hash table */
224 ftc_node_hash_unlink( FTC_Node node0
,
227 FTC_Node
*pnode
= FTC_NODE_TOP_FOR_HASH( cache
, node0
->hash
);
232 FTC_Node node
= *pnode
;
237 FT_TRACE0(( "ftc_node_hash_unlink: unknown node\n" ));
244 pnode
= &(*pnode
)->link
;
247 *pnode
= node0
->link
;
251 ftc_cache_resize( cache
);
255 /* add a node to the `top' of its cache's hash table */
257 ftc_node_hash_link( FTC_Node node
,
260 FTC_Node
*pnode
= FTC_NODE_TOP_FOR_HASH( cache
, node
->hash
);
267 ftc_cache_resize( cache
);
271 /* remove a node from the cache manager */
273 ftc_node_destroy( FTC_Node node
,
274 FTC_Manager manager
)
279 #ifdef FT_DEBUG_ERROR
280 /* find node's cache */
281 if ( node
->cache_index
>= manager
->num_caches
)
283 FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
288 cache
= manager
->caches
[node
->cache_index
];
290 #ifdef FT_DEBUG_ERROR
293 FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
298 manager
->cur_weight
-= cache
->clazz
.node_weight( node
, cache
);
300 /* remove node from mru list */
301 ftc_node_mru_unlink( node
, manager
);
303 /* remove node from cache's hash table */
304 ftc_node_hash_unlink( node
, cache
);
306 /* now finalize it */
307 cache
->clazz
.node_free( node
, cache
);
310 /* check, just in case of general corruption :-) */
311 if ( manager
->num_nodes
== 0 )
312 FT_TRACE0(( "ftc_node_destroy: invalid cache node count (%d)\n",
313 manager
->num_nodes
));
318 /*************************************************************************/
319 /*************************************************************************/
321 /***** ABSTRACT CACHE CLASS *****/
323 /*************************************************************************/
324 /*************************************************************************/
327 FT_LOCAL_DEF( FT_Error
)
328 FTC_Cache_Init( FTC_Cache cache
)
330 return ftc_cache_init( cache
);
334 FT_LOCAL_DEF( FT_Error
)
335 ftc_cache_init( FTC_Cache cache
)
337 FT_Memory memory
= cache
->memory
;
342 cache
->mask
= FTC_HASH_INITIAL_SIZE
- 1;
343 cache
->slack
= FTC_HASH_INITIAL_SIZE
* FTC_HASH_MAX_LOAD
;
345 (void)FT_NEW_ARRAY( cache
->buckets
, FTC_HASH_INITIAL_SIZE
* 2 );
351 FTC_Cache_Clear( FTC_Cache cache
)
353 if ( cache
&& cache
->buckets
)
355 FTC_Manager manager
= cache
->manager
;
360 count
= cache
->p
+ cache
->mask
+ 1;
362 for ( i
= 0; i
< count
; i
++ )
364 FTC_Node
*pnode
= cache
->buckets
+ i
, next
, node
= *pnode
;
372 /* remove node from mru list */
373 ftc_node_mru_unlink( node
, manager
);
375 /* now finalize it */
376 manager
->cur_weight
-= cache
->clazz
.node_weight( node
, cache
);
378 cache
->clazz
.node_free( node
, cache
);
381 cache
->buckets
[i
] = NULL
;
383 ftc_cache_resize( cache
);
389 ftc_cache_done( FTC_Cache cache
)
393 FT_Memory memory
= cache
->memory
;
396 FTC_Cache_Clear( cache
);
398 FT_FREE( cache
->buckets
);
403 cache
->memory
= NULL
;
409 FTC_Cache_Done( FTC_Cache cache
)
411 ftc_cache_done( cache
);
416 ftc_cache_add( FTC_Cache cache
,
421 node
->cache_index
= (FT_UInt16
)cache
->index
;
424 ftc_node_hash_link( node
, cache
);
425 ftc_node_mru_link( node
, cache
->manager
);
428 FTC_Manager manager
= cache
->manager
;
431 manager
->cur_weight
+= cache
->clazz
.node_weight( node
, cache
);
433 if ( manager
->cur_weight
>= manager
->max_weight
)
436 FTC_Manager_Compress( manager
);
443 FT_LOCAL_DEF( FT_Error
)
444 FTC_Cache_NewNode( FTC_Cache cache
,
454 * We use the FTC_CACHE_TRYLOOP macros to support out-of-memory
455 * errors (OOM) correctly, i.e., by flushing the cache progressively
456 * in order to make more room.
459 FTC_CACHE_TRYLOOP( cache
)
461 error
= cache
->clazz
.node_new( &node
, query
, cache
);
463 FTC_CACHE_TRYLOOP_END( NULL
);
469 /* don't assume that the cache has the same number of buckets, since
470 * our allocation request might have triggered global cache flushing
472 ftc_cache_add( cache
, hash
, node
);
482 FT_LOCAL_DEF( FT_Error
)
483 FTC_Cache_Lookup( FTC_Cache cache
,
491 FT_Error error
= FT_Err_Ok
;
492 FT_Bool list_changed
= FALSE
;
494 FTC_Node_CompareFunc compare
= cache
->clazz
.node_compare
;
497 if ( !cache
|| !anode
)
498 return FT_THROW( Invalid_Argument
);
500 /* Go to the `top' node of the list sharing same masked hash */
501 bucket
= pnode
= FTC_NODE_TOP_FOR_HASH( cache
, hash
);
503 /* Lookup a node with exactly same hash and queried properties. */
504 /* NOTE: _nodcomp() may change the linked list to reduce memory. */
511 if ( node
->hash
== hash
&&
512 compare( node
, query
, cache
, &list_changed
) )
520 /* Update bucket by modified linked list */
521 bucket
= pnode
= FTC_NODE_TOP_FOR_HASH( cache
, hash
);
523 /* Update pnode by modified linked list */
524 while ( *pnode
!= node
)
528 FT_ERROR(( "FTC_Cache_Lookup: oops!!! node missing\n" ));
532 pnode
= &((*pnode
)->link
);
536 /* Reorder the list to move the found node to the `top' */
537 if ( node
!= *bucket
)
540 node
->link
= *bucket
;
544 /* move to head of MRU list */
546 FTC_Manager manager
= cache
->manager
;
549 if ( node
!= manager
->nodes_list
)
550 ftc_node_mru_up( node
, manager
);
557 return FTC_Cache_NewNode( cache
, hash
, query
, anode
);
560 #endif /* !FTC_INLINE */
564 FTC_Cache_RemoveFaceID( FTC_Cache cache
,
568 FTC_Manager manager
= cache
->manager
;
569 FTC_Node frees
= NULL
;
572 count
= cache
->p
+ cache
->mask
+ 1;
573 for ( i
= 0; i
< count
; i
++ )
575 FTC_Node
* bucket
= cache
->buckets
+ i
;
576 FTC_Node
* pnode
= bucket
;
581 FTC_Node node
= *pnode
;
582 FT_Bool list_changed
= FALSE
;
588 if ( cache
->clazz
.node_remove_faceid( node
, face_id
,
589 cache
, &list_changed
) )
600 /* remove all nodes in the free list */
609 manager
->cur_weight
-= cache
->clazz
.node_weight( node
, cache
);
610 ftc_node_mru_unlink( node
, manager
);
612 cache
->clazz
.node_free( node
, cache
);
617 ftc_cache_resize( cache
);