ReactOS 0.4.15-dev-8145-ga541a46
ftccache.c File Reference
#include <ft2build.h>
#include "ftcmanag.h"
#include "ftccback.h"
#include "ftcerror.h"
Include dependency graph for ftccache.c:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define FT_COMPONENT   trace_cache
 
#define FTC_HASH_MAX_LOAD   2
 
#define FTC_HASH_MIN_LOAD   1
 
#define FTC_HASH_SUB_LOAD   ( FTC_HASH_MAX_LOAD - FTC_HASH_MIN_LOAD )
 
#define FTC_HASH_INITIAL_SIZE   8
 

Functions

static void ftc_node_mru_link (FTC_Node node, FTC_Manager manager)
 
static void ftc_node_mru_unlink (FTC_Node node, FTC_Manager manager)
 
static void ftc_cache_resize (FTC_Cache cache)
 
static void ftc_node_hash_unlink (FTC_Node node0, FTC_Cache cache)
 
static void ftc_node_hash_link (FTC_Node node, FTC_Cache cache)
 
 ftc_node_destroy (FTC_Node node, FTC_Manager manager)
 
 FTC_Cache_Init (FTC_Cache cache)
 
 ftc_cache_init (FTC_Cache cache)
 
static void FTC_Cache_Clear (FTC_Cache cache)
 
 ftc_cache_done (FTC_Cache cache)
 
 FTC_Cache_Done (FTC_Cache cache)
 
static void ftc_cache_add (FTC_Cache cache, FT_Offset hash, FTC_Node node)
 
 FTC_Cache_NewNode (FTC_Cache cache, FT_Offset hash, FT_Pointer query, FTC_Node *anode)
 
 FTC_Cache_RemoveFaceID (FTC_Cache cache, FTC_FaceID face_id)
 

Macro Definition Documentation

◆ FT_COMPONENT

#define FT_COMPONENT   trace_cache

Definition at line 28 of file ftccache.c.

◆ FTC_HASH_INITIAL_SIZE

#define FTC_HASH_INITIAL_SIZE   8

Definition at line 36 of file ftccache.c.

◆ FTC_HASH_MAX_LOAD

#define FTC_HASH_MAX_LOAD   2

Definition at line 31 of file ftccache.c.

◆ FTC_HASH_MIN_LOAD

#define FTC_HASH_MIN_LOAD   1

Definition at line 32 of file ftccache.c.

◆ FTC_HASH_SUB_LOAD

#define FTC_HASH_SUB_LOAD   ( FTC_HASH_MAX_LOAD - FTC_HASH_MIN_LOAD )

Definition at line 33 of file ftccache.c.

Function Documentation

◆ ftc_cache_add()

static void ftc_cache_add ( FTC_Cache  cache,
FT_Offset  hash,
FTC_Node  node 
)
static

Definition at line 416 of file ftccache.c.

419 {
420 node->hash = hash;
421 node->cache_index = (FT_UInt16)cache->index;
422 node->ref_count = 0;
423
425 ftc_node_mru_link( node, cache->manager );
426
427 {
428 FTC_Manager manager = cache->manager;
429
430
431 manager->cur_weight += cache->clazz.node_weight( node, cache );
432
433 if ( manager->cur_weight >= manager->max_weight )
434 {
435 node->ref_count++;
436 FTC_Manager_Compress( manager );
437 node->ref_count--;
438 }
439 }
440 }
static void ftc_node_mru_link(FTC_Node node, FTC_Manager manager)
Definition: ftccache.c:49
static void ftc_node_hash_link(FTC_Node node, FTC_Cache cache)
Definition: ftccache.c:257
FTC_Manager_Compress(FTC_Manager manager)
Definition: ftcmanag.c:538
unsigned short FT_UInt16
Definition: ftconfig.h:181
FT_Offset cur_weight
Definition: ftcmanag.h:98
FT_Offset max_weight
Definition: ftcmanag.h:97
Definition: cache.c:49
Definition: _hash_fun.h:40
Definition: dlist.c:348

Referenced by FTC_Cache_NewNode().

◆ FTC_Cache_Clear()

static void FTC_Cache_Clear ( FTC_Cache  cache)
static

Definition at line 351 of file ftccache.c.

352 {
353 if ( cache && cache->buckets )
354 {
355 FTC_Manager manager = cache->manager;
356 FT_UFast i;
357 FT_UFast count;
358
359
360 count = cache->p + cache->mask + 1;
361
362 for ( i = 0; i < count; i++ )
363 {
364 FTC_Node *pnode = cache->buckets + i, next, node = *pnode;
365
366
367 while ( node )
368 {
369 next = node->link;
370 node->link = NULL;
371
372 /* remove node from mru list */
373 ftc_node_mru_unlink( node, manager );
374
375 /* now finalize it */
376 manager->cur_weight -= cache->clazz.node_weight( node, cache );
377
378 cache->clazz.node_free( node, cache );
379 node = next;
380 }
381 cache->buckets[i] = NULL;
382 }
384 }
385 }
#define NULL
Definition: types.h:112
static void ftc_cache_resize(FTC_Cache cache)
Definition: ftccache.c:113
static void ftc_node_mru_unlink(FTC_Node node, FTC_Manager manager)
Definition: ftccache.c:63
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
static unsigned __int64 next
Definition: rand_nt.c:6

Referenced by ftc_cache_done().

◆ ftc_cache_done()

ftc_cache_done ( FTC_Cache  cache)

Definition at line 389 of file ftccache.c.

390 {
391 if ( cache->memory )
392 {
393 FT_Memory memory = cache->memory;
394
395
397
398 FT_FREE( cache->buckets );
399 cache->mask = 0;
400 cache->p = 0;
401 cache->slack = 0;
402
403 cache->memory = NULL;
404 }
405 }
static void FTC_Cache_Clear(FTC_Cache cache)
Definition: ftccache.c:351
#define FT_FREE(ptr)
Definition: ftmemory.h:329
typedefFT_BEGIN_HEADER struct FT_MemoryRec_ * FT_Memory
Definition: ftsystem.h:66
static char memory[1024 *256]
Definition: process.c:116

Referenced by FTC_Cache_Done().

◆ FTC_Cache_Done()

FTC_Cache_Done ( FTC_Cache  cache)

Definition at line 409 of file ftccache.c.

410 {
412 }
ftc_cache_done(FTC_Cache cache)
Definition: ftccache.c:389

Referenced by ftc_gcache_done().

◆ FTC_Cache_Init()

FTC_Cache_Init ( FTC_Cache  cache)

Definition at line 328 of file ftccache.c.

329 {
330 return ftc_cache_init( cache );
331 }
ftc_cache_init(FTC_Cache cache)
Definition: ftccache.c:335

Referenced by ftc_gcache_init().

◆ ftc_cache_init()

ftc_cache_init ( FTC_Cache  cache)

Definition at line 335 of file ftccache.c.

336 {
337 FT_Memory memory = cache->memory;
339
340
341 cache->p = 0;
342 cache->mask = FTC_HASH_INITIAL_SIZE - 1;
344
346 return error;
347 }
#define FTC_HASH_INITIAL_SIZE
Definition: ftccache.c:36
#define FTC_HASH_MAX_LOAD
Definition: ftccache.c:31
#define FT_NEW_ARRAY(ptr, count)
Definition: ftmemory.h:333
int FT_Error
Definition: fttypes.h:300
#define error(str)
Definition: mkdosfs.c:1605

Referenced by FTC_Cache_Init().

◆ FTC_Cache_NewNode()

FTC_Cache_NewNode ( FTC_Cache  cache,
FT_Offset  hash,
FT_Pointer  query,
FTC_Node anode 
)

Definition at line 444 of file ftccache.c.

448 {
451
452
453 /*
454 * We use the FTC_CACHE_TRYLOOP macros to support out-of-memory
455 * errors (OOM) correctly, i.e., by flushing the cache progressively
456 * in order to make more room.
457 */
458
460 {
461 error = cache->clazz.node_new( &node, query, cache );
462 }
464
465 if ( error )
466 node = NULL;
467 else
468 {
469 /* don't assume that the cache has the same number of buckets, since
470 * our allocation request might have triggered global cache flushing
471 */
473 }
474
475 *anode = node;
476 return error;
477 }
static void ftc_cache_add(FTC_Cache cache, FT_Offset hash, FTC_Node node)
Definition: ftccache.c:416
#define FTC_CACHE_TRYLOOP_END(list_changed)
Definition: ftccache.h:323
#define FTC_CACHE_TRYLOOP(cache)
Definition: ftccache.h:312

◆ FTC_Cache_RemoveFaceID()

FTC_Cache_RemoveFaceID ( FTC_Cache  cache,
FTC_FaceID  face_id 
)

Definition at line 564 of file ftccache.c.

566 {
567 FT_UFast i, count;
568 FTC_Manager manager = cache->manager;
569 FTC_Node frees = NULL;
570
571
572 count = cache->p + cache->mask + 1;
573 for ( i = 0; i < count; i++ )
574 {
575 FTC_Node* bucket = cache->buckets + i;
576 FTC_Node* pnode = bucket;
577
578
579 for (;;)
580 {
581 FTC_Node node = *pnode;
582 FT_Bool list_changed = FALSE;
583
584
585 if ( !node )
586 break;
587
588 if ( cache->clazz.node_remove_faceid( node, face_id,
589 cache, &list_changed ) )
590 {
591 *pnode = node->link;
592 node->link = frees;
593 frees = node;
594 }
595 else
596 pnode = &node->link;
597 }
598 }
599
600 /* remove all nodes in the free list */
601 while ( frees )
602 {
604
605
606 node = frees;
607 frees = node->link;
608
609 manager->cur_weight -= cache->clazz.node_weight( node, cache );
610 ftc_node_mru_unlink( node, manager );
611
612 cache->clazz.node_free( node, cache );
613
614 cache->slack++;
615 }
616
618 }
#define FALSE
Definition: types.h:117
FT_BEGIN_HEADER typedef unsigned char FT_Bool
Definition: fttypes.h:108

Referenced by FTC_Manager_RemoveFaceID().

◆ ftc_cache_resize()

static void ftc_cache_resize ( FTC_Cache  cache)
static

Definition at line 113 of file ftccache.c.

114 {
115 for (;;)
116 {
117 FTC_Node node, *pnode;
118 FT_UFast p = cache->p;
119 FT_UFast mask = cache->mask;
120 FT_UFast count = mask + p + 1; /* number of buckets */
121
122
123 /* do we need to shrink the buckets array? */
124 if ( cache->slack < 0 )
125 {
126 FTC_Node new_list = NULL;
127
128
129 /* try to expand the buckets array _before_ splitting
130 * the bucket lists
131 */
132 if ( p >= mask )
133 {
134 FT_Memory memory = cache->memory;
136
137
138 /* if we can't expand the array, leave immediately */
139 if ( FT_RENEW_ARRAY( cache->buckets,
140 ( mask + 1 ) * 2, ( mask + 1 ) * 4 ) )
141 break;
142 }
143
144 /* split a single bucket */
145 pnode = cache->buckets + p;
146
147 for (;;)
148 {
149 node = *pnode;
150 if ( !node )
151 break;
152
153 if ( node->hash & ( mask + 1 ) )
154 {
155 *pnode = node->link;
156 node->link = new_list;
157 new_list = node;
158 }
159 else
160 pnode = &node->link;
161 }
162
163 cache->buckets[p + mask + 1] = new_list;
164
165 cache->slack += FTC_HASH_MAX_LOAD;
166
167 if ( p >= mask )
168 {
169 cache->mask = 2 * mask + 1;
170 cache->p = 0;
171 }
172 else
173 cache->p = p + 1;
174 }
175
176 /* do we need to expand the buckets array? */
177 else if ( cache->slack > (FT_Long)count * FTC_HASH_SUB_LOAD )
178 {
179 FT_UFast old_index = p + mask;
180 FTC_Node* pold;
181
182
183 if ( old_index + 1 <= FTC_HASH_INITIAL_SIZE )
184 break;
185
186 if ( p == 0 )
187 {
188 FT_Memory memory = cache->memory;
190
191
192 /* if we can't shrink the array, leave immediately */
193 if ( FT_RENEW_ARRAY( cache->buckets,
194 ( mask + 1 ) * 2, mask + 1 ) )
195 break;
196
197 cache->mask >>= 1;
198 p = cache->mask;
199 }
200 else
201 p--;
202
203 pnode = cache->buckets + p;
204 while ( *pnode )
205 pnode = &(*pnode)->link;
206
207 pold = cache->buckets + old_index;
208 *pnode = *pold;
209 *pold = NULL;
210
211 cache->slack -= FTC_HASH_MAX_LOAD;
212 cache->p = p;
213 }
214
215 /* otherwise, the hash table is balanced */
216 else
217 break;
218 }
219 }
#define FTC_HASH_SUB_LOAD
Definition: ftccache.c:33
#define FT_RENEW_ARRAY(ptr, curcnt, newcnt)
Definition: ftmemory.h:336
signed long FT_Long
Definition: fttypes.h:242
GLenum GLint GLuint mask
Definition: glext.h:6028
GLfloat GLfloat p
Definition: glext.h:8902
FTC_Node link
Definition: ftccache.h:61

Referenced by FTC_Cache_Clear(), FTC_Cache_RemoveFaceID(), ftc_node_hash_link(), and ftc_node_hash_unlink().

◆ ftc_node_destroy()

ftc_node_destroy ( FTC_Node  node,
FTC_Manager  manager 
)

Definition at line 273 of file ftccache.c.

275 {
277
278
279#ifdef FT_DEBUG_ERROR
280 /* find node's cache */
281 if ( node->cache_index >= manager->num_caches )
282 {
283 FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
284 return;
285 }
286#endif
287
288 cache = manager->caches[node->cache_index];
289
290#ifdef FT_DEBUG_ERROR
291 if ( !cache )
292 {
293 FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
294 return;
295 }
296#endif
297
298 manager->cur_weight -= cache->clazz.node_weight( node, cache );
299
300 /* remove node from mru list */
301 ftc_node_mru_unlink( node, manager );
302
303 /* remove node from cache's hash table */
305
306 /* now finalize it */
307 cache->clazz.node_free( node, cache );
308
309#if 0
310 /* check, just in case of general corruption :-) */
311 if ( manager->num_nodes == 0 )
312 FT_TRACE0(( "ftc_node_destroy: invalid cache node count (%d)\n",
313 manager->num_nodes ));
314#endif
315 }
static void ftc_node_hash_unlink(FTC_Node node0, FTC_Cache cache)
Definition: ftccache.c:224
#define FT_TRACE0(varformat)
Definition: ftdebug.h:157
FT_UInt num_caches
Definition: ftcmanag.h:102
FTC_Cache caches[FTC_MAX_CACHES]
Definition: ftcmanag.h:101
FT_UInt num_nodes
Definition: ftcmanag.h:99

Referenced by FTC_Manager_Compress(), and FTC_Manager_FlushN().

◆ ftc_node_hash_link()

static void ftc_node_hash_link ( FTC_Node  node,
FTC_Cache  cache 
)
static

Definition at line 257 of file ftccache.c.

259 {
260 FTC_Node *pnode = FTC_NODE_TOP_FOR_HASH( cache, node->hash );
261
262
263 node->link = *pnode;
264 *pnode = node;
265
266 cache->slack--;
268 }
#define FTC_NODE_TOP_FOR_HASH(cache, hash)
Definition: ftccache.h:76

Referenced by ftc_cache_add().

◆ ftc_node_hash_unlink()

static void ftc_node_hash_unlink ( FTC_Node  node0,
FTC_Cache  cache 
)
static

Definition at line 224 of file ftccache.c.

226 {
227 FTC_Node *pnode = FTC_NODE_TOP_FOR_HASH( cache, node0->hash );
228
229
230 for (;;)
231 {
232 FTC_Node node = *pnode;
233
234
235 if ( !node )
236 {
237 FT_TRACE0(( "ftc_node_hash_unlink: unknown node\n" ));
238 return;
239 }
240
241 if ( node == node0 )
242 break;
243
244 pnode = &(*pnode)->link;
245 }
246
247 *pnode = node0->link;
248 node0->link = NULL;
249
250 cache->slack++;
252 }
FT_Offset hash
Definition: ftccache.h:62

Referenced by ftc_node_destroy().

◆ ftc_node_mru_link()

static void ftc_node_mru_link ( FTC_Node  node,
FTC_Manager  manager 
)
static

Definition at line 49 of file ftccache.c.

51 {
52 void *nl = &manager->nodes_list;
53
54
57 manager->num_nodes++;
58 }
FTC_MruNode_Prepend(FTC_MruNode *plist, FTC_MruNode node)
Definition: ftcmru.c:29
typedefFT_BEGIN_HEADER struct FTC_MruNodeRec_ * FTC_MruNode
Definition: ftcmru.h:61
FTC_Node nodes_list
Definition: ftcmanag.h:96

Referenced by ftc_cache_add().

◆ ftc_node_mru_unlink()

static void ftc_node_mru_unlink ( FTC_Node  node,
FTC_Manager  manager 
)
static

Definition at line 63 of file ftccache.c.

65 {
66 void *nl = &manager->nodes_list;
67
68
71 manager->num_nodes--;
72 }
FTC_MruNode_Remove(FTC_MruNode *plist, FTC_MruNode node)
Definition: ftcmru.c:122

Referenced by FTC_Cache_Clear(), FTC_Cache_RemoveFaceID(), and ftc_node_destroy().