add "trackmemusage" property to use in improved _XftFontUncacheGlyph

The linear search used for randomly selecting a glyph to discard is
inefficient.  This commit provides for a doubly-linked list which
could be maintained by the library to quickly discard the least
recently used glyph.

Signed-off-by: Thomas E. Dickey <dickey@invisible-island.net>

7 files changed, 71 insertions, 27 deletions

diff --git a/include/X11/Xft/Xft.h.in b/include/X11/Xft/Xft.h.in
index 7341f56..0fcc7d6 100644
--- a/include/X11/Xft/Xft.h.in
+++ b/include/X11/Xft/Xft.h.in
@@ -55,6 +55,7 @@
 #define XFT_XLFD		"xlfd"
 #define XFT_MAX_GLYPH_MEMORY	"maxglyphmemory"
 #define XFT_MAX_UNREF_FONTS	"maxunreffonts"
+#define XFT_TRACK_MEM_USAGE	"trackmemusage"
 
 extern FT_Library	_XftFTlibrary;
 
diff --git a/src/xftdpy.c b/src/xftdpy.c
index 1d9a129..f431ec1 100644
--- a/src/xftdpy.c
+++ b/src/xftdpy.c
@@ -22,6 +22,8 @@
 
 #include "xftint.h"
 
+#define BtoS(b) ((b) ? "true" : "false")
+
 _X_HIDDEN XftDisplayInfo	*_XftDisplayInfo;
 
 static int
@@ -85,7 +87,7 @@ _XftDisplayInfoGet (Display *dpy, FcBool createIfNecessary)
     if (!createIfNecessary)
 	return NULL;
 
-    info = (XftDisplayInfo *) malloc (sizeof (XftDisplayInfo));
+    info = malloc (sizeof (XftDisplayInfo));
     if (!info)
 	goto bail0;
     info->codes = XAddExtension (dpy);
@@ -177,7 +179,14 @@ _XftDisplayInfoGet (Display *dpy, FcBool createIfNecessary)
 						  XFT_MAX_UNREF_FONTS, 0,
 						  XFT_DPY_MAX_UNREF_FONTS);
     if (XftDebug() & XFT_DBG_CACHE)
-	printf ("global max unref fonts %d\n", info->max_unref_fonts);
+	printf ("global max unref fonts  %d\n", info->max_unref_fonts);
+
+    info->track_mem_usage = FcFalse;
+    info->track_mem_usage = XftDefaultGetBool (dpy,
+					       XFT_TRACK_MEM_USAGE, 0,
+					       FcFalse);
+    if (XftDebug() & XFT_DBG_CACHE)
+	printf ("global track mem usage  %s\n", BtoS(info->track_mem_usage));
 
     memset (info->fontHash, '\0', sizeof (XftFont *) * XFT_NUM_FONT_HASH);
     return info;
@@ -272,6 +281,7 @@ XftDefaultSet (Display *dpy, FcPattern *defaults)
     if (info->defaults)
 	FcPatternDestroy (info->defaults);
     info->defaults = defaults;
+
     if (!info->max_glyph_memory)
 	info->max_glyph_memory = XFT_DPY_MAX_GLYPH_MEMORY;
     info->max_glyph_memory = (unsigned long)XftDefaultGetInteger (dpy,
@@ -279,13 +289,21 @@ XftDefaultSet (Display *dpy, FcPattern *defaults)
 						   (int)info->max_glyph_memory);
     if (XftDebug () & XFT_DBG_CACHE)
 	printf ("update max cache memory %ld\n", info->max_glyph_memory);
+
     if (!info->max_unref_fonts)
 	info->max_unref_fonts = XFT_DPY_MAX_UNREF_FONTS;
     info->max_unref_fonts = XftDefaultGetInteger (dpy,
 						  XFT_MAX_UNREF_FONTS, 0,
 						  info->max_unref_fonts);
     if (XftDebug() & XFT_DBG_CACHE)
-	printf ("update max unref fonts %d\n", info->max_unref_fonts);
+	printf ("update max unref fonts  %d\n", info->max_unref_fonts);
+
+    info->track_mem_usage = XftDefaultGetBool (dpy,
+					       XFT_TRACK_MEM_USAGE, 0,
+					       info->track_mem_usage);
+    if (XftDebug() & XFT_DBG_CACHE)
+	printf ("update track mem usage  %s\n", BtoS(info->track_mem_usage));
+
     return True;
 }
 
diff --git a/src/xftdraw.c b/src/xftdraw.c
index 4054714..c77cdee 100644
--- a/src/xftdraw.c
+++ b/src/xftdraw.c
@@ -132,7 +132,7 @@ XftDrawCreate (Display   *dpy,
 {
     XftDraw	*draw;
 
-    draw = (XftDraw *) malloc (sizeof (XftDraw));
+    draw = malloc (sizeof (XftDraw));
     if (!draw)
 	return NULL;
 
@@ -158,7 +158,7 @@ XftDrawCreateBitmap (Display	*dpy,
 {
     XftDraw	*draw;
 
-    draw = (XftDraw *) malloc (sizeof (XftDraw));
+    draw = malloc (sizeof (XftDraw));
     if (!draw)
 	return NULL;
     draw->dpy = dpy;
@@ -184,7 +184,7 @@ XftDrawCreateAlpha (Display *dpy,
 {
     XftDraw	*draw;
 
-    draw = (XftDraw *) malloc (sizeof (XftDraw));
+    draw = malloc (sizeof (XftDraw));
     if (!draw)
 	return NULL;
     draw->dpy = dpy;
diff --git a/src/xftfreetype.c b/src/xftfreetype.c
index bcf9e6a..6a66442 100644
--- a/src/xftfreetype.c
+++ b/src/xftfreetype.c
@@ -87,7 +87,7 @@ _XftGetFaceFile (FT_Face face)
     f = malloc (sizeof (XftFtFile));
     if (!f)
 	return NULL;
-    XftMemAlloc (XFT_MEM_FILE, sizeof(XftFtFile));
+    XftMemAlloc (XFT_MEM_FILE, sizeof (XftFtFile));
     f->next = NULL;
 
     f->ref = 1;
@@ -385,7 +385,7 @@ XftFontInfoFill (Display *dpy, _Xconst FcPattern *pattern, XftFontInfo *fi)
      * hash or XftFontInfoEqual().
      */
 
-    memset (fi, '\0', sizeof(*fi));
+    memset (fi, '\0', sizeof (*fi));
 
     /*
      * Find the associated file
@@ -999,9 +999,13 @@ XftFontOpenInfo (Display	*dpy,
     /*
      * Glyph memory management fields
      */
-    font->glyph_memory = 0;
+    font->glyph_memory     = 0;
     font->max_glyph_memory = (unsigned long)max_glyph_memory;
-    font->use_free_glyphs = info->use_free_glyphs;
+    font->track_mem_usage  = info->track_mem_usage;
+    font->use_free_glyphs  = info->use_free_glyphs;
+    font->sizeof_glyph     = (font->track_mem_usage
+    			      ? sizeof(XftGlyphUsage)
+			      : sizeof(XftGlyph));
 
     _XftUnlockFile (fi->file);
 
diff --git a/src/xftglyphs.c b/src/xftglyphs.c
index e04387a..9d37644 100644
--- a/src/xftglyphs.c
+++ b/src/xftglyphs.c
@@ -662,7 +662,7 @@ XftFontLoadGlyphs (Display	    *dpy,
 	 */
 	glyph = (Glyph) glyphindex;
 
-	xftg->glyph_memory = (size_t)size + sizeof (XftGlyph);
+	xftg->glyph_memory = (size_t)size + font->sizeof_glyph;
 	if (font->format)
 	{
 	    if (!font->glyphset)
@@ -764,7 +764,7 @@ XftFontUnloadGlyphs (Display		*dpy,
 		info->glyph_memory -= xftg->glyph_memory;
 	}
 	free (xftg);
-	XftMemFree (XFT_MEM_GLYPH, sizeof (XftGlyph));
+	XftMemFree (XFT_MEM_GLYPH, font->sizeof_glyph);
 	font->glyphs[glyphindex] = NULL;
     }
     if (font->glyphset && nused)
@@ -790,10 +790,10 @@ XftFontCheckGlyph (Display	*dpy,
     {
 	if (!xftg)
 	{
-	    xftg = (XftGlyph *) malloc (sizeof (XftGlyph));
+	    xftg = malloc (font->sizeof_glyph);
 	    if (!xftg)
 		return FcFalse;
-	    XftMemAlloc (XFT_MEM_GLYPH, sizeof (XftGlyph));
+	    XftMemAlloc (XFT_MEM_GLYPH, font->sizeof_glyph);
 	    xftg->bitmap = NULL;
 	    xftg->glyph_memory = 0;
 	    font->glyphs[glyph] = xftg;
diff --git a/src/xftinit.c b/src/xftinit.c
index 0a52536..b7632e3 100644
--- a/src/xftinit.c
+++ b/src/xftinit.c
@@ -48,10 +48,10 @@ static struct {
     int	    free_count;
     size_t  free_mem;
 } XftInUse[XFT_MEM_NUM] = {
-    { "XftDraw",   0, 0, 0, 0 },
-    { "XftFont",   0, 0, 0, 0 },
-    { "XftFtFile", 0, 0, 0, 0 },
-    { "XftGlyph",  0, 0, 0, 0 },
+    { "XftDraw",   0, 0, 0, 0 },	/* XFT_MEM_DRAW */
+    { "XftFont",   0, 0, 0, 0 },	/* XFT_MEM_FONT */
+    { "XftFtFile", 0, 0, 0, 0 },	/* XFT_MEM_FILE */
+    { "XftGlyph",  0, 0, 0, 0 },	/* XFT_MEM_GLYPH */
 };
 
 static int  XftAllocCount;
@@ -69,14 +69,14 @@ XftMemReport (void)
 {
     int	i;
     printf ("Xft Memory Usage:\n");
-    printf ("\t   Which       Alloc           Free\n");
-    printf ("\t           count   bytes   count   bytes\n");
+    printf ("\t    Which       Alloc           Free\n");
+    printf ("\t            count   bytes   count   bytes\n");
     for (i = 0; i < XFT_MEM_NUM; i++)
-	printf ("\t%8.8s%8d%8lu%8d%8lu\n",
+	printf ("\t%9.9s%8d%8lu%8d%8lu\n",
 		XftInUse[i].name,
 		XftInUse[i].alloc_count, (unsigned long) XftInUse[i].alloc_mem,
 		XftInUse[i].free_count, (unsigned long) XftInUse[i].free_mem);
-    printf ("\t%8.8s%8d%8lu%8d%8lu\n",
+    printf ("\t%9.9s%8d%8lu%8d%8lu\n",
 	    "Total",
 	    XftAllocCount, (unsigned long) XftAllocMem,
 	    XftFreeCount, (unsigned long) XftFreeMem);
diff --git a/src/xftint.h b/src/xftint.h
index f35823f..3687d6f 100644
--- a/src/xftint.h
+++ b/src/xftint.h
@@ -88,6 +88,16 @@ typedef struct _XftGlyph {
 } XftGlyph;
 
 /*
+ * If the "trackmemusage" option is set, glyphs are managed via a doubly-linked
+ * list.  To save space, the links are just array indices.
+ */
+typedef struct _XftGlyphUsage {
+    XftGlyph        contents;
+    FT_UInt	    newer;
+    FT_UInt	    older;
+} XftGlyphUsage;
+
+/*
  * A hash table translates Unicode values into glyph indices
  */
 typedef struct _XftUcsHash {
@@ -181,6 +191,8 @@ typedef struct _XftFontInt {
      */
     unsigned long	glyph_memory;
     unsigned long	max_glyph_memory;
+    unsigned            sizeof_glyph;	/* sizeof(XftGlyph) or XftGlyphUsage */
+    FcBool		track_mem_usage;   /* Use XftGlyphUsage */
     FcBool		use_free_glyphs;   /* Use XRenderFreeGlyphs */
 } XftFontInt;
 
@@ -250,6 +262,7 @@ typedef struct _XftDisplayInfo {
     XRenderPictFormat	    *solidFormat;
     unsigned long	    glyph_memory;
     unsigned long	    max_glyph_memory;
+    FcBool		    track_mem_usage;
     FcBool		    use_free_glyphs;
     int			    num_unref_fonts;
     int			    max_unref_fonts;
@@ -273,6 +286,9 @@ typedef struct _XftDisplayInfo {
 
 extern XftDisplayInfo	*_XftDisplayInfo;
 
+/*
+ * Bits in $XFT_DEBUG, which can be combined.
+ */
 #define XFT_DBG_OPEN	1
 #define XFT_DBG_OPENV	2
 #define XFT_DBG_RENDER	4
@@ -284,11 +300,16 @@ extern XftDisplayInfo	*_XftDisplayInfo;
 #define XFT_DBG_CACHEV	256
 #define XFT_DBG_MEMORY	512
 
-#define XFT_MEM_DRAW	0
-#define XFT_MEM_FONT	1
-#define XFT_MEM_FILE	2
-#define XFT_MEM_GLYPH	3
-#define XFT_MEM_NUM	4
+/*
+ * Categories for memory allocation.
+ */
+typedef enum {
+    XFT_MEM_DRAW
+    , XFT_MEM_FONT
+    , XFT_MEM_FILE
+    , XFT_MEM_GLYPH
+    , XFT_MEM_NUM
+} XFT_MEM_KIND;
 
 #define AllocTypedArray(n,type)         malloc ((size_t)(n) * sizeof (type))
 #define AllocUIntArray(n)               AllocTypedArray(n, FT_UInt)