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