OLD | NEW |
(Empty) | |
| 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 <ft2build.h> |
| 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 */ |
OLD | NEW |