ReactOS 0.4.15-dev-8135-g1bc6c90
ftccache.c
Go to the documentation of this file.
1/***************************************************************************/
2/* */
3/* ftccache.c */
4/* */
5/* The FreeType internal cache interface (body). */
6/* */
7/* Copyright 2000-2018 by */
8/* David Turner, Robert Wilhelm, and Werner Lemberg. */
9/* */
10/* This file is part of the FreeType project, and may only be used, */
11/* modified, and distributed under the terms of the FreeType project */
12/* license, LICENSE.TXT. By continuing to use, modify, or distribute */
13/* this file you indicate that you have read the license and */
14/* understand and accept it fully. */
15/* */
16/***************************************************************************/
17
18
19#include <ft2build.h>
20#include "ftcmanag.h"
21#include FT_INTERNAL_OBJECTS_H
22#include FT_INTERNAL_DEBUG_H
23
24#include "ftccback.h"
25#include "ftcerror.h"
26
27#undef FT_COMPONENT
28#define FT_COMPONENT trace_cache
29
30
31#define FTC_HASH_MAX_LOAD 2
32#define FTC_HASH_MIN_LOAD 1
33#define FTC_HASH_SUB_LOAD ( FTC_HASH_MAX_LOAD - FTC_HASH_MIN_LOAD )
34
35 /* this one _must_ be a power of 2! */
36#define FTC_HASH_INITIAL_SIZE 8
37
38
39 /*************************************************************************/
40 /*************************************************************************/
41 /***** *****/
42 /***** CACHE NODE DEFINITIONS *****/
43 /***** *****/
44 /*************************************************************************/
45 /*************************************************************************/
46
47 /* add a new node to the head of the manager's circular MRU list */
48 static void
50 FTC_Manager manager )
51 {
52 void *nl = &manager->nodes_list;
53
54
57 manager->num_nodes++;
58 }
59
60
61 /* remove a node from the manager's MRU list */
62 static void
64 FTC_Manager manager )
65 {
66 void *nl = &manager->nodes_list;
67
68
71 manager->num_nodes--;
72 }
73
74
75#ifndef FTC_INLINE
76
77 /* move a node to the head of the manager's MRU list */
78 static void
79 ftc_node_mru_up( FTC_Node node,
80 FTC_Manager manager )
81 {
84 }
85
86
87 /* get a top bucket for specified hash from cache,
88 * body for FTC_NODE_TOP_FOR_HASH( cache, hash )
89 */
91 ftc_get_top_node_for_hash( FTC_Cache cache,
93 {
94 FTC_Node* pnode;
96
97
98 idx = hash & cache->mask;
99 if ( idx < cache->p )
100 idx = hash & ( 2 * cache->mask + 1 );
101 pnode = cache->buckets + idx;
102 return pnode;
103 }
104
105#endif /* !FTC_INLINE */
106
107
108 /* Note that this function cannot fail. If we cannot re-size the
109 * buckets array appropriately, we simply degrade the hash table's
110 * performance!
111 */
112 static void
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 }
220
221
222 /* remove a node from its cache's hash table */
223 static void
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 }
253
254
255 /* add a node to the `top' of its cache's hash table */
256 static void
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 }
269
270
271 /* remove a node from the cache manager */
272 FT_LOCAL_DEF( void )
274 FTC_Manager manager )
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 }
316
317
318 /*************************************************************************/
319 /*************************************************************************/
320 /***** *****/
321 /***** ABSTRACT CACHE CLASS *****/
322 /***** *****/
323 /*************************************************************************/
324 /*************************************************************************/
325
326
329 {
330 return ftc_cache_init( cache );
331 }
332
333
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 }
348
349
350 static void
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 }
386
387
388 FT_LOCAL_DEF( void )
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 }
406
407
408 FT_LOCAL_DEF( void )
410 {
412 }
413
414
415 static void
418 FTC_Node node )
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 }
441
442
447 FTC_Node *anode )
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 }
478
479
480#ifndef FTC_INLINE
481
483 FTC_Cache_Lookup( FTC_Cache cache,
486 FTC_Node *anode )
487 {
488 FTC_Node* bucket;
489 FTC_Node* pnode;
492 FT_Bool list_changed = FALSE;
493
494 FTC_Node_CompareFunc compare = cache->clazz.node_compare;
495
496
497 if ( !cache || !anode )
498 return FT_THROW( Invalid_Argument );
499
500 /* Go to the `top' node of the list sharing same masked hash */
501 bucket = pnode = FTC_NODE_TOP_FOR_HASH( cache, hash );
502
503 /* Lookup a node with exactly same hash and queried properties. */
504 /* NOTE: _nodcomp() may change the linked list to reduce memory. */
505 for (;;)
506 {
507 node = *pnode;
508 if ( !node )
509 goto NewNode;
510
511 if ( node->hash == hash &&
512 compare( node, query, cache, &list_changed ) )
513 break;
514
515 pnode = &node->link;
516 }
517
518 if ( list_changed )
519 {
520 /* Update bucket by modified linked list */
521 bucket = pnode = FTC_NODE_TOP_FOR_HASH( cache, hash );
522
523 /* Update pnode by modified linked list */
524 while ( *pnode != node )
525 {
526 if ( !*pnode )
527 {
528 FT_ERROR(( "FTC_Cache_Lookup: oops!!! node missing\n" ));
529 goto NewNode;
530 }
531 else
532 pnode = &((*pnode)->link);
533 }
534 }
535
536 /* Reorder the list to move the found node to the `top' */
537 if ( node != *bucket )
538 {
539 *pnode = node->link;
540 node->link = *bucket;
541 *bucket = node;
542 }
543
544 /* move to head of MRU list */
545 {
546 FTC_Manager manager = cache->manager;
547
548
549 if ( node != manager->nodes_list )
550 ftc_node_mru_up( node, manager );
551 }
552 *anode = node;
553
554 return error;
555
556 NewNode:
557 return FTC_Cache_NewNode( cache, hash, query, anode );
558 }
559
560#endif /* !FTC_INLINE */
561
562
563 FT_LOCAL_DEF( void )
565 FTC_FaceID face_id )
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 }
619
620
621/* END */
#define NULL
Definition: types.h:112
#define FALSE
Definition: types.h:117
unsigned int idx
Definition: utils.c:41
return FT_Err_Ok
Definition: ftbbox.c:511
FT_BEGIN_HEADER typedef FT_Pointer FTC_FaceID
Definition: ftcache.h:171
static void ftc_cache_resize(FTC_Cache cache)
Definition: ftccache.c:113
static void ftc_node_mru_link(FTC_Node node, FTC_Manager manager)
Definition: ftccache.c:49
ftc_cache_init(FTC_Cache cache)
Definition: ftccache.c:335
static void ftc_node_mru_unlink(FTC_Node node, FTC_Manager manager)
Definition: ftccache.c:63
FTC_Cache_NewNode(FTC_Cache cache, FT_Offset hash, FT_Pointer query, FTC_Node *anode)
Definition: ftccache.c:444
static void FTC_Cache_Clear(FTC_Cache cache)
Definition: ftccache.c:351
ftc_node_destroy(FTC_Node node, FTC_Manager manager)
Definition: ftccache.c:273
FTC_Cache_Done(FTC_Cache cache)
Definition: ftccache.c:409
#define FTC_HASH_SUB_LOAD
Definition: ftccache.c:33
#define FTC_HASH_INITIAL_SIZE
Definition: ftccache.c:36
#define FTC_HASH_MAX_LOAD
Definition: ftccache.c:31
static void ftc_node_hash_link(FTC_Node node, FTC_Cache cache)
Definition: ftccache.c:257
static void ftc_cache_add(FTC_Cache cache, FT_Offset hash, FTC_Node node)
Definition: ftccache.c:416
FTC_Cache_Init(FTC_Cache cache)
Definition: ftccache.c:328
FTC_Cache_RemoveFaceID(FTC_Cache cache, FTC_FaceID face_id)
Definition: ftccache.c:564
static void ftc_node_hash_unlink(FTC_Node node0, FTC_Cache cache)
Definition: ftccache.c:224
ftc_cache_done(FTC_Cache cache)
Definition: ftccache.c:389
#define FTC_CACHE_TRYLOOP_END(list_changed)
Definition: ftccache.h:323
#define FTC_NODE_TOP_FOR_HASH(cache, hash)
Definition: ftccache.h:76
#define FTC_CACHE_TRYLOOP(cache)
Definition: ftccache.h:312
FT_Bool(* FTC_Node_CompareFunc)(FTC_Node node, FT_Pointer key, FTC_Cache cache, FT_Bool *list_changed)
Definition: ftccache.h:110
FTC_Manager_Compress(FTC_Manager manager)
Definition: ftcmanag.c:538
FTC_MruNode_Up(FTC_MruNode *plist, FTC_MruNode node)
Definition: ftcmru.c:73
FTC_MruNode_Prepend(FTC_MruNode *plist, FTC_MruNode node)
Definition: ftcmru.c:29
FTC_MruNode_Remove(FTC_MruNode *plist, FTC_MruNode node)
Definition: ftcmru.c:122
typedefFT_BEGIN_HEADER struct FTC_MruNodeRec_ * FTC_MruNode
Definition: ftcmru.h:61
#define FT_LOCAL_DEF(x)
Definition: ftconfig.h:388
unsigned short FT_UInt16
Definition: ftconfig.h:181
#define FT_TRACE0(varformat)
Definition: ftdebug.h:157
#define FT_ERROR(varformat)
Definition: ftdebug.h:181
#define FT_THROW(e)
Definition: ftdebug.h:213
#define FT_NEW_ARRAY(ptr, count)
Definition: ftmemory.h:333
#define FT_FREE(ptr)
Definition: ftmemory.h:329
#define FT_RENEW_ARRAY(ptr, curcnt, newcnt)
Definition: ftmemory.h:336
typedefFT_BEGIN_HEADER struct FT_MemoryRec_ * FT_Memory
Definition: ftsystem.h:66
FT_BEGIN_HEADER typedef unsigned char FT_Bool
Definition: fttypes.h:108
int FT_Error
Definition: fttypes.h:300
signed long FT_Long
Definition: fttypes.h:242
size_t FT_Offset
Definition: fttypes.h:324
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLenum GLint GLuint mask
Definition: glext.h:6028
GLfloat GLfloat p
Definition: glext.h:8902
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
#define error(str)
Definition: mkdosfs.c:1605
static char memory[1024 *256]
Definition: process.c:116
static unsigned __int64 next
Definition: rand_nt.c:6
FT_Offset cur_weight
Definition: ftcmanag.h:98
FT_Offset max_weight
Definition: ftcmanag.h:97
FTC_Node nodes_list
Definition: ftcmanag.h:96
FT_UInt num_nodes
Definition: ftcmanag.h:99
FT_Offset hash
Definition: ftccache.h:62
FTC_Node link
Definition: ftccache.h:61
Definition: cache.c:49
Definition: bug.cpp:8
Definition: _hash_fun.h:40
Definition: dlist.c:348