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