1 /**************************************************************************** 2 * 3 * ftccache.c 4 * 5 * The FreeType internal cache interface (body). 6 * 7 * Copyright 2000-2018 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_Offset hash)91 ftc_get_top_node_for_hash( FTC_Cache cache, 92 FT_Offset hash ) 93 { 94 FTC_Node* pnode; 95 FT_Offset idx; 96 97 98 idx = hash & cache->mask; 99 if ( idx < cache->p ) 100 idx = 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 ) 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 ) 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 FT_LOCAL_DEF( void ) ftc_node_destroy(FTC_Node node,FTC_Manager manager)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 ) 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 ) FTC_Cache_Init(FTC_Cache cache)328 FTC_Cache_Init( FTC_Cache cache ) 329 { 330 return ftc_cache_init( cache ); 331 } 332 333 334 FT_LOCAL_DEF( FT_Error ) ftc_cache_init(FTC_Cache cache)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 FTC_Cache_Clear(FTC_Cache cache)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 ) ftc_cache_done(FTC_Cache cache)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 ) FTC_Cache_Done(FTC_Cache cache)409 FTC_Cache_Done( FTC_Cache cache ) 410 { 411 ftc_cache_done( cache ); 412 } 413 414 415 static void ftc_cache_add(FTC_Cache cache,FT_Offset hash,FTC_Node node)416 ftc_cache_add( FTC_Cache cache, 417 FT_Offset 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 ) FTC_Cache_NewNode(FTC_Cache cache,FT_Offset hash,FT_Pointer query,FTC_Node * anode)444 FTC_Cache_NewNode( FTC_Cache cache, 445 FT_Offset 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 ) FTC_Cache_Lookup(FTC_Cache cache,FT_Offset hash,FT_Pointer query,FTC_Node * anode)483 FTC_Cache_Lookup( FTC_Cache cache, 484 FT_Offset 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 || !anode ) 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 ) 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 ) 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 ) FTC_Cache_RemoveFaceID(FTC_Cache cache,FTC_FaceID face_id)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 ) 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 */ 622