← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/3rdparty/freetype/src/cache/ftccache.c

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/3rdparty/freetype/src/cache/ftccache.c
 
1
/***************************************************************************/
 
2
/*                                                                         */
 
3
/*  ftccache.c                                                             */
 
4
/*                                                                         */
 
5
/*    The FreeType internal cache interface (body).                        */
 
6
/*                                                                         */
 
7
/*  Copyright 2000-2001, 2002, 2003, 2004 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 FT_CACHE_INTERNAL_MANAGER_H
 
21
#include FT_INTERNAL_OBJECTS_H
 
22
#include FT_INTERNAL_DEBUG_H
 
23
 
 
24
#include "ftccback.h"
 
25
#include "ftcerror.h"
 
26
 
 
27
 
 
28
#define FTC_HASH_MAX_LOAD  2
 
29
#define FTC_HASH_MIN_LOAD  1
 
30
#define FTC_HASH_SUB_LOAD  ( FTC_HASH_MAX_LOAD - FTC_HASH_MIN_LOAD )
 
31
 
 
32
/* this one _must_ be a power of 2! */
 
33
#define FTC_HASH_INITIAL_SIZE  8
 
34
 
 
35
 
 
36
  /*************************************************************************/
 
37
  /*************************************************************************/
 
38
  /*****                                                               *****/
 
39
  /*****                   CACHE NODE DEFINITIONS                      *****/
 
40
  /*****                                                               *****/
 
41
  /*************************************************************************/
 
42
  /*************************************************************************/
 
43
 
 
44
  /* add a new node to the head of the manager's circular MRU list */
 
45
  static void
 
46
  ftc_node_mru_link( FTC_Node     node,
 
47
                     FTC_Manager  manager )
 
48
  {
 
49
    FTC_MruNode_Prepend( (FTC_MruNode*)&manager->nodes_list,
 
50
                         (FTC_MruNode)node );
 
51
    manager->num_nodes++;
 
52
  }
 
53
 
 
54
 
 
55
  /* remove a node from the manager's MRU list */
 
56
  static void
 
57
  ftc_node_mru_unlink( FTC_Node     node,
 
58
                       FTC_Manager  manager )
 
59
  {
 
60
    FTC_MruNode_Remove( (FTC_MruNode*)&manager->nodes_list,
 
61
                        (FTC_MruNode)node );
 
62
    manager->num_nodes--;
 
63
  }
 
64
 
 
65
 
 
66
  /* move a node to the head of the manager's MRU list */
 
67
  static void
 
68
  ftc_node_mru_up( FTC_Node     node,
 
69
                   FTC_Manager  manager )
 
70
  {
 
71
    FTC_MruNode_Up( (FTC_MruNode*)&manager->nodes_list,
 
72
                    (FTC_MruNode)node );
 
73
  }
 
74
 
 
75
 
 
76
  /* Note that this function cannot fail.  If we cannot re-size the
 
77
   * buckets array appropriately, we simply degrade the hash table's
 
78
   * performance!
 
79
   */
 
80
  static void
 
81
  ftc_cache_resize( FTC_Cache  cache )
 
82
  {
 
83
    for (;;)
 
84
    {
 
85
      FTC_Node  node, *pnode;
 
86
      FT_UInt   p      = cache->p;
 
87
      FT_UInt   mask   = cache->mask;
 
88
      FT_UInt   count  = mask + p + 1;    /* number of buckets */
 
89
 
 
90
 
 
91
      /* do we need to shrink the buckets array? */
 
92
      if ( cache->slack < 0 )
 
93
      {
 
94
        FTC_Node  new_list = NULL;
 
95
 
 
96
 
 
97
        /* try to expand the buckets array _before_ splitting
 
98
         * the bucket lists
 
99
         */
 
100
        if ( p >= mask )
 
101
        {
 
102
          FT_Memory  memory = cache->memory;
 
103
 
 
104
 
 
105
          /* if we can't expand the array, leave immediately */
 
106
          if ( FT_MEM_RENEW_ARRAY( cache->buckets, (mask+1)*2, (mask+1)*4 ) )
 
107
            break;
 
108
        }
 
109
 
 
110
        /* split a single bucket */
 
111
        pnode = cache->buckets + p;
 
112
 
 
113
        for (;;)
 
114
        {
 
115
          node = *pnode;
 
116
          if ( node == NULL )
 
117
            break;
 
118
 
 
119
          if ( node->hash & ( mask + 1 ) )
 
120
          {
 
121
            *pnode     = node->link;
 
122
            node->link = new_list;
 
123
            new_list   = node;
 
124
          }
 
125
          else
 
126
            pnode = &node->link;
 
127
        }
 
128
 
 
129
        cache->buckets[p + mask + 1] = new_list;
 
130
 
 
131
        cache->slack += FTC_HASH_MAX_LOAD;
 
132
 
 
133
        if ( p >= mask )
 
134
        {
 
135
          cache->mask = 2 * mask + 1;
 
136
          cache->p    = 0;
 
137
        }
 
138
        else
 
139
          cache->p = p + 1;
 
140
      }
 
141
 
 
142
      /* do we need to expand the buckets array? */
 
143
      else if ( cache->slack > (FT_Long)count * FTC_HASH_SUB_LOAD )
 
144
      {
 
145
        FT_UInt    old_index = p + mask;
 
146
        FTC_Node*  pold;
 
147
 
 
148
 
 
149
        if ( old_index + 1 <= FTC_HASH_INITIAL_SIZE )
 
150
          break;
 
151
 
 
152
        if ( p == 0 )
 
153
        {
 
154
          FT_Memory  memory = cache->memory;
 
155
 
 
156
 
 
157
          /* if we can't shrink the array, leave immediately */
 
158
          if ( FT_MEM_RENEW_ARRAY( cache->buckets,
 
159
                                   ( mask + 1 ) * 2, mask + 1 ) )
 
160
            break;
 
161
 
 
162
          cache->mask >>= 1;
 
163
          p             = cache->mask;
 
164
        }
 
165
        else
 
166
          p--;
 
167
 
 
168
        pnode = cache->buckets + p;
 
169
        while ( *pnode )
 
170
          pnode = &(*pnode)->link;
 
171
 
 
172
        pold   = cache->buckets + old_index;
 
173
        *pnode = *pold;
 
174
        *pold  = NULL;
 
175
 
 
176
        cache->slack -= FTC_HASH_MAX_LOAD;
 
177
        cache->p      = p;
 
178
      }
 
179
      else /* the hash table is balanced */
 
180
        break;
 
181
    }
 
182
  }
 
183
 
 
184
 
 
185
  /* remove a node from its cache's hash table */
 
186
  static void
 
187
  ftc_node_hash_unlink( FTC_Node   node0,
 
188
                        FTC_Cache  cache )
 
189
  {
 
190
    FTC_Node  *pnode;
 
191
    FT_UInt    idx;
 
192
 
 
193
 
 
194
    idx = (FT_UInt)( node0->hash & cache->mask );
 
195
    if ( idx < cache->p )
 
196
      idx = (FT_UInt)( node0->hash & ( 2 * cache->mask + 1 ) );
 
197
 
 
198
    pnode = cache->buckets + idx;
 
199
 
 
200
    for (;;)
 
201
    {
 
202
      FTC_Node  node = *pnode;
 
203
 
 
204
 
 
205
      if ( node == NULL )
 
206
      {
 
207
        FT_ERROR(( "ftc_node_hash_unlink: unknown node!\n" ));
 
208
        return;
 
209
      }
 
210
 
 
211
      if ( node == node0 )
 
212
        break;
 
213
 
 
214
      pnode = &(*pnode)->link;
 
215
    }
 
216
 
 
217
    *pnode      = node0->link;
 
218
    node0->link = NULL;
 
219
 
 
220
    cache->slack++;
 
221
    ftc_cache_resize( cache );
 
222
  }
 
223
 
 
224
 
 
225
  /* add a node to the `top' of its cache's hash table */
 
226
  static void
 
227
  ftc_node_hash_link( FTC_Node   node,
 
228
                      FTC_Cache  cache )
 
229
  {
 
230
    FTC_Node  *pnode;
 
231
    FT_UInt    idx;
 
232
 
 
233
 
 
234
    idx = (FT_UInt)( node->hash & cache->mask );
 
235
    if ( idx < cache->p )
 
236
      idx = (FT_UInt)( node->hash & (2 * cache->mask + 1 ) );
 
237
 
 
238
    pnode = cache->buckets + idx;
 
239
 
 
240
    node->link = *pnode;
 
241
    *pnode     = node;
 
242
 
 
243
    cache->slack--;
 
244
    ftc_cache_resize( cache );
 
245
  }
 
246
 
 
247
 
 
248
  /* remove a node from the cache manager */
 
249
  FT_EXPORT_DEF( void )
 
250
  ftc_node_destroy( FTC_Node     node,
 
251
                    FTC_Manager  manager )
 
252
  {
 
253
    FTC_Cache  cache;
 
254
 
 
255
 
 
256
#ifdef FT_DEBUG_ERROR
 
257
    /* find node's cache */
 
258
    if ( node->cache_index >= manager->num_caches )
 
259
    {
 
260
      FT_ERROR(( "ftc_node_destroy: invalid node handle\n" ));
 
261
      return;
 
262
    }
 
263
#endif
 
264
 
 
265
    cache = manager->caches[node->cache_index];
 
266
 
 
267
#ifdef FT_DEBUG_ERROR
 
268
    if ( cache == NULL )
 
269
    {
 
270
      FT_ERROR(( "ftc_node_destroy: invalid node handle\n" ));
 
271
      return;
 
272
    }
 
273
#endif
 
274
 
 
275
    manager->cur_weight -= cache->clazz.node_weight( node, cache );
 
276
 
 
277
    /* remove node from mru list */
 
278
    ftc_node_mru_unlink( node, manager );
 
279
 
 
280
    /* remove node from cache's hash table */
 
281
    ftc_node_hash_unlink( node, cache );
 
282
 
 
283
    /* now finalize it */
 
284
    cache->clazz.node_free( node, cache );
 
285
 
 
286
#if 0
 
287
    /* check, just in case of general corruption :-) */
 
288
    if ( manager->num_nodes == 0 )
 
289
      FT_ERROR(( "ftc_node_destroy: invalid cache node count! = %d\n",
 
290
                  manager->num_nodes ));
 
291
#endif
 
292
  }
 
293
 
 
294
 
 
295
  /*************************************************************************/
 
296
  /*************************************************************************/
 
297
  /*****                                                               *****/
 
298
  /*****                    ABSTRACT CACHE CLASS                       *****/
 
299
  /*****                                                               *****/
 
300
  /*************************************************************************/
 
301
  /*************************************************************************/
 
302
 
 
303
 
 
304
  FT_EXPORT_DEF( FT_Error )
 
305
  FTC_Cache_Init( FTC_Cache  cache )
 
306
  {
 
307
    return ftc_cache_init( cache );
 
308
  }
 
309
 
 
310
 
 
311
  FT_LOCAL_DEF( FT_Error )
 
312
  ftc_cache_init( FTC_Cache  cache )
 
313
  {
 
314
    FT_Memory  memory = cache->memory;
 
315
 
 
316
 
 
317
    cache->p     = 0;
 
318
    cache->mask  = FTC_HASH_INITIAL_SIZE - 1;
 
319
    cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD;
 
320
 
 
321
    return ( FT_MEM_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 ) );
 
322
  }
 
323
 
 
324
 
 
325
  FT_EXPORT_DEF( void )
 
326
  FTC_Cache_Clear( FTC_Cache  cache )
 
327
  {
 
328
    if ( cache )
 
329
    {
 
330
      FTC_Manager  manager = cache->manager;
 
331
      FT_UFast     i;
 
332
      FT_UInt      count;
 
333
 
 
334
 
 
335
      count = cache->p + cache->mask + 1;
 
336
 
 
337
      for ( i = 0; i < count; i++ )
 
338
      {
 
339
        FTC_Node  *pnode = cache->buckets + i, next, node = *pnode;
 
340
 
 
341
 
 
342
        while ( node )
 
343
        {
 
344
          next        = node->link;
 
345
          node->link  = NULL;
 
346
 
 
347
          /* remove node from mru list */
 
348
          ftc_node_mru_unlink( node, manager );
 
349
 
 
350
          /* now finalize it */
 
351
          manager->cur_weight -= cache->clazz.node_weight( node, cache );
 
352
 
 
353
          cache->clazz.node_free( node, cache );
 
354
          node = next;
 
355
        }
 
356
        cache->buckets[i] = NULL;
 
357
      }
 
358
      ftc_cache_resize( cache );
 
359
    }
 
360
  }
 
361
 
 
362
 
 
363
  FT_LOCAL_DEF( void )
 
364
  ftc_cache_done( FTC_Cache  cache )
 
365
  {
 
366
    if ( cache->memory )
 
367
    {
 
368
      FT_Memory  memory = cache->memory;
 
369
 
 
370
 
 
371
      FTC_Cache_Clear( cache );
 
372
 
 
373
      FT_FREE( cache->buckets );
 
374
      cache->mask  = 0;
 
375
      cache->p     = 0;
 
376
      cache->slack = 0;
 
377
 
 
378
      cache->memory = NULL;
 
379
    }
 
380
  }
 
381
 
 
382
 
 
383
  FT_EXPORT_DEF( void )
 
384
  FTC_Cache_Done( FTC_Cache  cache )
 
385
  {
 
386
    ftc_cache_done( cache );
 
387
  }
 
388
 
 
389
 
 
390
  static void
 
391
  ftc_cache_add( FTC_Cache  cache,
 
392
                 FT_UInt32  hash,
 
393
                 FTC_Node   node )
 
394
  {
 
395
    node->hash = hash;
 
396
    node->cache_index = (FT_UInt16) cache->index;
 
397
    node->ref_count   = 0;
 
398
 
 
399
    ftc_node_hash_link( node, cache );
 
400
    ftc_node_mru_link( node, cache->manager );
 
401
 
 
402
    {
 
403
      FTC_Manager  manager = cache->manager;
 
404
 
 
405
 
 
406
      manager->cur_weight += cache->clazz.node_weight( node, cache );
 
407
 
 
408
      if ( manager->cur_weight >= manager->max_weight )
 
409
      {
 
410
        node->ref_count++;
 
411
        FTC_Manager_Compress( manager );
 
412
        node->ref_count--;
 
413
      }
 
414
    }
 
415
  }
 
416
 
 
417
 
 
418
  FT_EXPORT_DEF( FT_Error )
 
419
  FTC_Cache_NewNode( FTC_Cache   cache,
 
420
                     FT_UInt32   hash,
 
421
                     FT_Pointer  query,
 
422
                     FTC_Node   *anode )
 
423
  {
 
424
    FT_Error  error;
 
425
    FTC_Node  node;
 
426
 
 
427
    /*
 
428
     *  Try to allocate a new cache node.  Note that in case of
 
429
     *  out-of-memory error (OOM), we'll flush the cache a bit,
 
430
     *  then try again.
 
431
     *
 
432
     *  On each try, the `tries' variable gives the number
 
433
     *  of old nodes we want to flush from the manager's global list
 
434
     *  before the next allocation attempt.  It barely doubles on
 
435
     *  each iteration.
 
436
     *
 
437
     */
 
438
    error = cache->clazz.node_new( &node, query, cache );
 
439
    if ( error )
 
440
      goto FlushCache;
 
441
 
 
442
  AddNode:
 
443
    /* don't assume that the cache has the same number of buckets, since
 
444
     * our allocation request might have triggered global cache flushing
 
445
     */
 
446
    ftc_cache_add( cache, hash, node );
 
447
 
 
448
  Exit:
 
449
    *anode = node;
 
450
    return error;
 
451
 
 
452
  FlushCache:
 
453
    node = NULL;
 
454
    if ( error != FT_Err_Out_Of_Memory )
 
455
      goto Exit;
 
456
 
 
457
    {
 
458
      FTC_Manager  manager = cache->manager;
 
459
      FT_UInt      count, tries = 1;
 
460
 
 
461
 
 
462
      for (;;)
 
463
      {
 
464
        error = cache->clazz.node_new( &node, query, cache );
 
465
        if ( !error )
 
466
          break;
 
467
 
 
468
        node = NULL;
 
469
        if ( error != FT_Err_Out_Of_Memory )
 
470
          goto Exit;
 
471
 
 
472
        count = FTC_Manager_FlushN( manager, tries );
 
473
        if ( count == 0 )
 
474
          goto Exit;
 
475
 
 
476
        if ( count == tries )
 
477
        {
 
478
          count = tries * 2;
 
479
          if ( count < tries || count > manager->num_nodes )
 
480
            count = manager->num_nodes;
 
481
        }
 
482
        tries = count;
 
483
      }
 
484
    }
 
485
    goto AddNode;
 
486
  }
 
487
 
 
488
 
 
489
  FT_EXPORT_DEF( FT_Error )
 
490
  FTC_Cache_Lookup( FTC_Cache   cache,
 
491
                    FT_UInt32   hash,
 
492
                    FT_Pointer  query,
 
493
                    FTC_Node   *anode )
 
494
  {
 
495
    FT_UFast   idx;
 
496
    FTC_Node*  bucket;
 
497
    FTC_Node*  pnode;
 
498
    FTC_Node   node;
 
499
    FT_Error   error = 0;
 
500
 
 
501
    FTC_Node_CompareFunc  compare = cache->clazz.node_compare;
 
502
 
 
503
 
 
504
    if ( cache == NULL || anode == NULL )
 
505
      return FT_Err_Invalid_Argument;
 
506
 
 
507
    idx = hash & cache->mask;
 
508
    if ( idx < cache->p )
 
509
      idx = hash & ( cache->mask * 2 + 1 );
 
510
 
 
511
    bucket = cache->buckets + idx;
 
512
    pnode  = bucket;
 
513
    for (;;)
 
514
    {
 
515
      node = *pnode;
 
516
      if ( node == NULL )
 
517
        goto NewNode;
 
518
 
 
519
      if ( node->hash == hash && compare( node, query, cache ) )
 
520
        break;
 
521
 
 
522
      pnode = &node->link;
 
523
    }
 
524
 
 
525
    if ( node != *bucket )
 
526
    {
 
527
      *pnode     = node->link;
 
528
      node->link = *bucket;
 
529
      *bucket    = node;
 
530
    }
 
531
 
 
532
    /* move to head of MRU list */
 
533
    {
 
534
      FTC_Manager  manager = cache->manager;
 
535
 
 
536
 
 
537
      if ( node != manager->nodes_list )
 
538
        ftc_node_mru_up( node, manager );
 
539
    }
 
540
    *anode = node;
 
541
    return error;
 
542
 
 
543
  NewNode:
 
544
    return FTC_Cache_NewNode( cache, hash, query, anode );
 
545
  }
 
546
 
 
547
 
 
548
  FT_EXPORT_DEF( void )
 
549
  FTC_Cache_RemoveFaceID( FTC_Cache   cache,
 
550
                          FTC_FaceID  face_id )
 
551
  {
 
552
    FT_UFast     i, count;
 
553
    FTC_Manager  manager = cache->manager;
 
554
    FTC_Node     frees   = NULL;
 
555
 
 
556
 
 
557
    count = cache->p + cache->mask;
 
558
    for ( i = 0; i < count; i++ )
 
559
    {
 
560
      FTC_Node*  bucket = cache->buckets + i;
 
561
      FTC_Node*  pnode  = bucket;
 
562
 
 
563
 
 
564
      for ( ;; )
 
565
      {
 
566
        FTC_Node  node = *pnode;
 
567
 
 
568
 
 
569
        if ( node == NULL )
 
570
          break;
 
571
 
 
572
        if ( cache->clazz.node_remove_faceid( node, face_id, cache ) )
 
573
        {
 
574
          *pnode     = node->link;
 
575
          node->link = frees;
 
576
          frees      = node;
 
577
        }
 
578
        else
 
579
          pnode = &node->link;
 
580
      }
 
581
    }
 
582
 
 
583
    /* remove all nodes in the free list */
 
584
    while ( frees )
 
585
    {
 
586
      FTC_Node  node;
 
587
 
 
588
 
 
589
      node  = frees;
 
590
      frees = node->link;
 
591
 
 
592
      manager->cur_weight -= cache->clazz.node_weight( node, cache );
 
593
      ftc_node_mru_unlink( node, manager );
 
594
 
 
595
      cache->clazz.node_free( node, cache );
 
596
 
 
597
      cache->slack++;
 
598
    }
 
599
 
 
600
    ftc_cache_resize( cache );
 
601
  }
 
602
 
 
603
 
 
604
/* END */