1 /***************************************************************************/ 2 /* */ 3 /* ftccache.c */ 4 /* */ 5 /* The FreeType internal cache interface (body). */ 6 /* */ 7 /* Copyright 2000-2001, 2002 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 FT_CACHE_MANAGER_H 21 #include FT_INTERNAL_OBJECTS_H 22 #include FT_INTERNAL_DEBUG_H 23 24 #include "ftcerror.h" 25 26 27 #define FTC_HASH_MAX_LOAD 2 28 #define FTC_HASH_MIN_LOAD 1 29 #define FTC_HASH_SUB_LOAD ( FTC_HASH_MAX_LOAD - FTC_HASH_MIN_LOAD ) 30 31 /* this one _must_ be a power of 2! */ 32 #define FTC_HASH_INITIAL_SIZE 8 33 34 35 /*************************************************************************/ 36 /*************************************************************************/ 37 /***** *****/ 38 /***** CACHE NODE DEFINITIONS *****/ 39 /***** *****/ 40 /*************************************************************************/ 41 /*************************************************************************/ 42 43 FT_EXPORT_DEF( void ) ftc_node_done(FTC_Node node,FTC_Cache cache)44 ftc_node_done( FTC_Node node, 45 FTC_Cache cache ) 46 { 47 FTC_Family family; 48 FTC_FamilyEntry entry; 49 50 51 entry = cache->manager->families.entries + node->fam_index; 52 family = entry->family; 53 54 /* remove from parent set table - eventually destroy the set */ 55 if ( --family->num_nodes == 0 ) 56 FT_LruList_Remove( cache->families, (FT_LruNode) family ); 57 } 58 59 60 /* add a new node to the head of the manager's circular MRU list */ 61 static void ftc_node_mru_link(FTC_Node node,FTC_Manager manager)62 ftc_node_mru_link( FTC_Node node, 63 FTC_Manager manager ) 64 { 65 FTC_Node first = manager->nodes_list; 66 67 68 if ( first ) 69 { 70 FTC_Node last = first->mru_prev; 71 72 73 FT_ASSERT( last->mru_next == first ); 74 75 node->mru_prev = last; 76 node->mru_next = first; 77 78 last->mru_next = node; 79 first->mru_prev = node; 80 } 81 else 82 { 83 FT_ASSERT( manager->num_nodes == 0 ); 84 85 node->mru_next = node; 86 node->mru_prev = node; 87 } 88 89 manager->nodes_list = node; 90 manager->num_nodes++; 91 } 92 93 94 /* remove a node from the manager's MRU list */ 95 static void ftc_node_mru_unlink(FTC_Node node,FTC_Manager manager)96 ftc_node_mru_unlink( FTC_Node node, 97 FTC_Manager manager ) 98 { 99 FTC_Node first = manager->nodes_list; 100 FTC_Node prev = node->mru_prev; 101 FTC_Node next = node->mru_next; 102 103 104 FT_ASSERT( first != NULL && manager->num_nodes > 0 ); 105 FT_ASSERT( next->mru_prev == node ); 106 FT_ASSERT( prev->mru_next == node ); 107 108 next->mru_prev = prev; 109 prev->mru_next = next; 110 111 if ( node == first ) 112 { 113 /* this is the last node in the list; update its head pointer */ 114 if ( node == next ) 115 manager->nodes_list = NULL; 116 else 117 manager->nodes_list = next; 118 } 119 120 node->mru_next = NULL; 121 node->mru_prev = NULL; 122 manager->num_nodes--; 123 } 124 125 126 /* move a node to the head of the manager's MRU list */ 127 static void ftc_node_mru_up(FTC_Node node,FTC_Manager manager)128 ftc_node_mru_up( FTC_Node node, 129 FTC_Manager manager ) 130 { 131 FTC_Node first = manager->nodes_list; 132 133 134 if ( node != first ) 135 { 136 FTC_Node prev = node->mru_prev; 137 FTC_Node next = node->mru_next; 138 FTC_Node last; 139 140 141 prev->mru_next = next; 142 next->mru_prev = prev; 143 144 last = first->mru_prev; 145 node->mru_next = first; 146 node->mru_prev = last; 147 first->mru_prev = node; 148 last->mru_next = node; 149 150 manager->nodes_list = node; 151 } 152 } 153 154 155 /* remove a node from its cache's hash table */ 156 static FT_Error ftc_node_hash_unlink(FTC_Node node,FTC_Cache cache)157 ftc_node_hash_unlink( FTC_Node node, 158 FTC_Cache cache ) 159 { 160 FT_Error error = 0; 161 FTC_Node *pnode; 162 FT_UInt idx, num_buckets; 163 164 165 idx = (FT_UInt)( node->hash & cache->mask ); 166 if ( idx < cache->p ) 167 idx = (FT_UInt)( node->hash & ( 2 * cache->mask + 1 ) ); 168 169 pnode = cache->buckets + idx; 170 171 for (;;) 172 { 173 if ( *pnode == NULL ) 174 { 175 FT_ERROR(( "ftc_node_hash_unlink: unknown node!\n" )); 176 return FT_Err_Ok; 177 } 178 179 if ( *pnode == node ) 180 { 181 *pnode = node->link; 182 node->link = NULL; 183 break; 184 } 185 186 pnode = &(*pnode)->link; 187 } 188 189 num_buckets = ( cache->p + cache->mask + 1 ); 190 191 if ( ++cache->slack > (FT_Long)num_buckets * FTC_HASH_SUB_LOAD ) 192 { 193 FT_UInt p = cache->p; 194 FT_UInt mask = cache->mask; 195 FT_UInt old_index = p + mask; 196 FTC_Node* pold; 197 198 199 FT_ASSERT( old_index >= FTC_HASH_INITIAL_SIZE ); 200 201 if ( p == 0 ) 202 { 203 FT_Memory memory = cache->memory; 204 205 206 cache->mask >>= 1; 207 p = cache->mask; 208 209 if ( FT_RENEW_ARRAY( cache->buckets, ( mask + 1 ) * 2, (mask+1) ) ) 210 { 211 FT_ERROR(( "ftc_node_hash_unlink: couldn't shunk buckets!\n" )); 212 goto Exit; 213 } 214 } 215 else 216 p--; 217 218 pnode = cache->buckets + p; 219 while ( *pnode ) 220 pnode = &(*pnode)->link; 221 222 pold = cache->buckets + old_index; 223 *pnode = *pold; 224 *pold = NULL; 225 226 cache->slack -= FTC_HASH_MAX_LOAD; 227 cache->p = p; 228 } 229 230 Exit: 231 return error; 232 } 233 234 235 236 /* add a node to the "top" of its cache's hash table */ 237 static FT_Error ftc_node_hash_link(FTC_Node node,FTC_Cache cache)238 ftc_node_hash_link( FTC_Node node, 239 FTC_Cache cache ) 240 { 241 FTC_Node *pnode; 242 FT_UInt idx; 243 FT_Error error = 0; 244 245 246 idx = (FT_UInt)( node->hash & cache->mask ); 247 if ( idx < cache->p ) 248 idx = (FT_UInt)( node->hash & (2 * cache->mask + 1 ) ); 249 250 pnode = cache->buckets + idx; 251 252 node->link = *pnode; 253 *pnode = node; 254 255 if ( --cache->slack < 0 ) 256 { 257 FT_UInt p = cache->p; 258 FT_UInt mask = cache->mask; 259 FTC_Node new_list; 260 261 262 /* split a single bucket */ 263 new_list = NULL; 264 pnode = cache->buckets + p; 265 266 for (;;) 267 { 268 node = *pnode; 269 if ( node == NULL ) 270 break; 271 272 if ( node->hash & ( mask + 1 ) ) 273 { 274 *pnode = node->link; 275 node->link = new_list; 276 new_list = node; 277 } 278 else 279 pnode = &node->link; 280 } 281 282 cache->buckets[p + mask + 1] = new_list; 283 284 cache->slack += FTC_HASH_MAX_LOAD; 285 286 if ( p >= mask ) 287 { 288 FT_Memory memory = cache->memory; 289 290 291 if ( FT_RENEW_ARRAY( cache->buckets, 292 ( mask + 1 ) * 2, ( mask + 1 ) * 4 ) ) 293 { 294 FT_ERROR(( "ftc_node_hash_link: couldn't expand buckets!\n" )); 295 goto Exit; 296 } 297 298 cache->mask = 2 * mask + 1; 299 cache->p = 0; 300 } 301 else 302 cache->p = p + 1; 303 } 304 305 Exit: 306 return error; 307 } 308 309 310 311 312 /* remove a node from the cache manager */ 313 FT_EXPORT_DEF( void ) ftc_node_destroy(FTC_Node node,FTC_Manager manager)314 ftc_node_destroy( FTC_Node node, 315 FTC_Manager manager ) 316 { 317 FT_Memory memory = manager->library->memory; 318 FTC_Cache cache; 319 FTC_FamilyEntry entry; 320 FTC_Cache_Class clazz; 321 322 323 #ifdef FT_DEBUG_ERROR 324 /* find node's cache */ 325 if ( node->fam_index >= manager->families.count ) 326 { 327 FT_ERROR(( "ftc_node_destroy: invalid node handle\n" )); 328 return; 329 } 330 #endif 331 332 entry = manager->families.entries + node->fam_index; 333 cache = entry->cache; 334 335 #ifdef FT_DEBUG_ERROR 336 if ( cache == NULL ) 337 { 338 FT_ERROR(( "ftc_node_destroy: invalid node handle\n" )); 339 return; 340 } 341 #endif 342 343 clazz = cache->clazz; 344 345 manager->cur_weight -= clazz->node_weight( node, cache ); 346 347 /* remove node from mru list */ 348 ftc_node_mru_unlink( node, manager ); 349 350 /* remove node from cache's hash table */ 351 ftc_node_hash_unlink( node, cache ); 352 353 /* now finalize it */ 354 if ( clazz->node_done ) 355 clazz->node_done( node, cache ); 356 357 FT_FREE( node ); 358 359 /* check, just in case of general corruption :-) */ 360 if ( manager->num_nodes == 0 ) 361 FT_ERROR(( "ftc_node_destroy: invalid cache node count! = %d\n", 362 manager->num_nodes )); 363 } 364 365 366 /*************************************************************************/ 367 /*************************************************************************/ 368 /***** *****/ 369 /***** CACHE FAMILY DEFINITIONS *****/ 370 /***** *****/ 371 /*************************************************************************/ 372 /*************************************************************************/ 373 374 375 FT_EXPORT_DEF( FT_Error ) ftc_family_init(FTC_Family family,FTC_Query query,FTC_Cache cache)376 ftc_family_init( FTC_Family family, 377 FTC_Query query, 378 FTC_Cache cache ) 379 { 380 FT_Error error; 381 FTC_Manager manager = cache->manager; 382 FT_Memory memory = manager->library->memory; 383 FTC_FamilyEntry entry; 384 385 386 family->cache = cache; 387 family->num_nodes = 0; 388 389 /* now add to manager's family table */ 390 error = ftc_family_table_alloc( &manager->families, memory, &entry ); 391 if ( !error ) 392 { 393 entry->cache = cache; 394 entry->family = family; 395 family->fam_index = entry->index; 396 397 query->family = family; /* save family in query */ 398 } 399 400 return error; 401 } 402 403 404 FT_EXPORT_DEF( void ) ftc_family_done(FTC_Family family)405 ftc_family_done( FTC_Family family ) 406 { 407 FTC_Manager manager = family->cache->manager; 408 409 410 /* remove from manager's family table */ 411 ftc_family_table_free( &manager->families, family->fam_index ); 412 } 413 414 415 /*************************************************************************/ 416 /*************************************************************************/ 417 /***** *****/ 418 /***** ABSTRACT CACHE CLASS *****/ 419 /***** *****/ 420 /*************************************************************************/ 421 /*************************************************************************/ 422 423 424 425 FT_EXPORT_DEF( FT_Error ) ftc_cache_init(FTC_Cache cache)426 ftc_cache_init( FTC_Cache cache ) 427 { 428 FT_Memory memory = cache->memory; 429 FTC_Cache_Class clazz = cache->clazz; 430 FT_Error error; 431 432 433 cache->p = 0; 434 cache->mask = FTC_HASH_INITIAL_SIZE - 1; 435 cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD; 436 437 if ( FT_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 ) ) 438 goto Exit; 439 440 /* now, initialize the lru list of families for this cache */ 441 if ( clazz->family_size > 0 ) 442 { 443 FT_LruList_ClassRec* lru_class = &cache->family_class; 444 445 446 lru_class->list_size = sizeof( FT_LruListRec ); 447 lru_class->list_init = NULL; 448 lru_class->list_done = NULL; 449 450 lru_class->node_size = clazz->family_size; 451 lru_class->node_init = (FT_LruNode_InitFunc) clazz->family_init; 452 lru_class->node_done = (FT_LruNode_DoneFunc) clazz->family_done; 453 lru_class->node_flush = (FT_LruNode_FlushFunc) NULL; 454 lru_class->node_compare = (FT_LruNode_CompareFunc)clazz->family_compare; 455 456 error = FT_LruList_New( (FT_LruList_Class) lru_class, 457 0, /* max items == 0 => unbounded list */ 458 cache, 459 memory, 460 &cache->families ); 461 if ( error ) 462 FT_FREE( cache->buckets ); 463 } 464 465 Exit: 466 return error; 467 } 468 469 470 FT_EXPORT_DEF( void ) ftc_cache_clear(FTC_Cache cache)471 ftc_cache_clear( FTC_Cache cache ) 472 { 473 if ( cache ) 474 { 475 FT_Memory memory = cache->memory; 476 FTC_Cache_Class clazz = cache->clazz; 477 FTC_Manager manager = cache->manager; 478 FT_UFast i; 479 FT_UInt count; 480 481 count = cache->p + cache->mask + 1; 482 483 for ( i = 0; i < count; i++ ) 484 { 485 FTC_Node *pnode = cache->buckets + i, next, node = *pnode; 486 487 488 while ( node ) 489 { 490 next = node->link; 491 node->link = NULL; 492 493 /* remove node from mru list */ 494 ftc_node_mru_unlink( node, manager ); 495 496 /* now finalize it */ 497 manager->cur_weight -= clazz->node_weight( node, cache ); 498 499 if ( clazz->node_done ) 500 clazz->node_done( node, cache ); 501 502 FT_FREE( node ); 503 node = next; 504 } 505 cache->buckets[i] = NULL; 506 } 507 508 cache->p = 0; 509 510 /* destroy the families */ 511 if ( cache->families ) 512 FT_LruList_Reset( cache->families ); 513 } 514 } 515 516 517 FT_EXPORT_DEF( void ) ftc_cache_done(FTC_Cache cache)518 ftc_cache_done( FTC_Cache cache ) 519 { 520 if ( cache ) 521 { 522 FT_Memory memory = cache->memory; 523 524 525 ftc_cache_clear( cache ); 526 527 FT_FREE( cache->buckets ); 528 cache->mask = 0; 529 cache->slack = 0; 530 531 if ( cache->families ) 532 { 533 FT_LruList_Destroy( cache->families ); 534 cache->families = NULL; 535 } 536 } 537 } 538 539 540 /* Look up a node in "top" of its cache's hash table. */ 541 /* If not found, create a new node. */ 542 /* */ 543 FT_EXPORT_DEF( FT_Error ) ftc_cache_lookup(FTC_Cache cache,FTC_Query query,FTC_Node * anode)544 ftc_cache_lookup( FTC_Cache cache, 545 FTC_Query query, 546 FTC_Node *anode ) 547 { 548 FT_Error error = FT_Err_Ok; 549 FT_LruNode lru; 550 551 552 if ( !cache || !query || !anode ) 553 return FTC_Err_Invalid_Argument; 554 555 *anode = NULL; 556 557 query->hash = 0; 558 query->family = NULL; 559 560 /* XXX: we break encapsulation for the sake of speed! */ 561 { 562 /* first of all, find the relevant family */ 563 FT_LruList list = cache->families; 564 FT_LruNode fam, *pfam; 565 FT_LruNode_CompareFunc compare = list->clazz->node_compare; 566 567 pfam = &list->nodes; 568 for (;;) 569 { 570 fam = *pfam; 571 if ( fam == NULL ) 572 { 573 error = FT_LruList_Lookup( list, query, &lru ); 574 if ( error ) 575 goto Exit; 576 577 goto Skip; 578 } 579 580 if ( compare( fam, query, list->data ) ) 581 break; 582 583 pfam = &fam->next; 584 } 585 586 FT_ASSERT( fam != NULL ); 587 588 /* move to top of list when needed */ 589 if ( fam != list->nodes ) 590 { 591 *pfam = fam->next; 592 fam->next = list->nodes; 593 list->nodes = fam; 594 } 595 596 lru = fam; 597 598 Skip: 599 ; 600 } 601 602 { 603 FTC_Family family = (FTC_Family) lru; 604 FT_UFast hash = query->hash; 605 FTC_Node* bucket; 606 FT_UInt idx; 607 608 609 idx = hash & cache->mask; 610 if ( idx < cache->p ) 611 idx = hash & ( cache->mask * 2 + 1 ); 612 613 bucket = cache->buckets + idx; 614 615 616 if ( query->family != family || 617 family->fam_index >= cache->manager->families.size ) 618 { 619 FT_ERROR(( 620 "ftc_cache_lookup: invalid query (bad 'family' field)\n" )); 621 return FTC_Err_Invalid_Argument; 622 } 623 624 if ( *bucket ) 625 { 626 FTC_Node* pnode = bucket; 627 FTC_Node_CompareFunc compare = cache->clazz->node_compare; 628 629 630 for ( ;; ) 631 { 632 FTC_Node node; 633 634 635 node = *pnode; 636 if ( node == NULL ) 637 break; 638 639 if ( node->hash == hash && 640 (FT_UInt)node->fam_index == family->fam_index && 641 compare( node, query, cache ) ) 642 { 643 /* move to head of bucket list */ 644 if ( pnode != bucket ) 645 { 646 *pnode = node->link; 647 node->link = *bucket; 648 *bucket = node; 649 } 650 651 /* move to head of MRU list */ 652 if ( node != cache->manager->nodes_list ) 653 ftc_node_mru_up( node, cache->manager ); 654 655 *anode = node; 656 goto Exit; 657 } 658 659 pnode = &node->link; 660 } 661 } 662 663 /* didn't find a node, create a new one */ 664 { 665 FTC_Cache_Class clazz = cache->clazz; 666 FTC_Manager manager = cache->manager; 667 FT_Memory memory = cache->memory; 668 FTC_Node node; 669 670 671 if ( FT_ALLOC( node, clazz->node_size ) ) 672 goto Exit; 673 674 node->fam_index = (FT_UShort) family->fam_index; 675 node->hash = query->hash; 676 node->ref_count = 0; 677 678 error = clazz->node_init( node, query, cache ); 679 if ( error ) 680 { 681 FT_FREE( node ); 682 goto Exit; 683 } 684 685 error = ftc_node_hash_link( node, cache ); 686 if ( error ) 687 { 688 clazz->node_done( node, cache ); 689 FT_FREE( node ); 690 goto Exit; 691 } 692 693 ftc_node_mru_link( node, cache->manager ); 694 695 cache->manager->cur_weight += clazz->node_weight( node, cache ); 696 697 /* now try to compress the node pool when necessary */ 698 if ( manager->cur_weight >= manager->max_weight ) 699 { 700 node->ref_count++; 701 FTC_Manager_Compress( manager ); 702 node->ref_count--; 703 } 704 705 *anode = node; 706 } 707 } 708 709 Exit: 710 return error; 711 } 712 713 714 /* END */ 715