diff options
Diffstat (limited to 'src/fontcache')
| -rw-r--r-- | src/fontcache/fcqueue.h | 133 | ||||
| -rw-r--r-- | src/fontcache/fontcache.c | 1019 | ||||
| -rw-r--r-- | src/fontcache/fontcache.h | 121 |
3 files changed, 1273 insertions, 0 deletions
diff --git a/src/fontcache/fcqueue.h b/src/fontcache/fcqueue.h new file mode 100644 index 0000000..58ba6df --- /dev/null +++ b/src/fontcache/fcqueue.h @@ -0,0 +1,133 @@ +/* + * Copyright (c) 1991, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)queue.h 8.5 (Berkeley) 8/20/94 + * $_Id_: queue.h,v 1.10.2.4 1998/05/12 16:35:25 bde Exp $ + * + * ---------------------------------------------------------------------- + * + * Note: + * This header file derived from FreeBSD-2.2.7 + * /usr/include/sys/queue.h, modified for X-TrueType Server by + * Shunsuke Akiyama <akiyama@jp.FreeBSD.org>. + * + * Id: fcqueue.h,v 1.1 1999/01/06 13:36:42 akiyama Exp $ + */ + +#ifndef _FCQUEUE_H_ +#define _FCQUEUE_H_ + +/* + * Tail queue definitions. + */ +#define TAILQ_HEAD(name, type) \ +struct name { \ + struct type *tqh_first; /* first element */ \ + struct type **tqh_last; /* addr of last next element */ \ +} + +#define TAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).tqh_first } + +#define TAILQ_ENTRY(type) \ +struct { \ + struct type *tqe_next; /* next element */ \ + struct type **tqe_prev; /* address of previous next element */ \ +} + +/* + * Tail queue functions. + */ +#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) + +#define TAILQ_FOREACH(var, head, field) \ + for (var = TAILQ_FIRST(head); var; var = TAILQ_NEXT(var, field)) + +#define TAILQ_FIRST(head) ((head)->tqh_first) + +#define TAILQ_LAST(head, headname) \ + (*(((struct headname *)((head)->tqh_last))->tqh_last)) + +#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) + +#define TAILQ_PREV(elm, headname, field) \ + (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) + +#define TAILQ_INIT(head) do { \ + (head)->tqh_first = NULL; \ + (head)->tqh_last = &(head)->tqh_first; \ +} while (0) + +#define TAILQ_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ + (head)->tqh_first->field.tqe_prev = \ + &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (head)->tqh_first = (elm); \ + (elm)->field.tqe_prev = &(head)->tqh_first; \ +} while (0) + +#define TAILQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.tqe_next = NULL; \ + (elm)->field.tqe_prev = (head)->tqh_last; \ + *(head)->tqh_last = (elm); \ + (head)->tqh_last = &(elm)->field.tqe_next; \ +} while (0) + +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ + (elm)->field.tqe_next->field.tqe_prev = \ + &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (listelm)->field.tqe_next = (elm); \ + (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ +} while (0) + +#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ + (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ + (elm)->field.tqe_next = (listelm); \ + *(listelm)->field.tqe_prev = (elm); \ + (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ +} while (0) + +#define TAILQ_REMOVE(head, elm, field) do { \ + if (((elm)->field.tqe_next) != NULL) \ + (elm)->field.tqe_next->field.tqe_prev = \ + (elm)->field.tqe_prev; \ + else \ + (head)->tqh_last = (elm)->field.tqe_prev; \ + *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ +} while (0) + +#endif /* _FCQUEUE_H_ */ diff --git a/src/fontcache/fontcache.c b/src/fontcache/fontcache.c new file mode 100644 index 0000000..0fec03b --- /dev/null +++ b/src/fontcache/fontcache.c @@ -0,0 +1,1019 @@ +/*- + * Copyright (c) 1998-1999 Shunsuke Akiyama <akiyama@jp.FreeBSD.org>. + * All rights reserved. + * Copyright (c) 1998-1999 X-TrueType Server Project, All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * Id: fontcache.c,v 1.19 1999/01/31 13:06:00 akiyama Exp $ + */ +/* $XFree86: xc/lib/font/fontcache/fontcache.c,v 1.5 2001/10/28 03:32:45 tsi Exp $ */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "fontcache.h" + +#define LOW_MARK 0 +#define HI_MARK 1 + +#define PURGE_ENTRY 1 +#define PURGE_BITMAP 2 + +typedef struct { + long hiMark; /* Cache hi water mark */ + long lowMark; /* Cache low water mark */ + long allocated; /* Cache allocated size */ + long used; /* Cache used size */ +} FontCacheSize_t; + +static int CacheInitialized = 0; + +static TAILQ_HEAD(FcInUseQueue, cache_entry) InUseQueueHead, *InUseQueue; +static TAILQ_HEAD(FcFreeQueue, cache_entry) FreeQueueHead, *FreeQueue; +static FCBCB FreeBitmapHead, *FreeBitmap; + +static long CacheHiMark; +static long CacheLowMark; +static int CacheBalance; +static FontCacheSize_t HashSize; +static FontCacheSize_t AllocSize; +static int NeedPurgeCache; +static FontCacheStatistics CacheStatistics; + +static void fc_assign_cache(void); +static int fc_assign_entry(void); +static void fc_flush_cache(void); +static int fc_get_bitmap_area(FontCacheEntryPtr, int); +static void fc_free_bitmap_area(FontCacheBitmapPtr); +static int fc_check_size(int); +static void fc_purge_cache(void); +static void fc_purge_bitmap(void); +static void fc_flush_cache_bitmap(void); +static void fc_flush_cache_inuse(void); +static void fc_flush_cache_free(void); +static void fc_purge_cache_entry(void); +static void fc_purge_cache_entry_pool(void); +static void fc_purge_bitmap_pool(void); + + +/* + * FontCacheInitialize() + * + * Initialize cache work area. + */ + +int +FontCacheInitialize() +{ +#ifdef FONTCACHE + int i; + + if (!CacheInitialized) { + /* + * first time initialization + */ +#if defined(HASH_DEBUG) || defined(DEBUG) + fprintf(stderr, "FontCacheInitialize: initializing cache\n"); +#endif + InUseQueue = &InUseQueueHead; + TAILQ_INIT(InUseQueue); + + FreeQueue = &FreeQueueHead; + TAILQ_INIT(FreeQueue); + + FreeBitmap = &FreeBitmapHead; + FreeBitmap->index = 0; + for (i = 0; i < FC_MEM_HASH_SIZE; i++) { + TAILQ_INIT(&FreeBitmap->head[i]); + } + + CacheHiMark = FC_DEFAULT_CACHE_SIZE * 1024; /* temporary */ + CacheLowMark = (CacheHiMark / 4) * 3; + CacheBalance = FC_CACHE_BALANCE; + + NeedPurgeCache = 0; + + HashSize.allocated = HashSize.used = 0; + AllocSize.allocated = AllocSize.used = 0; + fc_assign_cache(); + fc_assign_entry(); +#if defined(DEBUG) + fprintf(stderr, "FontCacheInitialize: hi=%ld, lo=%ld, bal=%d\n", + CacheHiMark, CacheLowMark, CacheBalance); +#endif + + CacheInitialized = 1; + } else { + /* + * second time or later case. + * flush and reassign cache. + */ +#if defined(HASH_DEBUG) || defined(DEBUG) + fprintf(stderr, "FontCacheInitialize: initializing cache, again\n"); +#endif + } + + memset(&CacheStatistics, 0, sizeof (CacheStatistics)); +#endif /* FONTCACHE */ + + return 0; /* make lint happy */ +} + +/* + * FontCacheChangeSettings() + * + * Change cache size and reinitialize work areas. + * + * Returns 0, if memory allocation failed. Otherwise 1. + */ + +int +FontCacheChangeSettings(FontCacheSettingsPtr cs) +{ + int result; + + if (!CacheInitialized) { + FontCacheInitialize(); + if (!CacheInitialized) + return 0; + } + +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, + "FontCahceChangeSettings: hi-mark=%ld, low-mark=%ld, balance=%ld\n", + cs->himark, cs->lowmark, cs->balance); +#endif + + fc_flush_cache(); + + CacheHiMark = cs->himark; + CacheLowMark = cs->lowmark; + CacheBalance = cs->balance; + + fc_assign_cache(); + result = fc_assign_entry(); + + return result; +} + +/* + * FontCacheGetSettings() + * + * Get current cache control parameters. + */ + +void +FontCacheGetSettings(FontCacheSettingsPtr cs) +{ + if (!CacheInitialized) { + FontCacheInitialize(); + if (!CacheInitialized) + return; + } + + cs->himark = CacheHiMark; + cs->lowmark = CacheLowMark; + cs->balance = CacheBalance; +} + +/* + * FontCacheGetStatistics() + * + * Get current cache statistics. + */ + +void +FontCacheGetStatistics(FontCacheStatisticsPtr cs) +{ + if (!CacheInitialized) { + FontCacheInitialize(); + if (!CacheInitialized) + return; + } + + CacheStatistics.purge_stat = NeedPurgeCache; + CacheStatistics.balance = CacheBalance; + CacheStatistics.f.usage = HashSize.used; + CacheStatistics.v.usage = AllocSize.used; + + memcpy(cs, &CacheStatistics, sizeof (CacheStatistics)); +} + +/* + * FontCacheOpenCache() + * + * Allocate font cache control block and initialize it. + * + * Returns pointer to font cache control block. Or returns NULL when + * detected illegal parameter or memory allocation failed. + */ + +FCCBPtr +FontCacheOpenCache(void *arg) +{ + int linesize; + FCCBPtr this; + int size = 0, mask = 0; + int i; + + static int sizes[] = { 16, 32, 64, 128, 0 }; + + if (!CacheInitialized) { + FontCacheInitialize(); + if (!CacheInitialized) + return NULL; + } + + linesize = (long)arg; +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, "FontCacheOpenCache: line size=%d\n", linesize); +#endif + + for (i = 0; sizes[i] != 0; i++) { + if (sizes[i] == linesize) { + size = linesize; + mask = linesize - 1; + break; + } + } + if (sizes[i] == 0) { + return NULL; + } + + this = (FCCBPtr) malloc(sizeof (FCCB)); + if (this != NULL) { + memset(this, 0, sizeof (FCCB)); + this->head = (FontCacheHeadPtr) malloc(sizeof (FontCacheHead) * size); + if (this->head == NULL) { + free(this); + this = NULL; + } else { + this->size = size; + this->mask = mask; + for (i = 0; i < size; i++) { + TAILQ_INIT(&this->head[i]); + } + } + } + + return this; +} + +/* + * FontCacheCloseCache() + * + * Release font cache control block and all it's related entries. + */ + +void +FontCacheCloseCache(FCCBPtr this) +{ + FontCacheEntryPtr entry, next; + int i; + int size; + + if (!CacheInitialized) { + return; + } + + size = this->size; + for (i = 0; i < size; i++) { + entry = TAILQ_FIRST(&this->head[i]); + while (entry != NULL) { + /* remove entry from in-use queue, here */ + TAILQ_REMOVE(InUseQueue, entry, c_lru); + + /* remove entry from the hash */ + if (entry->bitmapsize > FC_SMALL_BITMAP_SIZE + && entry->charInfo.bits != NULL) { + fc_free_bitmap_area(entry->bmp); + } + entry->charInfo.bits = NULL; + entry->bitmapsize = 0; + + next = TAILQ_NEXT(entry, c_hash); + TAILQ_INSERT_HEAD(FreeQueue, entry, c_lru); + HashSize.used -= sizeof (FontCacheEntry); + entry = next; + } + } + + free(this->head); + free(this); +} + +/* + * FontCacheGetEntry() + * + * Allocate font cache entry and initialize it. + */ + +FontCacheEntryPtr +FontCacheGetEntry() +{ + FontCacheEntryPtr entry; + FontCacheEntryPtr p; + long size; + + /* scan in-use queue and purge if required */ + fc_purge_cache(); + + /* allocate hash entry */ + if (TAILQ_EMPTY(FreeQueue)) { + size = sizeof (FontCacheEntry); + p = (FontCacheEntryPtr) malloc(size); + if (p != NULL) { + TAILQ_INSERT_HEAD(FreeQueue, p, c_lru); + HashSize.allocated += size; +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, "FontCachegetEntry: allocated new entry\n"); +#endif + } + } + + if (!TAILQ_EMPTY(FreeQueue)) { + entry = TAILQ_FIRST(FreeQueue); + TAILQ_REMOVE(FreeQueue, entry, c_lru); + memset(entry, 0, sizeof (FontCacheEntry)); + } else { + entry = NULL; + } + + return entry; +} + +/* + * FontCacheGetBitmap() + * + * Allocate font glyph bitmap area. + * + * Note: + * Allocated area should be cleared. + */ + +int +FontCacheGetBitmap(FontCacheEntryPtr entry, int size) +{ + int oldsize; + int result; + + /* XXX */ + if ((AllocSize.used > AllocSize.hiMark - size) && + (size > FC_SMALL_BITMAP_SIZE)) { + fc_purge_bitmap(); + } + + if (size < 0) /* wrong size */ + return 0; + + result = 0; + oldsize = entry->bitmapsize; + if (size <= FC_SMALL_BITMAP_SIZE) { + /* use coresponding bitmap area */ + if (oldsize > FC_SMALL_BITMAP_SIZE) { + /* We don't need allocated area anymore */ + fc_free_bitmap_area(entry->bmp); + } + entry->bitmapsize = size; + if (size > 0) { + entry->charInfo.bits = entry->bitmap; + memset(entry->charInfo.bits, 0, size); + } else + entry->charInfo.bits = NULL; + + result = 1; + } else { + /* need extra bitmap area */ + if (entry->charInfo.bits == NULL) { + /* no any extra bitmap area */ + if (fc_get_bitmap_area(entry, size)) { + entry->bitmapsize = size; + memset(entry->charInfo.bits, 0, size); + if (fc_check_size(HI_MARK)) { + fc_purge_cache(); + } + result = 1; + } + } else { + /* we already have extra bitmap area */ + if (oldsize == size) { + /* same size, reuse it */ + memset(entry->charInfo.bits, 0, size); + result = 1; + } else { + /* different size */ + fc_free_bitmap_area(entry->bmp); + if (fc_get_bitmap_area(entry, size)) { + entry->bitmapsize = size; + memset(entry->charInfo.bits, 0, size); + if (fc_check_size(HI_MARK)) { + fc_purge_cache(); + } + result = 1; + } + } + } + } + + return result; +} + +/* + * FontCacheSearchEntry() + * + * Search an entry matched with the key from the hash. + */ + +int +FontCacheSearchEntry(FCCBPtr this, int key, FontCacheEntryPtr *value) +{ + FontCacheHeadPtr head; + FontCacheEntryPtr entry; + int index; + + index = key & this->mask; + head = &this->head[index]; + + TAILQ_FOREACH(entry, head, c_hash) { + if (entry->key == key) { + /* found, change position */ + CacheStatistics.f.hits++; + + TAILQ_REMOVE(InUseQueue, entry, c_lru); + TAILQ_INSERT_HEAD(InUseQueue, entry, c_lru); + + TAILQ_REMOVE(head, entry, c_hash); + TAILQ_INSERT_HEAD(head, entry, c_hash); + + /* purge least recentrly used cache entirs */ + fc_purge_cache(); + + *value = entry; + return 1; + } + } + + /* purge least recentrly used cache entirs */ + fc_purge_cache(); + + /* not found */ + CacheStatistics.f.misshits++; + *value = NULL; + return 0; +} + +/* + * FontCacheInsertEntry() + * + * Insert an entry into the cache pool. + */ + +int +FontCacheInsertEntry(FCCBPtr this, int key, FontCacheEntryPtr entry) +{ + FontCacheHeadPtr head; + int index; + + index = key & this->mask; + head = &this->head[index]; + + entry->key = key; + entry->c_head = head; + TAILQ_INSERT_HEAD(head, entry, c_hash); + + /* insert entry into in-use queue */ + TAILQ_INSERT_HEAD(InUseQueue, entry, c_lru); + + /* adjust cache in-use size */ + HashSize.used += sizeof (FontCacheEntry); + if (fc_check_size(HI_MARK)) { + fc_purge_cache(); + } + + return 1; +} + +/* + * fc_assign_cache() + * + * Assign cache size considered with cache balance rate. + */ + +static void +fc_assign_cache() +{ + HashSize.hiMark = (CacheHiMark * CacheBalance) / 100; + HashSize.lowMark = (CacheLowMark * CacheBalance) / 100; + + AllocSize.hiMark = (CacheHiMark * (100 - CacheBalance)) / 100; + AllocSize.lowMark = (CacheLowMark * (100 - CacheBalance)) / 100; +} + +/* + * fc_assign_entry() + * + * Assign cache entry into free queue. + * + * Returns 0, when memory allocation failed. Otherwise 1. + */ + +static int +fc_assign_entry() +{ + FontCacheEntryPtr entry; + long used; + int result = 1; + + used = 0; + while ((used + sizeof (FontCacheEntry)) < HashSize.hiMark) { + entry = (FontCacheEntryPtr) malloc(sizeof (FontCacheEntry)); + if (entry == NULL) { + fprintf(stderr, "fc_assign_entry: can't allocate memory.\n"); + result = 0; + break; + } + TAILQ_INSERT_HEAD(FreeQueue, entry, c_lru); + used += sizeof (FontCacheEntry); + HashSize.allocated += sizeof (FontCacheEntry); + } + + return result; +} + +/* + * fc_get_bitmap_area() + * + * Search allocated memory area from free bitmap hash pool. If there + * is no entry, then allocate new bitmap area. + * + * Returns 0, when memory allocation failed, otherwise 1. And some + * sort of cache entry structure members were updated. + */ + +static int +fc_get_bitmap_area(FontCacheEntryPtr this, int size) +{ + FontCacheBitmapHeadPtr head; + FontCacheBitmapPtr bitmap; + int index; + int result = 0; + + index = size & FC_MEM_HASH_MASK; + head = &FreeBitmap->head[index]; + TAILQ_FOREACH(bitmap, head, b_hash) { + if (bitmap->key == size) { + TAILQ_REMOVE(head, bitmap, b_hash); + this->bmp = bitmap; + this->charInfo.bits = (char *) (bitmap + 1); + bitmap->b_entry = this; + result = 1; + CacheStatistics.v.hits++; + AllocSize.used += (size + sizeof (FontCacheBitmap)); +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, "fc_get_bitmap_area: bitmap entry found in pool\n"); +#endif + break; + } + } + + if (result == 0) { + CacheStatistics.v.misshits++; + bitmap = (FontCacheBitmapPtr) malloc(size + sizeof (FontCacheBitmap)); + if (bitmap != NULL) { + bitmap->b_entry = this; + bitmap->size = size + sizeof (FontCacheBitmap); + bitmap->key = size; + this->bmp = bitmap; + this->charInfo.bits = (char *) (bitmap + 1); + AllocSize.allocated += (size + sizeof (FontCacheBitmap)); + AllocSize.used += (size + sizeof (FontCacheBitmap)); + result = 1; +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, "fc_get_bitmap_area: bitmap entry allocated\n"); +#endif + } else { + this->bmp = NULL; + this->charInfo.bits = NULL; + } + } + + return result; +} + +/* + * fc_free_bitmap_area() + * + * Release allocated bitmap area into free hash pool. + */ + +static void +fc_free_bitmap_area(FontCacheBitmapPtr this) +{ + FontCacheBitmapHeadPtr head; + FontCacheEntryPtr entry; + int index; + +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, "fc_free_bitmap_area: bitmap entry returns into pool\n"); +#endif + + index = this->key & FC_MEM_HASH_MASK; + head = &FreeBitmap->head[index]; + TAILQ_INSERT_HEAD(head, this, b_hash); + + AllocSize.used -= this->size; + + entry = this->b_entry; + entry->bmp = NULL; + entry->bitmapsize = 0; +} + +/* + * fc_flush_cache_bitmap() + * + * Flush all allocated bitmap area from the free hash pool. + */ + +static void +fc_flush_cache_bitmap() +{ + FontCacheBitmapHeadPtr head; + FontCacheBitmapPtr bitmap; + int i; + + for (i = 0; i < FC_MEM_HASH_SIZE; i++) { + head = &FreeBitmap->head[i]; + while (!TAILQ_EMPTY(head)) { + bitmap = TAILQ_FIRST(head); + TAILQ_REMOVE(head, bitmap, b_hash); + + AllocSize.allocated -= bitmap->size; + free(bitmap); + } + } +} + +/* + * fc_flush_cache_inuse() + * + * Release all in-use cache entries. + */ + +static void +fc_flush_cache_inuse() +{ + FontCacheEntryPtr entry; + FontCacheHeadPtr head; + + while (!TAILQ_EMPTY(InUseQueue)) { + /* remove this entry from in-use queue */ + entry = TAILQ_FIRST(InUseQueue); + TAILQ_REMOVE(InUseQueue, entry, c_lru); + + /* remove this entry from hash */ + head = entry->c_head; + TAILQ_REMOVE(head, entry, c_hash); + + /* release bitmap area */ + if (entry->bitmapsize > FC_SMALL_BITMAP_SIZE + && entry->charInfo.bits != NULL) { + fc_free_bitmap_area(entry->bmp); + } + entry->charInfo.bits = NULL; + entry->bitmapsize = 0; + + /* release font-specific private area */ + if ( entry->vfuncs && entry->vfuncs->f_private_dispose ) + (*entry->vfuncs->f_private_dispose)(entry->f_private); + entry->f_private = NULL; + entry->vfuncs = NULL; + + /* add this entry to free queue */ + TAILQ_INSERT_HEAD(FreeQueue, entry, c_lru); + + /* adjust size */ + HashSize.used -= sizeof (FontCacheEntry); + } +} + +/* + * fc_flush_cache_free() + * + * Flush all free cache entries from the free cache queue. + */ + +static void +fc_flush_cache_free() +{ + FontCacheEntryPtr entry; + + /* release entire entries of the free queue */ + while (!TAILQ_EMPTY(FreeQueue)) { + entry = TAILQ_FIRST(FreeQueue); + TAILQ_REMOVE(FreeQueue, entry, c_lru); + free(entry); + HashSize.allocated -= sizeof (FontCacheEntry); + } +} + +/* + * fc_flush_cache() + * + * Flush all cache entries and allocated bitmap area from the pool. + */ + +static void +fc_flush_cache() +{ + fc_flush_cache_inuse(); + fc_flush_cache_bitmap(); + fc_flush_cache_free(); + + memset(&CacheStatistics, 0, sizeof (CacheStatistics)); +} + +/* + * fc_check_size() + * + * Check cache size, then return it's result. + */ + +static int +fc_check_size(int mark) +{ + int result = 0; + + if (mark == LOW_MARK) { + if (HashSize.used > HashSize.lowMark) { + result |= PURGE_ENTRY; + } + if (AllocSize.used > AllocSize.lowMark) { + result |= PURGE_BITMAP; + } + } else { + if (HashSize.used > HashSize.hiMark) { + result |= PURGE_ENTRY; + } + if (AllocSize.used > AllocSize.hiMark) { + result |= PURGE_BITMAP; + } + } + + return result; +} + +/* + * fc_purge_cache_entry() + * + * Purge least recently used cache entry. + */ + +static void +fc_purge_cache_entry() +{ + FontCacheHeadPtr head; + FontCacheEntryPtr entry; + int i; + + for (i = 0; i < FC_PURGE_PER_SCAN; i++) { + /* get least recently used entry */ + entry = TAILQ_LAST(InUseQueue, FcInUseQueue); + +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, "fc_purge_cache_entry: purged: %p, %d\n", + entry, entry->key); +#endif + + /* remove this entry from in-use queue */ + TAILQ_REMOVE(InUseQueue, entry, c_lru); + + /* remove this entry from the hash */ + head = entry->c_head; + TAILQ_REMOVE(head, entry, c_hash); + + /* release bitmap area */ + if (entry->bitmapsize > FC_SMALL_BITMAP_SIZE + && entry->charInfo.bits != NULL) { + fc_free_bitmap_area(entry->bmp); + CacheStatistics.v.purged++; + } + entry->charInfo.bits = NULL; + entry->bitmapsize = 0; + + /* release font-specific private area */ + if ( entry->vfuncs && entry->vfuncs->f_private_dispose ) + (*entry->vfuncs->f_private_dispose)(entry->f_private); + entry->f_private = NULL; + entry->vfuncs = NULL; + + /* add this entry to free queue */ + TAILQ_INSERT_HEAD(FreeQueue, entry, c_lru); + + HashSize.used -= sizeof (FontCacheEntry); + CacheStatistics.f.purged++; + } +} + +/* + * fc_purge_cache_entry_pool() + * + * Purge free cache entries, to adjust cache size. + */ + +static void +fc_purge_cache_entry_pool() +{ + FontCacheEntryPtr entry; + + while (!TAILQ_EMPTY(FreeQueue)) { + entry = TAILQ_LAST(FreeQueue, FcFreeQueue); + TAILQ_REMOVE(FreeQueue, entry, c_lru); +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, "fc_purge_cache_entry_pool: purged from free queue: %p\n", + entry); +#endif + HashSize.allocated -= sizeof (FontCacheEntry); + free(entry); + if (HashSize.allocated <= HashSize.hiMark) { + break; + } + } +} + +/* + * fc_purge_bitmap() + * + * Purge least recently used allocated bitmap area. + */ + +static void +fc_purge_bitmap() +{ + FontCacheEntryPtr entry, first; + int purged = 0; + + /* release used entry, if required */ + first = TAILQ_FIRST(InUseQueue); + if (first != NULL) { + entry = TAILQ_LAST(InUseQueue, FcInUseQueue); + while (purged < FC_PURGE_PER_SCAN) { + if (entry->bmp != NULL) { +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, "fc_purge_bitmap: purged from live queue: %p, %d(%d)\n", + entry->bmp, entry->bmp->key, entry->bmp->size); +#endif + fc_free_bitmap_area(entry->bmp); + entry->charInfo.bits = NULL; + CacheStatistics.v.purged++; + purged++; + } + if (entry == first) { + break; + } + entry = TAILQ_PREV(entry, FcInUseQueue, c_lru); + } + } +} + +/* + * fc_purge_bitmap_pool() + * + * Purge free bitmap area from pool, to adjust cache size. + */ + +static void +fc_purge_bitmap_pool() +{ + int this, stop, quit; + FontCacheBitmapHeadPtr head; + FontCacheBitmapPtr bitmap; + + /* release free bitmap entry */ + this = FreeBitmap->index; + stop = this; + quit = 0; + + do { + head = &FreeBitmap->head[this]; + while (!TAILQ_EMPTY(head)) { + bitmap = TAILQ_LAST(head, fcmem_head); + TAILQ_REMOVE(head, bitmap, b_hash); +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, "fc_purge_bitmap_pool: purged from pool: %p, %d(%d)\n", + bitmap, bitmap->key, bitmap->size); +#endif + AllocSize.allocated -= bitmap->size; + free(bitmap); + if (AllocSize.allocated <= AllocSize.hiMark) { + quit = 1; + break; + } + } + this++; + this &= FC_MEM_HASH_MASK; + } while (this != stop && quit == 0); + + FreeBitmap->index++; + FreeBitmap->index &= FC_MEM_HASH_MASK; +} + +/* + * fc_purge_cache() + * + * Purge font cache, if required. + */ + +static void +fc_purge_cache() +{ + int strategy; + + if (NeedPurgeCache) { + strategy = fc_check_size(LOW_MARK); + switch (strategy) { + case PURGE_ENTRY : + CacheStatistics.purge_runs++; + fc_purge_cache_entry(); + break; + case PURGE_BITMAP : + CacheStatistics.purge_runs++; + fc_purge_bitmap(); + break; + case (PURGE_ENTRY | PURGE_BITMAP) : + CacheStatistics.purge_runs++; + fc_purge_cache_entry(); + fc_purge_bitmap(); + break; + default : + NeedPurgeCache = 0; + break; + } + } else { + strategy = fc_check_size(HI_MARK); + switch (strategy) { + case PURGE_ENTRY : + if ((CacheBalance + FC_BALANCE_DIFFS) <= FC_BALANCE_HI) { + CacheBalance += FC_BALANCE_DIFFS; +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, "fc_purge_cache: cache balance changed to %d\n", CacheBalance); +#endif + fc_assign_cache(); + fc_purge_bitmap_pool(); + } else { + CacheStatistics.purge_runs++; + NeedPurgeCache = 1; + while (fc_check_size(HI_MARK) & PURGE_ENTRY) { + fc_purge_cache_entry(); + } + } + break; + case PURGE_BITMAP : + if ((CacheBalance - FC_BALANCE_DIFFS) >= FC_BALANCE_LOW) { + CacheBalance -= FC_BALANCE_DIFFS; +#if defined(HASH_DEBUG) || defined(DEBUG) +fprintf(stderr, "fc_purge_cache: cache balance changed to %d\n", CacheBalance); +#endif + fc_assign_cache(); + fc_purge_cache_entry_pool(); + } else { + CacheStatistics.purge_runs++; + NeedPurgeCache = 1; + while (fc_check_size(HI_MARK) & PURGE_BITMAP) { + fc_purge_bitmap(); + } + } + break; + case (PURGE_ENTRY | PURGE_BITMAP) : + CacheStatistics.purge_runs++; + NeedPurgeCache = 1; + while (fc_check_size(HI_MARK)) { + fc_purge_cache_entry(); + fc_purge_bitmap(); + } + break; + default : + break; + } + } +} diff --git a/src/fontcache/fontcache.h b/src/fontcache/fontcache.h new file mode 100644 index 0000000..3a10b9f --- /dev/null +++ b/src/fontcache/fontcache.h @@ -0,0 +1,121 @@ +/*- + * Copyright (c) 1998-1999 Shunsuke Akiyama <akiyama@jp.FreeBSD.org>. + * All rights reserved. + * Copyright (c) 1998-1999 X-TrueType Server Project, All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * Id: fontcache.h,v 1.12 1999/01/09 06:24:30 akiyama Exp $ + */ +/* $XFree86: xc/lib/font/fontcache/fontcache.h,v 1.7 2003/01/26 03:02:19 dawes Exp $ */ + +#ifndef _FONTCACHE_H_ +#define _FONTCACHE_H_ + +#include "fontmisc.h" +#include "fontstruct.h" +#include "fcqueue.h" +#define _FONTCACHE_SERVER_ +#include <X11/extensions/fontcacheP.h> + +/* constant declarations */ + +#ifndef FC_DEFAULT_CACHE_SIZE +#define FC_DEFAULT_CACHE_SIZE 5120 /* in KB */ +#endif + +#define FC_CACHE_BALANCE 70 /* in percentage */ +#define FC_BALANCE_LOW 10 /* in percentage */ +#define FC_BALANCE_HI 90 /* in percentage */ +#define FC_BALANCE_DIFFS 5 /* in percentage */ + +#define FC_SMALL_BITMAP_SIZE 128 + +#define FC_MEM_HASH_SIZE 256 +#define FC_MEM_HASH_MASK (FC_MEM_HASH_SIZE - 1) + +#define FC_PURGE_PER_SCAN 2 + +/* data type declarations */ + +struct cache_entry; +struct fcbitmap; + +TAILQ_HEAD(fchash_head, cache_entry); +TAILQ_HEAD(fcmem_head, fcbitmap); + +struct fcbitmap { + TAILQ_ENTRY(fcbitmap) b_hash; + struct cache_entry *b_entry; + int size; + int key; +}; + +struct fc_entry_vfuncs { + void (*f_private_dispose)(void *f_private); +}; + +struct cache_entry { + TAILQ_ENTRY(cache_entry) c_hash; /* Hash chain. */ + TAILQ_ENTRY(cache_entry) c_lru; /* Font cache LRU list chain. */ + struct fchash_head *c_head; /* Pointer to head. */ + int key; /* hash key */ + CharInfoRec charInfo; /* CharInfo record */ + struct fcbitmap *bmp; + void *f_private; /* Font-specific private data */ + struct fc_entry_vfuncs *vfuncs; /* virtual function table */ + int bitmapsize; /* Bitmap size */ + char bitmap[FC_SMALL_BITMAP_SIZE]; /* Small bitmap data area */ +}; + +struct fchash { + int size; + int mask; + struct fchash_head *head; +}; + +struct fcmemhash { + int index; + struct fcmem_head head[FC_MEM_HASH_SIZE]; +}; + +typedef struct fcbitmap FontCacheBitmap, *FontCacheBitmapPtr; +typedef struct cache_entry FontCacheEntry, *FontCacheEntryPtr; +typedef struct fchash_head FontCacheHead, *FontCacheHeadPtr; +typedef struct fcmem_head FontCacheBitmapHead, *FontCacheBitmapHeadPtr; +typedef struct fchash FCCB, *FCCBPtr; +typedef struct fcmemhash FCBCB, *FCBCBPtr; + +/* Function prototypes */ + +int FontCacheInitialize(void); +FCCBPtr FontCacheOpenCache(void * /* arg */); +void FontCacheCloseCache(FCCBPtr /* this */); +FontCacheEntryPtr FontCacheGetEntry(void); +int FontCacheSearchEntry(FCCBPtr /* this */, int /* key */, + FontCacheEntryPtr * /* value */); +int FontCacheInsertEntry(FCCBPtr /* this */, int /* key */, + FontCacheEntryPtr /* entry */); +int FontCacheGetBitmap(FontCacheEntryPtr /* entry */, + int /* size */); + +#endif /* _FONTCACHE_H_ */ |