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 */ |
600 | |