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_Sizehandles 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.

When a lookup is performed in a cache, the latter begins by finding the family corresponding to the request (if none is available, it creates a new one). Once found, the family determines the hash value to use to lookup the node in the hash table.




d. the FTC_Query class:

Which leads us to the FTC_Query class, which is used exclusively within lookups to during lookups

When a cache is searched, the information relevant to select or create the right node is gathered in a type called a "query". Its base class is FTC_Query , which must be derived too for "real" queries / lookups.