1 /****************************************************************************
2 *
3 * ftccache.c
4 *
5 * The FreeType internal cache interface (body).
6 *
7 * Copyright (C) 2000-2023 by
8 * David Turner, Robert Wilhelm, and Werner Lemberg.
9 *
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.
15 *
16 */
17
18
19 #include "ftcmanag.h"
20 #include <freetype/internal/ftobjs.h>
21 #include <freetype/internal/ftdebug.h>
22
23 #include "ftccback.h"
24 #include "ftcerror.h"
25
26 #undef FT_COMPONENT
27 #define FT_COMPONENT cache
28
29
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 )
33
34 /* this one _must_ be a power of 2! */
35 #define FTC_HASH_INITIAL_SIZE 8
36
37
38 /*************************************************************************/
39 /*************************************************************************/
40 /***** *****/
41 /***** CACHE NODE DEFINITIONS *****/
42 /***** *****/
43 /*************************************************************************/
44 /*************************************************************************/
45
46 /* add a new node to the head of the manager's circular MRU list */
47 static void
48 ftc_node_mru_link( FTC_Node node,
49 FTC_Manager manager )
50 {
51 void *nl = &manager->nodes_list;
52
53
54 FTC_MruNode_Prepend( (FTC_MruNode*)nl,
55 (FTC_MruNode)node );
56 manager->num_nodes++;
57 }
58
59
60 /* remove a node from the manager's MRU list */
61 static void
62 ftc_node_mru_unlink( FTC_Node node,
63 FTC_Manager manager )
64 {
65 void *nl = &manager->nodes_list;
66
67
68 FTC_MruNode_Remove( (FTC_MruNode*)nl,
69 (FTC_MruNode)node );
70 manager->num_nodes--;
71 }
72
73
74 #ifndef FTC_INLINE
75
76 /* move a node to the head of the manager's MRU list */
77 static void
78 ftc_node_mru_up( FTC_Node node,
79 FTC_Manager manager )
80 {
81 FTC_MruNode_Up( (FTC_MruNode*)&manager->nodes_list,
82 (FTC_MruNode)node );
83 }
84
85
86 /* get a top bucket for specified hash from cache,
87 * body for FTC_NODE_TOP_FOR_HASH( cache, hash )
88 */
89 FT_LOCAL_DEF( FTC_Node* )
90 ftc_get_top_node_for_hash( FTC_Cache cache,
91 FT_Offset hash )
92 {
93 FT_Offset idx;
94
95
96 idx = hash & cache->mask;
97 if ( idx >= cache->p )
98 idx = hash & ( cache->mask >> 1 );
99
100 return cache->buckets + idx;
101 }
102
103 #endif /* !FTC_INLINE */
104
105
106 /* Note that this function cannot fail. If we cannot re-size the
107 * buckets array appropriately, we simply degrade the hash table's
108 * performance!
109 */
110 static void
111 ftc_cache_resize( FTC_Cache cache )
112 {
113 for (;;)
114 {
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;
119
120
121 /* do we need to expand the buckets array? */
122 if ( cache->slack < 0 )
123 {
124 FTC_Node new_list = NULL;
125
126
127 /* try to expand the buckets array _before_ splitting
128 * the bucket lists
129 */
130 if ( p == size )
131 {
132 FT_Memory memory = cache->memory;
133 FT_Error error;
134
135
136 /* if we can't expand the array, leave immediately */
137 if ( FT_QRENEW_ARRAY( cache->buckets, size, size * 2 ) )
138 break;
139
140 cache->mask = 2 * size - 1;
141 half = size;
142 }
143
144 /* the bucket to split */
145 pnode = cache->buckets + p - half;
146
147 for (;;)
148 {
149 node = *pnode;
150 if ( !node )
151 break;
152
153 if ( node->hash & half )
154 {
155 *pnode = node->link;
156 node->link = new_list;
157 new_list = node;
158 }
159 else
160 pnode = &node->link;
161 }
162
163 cache->buckets[p] = new_list;
164
165 cache->slack += FTC_HASH_MAX_LOAD;
166 cache->p = p + 1;
167
168 FT_TRACE2(( "ftc_cache_resize: cache %u increased to %u hashes\n",
169 cache->index, cache->p ));
170 }
171
172 /* do we need to shrink the buckets array? */
173 else if ( cache->slack > (FT_Long)p * FTC_HASH_SUB_LOAD )
174 {
175 FTC_Node old_list = cache->buckets[--p];
176
177
178 if ( p < FTC_HASH_INITIAL_SIZE )
179 break;
180
181 if ( p == half )
182 {
183 FT_Memory memory = cache->memory;
184 FT_Error error;
185
186
187 /* if we can't shrink the array, leave immediately */
188 if ( FT_QRENEW_ARRAY( cache->buckets, size, half ) )
189 break;
190
191 cache->mask = half - 1;
192 }
193
194 /* the bucket to merge */
195 pnode = cache->buckets + p - half;
196
197 while ( *pnode )
198 pnode = &(*pnode)->link;
199
200 *pnode = old_list;
201
202 cache->slack -= FTC_HASH_MAX_LOAD;
203 cache->p = p;
204
205 FT_TRACE2(( "ftc_cache_resize: cache %u decreased to %u hashes\n",
206 cache->index, cache->p ));
207 }
208
209 /* otherwise, the hash table is balanced */
210 else
211 break;
212 }
213 }
214
215
216 /* remove a node from its cache's hash table */
217 static void
218 ftc_node_hash_unlink( FTC_Node node0,
219 FTC_Cache cache )
220 {
221 FTC_Node *pnode = FTC_NODE_TOP_FOR_HASH( cache, node0->hash );
222
223
224 for (;;)
225 {
226 FTC_Node node = *pnode;
227
228
229 if ( !node )
230 {
231 FT_TRACE0(( "ftc_node_hash_unlink: unknown node\n" ));
232 return;
233 }
234
235 if ( node == node0 )
236 break;
237
238 pnode = &node->link;
239 }
240
241 *pnode = node0->link;
242 node0->link = NULL;
243
244 cache->slack++;
245 ftc_cache_resize( cache );
246 }
247
248
249 /* add a node to the `top' of its cache's hash table */
250 static void
251 ftc_node_hash_link( FTC_Node node,
252 FTC_Cache cache )
253 {
254 FTC_Node *pnode = FTC_NODE_TOP_FOR_HASH( cache, node->hash );
255
256
257 node->link = *pnode;
258 *pnode = node;
259
260 cache->slack--;
261 ftc_cache_resize( cache );
262 }
263
264
265 /* remove a node from the cache manager */
266 FT_LOCAL_DEF( void )
267 ftc_node_destroy( FTC_Node node,
268 FTC_Manager manager )
269 {
270 FTC_Cache cache;
271
272
273 #ifdef FT_DEBUG_ERROR
274 /* find node's cache */
275 if ( node->cache_index >= manager->num_caches )
276 {
277 FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
278 return;
279 }
280 #endif
281
282 cache = manager->caches[node->cache_index];
283
284 #ifdef FT_DEBUG_ERROR
285 if ( !cache )
286 {
287 FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
288 return;
289 }
290 #endif
291
292 manager->cur_weight -= cache->clazz.node_weight( node, cache );
293
294 /* remove node from mru list */
295 ftc_node_mru_unlink( node, manager );
296
297 /* remove node from cache's hash table */
298 ftc_node_hash_unlink( node, cache );
299
300 /* now finalize it */
301 cache->clazz.node_free( node, cache );
302
303 #if 0
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 ));
308 #endif
309 }
310
311
312 /*************************************************************************/
313 /*************************************************************************/
314 /***** *****/
315 /***** ABSTRACT CACHE CLASS *****/
316 /***** *****/
317 /*************************************************************************/
318 /*************************************************************************/
319
320
321 FT_LOCAL_DEF( FT_Error )
322 ftc_cache_init( FTC_Cache cache )
323 {
324 FT_Memory memory = cache->memory;
325 FT_Error error;
326
327
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;
331
332 FT_MEM_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE );
333 return error;
334 }
335
336
337 FT_LOCAL_DEF( FT_Error )
338 FTC_Cache_Init( FTC_Cache cache )
339 {
340 return ftc_cache_init( cache );
341 }
342
343
344 FT_LOCAL_DEF( void )
345 ftc_cache_done( FTC_Cache cache )
346 {
347 FT_Memory memory = cache->memory;
348
349
350 if ( cache->buckets )
351 {
352 FTC_Manager manager = cache->manager;
353 FT_UFast count = cache->p;
354 FT_UFast i;
355
356
357 for ( i = 0; i < count; i++ )
358 {
359 FTC_Node node = cache->buckets[i], next;
360
361
362 while ( node )
363 {
364 next = node->link;
365 node->link = NULL;
366
367 /* remove node from mru list */
368 ftc_node_mru_unlink( node, manager );
369
370 /* now finalize it */
371 manager->cur_weight -= cache->clazz.node_weight( node, cache );
372
373 cache->clazz.node_free( node, cache );
374 node = next;
375 }
376 }
377 }
378
379 FT_FREE( cache->buckets );
380
381 cache->p = 0;
382 cache->mask = 0;
383 cache->slack = 0;
384 }
385
386
387 FT_LOCAL_DEF( void )
388 FTC_Cache_Done( FTC_Cache cache )
389 {
390 ftc_cache_done( cache );
391 }
392
393
394 static void
395 ftc_cache_add( FTC_Cache cache,
396 FT_Offset hash,
397 FTC_Node node )
398 {
399 node->hash = hash;
400 node->cache_index = (FT_UShort)cache->index;
401 node->ref_count = 0;
402
403 ftc_node_hash_link( node, cache );
404 ftc_node_mru_link( node, cache->manager );
405
406 {
407 FTC_Manager manager = cache->manager;
408
409
410 manager->cur_weight += cache->clazz.node_weight( node, cache );
411
412 if ( manager->cur_weight >= manager->max_weight )
413 {
414 node->ref_count++;
415 FTC_Manager_Compress( manager );
416 node->ref_count--;
417 }
418 }
419 }
420
421
422 FT_LOCAL_DEF( FT_Error )
423 FTC_Cache_NewNode( FTC_Cache cache,
424 FT_Offset hash,
425 FT_Pointer query,
426 FTC_Node *anode )
427 {
428 FT_Error error;
429 FTC_Node node;
430
431
432 /*
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.
436 */
437
438 FTC_CACHE_TRYLOOP( cache )
439 {
440 error = cache->clazz.node_new( &node, query, cache );
441 }
442 FTC_CACHE_TRYLOOP_END( NULL )
443
444 if ( error )
445 node = NULL;
446 else
447 {
448 /* don't assume that the cache has the same number of buckets, since
449 * our allocation request might have triggered global cache flushing
450 */
451 ftc_cache_add( cache, hash, node );
452 }
453
454 *anode = node;
455 return error;
456 }
457
458
459 #ifndef FTC_INLINE
460
461 FT_LOCAL_DEF( FT_Error )
462 FTC_Cache_Lookup( FTC_Cache cache,
463 FT_Offset hash,
464 FT_Pointer query,
465 FTC_Node *anode )
466 {
467 FTC_Node* bucket;
468 FTC_Node* pnode;
469 FTC_Node node;
470 FT_Error error = FT_Err_Ok;
471 FT_Bool list_changed = FALSE;
472
473 FTC_Node_CompareFunc compare = cache->clazz.node_compare;
474
475
476 if ( !cache || !anode )
477 return FT_THROW( Invalid_Argument );
478
479 /* Go to the `top' node of the list sharing same masked hash */
480 bucket = pnode = FTC_NODE_TOP_FOR_HASH( cache, hash );
481
482 /* Lookup a node with exactly same hash and queried properties. */
483 /* NOTE: _nodcomp() may change the linked list to reduce memory. */
484 for (;;)
485 {
486 node = *pnode;
487 if ( !node )
488 goto NewNode;
489
490 if ( node->hash == hash &&
491 compare( node, query, cache, &list_changed ) )
492 break;
493
494 pnode = &node->link;
495 }
496
497 if ( list_changed )
498 {
499 /* Update bucket by modified linked list */
500 bucket = pnode = FTC_NODE_TOP_FOR_HASH( cache, hash );
501
502 /* Update pnode by modified linked list */
503 while ( *pnode != node )
504 {
505 if ( !*pnode )
506 {
507 FT_ERROR(( "FTC_Cache_Lookup: oops!!! node missing\n" ));
508 goto NewNode;
509 }
510 else
511 pnode = &(*pnode)->link;
512 }
513 }
514
515 /* Reorder the list to move the found node to the `top' */
516 if ( node != *bucket )
517 {
518 *pnode = node->link;
519 node->link = *bucket;
520 *bucket = node;
521 }
522
523 /* move to head of MRU list */
524 {
525 FTC_Manager manager = cache->manager;
526
527
528 if ( node != manager->nodes_list )
529 ftc_node_mru_up( node, manager );
530 }
531 *anode = node;
532
533 return error;
534
535 NewNode:
536 return FTC_Cache_NewNode( cache, hash, query, anode );
537 }
538
539 #endif /* !FTC_INLINE */
540
541
542 FT_LOCAL_DEF( void )
543 FTC_Cache_RemoveFaceID( FTC_Cache cache,
544 FTC_FaceID face_id )
545 {
546 FTC_Manager manager = cache->manager;
547 FTC_Node frees = NULL;
548 FT_UFast count = cache->p;
549 FT_UFast i;
550
551
552 for ( i = 0; i < count; i++ )
553 {
554 FTC_Node* pnode = cache->buckets + i;
555
556
557 for (;;)
558 {
559 FTC_Node node = *pnode;
560 FT_Bool list_changed = FALSE;
561
562
563 if ( !node )
564 break;
565
566 if ( cache->clazz.node_remove_faceid( node, face_id,
567 cache, &list_changed ) )
568 {
569 *pnode = node->link;
570 node->link = frees;
571 frees = node;
572 }
573 else
574 pnode = &node->link;
575 }
576 }
577
578 /* remove all nodes in the free list */
579 while ( frees )
580 {
581 FTC_Node node;
582
583
584 node = frees;
585 frees = node->link;
586
587 manager->cur_weight -= cache->clazz.node_weight( node, cache );
588 ftc_node_mru_unlink( node, manager );
589
590 cache->clazz.node_free( node, cache );
591
592 cache->slack++;
593 }
594
595 ftc_cache_resize( cache );
596 }
597
598
599 /* END */