#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#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;
long lowMark;
long allocated;
long used;
} 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);
int
FontCacheInitialize()
{
#ifdef FONTCACHE
int i;
if (!CacheInitialized) {
#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;
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 {
#if defined(HASH_DEBUG) || defined(DEBUG)
fprintf(stderr, "FontCacheInitialize: initializing cache, again\n");
#endif
}
memset(&CacheStatistics, 0, sizeof (CacheStatistics));
#endif
return 0;
}
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;
}
void
FontCacheGetSettings(FontCacheSettingsPtr cs)
{
if (!CacheInitialized) {
FontCacheInitialize();
if (!CacheInitialized)
return;
}
cs->himark = CacheHiMark;
cs->lowmark = CacheLowMark;
cs->balance = CacheBalance;
}
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));
}
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;
}
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) {
TAILQ_REMOVE(InUseQueue, entry, c_lru);
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);
}
FontCacheEntryPtr
FontCacheGetEntry()
{
FontCacheEntryPtr entry;
FontCacheEntryPtr p;
long size;
fc_purge_cache();
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;
}
int
FontCacheGetBitmap(FontCacheEntryPtr entry, int size)
{
int oldsize;
int result;
if ((AllocSize.used > AllocSize.hiMark - size) &&
(size > FC_SMALL_BITMAP_SIZE)) {
fc_purge_bitmap();
}
if (size < 0)
return 0;
result = 0;
oldsize = entry->bitmapsize;
if (size <= FC_SMALL_BITMAP_SIZE) {
if (oldsize > FC_SMALL_BITMAP_SIZE) {
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 {
if (entry->charInfo.bits == NULL) {
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 {
if (oldsize == size) {
memset(entry->charInfo.bits, 0, size);
result = 1;
} else {
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;
}
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) {
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);
fc_purge_cache();
*value = entry;
return 1;
}
}
fc_purge_cache();
CacheStatistics.f.misshits++;
*value = NULL;
return 0;
}
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);
TAILQ_INSERT_HEAD(InUseQueue, entry, c_lru);
HashSize.used += sizeof (FontCacheEntry);
if (fc_check_size(HI_MARK)) {
fc_purge_cache();
}
return 1;
}
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;
}
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;
}
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;
}
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;
}
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);
}
}
}
static void
fc_flush_cache_inuse()
{
FontCacheEntryPtr entry;
FontCacheHeadPtr head;
while (!TAILQ_EMPTY(InUseQueue)) {
entry = TAILQ_FIRST(InUseQueue);
TAILQ_REMOVE(InUseQueue, entry, c_lru);
head = entry->c_head;
TAILQ_REMOVE(head, entry, c_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;
if ( entry->vfuncs && entry->vfuncs->f_private_dispose )
(*entry->vfuncs->f_private_dispose)(entry->f_private);
entry->f_private = NULL;
entry->vfuncs = NULL;
TAILQ_INSERT_HEAD(FreeQueue, entry, c_lru);
HashSize.used -= sizeof (FontCacheEntry);
}
}
static void
fc_flush_cache_free()
{
FontCacheEntryPtr entry;
while (!TAILQ_EMPTY(FreeQueue)) {
entry = TAILQ_FIRST(FreeQueue);
TAILQ_REMOVE(FreeQueue, entry, c_lru);
free(entry);
HashSize.allocated -= sizeof (FontCacheEntry);
}
}
static void
fc_flush_cache()
{
fc_flush_cache_inuse();
fc_flush_cache_bitmap();
fc_flush_cache_free();
memset(&CacheStatistics, 0, sizeof (CacheStatistics));
}
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;
}
static void
fc_purge_cache_entry()
{
FontCacheHeadPtr head;
FontCacheEntryPtr entry;
int i;
for (i = 0; i < FC_PURGE_PER_SCAN; i++) {
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
TAILQ_REMOVE(InUseQueue, entry, c_lru);
head = entry->c_head;
TAILQ_REMOVE(head, entry, c_hash);
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;
if ( entry->vfuncs && entry->vfuncs->f_private_dispose )
(*entry->vfuncs->f_private_dispose)(entry->f_private);
entry->f_private = NULL;
entry->vfuncs = NULL;
TAILQ_INSERT_HEAD(FreeQueue, entry, c_lru);
HashSize.used -= sizeof (FontCacheEntry);
CacheStatistics.f.purged++;
}
}
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;
}
}
}
static void
fc_purge_bitmap()
{
FontCacheEntryPtr entry, first;
int purged = 0;
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);
}
}
}
static void
fc_purge_bitmap_pool()
{
int this, stop, quit;
FontCacheBitmapHeadPtr head;
FontCacheBitmapPtr bitmap;
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;
}
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;
}
}
}