1/*
2 * Copyright (c) 2003, 2012, 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 <stdlib.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 */
62GlyphCacheInfo *
63AccelGlyphCache_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 */
106CacheCellInfo *
107AccelGlyphCache_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 */
252void
253AccelGlyphCache_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 */
284void
285AccelGlyphCache_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 */
317void
318AccelGlyphCache_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 */
334void
335AccelGlyphCache_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 */
366JNIEXPORT void
367AccelGlyphCache_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 */
393CacheCellInfo *
394AccelGlyphCache_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
416