lib/freetype/src/cache/ftccache.i

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftccache.i                                                             */
   4 /*                                                                         */
   5 /*    FreeType template for generic cache.                                 */
   6 /*                                                                         */
   7 /*  Copyright 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 #ifndef GEN_CACHE_FAMILY_COMPARE
  20 #error "GEN_CACHE_FAMILY_COMPARE not defined in template instantiation"
  21 #endif
  22
  23 #ifndef GEN_CACHE_NODE_COMPARE
  24 #error "GEN_CACHE_NODE_COMPARE not defined in template instantiation"
  25 #endif
  26
  27
  28   static FT_Error
  29   GEN_CACHE_LOOKUP( FTC_Cache   cache,
  30                     FTC_Query   query,
  31                     FTC_Node   *anode )
  32   {
  33     FT_LruNode  lru;
  34     FTC_Family  family;
  35     FT_UFast    hash;
  36
  37
  38     query->hash   = 0;
  39     query->family = NULL;
  40
  41     /* XXX: we break encapsulation for the sake of speed! */
  42     {
  43       /* first of all, find the relevant family */
  44       FT_LruList  list  = cache->families;
  45       FT_LruNode  fam, *pfam;
  46
  47
  48       pfam = &list->nodes;
  49       for (;;)
  50       {
  51         fam = *pfam;
  52         if ( fam == NULL )
  53           goto Normal;
  54
  55         if ( GEN_CACHE_FAMILY_COMPARE( fam, query, list->data ) )
  56           break;
  57
  58         pfam = &fam->next;
  59       }
  60
  61       FT_ASSERT( fam != NULL );
  62
  63       /* move to top of list when needed */
  64       if ( fam != list->nodes )
  65       {
  66         *pfam       = fam->next;
  67         fam->next   = list->nodes;
  68         list->nodes = fam;
  69       }
  70
  71       lru = fam;
  72     }
  73
  74     {
  75       FTC_Node  node, *pnode, *bucket;
  76
  77
  78       family = (FTC_Family)lru;
  79       hash   = query->hash;
  80
  81       {
  82         FT_UInt  idx;
  83
  84
  85         idx = hash & cache->mask;
  86         if ( idx < cache->p )
  87           idx = hash & ( cache->mask * 2 + 1 );
  88
  89         bucket  = cache->buckets + idx;
  90       }
  91
  92       pnode = bucket;
  93
  94       for ( ;; )
  95       {
  96         node = *pnode;
  97         if ( node == NULL )
  98           goto Normal;
  99
 100         if ( node->hash == hash                            &&
 101              (FT_UInt)node->fam_index == family->fam_index &&
 102              GEN_CACHE_NODE_COMPARE( node, query, cache )  )
 103         {
 104           /* we place the following out of the loop to make it */
 105           /* as small as possible...                           */
 106           goto Found;
 107         }
 108
 109         pnode = &node->link;
 110       }
 111
 112   Normal:
 113       return ftc_cache_lookup( cache, query, anode );
 114
 115   Found:
 116       /* move to head of bucket list */
 117       if ( pnode != bucket )
 118       {
 119         *pnode     = node->link;
 120         node->link = *bucket;
 121         *bucket    = node;
 122       }
 123
 124       /* move to head of MRU list */
 125       if ( node != cache->manager->nodes_list )
 126       {
 127         /* XXX: again, this is an inlined version of ftc_node_mru_up */
 128         FTC_Manager  manager = cache->manager;
 129         FTC_Node     first   = manager->nodes_list;
 130         FTC_Node     prev = node->mru_prev;
 131         FTC_Node     next = node->mru_next;
 132         FTC_Node     last;
 133
 134
 135         prev->mru_next = next;
 136         next->mru_prev = prev;
 137
 138         last            = first->mru_prev;
 139         node->mru_next  = first;
 140         node->mru_prev  = last;
 141         first->mru_prev = node;
 142         last->mru_next  = node;
 143
 144         manager->nodes_list = node;
 145       }
 146
 147       *anode = node;
 148       return 0;
 149     }
 150   }
 151
 152 #undef GEN_CACHE_NODE_COMPARE
 153 #undef GEN_CACHE_FAMILY_COMPARE
 154 #undef GEN_CACHE_LOOKUP
 155
 156
 157 /* END */