* include/freetype/cache/ftccache.h, src/cache/ftccache.c,

          src/cache/ftccache.i, src/cache/ftcsbits.c: adding various
          experimental optimisations to the cache manager

        * src/type42/t42parse.c: removing duplicate function

5 files changed, 344 insertions, 130 deletions

diff --git a/ChangeLog b/ChangeLog
index 13166b7e9..c7c28cc0e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
 2002-06-07  Graham Asher  <graham.asher@btinternet.com>
 
+        * include/freetype/cache/ftccache.h, src/cache/ftccache.c,
+          src/cache/ftccache.i, src/cache/ftcsbits.c: adding various
+          experimental optimisations to the cache manager
+
+        * src/type42/t42parse.c: removing duplicate function
+
         * src/base/ftobjs.c (FT_Render_Glyph_Internal): changed definition
           from FT_EXPORT_DEF to FT_BASE_DEF
 
diff --git a/include/freetype/cache/ftccache.h b/include/freetype/cache/ftccache.h
index 97d8bc864..9da989116 100644
--- a/include/freetype/cache/ftccache.h
+++ b/include/freetype/cache/ftccache.h
@@ -20,6 +20,12 @@
 #define __FTCCACHE_H__
 
 
+/* define to allow cache lookup inlining */
+#undef   FTC_CACHE_USE_INLINE
+
+/* define to use linear hash table */
+#undef   FTC_CACHE_USE_LINEAR_HASHING
+
 FT_BEGIN_HEADER
 
   /* handle to cache object */
@@ -174,8 +180,14 @@ FT_BEGIN_HEADER
     FT_UInt              cache_index;  /* in manager's table         */
     FT_Pointer           cache_data;   /* used by cache node methods */
 
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+    FT_UFast             p;
+    FT_UFast             mask;
+    FT_Long              slack;
+#else
     FT_UFast             nodes;
     FT_UFast             size;
+#endif
     FTC_Node*            buckets;
 
     FT_LruList_ClassRec  family_class;
@@ -290,7 +302,6 @@ FT_BEGIN_HEADER
 
  /* */
 
-
 FT_END_HEADER
 
 
diff --git a/src/cache/ftccache.c b/src/cache/ftccache.c
index 3a3ef5b43..da0456296 100644
--- a/src/cache/ftccache.c
+++ b/src/cache/ftccache.c
@@ -23,6 +23,21 @@
 
 #include "ftcerror.h"
 
+/* define for level-1 optimisations */
+#undef   OPT1
+
+
+
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+
+#define  FTC_HASH_MAX_LOAD  2
+#define  FTC_HASH_MIN_LOAD  1
+#define  FTC_HASH_SUB_LOAD  (FTC_HASH_MAX_LOAD-FTC_HASH_MIN_LOAD)
+
+/* this one _must_ be a power of 2 !! */
+#define  FTC_HASH_INITIAL_SIZE  8
+
+#endif /* FTC_CACHE_USE_LINEAR_HASHING */
 
   /*************************************************************************/
   /*************************************************************************/
@@ -59,11 +74,13 @@
 
     if ( first )
     {
-      node->mru_prev = first->mru_prev;
+      FTC_Node  last = first->mru_prev;
+      
+      node->mru_prev = last;
       node->mru_next = first;
 
-      first->mru_prev->mru_next = node;
-      first->mru_prev           = node;
+      last->mru_next  = node;
+      first->mru_prev = node;
     }
     else
     {
@@ -114,11 +131,103 @@
 
     if ( node != first )
     {
-      ftc_node_mru_unlink( node, manager );
-      ftc_node_mru_link( node, manager );
+      FTC_Node  prev = node->mru_prev;
+      FTC_Node  next = node->mru_next;
+      FTC_Node  last = first->mru_prev;
+
+      prev->mru_next = next;
+      next->mru_prev = prev;
+
+      node->mru_next  = first;
+      node->mru_prev  = last;
+      first->mru_prev = node;
+      last->mru_next  = node;
+
+      manager->nodes_list = node;
+    }
+  }
+
+
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+
+  /* remove a node from its cache's hash table */
+  static FT_Error
+  ftc_node_hash_unlink( FTC_Node   node,
+                        FTC_Cache  cache )
+  {
+    FT_Error   error = 0;
+    FTC_Node  *pnode;
+    FT_UInt    index, num_buckets;
+
+    index = (FT_UInt)( node->hash & cache->mask );
+    if ( index < cache->p )
+      index = (FT_UInt)( node->hash & (2*cache->mask+1) );
+
+    pnode = cache->buckets + index;
+
+    for (;;)
+    {
+      if ( *pnode == NULL )
+      {
+        FT_ERROR(( "FreeType.cache.hash_unlink: unknown node!\n" ));
+        return 0;
+      }
+
+      if ( *pnode == node )
+      {
+        *pnode     = node->link;
+        node->link = NULL;
+        break;
+      }
+
+      pnode = &(*pnode)->link;
+    }
+
+    num_buckets = ( cache->p + cache->mask + 1) ;
+
+    if ( ++ cache->slack > (FT_Long)num_buckets*FTC_HASH_SUB_LOAD )
+    {
+      FT_UInt    p         = cache->p;
+      FT_UInt    mask      = cache->mask;
+      FT_UInt    old_index = p + mask;
+      FTC_Node*  pold;
+
+      FT_ASSERT( old_index >= FTC_HASH_INITIAL_SIZE );
+
+      if ( p == 0 )
+      {
+        FT_Memory  memory = cache->memory;
+
+
+        cache->mask >>= 1;
+        p             = cache->mask;
+
+        if ( FT_RENEW_ARRAY( cache->buckets, (mask+1)*2, (mask) ) )
+        {
+          FT_ERROR(( "FreeType.cache.hash_unlink: couldn't shunk buckets !\n" ));
+          goto Exit;
+        }
+      }
+      else
+        p--;
+
+      pnode = cache->buckets + p;
+      while ( *pnode )
+        pnode = &(*pnode)->link;
+
+      pold   = cache->buckets + old_index;
+      *pnode = *pold;
+      *pold  = NULL;
+
+      cache->slack -= FTC_HASH_MAX_LOAD;
+      cache->p      = p;
     }
+
+  Exit:
+    return error;
   }
 
+#else /* !FTC_CACHE_USE_LINEAR_HASHING */
 
   /* remove a node from its cache's hash table */
   static void
@@ -127,7 +236,6 @@
   {
     FTC_Node  *pnode = cache->buckets + ( node->hash % cache->size );
 
-
     for (;;)
     {
       if ( *pnode == NULL )
@@ -149,6 +257,81 @@
     }
   }
 
+#endif /* !FTC_CACHE_USE_LINEAR_HASHING */
+
+
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+
+  /* add a node to the "top" of its cache's hash table */
+  static FT_Error
+  ftc_node_hash_link( FTC_Node   node,
+                      FTC_Cache  cache )
+  {
+    FTC_Node  *pnode;
+    FT_UInt    index;
+    FT_Error   error = 0;
+
+    index = (FT_UInt)( node->hash & cache->mask );
+    if ( index < cache->p )
+      index = (FT_UInt)( node->hash & (2*cache->mask+1) );
+
+    pnode = cache->buckets + index;
+
+    node->link = *pnode;
+    *pnode     = node;
+
+    if ( --cache->slack < 0 )
+    {
+      FT_UInt    p     = cache->p;
+      FT_UInt    mask  = cache->mask;
+      FTC_Node   new_list;
+
+      /* split a single bucket */
+      new_list = NULL;
+      pnode    = cache->buckets + p;
+      for (;;)
+      {
+        node = *pnode;
+        if ( node == NULL )
+          break;
+
+        if ( node->hash & (mask+1) )
+        {
+          *pnode     = node->link;
+          node->link = new_list;
+          new_list   = node;
+        }
+        else
+          pnode = &node->link;
+      }
+
+      cache->buckets[ p + mask + 1 ] = new_list;
+
+      cache->slack += FTC_HASH_MAX_LOAD;
+
+      if ( p >= mask )
+      {
+        FT_Memory  memory = cache->memory;
+
+
+        if ( FT_RENEW_ARRAY( cache->buckets, (mask+1)*2, (mask+1)*4 ) )
+        {
+          FT_ERROR(( "FreeType.cache.hash_unlink: couldn't expand buckets !\n" ));
+          goto Exit;
+        }
+
+        cache->mask = 2*mask + 1;
+        cache->p    = 0;
+      }
+      else
+        cache->p = p + 1;
+    }
+
+  Exit:
+    return error;
+  }
+
+#else /* !FTC_CACHE_USE_LINEAR_HASHING */
 
   /* add a node to the "top" of its cache's hash table */
   static void
@@ -157,13 +340,15 @@
   {
     FTC_Node  *pnode = cache->buckets + ( node->hash % cache->size );
 
-
     node->link = *pnode;
     *pnode     = node;
 
     cache->nodes++;
   }
 
+#endif /* !FTC_CACHE_USE_LINEAR_HASHING */
+
+
 
   /* remove a node from the cache manager */
   FT_EXPORT_DEF( void )
@@ -276,6 +461,11 @@
   /*************************************************************************/
   /*************************************************************************/
 
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+
+
+#else /* !FTC_CACHE_USE_LINEAR_HASHING */
+
 #define FTC_PRIMES_MIN  7
 #define FTC_PRIMES_MAX  13845163
 
@@ -388,6 +578,7 @@
     }
   }
 
+#endif /* !FTC_CACHE_USE_LINEAR_HASHING */
 
   FT_EXPORT_DEF( FT_Error )
   ftc_cache_init( FTC_Cache  cache )
@@ -397,12 +588,24 @@
     FT_Error         error;
 
 
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+
+    cache->p     = 0;
+    cache->mask  = FTC_HASH_INITIAL_SIZE-1;
+    cache->slack = FTC_HASH_INITIAL_SIZE*FTC_HASH_MAX_LOAD;
+
+    if ( FT_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE*2 ) )
+      goto Exit;
+
+#else /* !FTC_CACHE_USE_LINEAR_HASHING */
     cache->nodes = 0;
     cache->size  = FTC_PRIMES_MIN;
 
     if ( FT_NEW_ARRAY( cache->buckets, cache->size ) )
       goto Exit;
 
+#endif /* !FTC_CACHE_USE_LINEAR_HASHING */
+
     /* now, initialize the lru list of families for this cache */
     if ( clazz->family_size > 0 )
     {
@@ -442,9 +645,15 @@
       FTC_Cache_Class  clazz   = cache->clazz;
       FTC_Manager      manager = cache->manager;
       FT_UFast         i;
+      FT_UInt          count;
 
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+      count = cache->p + cache->mask + 1;
+#else
+      count = cache->size;
+#endif
 
-      for ( i = 0; i < cache->size; i++ )
+      for ( i = 0; i < count; i++ )
       {
         FTC_Node  *pnode = cache->buckets + i, next, node = *pnode;
 
@@ -469,8 +678,11 @@
         cache->buckets[i] = NULL;
       }
 
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+      cache->p = 0;
+#else
       cache->nodes = 0;
-
+#endif
       /* destroy the families */
       if ( cache->families )
         FT_LruList_Reset( cache->families );
@@ -489,7 +701,12 @@
       ftc_cache_clear( cache );
 
       FT_FREE( cache->buckets );
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+      cache->mask  = 0;
+      cache->slack = 0;
+#else
       cache->size = 0;
+#endif
 
       if ( cache->families )
       {
@@ -508,7 +725,7 @@
                     FTC_Query   query,
                     FTC_Node   *anode )
   {
-    FT_Error    error;
+    FT_Error    error = 0;
     FT_LruNode  lru;
 
 
@@ -520,12 +737,67 @@
     query->hash   = 0;
     query->family = NULL;
 
+#ifdef OPT1
+    {
+      /* first of all, find the relevant family */
+      FT_LruList              list  = cache->families;
+      FT_LruNode              fam, *pfam;
+      FT_LruNode_CompareFunc  compare = list->clazz->node_compare;
+
+      pfam = &list->nodes;
+      for (;;)
+      {
+        fam = *pfam;
+        if ( fam == NULL )
+        {
+          error = FT_LruList_Lookup( list, query, &lru );
+          if ( error )
+            goto Exit;
+
+          goto Skip;
+        }
+
+        if ( 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;
+
+    Skip:
+    }
+#else
     error = FT_LruList_Lookup( cache->families, query, &lru );
     if ( !error )
+#endif
     {
       FTC_Family  family = (FTC_Family) lru;
       FT_UFast    hash    = query->hash;
-      FTC_Node*   bucket  = cache->buckets + (hash % cache->size);
+      FTC_Node*   bucket;
+
+
+#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
 
 
       if ( query->family     != family                        ||
@@ -551,8 +823,14 @@
           if ( node == NULL )
             break;
 
+#ifdef OPT1
+          if ( node->hash == hash                            &&
+               (FT_UInt)node->fam_index == family->fam_index &&
+               compare( node, query, cache ) )
+#else
           if ( (FT_UInt)node->fam_index == family->fam_index &&
                compare( node, query, cache ) )
+#endif
           {
             /* move to head of bucket list */
             if ( pnode != bucket )
@@ -596,7 +874,18 @@
           goto Exit;
         }
 
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+        error = ftc_node_hash_link( node, cache );
+        if ( error )
+        {
+          clazz->node_done( node, cache );
+          FT_FREE( node );
+          goto Exit;
+        }
+#else
         ftc_node_hash_link( node, cache );
+#endif
+
         ftc_node_mru_link( node, cache->manager );
 
         cache->manager->cur_weight += clazz->node_weight( node, cache );
@@ -609,9 +898,11 @@
           node->ref_count--;
         }
 
+#ifndef FTC_CACHE_USE_LINEAR_HASHING
         /* try to resize the hash table if appropriate */
         if ( FTC_CACHE_RESIZE_TEST( cache ) )
           ftc_cache_resize( cache );
+#endif
 
         *anode = node;
       }
diff --git a/src/cache/ftcsbits.c b/src/cache/ftcsbits.c
index 2f87c3530..25056e319 100644
--- a/src/cache/ftcsbits.c
+++ b/src/cache/ftcsbits.c
@@ -63,8 +63,8 @@
     FTC_ImageDesc       desc;
 
   } FTC_SBitFamilyRec;
- 
-  
+
+
 #define FTC_SBIT_FAMILY( x )         ( (FTC_SBitFamily)( x ) )
 #define FTC_SBIT_FAMILY_MEMORY( x )  FTC_GLYPH_FAMILY_MEMORY( &( x )->cset )
 
@@ -462,6 +462,23 @@
 
   /* documentation is in ftcsbits.h */
 
+#ifdef FTC_CACHE_USE_INLINE
+
+#  define GEN_CACHE_FAMILY_COMPARE(f,q,c)  \
+             ftc_sbit_family_compare( (FTC_SBitFamily)(f), (FTC_SBitQuery)(q) )
+
+#  define GEN_CACHE_NODE_COMPARE(n,q,c)  \
+             ftc_sbit_node_compare( (FTC_SBitNode)(n), (FTC_SBitQuery)(q), c )
+
+#  define GEN_CACHE_LOOKUP          ftc_sbit_cache_lookup
+#  include "ftccache.i"
+
+#else  /* !FTC_CACHE_USE_INLINE */
+
+#  define ftc_sbit_cache_lookup  ftc_cache_lookup
+
+#endif /* !FTC_CACHE_USE_INLINE */
+
   FT_EXPORT_DEF( FT_Error )
   FTC_SBitCache_Lookup( FTC_SBitCache   cache,
                         FTC_ImageDesc*  desc,
@@ -486,9 +503,9 @@
     squery.gquery.gindex = gindex;
     squery.desc          = *desc;
 
-    error = ftc_cache_lookup( FTC_CACHE( cache ),
-                              FTC_QUERY( &squery ),
-                              (FTC_Node*)&node );
+    error = ftc_sbit_cache_lookup( FTC_CACHE( cache ),
+                                   FTC_QUERY( &squery ),
+                                   (FTC_Node*)&node );
     if ( !error )
     {
       *ansbit = node->sbits + ( gindex - FTC_GLYPH_NODE( node )->item_start );
@@ -520,11 +537,11 @@
                          FTC_SBit        *ansbit )
   {
     FTC_ImageDesc  desc0;
-    
+
 
     if ( !desc )
       return FTC_Err_Invalid_Argument;
-      
+
     desc0.font = desc->font;
     desc0.type = (FT_UInt32)desc->image_type;
 
diff --git a/src/type42/t42parse.c b/src/type42/t42parse.c
index f2806e2ed..870d2eeec 100644
--- a/src/type42/t42parse.c
+++ b/src/type42/t42parse.c
@@ -970,114 +970,3 @@
   }
 
 
-  FT_LOCAL_DEF( FT_Error )
-  T42_Open_Face( T42_Face  face )
-  {
-    T42_LoaderRec  loader;
-    T42_Parser     parser;
-    T1_Font        type1 = &face->type1;
-    FT_Memory      memory = face->root.memory;
-    FT_Error       error;
-
-    PSAux_Service  psaux  = (PSAux_Service)face->psaux;
-
-
-    t42_loader_init( &loader, face );
-
-    parser = &loader.parser;
-
-    if ( FT_ALLOC( face->ttf_data, 12 ) )
-      goto Exit;
-
-    error = t42_parser_init( parser,
-                             face->root.stream,
-                             memory,
-                             psaux);
-    if ( error )
-      goto Exit;
-
-    error = t42_parse_dict( face, &loader, parser->base_dict, parser->base_len );
-
-    if ( type1->font_type != 42 )
-    {
-      error = FT_Err_Unknown_File_Format;
-      goto Exit;
-    }
-
-    /* now, propagate the charstrings and glyphnames tables */
-    /* to the Type1 data                                    */
-    type1->num_glyphs = loader.num_glyphs;
-
-    if ( !loader.charstrings.init ) {
-      FT_ERROR(( "T42_Open_Face: no charstrings array in face!\n" ));
-      error = FT_Err_Invalid_File_Format;
-    }
-
-    loader.charstrings.init   = 0;
-    type1->charstrings_block = loader.charstrings.block;
-    type1->charstrings       = loader.charstrings.elements;
-    type1->charstrings_len   = loader.charstrings.lengths;
-
-    /* we copy the glyph names `block' and `elements' fields; */
-    /* the `lengths' field must be released later             */
-    type1->glyph_names_block   = loader.glyph_names.block;
-    type1->glyph_names         = (FT_String**)loader.glyph_names.elements;
-    loader.glyph_names.block    = 0;
-    loader.glyph_names.elements = 0;
-
-    /* we must now build type1.encoding when we have a custom array */
-    if ( type1->encoding_type == T1_ENCODING_TYPE_ARRAY )
-    {
-      FT_Int    charcode, idx, min_char, max_char;
-      FT_Byte*  char_name;
-      FT_Byte*  glyph_name;
-
-
-      /* OK, we do the following: for each element in the encoding   */
-      /* table, look up the index of the glyph having the same name  */
-      /* as defined in the CharStrings array.                        */
-      /* The index is then stored in type1.encoding.char_index, and  */
-      /* the name in type1.encoding.char_name                        */
-
-      min_char = +32000;
-      max_char = -32000;
-
-      charcode = 0;
-      for ( ; charcode < loader.encoding_table.max_elems; charcode++ )
-      {
-        type1->encoding.char_index[charcode] = 0;
-        type1->encoding.char_name [charcode] = (char *)".notdef";
-
-        char_name = loader.encoding_table.elements[charcode];
-        if ( char_name )
-          for ( idx = 0; idx < type1->num_glyphs; idx++ )
-          {
-            glyph_name = (FT_Byte*)type1->glyph_names[idx];
-            if ( ft_strcmp( (const char*)char_name,
-                            (const char*)glyph_name ) == 0 )
-            {
-              type1->encoding.char_index[charcode] = (FT_UShort)idx;
-              type1->encoding.char_name [charcode] = (char*)glyph_name;
-
-              /* Change min/max encoded char only if glyph name is */
-              /* not /.notdef                                      */
-              if ( ft_strcmp( (const char*)".notdef",
-                              (const char*)glyph_name ) != 0 )
-              {
-                if ( charcode < min_char ) min_char = charcode;
-                if ( charcode > max_char ) max_char = charcode;
-              }
-              break;
-            }
-          }
-      }
-      type1->encoding.code_first = min_char;
-      type1->encoding.code_last  = max_char;
-      type1->encoding.num_chars  = loader.num_chars;
-    }
-
-  Exit:
-    t42_loader_done( &loader );
-    return error;
-  }
-