# THIS IS A DRAFT - NOT FOR DISTRIBUTION

# Introduction :

This document describes the caching sub-system that comes with the FreeType library since release 2.0.6. As we'll see it provides a robust, high-performance and flexible way to manage faces, sizes, glyph images and charmaps.

The first section presents an overview of the cache manager and its main APIs. The second one explains how it's possible to extend it to support caching of custom data with very little efforts, due to its extensible design.

# I. Requirements and Design Goals:

When dealing with fonts, caching rapidly becomes a necessity for at least the following reasons:

- opening font files is relatively slow, since it needs to load data into memory, perform a minimum amount of validation on the input, as well as setup certain format-dependent tables which are much too esoteric to be detailed here. As a consequence, it is always a good idea to keep a `FT_Face` object opened as long as possible.

- on the other hand, each `FT_Face` or `FT_Size` object can take from a few hundreds to several dozen kilobytes each, depending on the font and its format. Since it's not easy to determine this footprint, it's a good idea to assume that it is always large, and limit the number of opened faces to the minimum.

- similarly, each face contains hundreds, if not thousands of distinct glyph images. Since typical text only uses a fraction of a face's glyphs, loading all glyphs at once is nearly never a good idea. Instead, it's better to only retrieve and store the ones we need more often.

- finally, when all glyphs belonging to a given face are already loaded in memory, the corresponding `FT_Face` object can be closed to reduce the total memory footprint.

The FreeType caching sub-system is nothing more than a powerful way to automate all these tasks very easily.

# II. The Cache Manager:

At the heart of the caching sub-system is a single object called the cache manager, used to handle all kinds of data within the cache. You should always begin your application by calling the API FTC_Manager_New to create a new manager object.

## 1. Identifying faces through `FTC_FaceIDs`:

For reasons of portability and flexibility, the cache manager has no direct knowledge of which fonts are "installed" or available during program execution. Instead, the application is responsible of the tasks of locating and identifying faces and opening the corresponding font files.

What this means is that a client application must uniquely identify any given available/installed face with a pointer, with type FTC_FaceID . The meaning of such pointers is not important to the cache manager, but their values must be constant throughout program lifetime, and are used to associate cached data to their corresponding faces.

The application must also provide (during `FTC_Manager_New`) a special callback function, named a FTC_Face_Requester . The face requester is simply in charge of "translating" a given `FTC_FaceID` into a fresh new `FT_Face`. This generally implies calling `FT_New_Face` or `FT_Open_Face`, but conveniently encapsulate any kind of font installation/listing problem to the application side.

In most cases, a `FTC_FaceID` is a pointer to a structure that contains a file pathname and a face index, and where the face requester simply calls `FT_New_Face`, as illustrated by the following code:

       /* define custom face identification structure */
       typedef struct MyFaceRec_
       {
         const char*  file_path;
         int          face_index;

       } MyFaceRec, *MyFace;

       /* our custom face requester is dead simple */
       static FT_Error
       my_face_requester( FTC_FaceID   face_id,
                          FT_Library   library,
                          FT_Pointer   request_data,
                          FT_Face     *aface )
       {
         MyFace  face = (MyFace) face_id;   // simple typecase

         return FT_New_Face( library, face->file_path, face->face_index, aface );
       }

       {
         FTC_Manager  manager;
         ...
         /* initialize cache manager */
         error = FTC_Manager_New(
                     library,
                     0,  /* use default */
                     0,  /* use default */
                     0,  /* use default */
                     & my_face_requester,  /* use our requester */
                     NULL,                 /* don't need this.  */
                     &manager );
       }

What this code doesn't show is how the list of available/existing `FTC_FaceID`/`MyFace` handle is generated, since this is highly program or platform specific. For a more concrete example, have a look at the file `ftcommon.i` in the "`ft2demos`" package distributed by FreeType.

## 2. Caching `FT_Face` and `FT_Size` objects:

Client applications should not open new `FT_Face` objects directly with FT_New_Face or FT_Open_Face . Instead, they should directly query them from the cache manager with a call to the FTC_Lookup_Face API.

The reason for this is that the manager automatically limits the number of opened `FT_Face` objects during program execution, according to a pre-determined threshold. It does so by keeping all opened face objects in a list sorted in most-recently-used (MRU) order.

When a new face object is requested and when the list if 'full', the oldest `FT_Face` is automatically closed to leave room for the new one. Each time you call `FTC_Lookup_Face`, the returned face is also placed at the head of the manager's list.

Note that `FTC_Lookup_Face` takes a `FTC_FaceID` on input and returns a valid `FT_Face` handle (or an error).

Similarly to `FT_Face` handles, the cache manager also handles a list containing opened `FT_Size` objects, which correspond to specific character pixel sizes of given `FTC_FaceID` handles.

As a consequence, applications should never try to set a face's current character size with FT_Set_Char_Size or FT_Set_Pixel_Sizes on a given `FT_Face`. Instead, they should use FTC_Lookup_Size .

It's very important to note that `FT_Face` and `FT_Size`handles returned by the cache manager should be considered temporary objects, as these can be flushed out of the cache any time you call any of the caching sub-system APIs, even one that do not directly deal with these types.

It is indeed not possible to "lock" one of these objects within the cache to prevent them from being flushed. This is not a bug but an important design feature.

However, we'll see in the next section that it is possible to extract a variety of data from these items (like glyph images, charmaps, etc..), and cache them in a more friendly and efficient way..

# II. The Cache Pool

The final purpose of the cache manager is to provide an "area", called the cache pool, where specific font data can be cached in a very efficient way. More specifically, this data is organized in abstract cache "nodes".

## 1. Cache Nodes

Each cache node corresponds to a small fragment of the information contained in a face that is likely to be used very often for text rendering and other common operations. For examples: glyph images, bitmaps or charmaps (though other types of data can be easily added as described later). Cache nodes have the following properties:

- the cache manager is capable of computing the exact memory footprint of each cache node quickly, and keeps all nodes in a MRU list as well.

- when the pool is "full", the manager is capable of destroying the "oldest" node(s) in order to create a new one.

- each node is reference-counted, with an initial count of 0. The manager will never destroy a node whose count isn't zero, and thus supports "locking" nodes in the cache.

This allows the manager to limit the total memory size taken by cache nodes (instead of their number), thus ensuring a controlled memory footprint for all cached data. This means that, independently of the number of faces and sizes used, these nodes will never take more than, say, 300 KB, in memory.

It's of course possible to use different types of cache nodes within the manager's pool. Notice that the "pool size" is set when calling `FTC_Manager_New` and doesn't change afterwards. Its exact value doesn't influence the API or the code of the programs using it (only their performance, eventually).

All of this is performed automatically, but the cache manager doesn't provide APIs to actually create new nodes in its pool. That's the task of cache objects.

## 2. Cache Objects

A cache object is used to managed a single type of nodes. It thus provides:

- a high-level API to client applications, to let them lookup nodes. (this function create new nodes when they're not available yet in the cache pool)

- a simple description of its cache nodes to the manager, (which is hidden to client apps). Basically, this means how to compute a node's footprint, how to destroy a node, etc..

Several cache objects can be used concurrently in a single manager. Up to 16 caches can be used in a single cache manager, but this number can be changed at build time through the definition of the FTC_MAX_CACHES macro. For example, the `ftview` demo program uses three cache objects provided by the default FT2 cache sub-system:

- a FTC_SBitCache to store small glyph bitmaps.
- a FTC_ImageCache to store glyph outlines.
- a FTC_CMapCache to store character code to glyph indices mappings

The high-level API of each cache is generally made of two important functions:

- a `New` function, used to create a new cache object within a given manager and return its handle. This should be called only once by your application, just after FTC_Manager_New . See FTC_ImageCache_New , FTC_SBitsCache_New or FTC_CMapCache_New for examples. Note that all caches are automatically cleared and destroyed with their parent manager.

- a `Lookup` function, used to lookup data in a given cache, eventually creating new nodes when they're not available in the cache and destroying old ones when the cache is full. See FTC_ImageCache_Lookup , FTC_SBitsCache_Lookup or FTC_CMapCache_Lookup for examples.

Note that even though each `Lookup` function returns raw data (like glyph images, metrics, etc..), it may also optionally return an opaque `FTC_Node` handle corresponding to the cache node where this data was found.

More precisely, the last parameter of some `Lookup` routines is a `FTC_Node*` pointer, i.e. the address of a variable that will receive the cache node handle. if this address is NULL, the raw data is simply returned, and the node is left unchanged (and hidden to the application).

If this address is _not_ NULL, the cache node handle is written to it, and its reference-count is incremented before `Lookup` returns. It's then up to the caller to later call FTC_Node_Unref to decrement it back.

Finally, you can also use FTC_Node_Ref to manually increment the reference count of a given cache node. You should however never forget to call `FTC_Node_Unref` when you don't need it anymore, in order to ensure correct behaviour of the cache manager.

Leaving cache nodes "locked" in the cache leads to its saturation as well as further lookup failures.

# III. Designing custom cache types

If you're perfectly happy and satisfied by the three cache objects provided with the standard cache manager (i.e. glyph images, small bitmaps and charmaps), I advise you to jump directly to this document's conclusion.

Indeed, this section details the sophisticated subject of providing custom cache object types in order to extend the caching sub-system. We'll see that this is not very difficult and doesn't need large amounts of code. However, its requires a good understanding of the sub-system's internals that will be explained here..

## 1. Internals Overview

First of all, you should always include the file `FT_CACHE_MANAGER_H` (a.k.a. `<freetype/cache/ftcmanag.h>` in most installations) before your custom cache code, since it contains a bunch of necessary type and functions declarations.

More specifically, it provides the definition of four important types which will be treated as abstract object classes in the rest of this section:

### a. the `FTC_Node` class:

Each cache node is modeled by a `FTC_Node` handle, which is a pointer to the FTC_NodeRec structure.

      typedef struct  FTC_NodeRec_
      {
        FTC_Node   mru_next;     /* circular mru list pointer           */
        FTC_Node   mru_prev;     /* circular mru list pointer           */
        FTC_Node   link;         /* used for hashing..                  */
        FT_UInt32  hash;         /* used for hashing too..              */
        FT_UShort  fam_index;    /* index of family the node belongs to */
        FT_Short   ref_count;    /* reference count for this node..     */

      } FTC_NodeRec;

It can be detailed with the following:

- Each node is part of a MRU-ordered global list owned by the cache manager, and thus contains two fields, named `mru_prev` and `mru_next`, for that purpose.

- Each cache object implements a fast and dynamic hash table. As a consequence, each node also contains a 32-bit field named `hash` and a bucket list pointer named `link`

- Finally, each node contains a 16-bit reference count (`ref_count`), and a 16-bit index (`fam_index`) into a global list of "families" (which are described below)

On a 32-bits system, the minimal size of a given cache node is thus of 20 bytes.

You can "derive" the base `FTC_Node` class by defining your own structures with a `FTC_NodeRec` as its first field, as in:

          typedef struct DummyNodeRec_
          {
            FTC_NodeRec   node;

            ........ my node information

          } DummyNodeRec, *DummyNode;

### b. the `FTC_Family` class:

All the nodes managed by a given cache can be grouped in families. Each family corresponds to a group of nodes sharing the same runtime properties. It is modeled by a FTC_Family handle.

For example, both the `FTC_ImageCache` and `FTC_SBitsCache` use families to group all image/bitmap nodes belonging to the same face, size and format. More precisely, each family object they manage contain a `FTC_FaceID`, character pixel sizes and a glyph image format descriptor.

Each family belongs to a single cache object, and it has a globally unique 16-bit index used to address it from a given cache node. If several cache nodes belong to the same family, this allows efficient sharing of information and prevent duplication of considerable amount of identical data.

Just like `FTC_Node`, `FTC_Family` is an abstract class that must be derived to create "real" types.

### c. the `FTC_Cache` class:

As said previously, each `FTC_Cache` object implements an optimized and dynamic hash table to hold all of its nodes. Additionally, the cache controls a MRU list of families for its nodes.

A cache object's most important field is a pointer to its corresponding FTC_Cache_ClassRec structure, used to model its behaviour and properties:

        typedef struct  FTC_Cache_ClassRec_
        {
          FT_UInt                 cache_size;
          FTC_Cache_InitFunc      cache_init;
          FTC_Cache_ClearFunc     cache_clear;
          FTC_Cache_DoneFunc      cache_done;

          FT_UInt                 family_size;
          FTC_Family_InitFunc     family_init;
          FTC_Family_CompareFunc  family_compare;
          FTC_Family_DoneFunc     family_done;

          FT_UInt                 node_size;
          FTC_Node_InitFunc       node_init;
          FTC_Node_WeightFunc     node_weight;
          FTC_Node_CompareFunc    node_compare;
          FTC_Node_DoneFunc       node_done;

        } FTC_Cache_ClassRec;

This structure is made of three sections related to the sub-classes of `FTC_Cache`, `FTC_Family` and `FTC_Node` specific to the cache. Most of its fields are function pointers used to implement "methods" of these objects.

FreeType provides several useful defaults for these callbacks. As we'll see, providing custom cache implementations is only a matter or writing a few number of specific methods, as well as a custom `FTC_Cache_ClassRec`, as detailed a bit further.

### d. the `FTC_Query` class:

When a cache is searched, the information relevant to select or create the right node is gathered in a sub-class of the class FTC_Query by the `Lookup` function, and then passed to the internal cache lookup function (i.e. `ftc_cache_lookup`).

      typedef struct FTC_QueryRec_
      {
        FTC_Family  family;
        FT_UFast    hash;

      } FTC_QueryRec;

This routine first tries to find the family corresponding to the request. it does so by comparing any family already created for the cache to the request. If none is found, a new family is created.

When a family is matched by a request, the base fields of the query (i.e. `family` and `hash`) are updated and then used to lookup the corresponding node in the cache's hash table.

Note that _both_ the family initializer and comparator (i.e. the `family_init` and `family_compare` fields of the `FTC_Cache_ClassRec`) need to update these base fields according to the request.

A typical sub-class of `FTC_Query` would add information about what is looked up. Some examples are given in the new sub-sections.

## 2. Implementing a simple cache:

Let's have a look at a real custom cache implementation. Imagine that we want to cache the advance widths of glyphs for specific faces and pixel sizes. We can do it by designing a custom cache with the following design:

We'll start by sub-classing `FTC_Node` as follows:

         typedef struct MyNodeRec_
         {
           FTC_NodeRec    node;
           FTC_FaceID     face_id;      /* face identifier              */
           FT_UInt        pix_width;    /* character pixel width        */
           FT_UInt        pix_height;   /* character pixel weigth       */
           FT_UInt        num_glyphs;   /* number of glyphs in font     */
           FT_Fixed*      advances;     /* array of 'num_glyphs' values */

         } MyNodeRec, *MyNode;

As you see, we use a `FTC_NodeRec` as the first field in our structure, since this can be seen as a "sub-class" of `FTC_NodeRec`.

Similarly, we're going to create a specific query, which sub-classes `FTC_Query`:

        typedef struct MyQueryRec_
        {
          FTC_QueryRec  query;
          FTC_FaceID    face_id;
          FT_UInt       pix_width;
          FT_UInt       pix_height;

        } MyQueryRec, *MyQuery;

We don't need to deal with several families per cache, since everything is stored in the node, so we create a dummy sub-class:

         typedef  struct MyFamilyRec_
         {
           FTC_FamilyRec  family;

         } MyFamilyRec, *MyFamily;

Now, let's write some sub-classed methods. Let's start by the easiest ones, which are used to create and compare families. Since we only really need one family per cache, we'll write:

         // update the base query fields 'family' and 'hash'
         static void
         my_query_update( MyQuery   my_query,
                          MyFamily  my_family )
         {
           FTC_Query   query  = FTC_QUERY(my_query);   // simple type casts
           FTC_Family  family = FTC_FAMILY(my_family);

           query->family = family;
           query->hash   = FTC_FACE_ID_HASH(my_query->face_id) ^
                           (my_query->pix_width << 8) ^
                           (my_query->pix_height);
         }

         // initialize a brand new family
         FT_Error
         my_family_init( MyFamily   my_family,
                         MyQuery    my_query,
                         FTC_Cache  cache )
         {
           FT_Error  error;

           // call base family initialiser
           error = ftc_family_init( FTC_FAMILY( my_family ),
                                    FTC_QUERY( my_query ),
                                    cache );
           if ( !error )
             my_query_update( my_query, my_family );

           return error;
         }

         // since we only want to use one family per cache, always
         // compare favorably, independently of the query..
         FT_Bool
         my_family_compare( MyFamily  my_family,
                            MyQuery   my_query )
         {
           query_update( my_query, my_family );
           return 1;
         }

Notice the static function `my_query_update`. It is used to update the `family` and `hash` field of the current query whenever a family is matched or created. This is actually extremely important for any cache sub-class.

Now, let's write the sub-classed node routines:

        // finalize node
        void
        my_node_done( MyNode     my_node,
                      FTC_Cache  cache )
        {
          if ( my_node->advances )
          {
            FT_Memory  memory = cache->memory;

            FREE( my_node->advances );
            my_nodes->num_glyphs = 0;
          }

          my_node->face_id    = NULL;
          my_node->pix_width  = 0;
          my_node->pix_height = 0;

          // call base node finalizer
          ftc_node_done( FTC_NODE(my_node), cache );
        }

        // compute node weight (size in bytes)
        FT_ULong
        my_node_weight( MyNode     my_node,
                        FTC_Cache  cache )
        {
          // easy, isn't it ;-)
          return sizeof(*my_node) + my_node->num_glyphs * sizeof(FT_Fixed);
        }

        // compare node to the current query
        FT_Bool
        my_node_compare( MyNode   my_node,
                         MyQuery  my_query )
        {
          return ( my_node->face_id    == my_query->face_id    &&
                   my_node->pix_width  == my_query->pix_width  &&
                   my_node->pix_height == my_query->pix_height );
        }

        // create new node from current query
        FT_Error
        my_node_init( MyNode     my_node,
                      MyQuery    my_query,
                      FTC_Cache  cache )
        {
          FT_Error  error;

          // call base node initialiser
          ftc_node_init( FTC_NODE(my_node),
                         FTC_QUERY(my_query),
                         cache );

          // load the advances table
          error = load_advances(
                     my_query->face_id,
                     my_query->pix_width,
                     my_query->pix_height,
                     cache->manager,
                     &my_node->num_glyphs,
                     &my_node->advances );

          return error;
        }

Except for the `load_advances` function, which we'll not detail here, we have finished our sub-classing code. All we need now is to pack everything in:

        static const FTC_Cache_ClassRec   my_cache_class =
        {
          sizeof( FTC_CacheRec ),      // keep base FTC class
          ftc_cache_init,              // and methods..
          ftc_cache_clear,
          ftc_cache_done,

          sizeof( My_FamilyRec ),
          my_family_init,
          my_family_compare,
          ftc_family_done,             // use base family finalizer

          sizeof( My_NodeRec ),
          my_node_init,
          my_node_compare,
          my_node_weight,
          my_node_done
        };

which we'll directly use in:

        typedef  FTC_Cache   My_Cache;

        FT_Error
        My_Cache_New( FTC_Manager   manager,
                      My_Cache     *acache )
        {
          return  FTC_Manager_Register( manager,
                                        &my_cache_class,
                                        (FTC_Cache*) acache );
        }

Finally, all we need now is the lookup function. Here it comes:

        FT_Error
        My_Cache_Lookup( My_Cache    my_cache,
                         FTC_FaceID  face_id,
                         FT_UInt     pix_width,
                         FT_UInt     pix_height,

                         FT_UInt    *anum_glyphs,   // output
                         FT_Fixed*  *aadvances,     // output

                         FTC_Node   *anode )        // optional output
        {
          FT_Error     error;
          My_Node      node;
          My_QueryRec  my_query;

          // setup query
          my_query.face_id    = face_id;
          my_query.pix_width  = pix_width;
          my_query.pix_height = pix_height;

          *anum_glyphs = 0;
          *aadvances   = NULL;

          // perform lookup
          error = ftc_cache_lookup( FTC_CACHE( my_cache ),
                                    FTC_QUERY( &my_query ),
                                    (FTC_Node*) &node );
          if (!error)
          {
            // return raw data
            *anum_glyphs = node->num_glyphs;
            *aadvances   = node->advances;

            // eventually return cache node handle, increment ref count
            if ( anode )
            {
              *anode = node;
              FTC_NODE(node)->ref_count++;
            }
          }
          return error;
        }

Voila ! We've completed a basic but working custom cache type and can start using it right now in our applications.

## 3. A slightly more complex case:

The previous example was relatively simple, though it didn't use families in its cache. We'll now design a cache used to store the scaled and hinted outlines of individal glyphs.

First, let's design the node and query sub-classes, and the corresponding code:

        typedef struct MyNodeRec_
        {
          FTC_NodeRec  node;
          FT_Outline   outline;

        } MyNodeRec, *MyNode;

        typedef struct MyQueryRec_
        {
          FTC_QueryRec  query;
          FTC_FaceID    face_id;
          FT_UInt       pix_width;
          FT_UInt       pix_height;
          FT_UInt       glyph_index;

        } MyQueryRec, *MyQuery;

        FT_Error  my_node_init( MyNode     node,
                                MyQuery    query,
                                FTC_Cache  cache )
        {
          FT_Error    error;
          FT_UInt32   hash;
          FT_Face     face;
          FT_Size     size;

          /* first, lookup face and size for the corresponding node */
          error = FTC_Manager_Lookup_Size( cache->manager,
                                           query->face_id,
                                           query->pix_width,
                                           query->pix_height,
                                           &face,
                                           &size );
          if (!error)
          {
            error = FT_Load_Glyph( face, query->glyph_index, FT_LOAD_NO_BITMAP );
            if (!error)
            {
              /* copy outline into the node */

            }
          }
          return error;
        }

</tml>