| /***************************************************************************/ |
| /* */ |
| /* ftccache.i */ |
| /* */ |
| /* FreeType template for generic cache. */ |
| /* */ |
| /* Copyright 2002 by */ |
| /* David Turner, Robert Wilhelm, and Werner Lemberg. */ |
| /* */ |
| /* This file is part of the FreeType project, and may only be used, */ |
| /* modified, and distributed under the terms of the FreeType project */ |
| /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ |
| /* this file you indicate that you have read the license and */ |
| /* understand and accept it fully. */ |
| /* */ |
| /***************************************************************************/ |
| |
| |
| #ifndef GEN_CACHE_FAMILY_COMPARE |
| #error "GEN_CACHE_FAMILY_COMPARE not defined in template instantiation" |
| #endif |
| |
| #ifndef GEN_CACHE_NODE_COMPARE |
| #error "GEN_CACHE_NODE_COMPARE not defined in template instantiation" |
| #endif |
| |
| |
| static FT_Error |
| GEN_CACHE_LOOKUP( FTC_Cache cache, |
| FTC_Query query, |
| FTC_Node *anode ) |
| { |
| FT_LruNode lru; |
| FTC_Family family; |
| FT_UFast hash; |
| |
| |
| query->hash = 0; |
| query->family = NULL; |
| |
| /* XXX: we break encapsulation for the sake of speed! */ |
| { |
| /* first of all, find the relevant family */ |
| FT_LruList list = cache->families; |
| FT_LruNode fam, *pfam; |
| |
| |
| pfam = &list->nodes; |
| for (;;) |
| { |
| fam = *pfam; |
| if ( fam == NULL ) |
| goto Normal; |
| |
| if ( GEN_CACHE_FAMILY_COMPARE( fam, query, list->data ) ) |
| break; |
| |
| pfam = &fam->next; |
| } |
| |
| FT_ASSERT( fam != NULL ); |
| |
| /* move to top of list when needed */ |
| if ( fam != list->nodes ) |
| { |
| *pfam = fam->next; |
| fam->next = list->nodes; |
| list->nodes = fam; |
| } |
| |
| lru = fam; |
| } |
| |
| { |
| FTC_Node node, *pnode, *bucket; |
| |
| |
| family = (FTC_Family)lru; |
| hash = query->hash; |
| |
| #ifdef FTC_CACHE_USE_LINEAR_HASHING |
| { |
| FT_UInt index; |
| |
| |
| index = hash & cache->mask; |
| if ( index < cache->p ) |
| index = hash & ( cache->mask * 2 + 1 ); |
| |
| bucket = cache->buckets + index; |
| } |
| #else |
| bucket = cache->buckets + ( hash % cache->size ); |
| #endif |
| |
| #ifdef FT_DEBUG_LEVEL_ERROR |
| if ( query->family != family || |
| family->fam_index >= cache->manager->families.size ) |
| { |
| FT_ERROR(( |
| "ftc_cache_lookup: invalid query (bad 'family' field)\n" )); |
| return FTC_Err_Invalid_Argument; |
| } |
| #endif |
| |
| pnode = bucket; |
| |
| for ( ;; ) |
| { |
| node = *pnode; |
| if ( node == NULL ) |
| goto Normal; |
| |
| if ( node->hash == hash && |
| (FT_UInt)node->fam_index == family->fam_index && |
| GEN_CACHE_NODE_COMPARE( node, query, cache ) ) |
| { |
| /* we place the following out of the loop to make it */ |
| /* as small as possible... */ |
| goto Found; |
| } |
| |
| pnode = &node->link; |
| } |
| |
| Normal: |
| return ftc_cache_lookup( cache, query, anode ); |
| |
| Found: |
| /* move to head of bucket list */ |
| if ( pnode != bucket ) |
| { |
| *pnode = node->link; |
| node->link = *bucket; |
| *bucket = node; |
| } |
| |
| /* move to head of MRU list */ |
| if ( node != cache->manager->nodes_list ) |
| { |
| /* XXX: again, this is an inlined version of ftc_node_mru_up */ |
| FTC_Manager manager = cache->manager; |
| FTC_Node first = manager->nodes_list; |
| FTC_Node prev = node->mru_prev; |
| FTC_Node next = node->mru_next; |
| FTC_Node last; |
| |
| |
| prev->mru_next = next; |
| next->mru_prev = prev; |
| |
| last = first->mru_prev; |
| node->mru_next = first; |
| node->mru_prev = last; |
| first->mru_prev = node; |
| last->mru_next = node; |
| |
| manager->nodes_list = node; |
| } |
| |
| *anode = node; |
| return 0; |
| } |
| } |
| |
| #undef GEN_CACHE_NODE_COMPARE |
| #undef GEN_CACHE_FAMILY_COMPARE |
| #undef GEN_CACHE_LOOKUP |
| |
| |
| /* END */ |