← Back to branch summary

~ubuntu-branches/ubuntu/wily/hedgewars/wily

« back to all changes in this revision

Viewing changes to misc/libfreetype/src/cache/ftccache.c

  • Committer: Package Import Robot
  • Author(s): Dmitry E. Oboukhov
  • Date: 2011-09-23 10:16:55 UTC
  • mfrom: (1.2.11 upstream)
  • Revision ID: package-import@ubuntu.com-20110923101655-3977th2gc5n0a3pv
Tags: 0.9.16-1
* New upstream version.
 + Downloadable content! Simply click to install any content.
   New voices, hats, maps, themes, translations, music, scripts...
   Hedgewars is now more customisable than ever before! As time goes
   by we will be soliciting community content to feature on this page,
   so remember to check it from time to time. If you decide you want
   to go back to standard Hedgewars, just remove the Data directory
   from your Hedgewars config directory.
 + 3-D rendering! Diorama-like rendering of the game in a variety
   of 3D modes. Let us know which ones work best for you, we didn't
   really have the equipment to test them all.
 + Resizable game window.
 + New utilities! The Time Box will remove one of your hedgehogs
   from the game for a while, protecting from attack until it returns,
   somewhere else on the map. Land spray will allow you to build bridges,
   seal up holes, or just make life unpleasant for your enemies.
 + New single player: Bamboo Thicket, That Sinking Feeling, Newton and
   the Tree and multi-player: The Specialists, Space Invaders,
   Racer - scripts! And a ton more script hooks for scripters
 + New twists on old weapons. Drill strike, seduction and fire have
   been adjusted. Defective mines have been added, rope can attach to
   hogs/crates/barrels again, grenades now have variable bounce (use
   precise key + 1-5). Portal gun is now more usable in flight and
   all game actions are a lot faster.
 + New theme - Golf, dozens of new community hats and a new
   localised Default voice, Ukranian.

Show diffs side-by-side

added added

removed removed

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