1 /*
   2  * Copyright (c) 2003, 2008, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 #include <malloc.h>
  27 #include "jni.h"
  28 #include "AccelGlyphCache.h"
  29 #include "Trace.h"
  30 
  31 /**
  32  * When the cache is full, we will try to reuse the cache cells that have
  33  * been used relatively less than the others (and we will save the cells that
  34  * have been rendered more than the threshold defined here).
  35  */
  36 #define TIMES_RENDERED_THRESHOLD 5
  37 
  38 /**
  39  * Creates a new GlyphCacheInfo structure, fills in the initial values, and
  40  * then returns a pointer to the GlyphCacheInfo record.
  41  *
  42  * Note that this method only sets up a data structure describing a
  43  * rectangular region of accelerated memory, containing "virtual" cells of
  44  * the requested size.  The cell information is added lazily to the linked
  45  * list describing the cache as new glyphs are added.  Platform specific
  46  * glyph caching code is responsible for actually creating the accelerated
  47  * memory surface that will contain the individual glyph images.
  48  *
  49  * Each glyph contains a reference to a list of cell infos - one per glyph
  50  * cache. There may be multiple glyph caches (for example, one per graphics
  51  * adapter), so if the glyph is cached on two devices its cell list will
  52  * consists of two elements corresponding to different glyph caches.
  53  *
  54  * The platform-specific glyph caching code is supposed to use
  55  * GetCellInfoForCache method for retrieving cache infos from the glyph's list.
  56  *
  57  * Note that if it is guaranteed that there will be only one global glyph
  58  * cache then it one does not have to use AccelGlyphCache_GetCellInfoForCache
  59  * for retrieving cell info for the glyph, but instead just use the struct's
  60  * field directly.
  61  */
  62 GlyphCacheInfo *
  63 AccelGlyphCache_Init(jint width, jint height,
  64                      jint cellWidth, jint cellHeight,
  65                      FlushFunc *func)
  66 {
  67     GlyphCacheInfo *gcinfo;
  68 
  69     J2dTraceLn(J2D_TRACE_INFO, "AccelGlyphCache_Init");
  70 
  71     gcinfo = (GlyphCacheInfo *)malloc(sizeof(GlyphCacheInfo));
  72     if (gcinfo == NULL) {
  73         J2dRlsTraceLn(J2D_TRACE_ERROR,
  74             "AccelGlyphCache_Init: could not allocate GlyphCacheInfo");
  75         return NULL;
  76     }
  77 
  78     gcinfo->head = NULL;
  79     gcinfo->tail = NULL;
  80     gcinfo->width = width;
  81     gcinfo->height = height;
  82     gcinfo->cellWidth = cellWidth;
  83     gcinfo->cellHeight = cellHeight;
  84     gcinfo->isFull = JNI_FALSE;
  85     gcinfo->Flush = func;
  86 
  87     return gcinfo;
  88 }
  89 
  90 /**
  91  * Attempts to add the provided glyph to the specified cache.  If the
  92  * operation is successful, a pointer to the newly occupied cache cell is
  93  * stored in the glyph's cellInfo field; otherwise, its cellInfo field is
  94  * set to NULL, indicating that the glyph's original bits should be rendered
  95  * instead.  If the cache is full, the least-recently-used glyph is
  96  * invalidated and its cache cell is reassigned to the new glyph being added.
  97  *
  98  * Note that this method only ensures that a rectangular region in the
  99  * "virtual" glyph cache is available for the glyph image.  Platform specific
 100  * glyph caching code is responsible for actually caching the glyph image
 101  * in the associated accelerated memory surface.
 102  *
 103  * Returns created cell info if it was successfully created and added to the
 104  * cache and glyph's cell lists, NULL otherwise.
 105  */
 106 CacheCellInfo *
 107 AccelGlyphCache_AddGlyph(GlyphCacheInfo *cache, GlyphInfo *glyph)
 108 {
 109     CacheCellInfo *cellinfo = NULL;
 110     jint w = glyph->width;
 111     jint h = glyph->height;
 112 
 113     J2dTraceLn(J2D_TRACE_INFO, "AccelGlyphCache_AddGlyph");
 114 
 115     if ((glyph->width > cache->cellWidth) ||
 116         (glyph->height > cache->cellHeight))
 117     {
 118         return NULL;
 119     }
 120 
 121     if (!cache->isFull) {
 122         jint x, y;
 123 
 124         if (cache->head == NULL) {
 125             x = 0;
 126             y = 0;
 127         } else {
 128             x = cache->tail->x + cache->cellWidth;
 129             y = cache->tail->y;
 130             if ((x + cache->cellWidth) > cache->width) {
 131                 x = 0;
 132                 y += cache->cellHeight;
 133                 if ((y + cache->cellHeight) > cache->height) {
 134                     // no room left for a new cell; we'll go through the
 135                     // isFull path below
 136                     cache->isFull = JNI_TRUE;
 137                 }
 138             }
 139         }
 140 
 141         if (!cache->isFull) {
 142             // create new CacheCellInfo
 143             cellinfo = (CacheCellInfo *)malloc(sizeof(CacheCellInfo));
 144             if (cellinfo == NULL) {
 145                 J2dTraceLn(J2D_TRACE_ERROR, "could not allocate CellInfo");
 146                 return NULL;
 147             }
 148 
 149             cellinfo->cacheInfo = cache;
 150             cellinfo->glyphInfo = glyph;
 151             cellinfo->timesRendered = 0;
 152             cellinfo->x = x;
 153             cellinfo->y = y;
 154             cellinfo->leftOff = 0;
 155             cellinfo->rightOff = 0;
 156             cellinfo->tx1 = (jfloat)cellinfo->x / cache->width;
 157             cellinfo->ty1 = (jfloat)cellinfo->y / cache->height;
 158             cellinfo->tx2 = cellinfo->tx1 + ((jfloat)w / cache->width);
 159             cellinfo->ty2 = cellinfo->ty1 + ((jfloat)h / cache->height);
 160 
 161             if (cache->head == NULL) {
 162                 // initialize the head cell
 163                 cache->head = cellinfo;
 164             } else {
 165                 // update existing tail cell
 166                 cache->tail->next = cellinfo;
 167             }
 168 
 169             // add the new cell to the end of the list
 170             cache->tail = cellinfo;
 171             cellinfo->next = NULL;
 172             cellinfo->nextGCI = NULL;
 173         }
 174     }
 175 
 176     if (cache->isFull) {
 177         /**
 178          * Search through the cells, and for each cell:
 179          *   - reset its timesRendered counter to zero
 180          *   - toss it to the end of the list
 181          * Eventually we will find a cell that either:
 182          *   - is empty, or
 183          *   - has been used less than the threshold
 184          * When we find such a cell, we will:
 185          *   - break out of the loop
 186          *   - invalidate any glyph that may be residing in that cell
 187          *   - update the cell with the new resident glyph's information
 188          *
 189          * The goal here is to keep the glyphs rendered most often in the
 190          * cache, while younger glyphs hang out near the end of the list.
 191          * Those young glyphs that have only been used a few times will move
 192          * towards the head of the list and will eventually be kicked to
 193          * the curb.
 194          *
 195          * In the worst-case scenario, all cells will be occupied and they
 196          * will all have timesRendered counts above the threshold, so we will
 197          * end up iterating through all the cells exactly once.  Since we are
 198          * resetting their counters along the way, we are guaranteed to
 199          * eventually hit the original "head" cell, whose counter is now zero.
 200          * This avoids the possibility of an infinite loop.
 201          */
 202 
 203         do {
 204             // the head cell will be updated on each iteration
 205             CacheCellInfo *current = cache->head;
 206 
 207             if ((current->glyphInfo == NULL) ||
 208                 (current->timesRendered < TIMES_RENDERED_THRESHOLD))
 209             {
 210                 // all bow before the chosen one (we will break out of the
 211                 // loop now that we've found an appropriate cell)
 212                 cellinfo = current;
 213             }
 214 
 215             // move cell to the end of the list; update existing head and
 216             // tail pointers
 217             cache->head = current->next;
 218             cache->tail->next = current;
 219             cache->tail = current;
 220             current->next = NULL;
 221             current->timesRendered = 0;
 222         } while (cellinfo == NULL);
 223 
 224         if (cellinfo->glyphInfo != NULL) {
 225             // flush in case any pending vertices are depending on the
 226             // glyph that is about to be kicked out
 227             if (cache->Flush != NULL) {
 228                 cache->Flush();
 229             }
 230 
 231             // if the cell is occupied, notify the base glyph that the
 232             // cached version for this cache is about to be kicked out
 233             AccelGlyphCache_RemoveCellInfo(cellinfo->glyphInfo, cellinfo);
 234         }
 235 
 236         // update cellinfo with glyph's occupied region information
 237         cellinfo->glyphInfo = glyph;
 238         cellinfo->tx2 = cellinfo->tx1 + ((jfloat)w / cache->width);
 239         cellinfo->ty2 = cellinfo->ty1 + ((jfloat)h / cache->height);
 240     }
 241 
 242     // add cache cell to the glyph's cells list
 243     AccelGlyphCache_AddCellInfo(glyph, cellinfo);
 244     return cellinfo;
 245 }
 246 
 247 /**
 248  * Invalidates all cells in the cache.  Note that this method does not
 249  * attempt to compact the cache in any way; it just invalidates any cells
 250  * that already exist.
 251  */
 252 void
 253 AccelGlyphCache_Invalidate(GlyphCacheInfo *cache)
 254 {
 255     CacheCellInfo *cellinfo;
 256 
 257     J2dTraceLn(J2D_TRACE_INFO, "AccelGlyphCache_Invalidate");
 258 
 259     if (cache == NULL) {
 260         return;
 261     }
 262 
 263     // flush any pending vertices that may be depending on the current
 264     // glyph cache layout
 265     if (cache->Flush != NULL) {
 266         cache->Flush();
 267     }
 268 
 269     cellinfo = cache->head;
 270     while (cellinfo != NULL) {
 271         if (cellinfo->glyphInfo != NULL) {
 272             // if the cell is occupied, notify the base glyph that its
 273             // cached version for this cache is about to be invalidated
 274             AccelGlyphCache_RemoveCellInfo(cellinfo->glyphInfo, cellinfo);
 275         }
 276         cellinfo = cellinfo->next;
 277     }
 278 }
 279 
 280 /**
 281  * Invalidates and frees all cells and the cache itself. The "cache" pointer
 282  * becomes invalid after this function returns.
 283  */
 284 void
 285 AccelGlyphCache_Free(GlyphCacheInfo *cache)
 286 {
 287     CacheCellInfo *cellinfo;
 288 
 289     J2dTraceLn(J2D_TRACE_INFO, "AccelGlyphCache_Free");
 290 
 291     if (cache == NULL) {
 292         return;
 293     }
 294 
 295     // flush any pending vertices that may be depending on the current
 296     // glyph cache
 297     if (cache->Flush != NULL) {
 298         cache->Flush();
 299     }
 300 
 301     while (cache->head != NULL) {
 302         cellinfo = cache->head;
 303         if (cellinfo->glyphInfo != NULL) {
 304             // if the cell is occupied, notify the base glyph that its
 305             // cached version for this cache is about to be invalidated
 306             AccelGlyphCache_RemoveCellInfo(cellinfo->glyphInfo, cellinfo);
 307         }
 308         cache->head = cellinfo->next;
 309         free(cellinfo);
 310     }
 311     free(cache);
 312 }
 313 
 314 /**
 315  * Add cell info to the head of the glyph's list of cached cells.
 316  */
 317 void
 318 AccelGlyphCache_AddCellInfo(GlyphInfo *glyph, CacheCellInfo *cellInfo)
 319 {
 320     // assert (glyph != NULL && cellInfo != NULL)
 321     J2dTraceLn(J2D_TRACE_INFO, "AccelGlyphCache_AddCellInfo");
 322     J2dTraceLn2(J2D_TRACE_VERBOSE, "  glyph 0x%x: adding cell 0x%x to the list",
 323                 glyph, cellInfo);
 324 
 325     cellInfo->glyphInfo = glyph;
 326     cellInfo->nextGCI = glyph->cellInfo;
 327     glyph->cellInfo = cellInfo;
 328     glyph->managed = MANAGED_GLYPH;
 329 }
 330 
 331 /**
 332  * Removes cell info from the glyph's list of cached cells.
 333  */
 334 void
 335 AccelGlyphCache_RemoveCellInfo(GlyphInfo *glyph, CacheCellInfo *cellInfo)
 336 {
 337     CacheCellInfo *currCellInfo = glyph->cellInfo;
 338     CacheCellInfo *prevInfo = NULL;
 339     // assert (glyph!= NULL && glyph->cellInfo != NULL && cellInfo != NULL)
 340     J2dTraceLn(J2D_TRACE_INFO, "AccelGlyphCache_RemoveCellInfo");
 341     do {
 342         if (currCellInfo == cellInfo) {
 343             J2dTraceLn2(J2D_TRACE_VERBOSE,
 344                         "  glyph 0x%x: removing cell 0x%x from glyph's list",
 345                         glyph, currCellInfo);
 346             if (prevInfo == NULL) { // it's the head, chop-chop
 347                 glyph->cellInfo = currCellInfo->nextGCI;
 348             } else {
 349                 prevInfo->nextGCI = currCellInfo->nextGCI;
 350             }
 351             currCellInfo->glyphInfo = NULL;
 352             currCellInfo->nextGCI = NULL;
 353             return;
 354         }
 355         prevInfo = currCellInfo;
 356         currCellInfo = currCellInfo->nextGCI;
 357     } while (currCellInfo != NULL);
 358     J2dTraceLn2(J2D_TRACE_WARNING, "AccelGlyphCache_RemoveCellInfo: "\
 359                 "no cell 0x%x in glyph 0x%x's cell list",
 360                 cellInfo, glyph);
 361 }
 362 
 363 /**
 364  * Removes cell info from the glyph's list of cached cells.
 365  */
 366 JNIEXPORT void
 367 AccelGlyphCache_RemoveAllCellInfos(GlyphInfo *glyph)
 368 {
 369     CacheCellInfo *currCell, *prevCell;
 370 
 371     J2dTraceLn(J2D_TRACE_INFO, "AccelGlyphCache_RemoveAllCellInfos");
 372 
 373     if (glyph == NULL || glyph->cellInfo == NULL) {
 374         return;
 375     }
 376 
 377     // invalidate all of this glyph's accelerated cache cells
 378     currCell = glyph->cellInfo;
 379     do {
 380         currCell->glyphInfo = NULL;
 381         prevCell = currCell;
 382         currCell = currCell->nextGCI;
 383         prevCell->nextGCI = NULL;
 384     } while (currCell != NULL);
 385 
 386     glyph->cellInfo = NULL;
 387 }
 388 
 389 /**
 390  * Returns cell info associated with particular cache from the glyph's list of
 391  * cached cells.
 392  */
 393 CacheCellInfo *
 394 AccelGlyphCache_GetCellInfoForCache(GlyphInfo *glyph, GlyphCacheInfo *cache)
 395 {
 396     // assert (glyph != NULL && cache != NULL)
 397     J2dTraceLn(J2D_TRACE_VERBOSE2, "AccelGlyphCache_GetCellInfoForCache");
 398 
 399     if (glyph->cellInfo != NULL) {
 400         CacheCellInfo *cellInfo = glyph->cellInfo;
 401         do {
 402             if (cellInfo->cacheInfo == cache) {
 403                 J2dTraceLn3(J2D_TRACE_VERBOSE2,
 404                             "  glyph 0x%x: found cell 0x%x for cache 0x%x",
 405                             glyph, cellInfo, cache);
 406                 return cellInfo;
 407             }
 408             cellInfo = cellInfo->nextGCI;
 409         } while (cellInfo != NULL);
 410     }
 411     J2dTraceLn2(J2D_TRACE_VERBOSE2, "  glyph 0x%x: no cell for cache 0x%x",
 412                 glyph, cache);
 413     return NULL;
 414 }
 415