Commits

Anonymous committed c46d5ce

Rewrote cache using fixed adressing.
Added option to change default cache size.

  • Participants
  • Parent commits f120248
  • Branches pgreloaded

Comments (0)

Files changed (7)

 
 * freetype: render to buffer buffer support (like new bytearray, but
   write to a buffer instead)
-* freetype: add style support (underlined)
 * freetype: correct error messages (e.g. on trying to scale pcf fonts)
 * freetype: brush up docs and examples
 * freetype: description/markup language for rendering text (like e.g. pango

File examples/freetype/sdlfont.py

 
 def run():
     video.init ()
-    freetype.init ()
+    freetype.init (8)
 
     fontdir = os.path.dirname (os.path.abspath (__file__))
     font = freetype.Font (os.path.join (fontdir, "sans.ttf"))

File src/freetype/ft_cache.c

 
 #include FT_MODULE_H
 
-#define PGFT_DEBUG_CACHE
 
 FT_UInt32 _PGFT_Cache_Hash(const FontRenderMode *, FT_UInt);
 FT_UInt32 _PGFT_GetLoadFlags(const FontRenderMode *);
 
-FontGlyph *_PGFT_Cache_AllocateGlyph(FreeTypeInstance *, 
+PGFT_CacheNode *_PGFT_Cache_AllocateNode(FreeTypeInstance *, 
         PGFT_Cache *, const FontRenderMode *, FT_UInt);
-void _PGFT_Cache_FreeGlyph(FontGlyph *);
+void _PGFT_Cache_FreeNode(PGFT_Cache *, PGFT_CacheNode *);
 
 
 FT_UInt32 _PGFT_GetLoadFlags(const FontRenderMode *render)
 	return h;
 } 
 
-void PGFT_Cache_Init(PGFT_Cache *cache, PyFreeTypeFont *parent)
+void PGFT_Cache_Init(FreeTypeInstance *ft, 
+        PGFT_Cache *cache, PyFreeTypeFont *parent)
 {
-    /* 
-     * TODO: Let user specify the desired
-     * size for the cache?
+    int cache_size = MAX(ft->cache_size - 1, PGFT_MIN_CACHE_SIZE - 1);
+
+    /*
+     * Make sure this is a power of 2.
      */
-    const int cache_size = 64;
+    cache_size = cache_size | (cache_size >> 1);
+    cache_size = cache_size | (cache_size >> 2);
+    cache_size = cache_size | (cache_size >> 4);
+    cache_size = cache_size | (cache_size >> 8);
+    cache_size = cache_size | (cache_size >>16);
 
+    cache_size = cache_size + 1;
+
+    cache->nodes = calloc((size_t)cache_size, sizeof(FontGlyph *));
+    cache->depths = calloc((size_t)cache_size, sizeof(FT_Byte));
     cache->font = parent;
-    cache->nodes = calloc(cache_size, sizeof(FontGlyph *));
-    cache->size_mask = (cache_size - 1);
-    cache->lru_counter = 0;
+    cache->free_nodes = NULL;
+    cache->size_mask = (FT_UInt32)(cache_size - 1);
+
+#ifdef PGFT_DEBUG_CACHE
+    cache->count = 0;
+    cache->_debug_delete_count = 0;
+    cache->_debug_access = 0;
+    cache->_debug_hit = 0;
+    cache->_debug_miss = 0;
+#endif
 }
 
 void PGFT_Cache_Destroy(PGFT_Cache *cache)
 {
     FT_UInt i;
+    PGFT_CacheNode *node, *next;
 
     if (cache == NULL)
         return;
 
+#ifdef PGFT_DEBUG_CACHE
+    fprintf(stderr, "Cache stats:\n");
+    fprintf(stderr, "\t%d accesses in total\n", cache->_debug_access);
+    fprintf(stderr, "\t%d hits / %d misses\n", cache->_debug_hit, cache->_debug_miss);
+    fprintf(stderr, "\t%f hit ratio\n", (float)cache->_debug_hit/(float)cache->_debug_access);
+    fprintf(stderr, "\t%d nodes kicked\n", cache->_debug_delete_count);
+#endif
+
     for (i = 0; i <= cache->size_mask; ++i)
-        _PGFT_Cache_FreeGlyph(cache->nodes[i]);
+    {
+        node = cache->nodes[i];
+
+        while (node)
+        {
+            next = node->next;
+            _PGFT_Cache_FreeNode(cache, node);
+            node = next;
+        }
+    }
 
     free(cache->nodes);
+    free(cache->depths);
+}
+
+void PGFT_Cache_Cleanup(PGFT_Cache *cache)
+{
+    const FT_Byte MAX_BUCKET_DEPTH = 2;
+    PGFT_CacheNode *node, *prev;
+    FT_UInt32 i;
+
+    for (i = 0; i <= cache->size_mask; ++i)
+    {
+        if (cache->depths[i] > MAX_BUCKET_DEPTH)
+        {
+            node = cache->nodes[i];
+            prev = NULL;
+
+            for (;;)
+            {
+                if (!node->next)
+                {
+#ifdef PGFT_DEBUG_CACHE
+                    cache->_debug_delete_count++;
+#endif
+
+                    prev->next = NULL; 
+                    _PGFT_Cache_FreeNode(cache, node);
+                    break;
+                }
+
+                prev = node;
+                node = node->next;
+            }
+        }
+    }
+
 }
 
 FontGlyph *PGFT_Cache_FindGlyph(FreeTypeInstance *ft, PGFT_Cache *cache, 
         FT_UInt character, const FontRenderMode *render)
 {
-    FontGlyph **nodes = cache->nodes;
-    FT_UInt32 lowest, current, first, i;
+    PGFT_CacheNode **nodes = cache->nodes;
+    PGFT_CacheNode *node, *prev;
 
-    const FT_UInt32 hash = _PGFT_Cache_Hash(render, character);
-    FT_UInt32 perturb;
+    FT_UInt32 hash = _PGFT_Cache_Hash(render, character);
+    FT_UInt32 bucket = hash & cache->size_mask;
     
-    i = hash;
-    current = first = lowest = hash & cache->size_mask;
-    perturb = hash;
+    node = nodes[bucket];
+    prev = NULL;
 
-    /*
-     * Browse the whole cache with linear probing until either:
-     *
-     *  a) we find an empty spot for the glyph
-     *      => we load our glyph and store it there
-     *
-     *  b) we find the glyph already on the cache
-     *      => we return the reference to that glyph
-     *
-     *  c) we find no glyphs, and no empty spots
-     *      => we kick the LRU glyph from the cache,
-     *      and store the new one there
-     */
-    do
+#ifdef PGFT_DEBUG_CACHE
+    cache->_debug_access++;
+#endif
+        
+    while (node)
     {
-        if (nodes[current] == NULL)
+        if (node->hash == hash)
         {
-            /* A: found empty spot */
-            return (nodes[current] = 
-                   _PGFT_Cache_AllocateGlyph(ft, cache, render, character));
-        }
-        
-        if (nodes[current]->hash == hash)
-        {
-            /* B: found glyph on cache */
-            nodes[current]->lru = ++cache->lru_counter;
-            return nodes[current];
+            if (prev)
+            {
+                prev->next = node->next;
+                node->next = nodes[bucket];
+                nodes[bucket] = node;
+            }
+
+#ifdef PGFT_DEBUG_CACHE
+            cache->_debug_hit++;
+#endif
+
+            return &node->glyph;
         }
 
-        if (nodes[current]->lru < nodes[lowest]->lru)
-            lowest = current;
+        prev = node;
+        node = node->next;
+    }
 
-        i = (5 * i) + 1 + perturb;
-        perturb <<= 5;
+    node = _PGFT_Cache_AllocateNode(ft, cache, render, character);
 
-        current = i & cache->size_mask;
+#ifdef PGFT_DEBUG_CACHE
+    cache->_debug_miss++;
+#endif
 
-    } while (current != first);
-
-    /* C: kick glyph from cache */
-    _PGFT_Cache_FreeGlyph(nodes[lowest]);
-
-    return (nodes[lowest] = 
-            _PGFT_Cache_AllocateGlyph(ft, cache, render, character));
+    return &node->glyph;
 }
 
-void _PGFT_Cache_FreeGlyph(FontGlyph *glyph)
+void _PGFT_Cache_FreeNode(PGFT_Cache *cache, PGFT_CacheNode *node)
 {
-    if (glyph == NULL)
+    if (node == NULL)
         return;
 
-    FT_Done_Glyph(glyph->image);
-    free(glyph);
+#ifdef PGFT_DEBUG_CACHE
+    cache->count--;
+#endif
+
+    cache->depths[node->hash & cache->size_mask]--;
+
+    FT_Done_Glyph(node->glyph.image);
+    free(node);
 }
 
-FontGlyph *_PGFT_Cache_AllocateGlyph(FreeTypeInstance *ft, 
+PGFT_CacheNode *_PGFT_Cache_AllocateNode(FreeTypeInstance *ft, 
         PGFT_Cache *cache, const FontRenderMode *render, FT_UInt character)
 {
+    PGFT_CacheNode *node = NULL;
+    FontGlyph *glyph = NULL;
+
     FT_Glyph_Metrics *metrics;
-    FontGlyph *glyph = NULL;
+    FT_Face face;
+
     FT_UInt32 load_flags;
     FT_Fixed bold_str = 0;
     int gindex;
-
-    FT_Face face;
+    FT_UInt32 bucket;
 
     /*
      * Grab face reference
     /* 
      * Allocate cache node 
      */
-    glyph = malloc(sizeof(FontGlyph));
-
+    node = malloc(sizeof(PGFT_CacheNode));
+    glyph = &node->glyph;
 
     /*
      * Calculate the corresponding glyph index for the char
 
     glyph->glyph_index = (FT_UInt)gindex;
 
-
     /*
      * Get loading information
      */
     /*
      * Update cache internals
      */
-    glyph->lru = ++cache->lru_counter;
-    glyph->hash = _PGFT_Cache_Hash(render, character);
+    node->hash = _PGFT_Cache_Hash(render, character);
+    bucket = node->hash & cache->size_mask;
+    node->next = cache->nodes[bucket];
+    cache->nodes[bucket] = node;
 
-    return glyph;
+    cache->depths[bucket]++;
+
+#ifdef PGFT_DEBUG_CACHE
+    cache->count++;
+#endif
+
+    return node;
 
     /*
      * Cleanup on error
     if (glyph && glyph->image)
         FT_Done_Glyph(glyph->image);
 
-    free(glyph);
+    free(node);
     return NULL;
 }

File src/freetype/ft_mod.c

 static int _ft_clear (PyObject *mod);
 
 static PyObject *_ft_quit(PyObject *self);
-static PyObject *_ft_init(PyObject *self);
+static PyObject *_ft_init(PyObject *self, PyObject *args);
 static PyObject *_ft_get_version(PyObject *self);
 static PyObject *_ft_get_error(PyObject *self);
 static PyObject *_ft_was_init(PyObject *self);
     { 
         "init", 
         (PyCFunction) _ft_init, 
-        METH_NOARGS, 
+        METH_VARARGS, 
         DOC_BASE_INIT 
     },
     { 
 }
 
 static PyObject *
-_ft_init(PyObject *self)
+_ft_init(PyObject *self, PyObject *args)
 {
     FT_Error error;
+    FT_Int cache_size = PGFT_DEFAULT_CACHE_SIZE;
 
     if (FREETYPE_MOD_STATE (self)->freetype)
         Py_RETURN_NONE;
 
-    error = PGFT_Init(&(FREETYPE_MOD_STATE (self)->freetype));
+    if (!PyArg_ParseTuple(args, "|i", &cache_size))
+        return NULL;
+
+    error = PGFT_Init(&(FREETYPE_MOD_STATE (self)->freetype), cache_size);
     if (error != 0)
     {
         /* TODO: More accurate error message */

File src/freetype/ft_text.c

             string_length++;
     }
 
+    /* cleanup the cache */
+    PGFT_Cache_Cleanup(&PGFT_INTERNALS(font)->cache);
+
     /* create the text struct */
     ftext = &(PGFT_INTERNALS(font)->active_text);
 

File src/freetype/ft_wrap.c

     font->_internals = malloc(sizeof(FontInternals));
     memset(font->_internals, 0x0, sizeof(FontInternals));
 
-    PGFT_Cache_Init(&PGFT_INTERNALS(font)->cache, font);
+    PGFT_Cache_Init(ft, &PGFT_INTERNALS(font)->cache, font);
 
     return _PGFT_GetFace(ft, font) ? 0 : -1;
 }
  *
  *********************************************************/
 int
-PGFT_Init(FreeTypeInstance **_instance)
+PGFT_Init(FreeTypeInstance **_instance, int cache_size)
 {
     FreeTypeInstance *inst = NULL;
 
 
     memset(inst, 0, sizeof(FreeTypeInstance));
     inst->_error_msg = calloc(1024, sizeof(char));
+    inst->cache_size = cache_size;
     
     if (FT_Init_FreeType(&inst->library) != 0)
         goto error_cleanup;

File src/freetype/ft_wrap.h

 #define FT_RFLAG_DEFAULTS       (FT_RFLAG_NONE | FT_RFLAG_HINTED)
 
 #define MAX_GLYPHS      64
+#define PGFT_DEFAULT_CACHE_SIZE 64
+#define PGFT_MIN_CACHE_SIZE 32
+#define PGFT_DEBUG_CACHE
 
 
 typedef struct
     FTC_Manager cache_manager;
     FTC_CMapCache cache_charmap;
 
+    int cache_size;
     char *_error_msg;
 } FreeTypeInstance;
 
 
     FT_Fixed    baseline;
     FT_Vector   size;
-
-    FT_UInt32   lru;
-    FT_UInt32   hash;
 } FontGlyph;
 
 typedef struct FontText_
     FT_Vector baseline_offset;  /* 26.6 */
 } FontText;
 
+typedef struct __cachenode
+{
+    FontGlyph   glyph;
+    struct __cachenode *next;
+    FT_UInt32 hash;
+
+} PGFT_CacheNode;
+
 typedef struct __glyphcache
 {
-    FontGlyph   **nodes;
+    PGFT_CacheNode  **nodes;
+    PGFT_CacheNode  *free_nodes;
+
+    FT_Byte    *depths;
+
+#ifdef PGFT_DEBUG_CACHE
+    FT_UInt32   count;
+    FT_UInt32   _debug_delete_count;
+    FT_UInt32   _debug_access;
+    FT_UInt32   _debug_hit;
+    FT_UInt32   _debug_miss;
+#endif
+
     FT_UInt32   size_mask;
-
-    FT_UInt32   lru_counter;
-
     PyFreeTypeFont  *font;
 } PGFT_Cache;
 
 /********************************************************* General functions ****/
 const char *PGFT_GetError(FreeTypeInstance *);
 void        PGFT_Quit(FreeTypeInstance *);
-int         PGFT_Init(FreeTypeInstance **);
+int         PGFT_Init(FreeTypeInstance **, int cache_size);
 int         PGFT_TryLoadFont_Filename(FreeTypeInstance *, 
                 PyFreeTypeFont *, const char *, int);
 void        PGFT_UnloadFont(FreeTypeInstance *, PyFreeTypeFont *);
 
 
 /******************************************************** Glyph cache management ****/
-void        PGFT_Cache_Init(PGFT_Cache *cache, PyFreeTypeFont *parent);
+void        PGFT_Cache_Init(FreeTypeInstance *ft, PGFT_Cache *cache, PyFreeTypeFont *parent);
 void        PGFT_Cache_Destroy(PGFT_Cache *cache);
+void        PGFT_Cache_Cleanup(PGFT_Cache *cache);
 FontGlyph * PGFT_Cache_FindGlyph(FreeTypeInstance *ft, PGFT_Cache *cache, FT_UInt character, 
                 const FontRenderMode *render);