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 ftc_node_mru_link(FTC_Node node,FTC_Manager manager)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 ftc_node_mru_unlink(FTC_Node node,FTC_Manager manager)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 ftc_node_mru_up(FTC_Node node,FTC_Manager manager)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* ) ftc_get_top_node_for_hash(FTC_Cache cache,FT_PtrDist hash)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 ftc_cache_resize(FTC_Cache cache)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 ftc_node_hash_unlink(FTC_Node node0,FTC_Cache cache)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 ftc_node_hash_link(FTC_Node node,FTC_Cache cache)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 #ifdef FT_CONFIG_OPTION_OLD_INTERNALS 273 FT_BASE_DEF( void ) 274 #else 275 FT_LOCAL_DEF( void ) 276 #endif ftc_node_destroy(FTC_Node node,FTC_Manager manager)277 ftc_node_destroy( FTC_Node node, 278 FTC_Manager manager ) 279 { 280 FTC_Cache cache; 281 282 283 #ifdef FT_DEBUG_ERROR 284 /* find node's cache */ 285 if ( node->cache_index >= manager->num_caches ) 286 { 287 FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" )); 288 return; 289 } 290 #endif 291 292 cache = manager->caches[node->cache_index]; 293 294 #ifdef FT_DEBUG_ERROR 295 if ( cache == NULL ) 296 { 297 FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" )); 298 return; 299 } 300 #endif 301 302 manager->cur_weight -= cache->clazz.node_weight( node, cache ); 303 304 /* remove node from mru list */ 305 ftc_node_mru_unlink( node, manager ); 306 307 /* remove node from cache's hash table */ 308 ftc_node_hash_unlink( node, cache ); 309 310 /* now finalize it */ 311 cache->clazz.node_free( node, cache ); 312 313 #if 0 314 /* check, just in case of general corruption :-) */ 315 if ( manager->num_nodes == 0 ) 316 FT_TRACE0(( "ftc_node_destroy: invalid cache node count (%d)\n", 317 manager->num_nodes )); 318 #endif 319 } 320 321 322 /*************************************************************************/ 323 /*************************************************************************/ 324 /***** *****/ 325 /***** ABSTRACT CACHE CLASS *****/ 326 /***** *****/ 327 /*************************************************************************/ 328 /*************************************************************************/ 329 330 331 FT_LOCAL_DEF( FT_Error ) FTC_Cache_Init(FTC_Cache cache)332 FTC_Cache_Init( FTC_Cache cache ) 333 { 334 return ftc_cache_init( cache ); 335 } 336 337 338 FT_LOCAL_DEF( FT_Error ) ftc_cache_init(FTC_Cache cache)339 ftc_cache_init( FTC_Cache cache ) 340 { 341 FT_Memory memory = cache->memory; 342 FT_Error error; 343 344 345 cache->p = 0; 346 cache->mask = FTC_HASH_INITIAL_SIZE - 1; 347 cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD; 348 349 (void)FT_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 ); 350 return error; 351 } 352 353 354 static void FTC_Cache_Clear(FTC_Cache cache)355 FTC_Cache_Clear( FTC_Cache cache ) 356 { 357 if ( cache && cache->buckets ) 358 { 359 FTC_Manager manager = cache->manager; 360 FT_UFast i; 361 FT_UFast count; 362 363 364 count = cache->p + cache->mask + 1; 365 366 for ( i = 0; i < count; i++ ) 367 { 368 FTC_Node *pnode = cache->buckets + i, next, node = *pnode; 369 370 371 while ( node ) 372 { 373 next = node->link; 374 node->link = NULL; 375 376 /* remove node from mru list */ 377 ftc_node_mru_unlink( node, manager ); 378 379 /* now finalize it */ 380 manager->cur_weight -= cache->clazz.node_weight( node, cache ); 381 382 cache->clazz.node_free( node, cache ); 383 node = next; 384 } 385 cache->buckets[i] = NULL; 386 } 387 ftc_cache_resize( cache ); 388 } 389 } 390 391 392 FT_LOCAL_DEF( void ) ftc_cache_done(FTC_Cache cache)393 ftc_cache_done( FTC_Cache cache ) 394 { 395 if ( cache->memory ) 396 { 397 FT_Memory memory = cache->memory; 398 399 400 FTC_Cache_Clear( cache ); 401 402 FT_FREE( cache->buckets ); 403 cache->mask = 0; 404 cache->p = 0; 405 cache->slack = 0; 406 407 cache->memory = NULL; 408 } 409 } 410 411 412 FT_LOCAL_DEF( void ) FTC_Cache_Done(FTC_Cache cache)413 FTC_Cache_Done( FTC_Cache cache ) 414 { 415 ftc_cache_done( cache ); 416 } 417 418 419 static void ftc_cache_add(FTC_Cache cache,FT_PtrDist hash,FTC_Node node)420 ftc_cache_add( FTC_Cache cache, 421 FT_PtrDist hash, 422 FTC_Node node ) 423 { 424 node->hash = hash; 425 node->cache_index = (FT_UInt16)cache->index; 426 node->ref_count = 0; 427 428 ftc_node_hash_link( node, cache ); 429 ftc_node_mru_link( node, cache->manager ); 430 431 { 432 FTC_Manager manager = cache->manager; 433 434 435 manager->cur_weight += cache->clazz.node_weight( node, cache ); 436 437 if ( manager->cur_weight >= manager->max_weight ) 438 { 439 node->ref_count++; 440 FTC_Manager_Compress( manager ); 441 node->ref_count--; 442 } 443 } 444 } 445 446 447 FT_LOCAL_DEF( FT_Error ) FTC_Cache_NewNode(FTC_Cache cache,FT_PtrDist hash,FT_Pointer query,FTC_Node * anode)448 FTC_Cache_NewNode( FTC_Cache cache, 449 FT_PtrDist hash, 450 FT_Pointer query, 451 FTC_Node *anode ) 452 { 453 FT_Error error; 454 FTC_Node node; 455 456 457 /* 458 * We use the FTC_CACHE_TRYLOOP macros to support out-of-memory 459 * errors (OOM) correctly, i.e., by flushing the cache progressively 460 * in order to make more room. 461 */ 462 463 FTC_CACHE_TRYLOOP( cache ) 464 { 465 error = cache->clazz.node_new( &node, query, cache ); 466 } 467 FTC_CACHE_TRYLOOP_END( NULL ); 468 469 if ( error ) 470 node = NULL; 471 else 472 { 473 /* don't assume that the cache has the same number of buckets, since 474 * our allocation request might have triggered global cache flushing 475 */ 476 ftc_cache_add( cache, hash, node ); 477 } 478 479 *anode = node; 480 return error; 481 } 482 483 484 #ifndef FTC_INLINE 485 486 FT_LOCAL_DEF( FT_Error ) FTC_Cache_Lookup(FTC_Cache cache,FT_PtrDist hash,FT_Pointer query,FTC_Node * anode)487 FTC_Cache_Lookup( FTC_Cache cache, 488 FT_PtrDist hash, 489 FT_Pointer query, 490 FTC_Node *anode ) 491 { 492 FTC_Node* bucket; 493 FTC_Node* pnode; 494 FTC_Node node; 495 FT_Error error = FT_Err_Ok; 496 FT_Bool list_changed = FALSE; 497 498 FTC_Node_CompareFunc compare = cache->clazz.node_compare; 499 500 501 if ( cache == NULL || anode == NULL ) 502 return FT_THROW( Invalid_Argument ); 503 504 /* Go to the `top' node of the list sharing same masked hash */ 505 bucket = pnode = FTC_NODE__TOP_FOR_HASH( cache, hash ); 506 507 /* Lookup a node with exactly same hash and queried properties. */ 508 /* NOTE: _nodcomp() may change the linked list to reduce memory. */ 509 for (;;) 510 { 511 node = *pnode; 512 if ( node == NULL ) 513 goto NewNode; 514 515 if ( node->hash == hash && 516 compare( node, query, cache, &list_changed ) ) 517 break; 518 519 pnode = &node->link; 520 } 521 522 if ( list_changed ) 523 { 524 /* Update bucket by modified linked list */ 525 bucket = pnode = FTC_NODE__TOP_FOR_HASH( cache, hash ); 526 527 /* Update pnode by modified linked list */ 528 while ( *pnode != node ) 529 { 530 if ( *pnode == NULL ) 531 { 532 FT_ERROR(( "FTC_Cache_Lookup: oops!!! node missing\n" )); 533 goto NewNode; 534 } 535 else 536 pnode = &((*pnode)->link); 537 } 538 } 539 540 /* Reorder the list to move the found node to the `top' */ 541 if ( node != *bucket ) 542 { 543 *pnode = node->link; 544 node->link = *bucket; 545 *bucket = node; 546 } 547 548 /* move to head of MRU list */ 549 { 550 FTC_Manager manager = cache->manager; 551 552 553 if ( node != manager->nodes_list ) 554 ftc_node_mru_up( node, manager ); 555 } 556 *anode = node; 557 558 return error; 559 560 NewNode: 561 return FTC_Cache_NewNode( cache, hash, query, anode ); 562 } 563 564 #endif /* !FTC_INLINE */ 565 566 567 FT_LOCAL_DEF( void ) FTC_Cache_RemoveFaceID(FTC_Cache cache,FTC_FaceID face_id)568 FTC_Cache_RemoveFaceID( FTC_Cache cache, 569 FTC_FaceID face_id ) 570 { 571 FT_UFast i, count; 572 FTC_Manager manager = cache->manager; 573 FTC_Node frees = NULL; 574 575 576 count = cache->p + cache->mask + 1; 577 for ( i = 0; i < count; i++ ) 578 { 579 FTC_Node* bucket = cache->buckets + i; 580 FTC_Node* pnode = bucket; 581 582 583 for ( ;; ) 584 { 585 FTC_Node node = *pnode; 586 FT_Bool list_changed = FALSE; 587 588 589 if ( node == NULL ) 590 break; 591 592 if ( cache->clazz.node_remove_faceid( node, face_id, 593 cache, &list_changed ) ) 594 { 595 *pnode = node->link; 596 node->link = frees; 597 frees = node; 598 } 599 else 600 pnode = &node->link; 601 } 602 } 603 604 /* remove all nodes in the free list */ 605 while ( frees ) 606 { 607 FTC_Node node; 608 609 610 node = frees; 611 frees = node->link; 612 613 manager->cur_weight -= cache->clazz.node_weight( node, cache ); 614 ftc_node_mru_unlink( node, manager ); 615 616 cache->clazz.node_free( node, cache ); 617 618 cache->slack++; 619 } 620 621 ftc_cache_resize( cache ); 622 } 623 624 625 /* END */ 626