ftccache.c

a very goog book

  /*************************************************************************/
  /*************************************************************************/
  /*****                                                               *****/
  /*****                    ABSTRACT CACHE CLASS                       *****/
  /*****                                                               *****/
  /*************************************************************************/
  /*************************************************************************/

#ifdef FTC_CACHE_USE_LINEAR_HASHING

  /* nothing */

#else /* !FTC_CACHE_USE_LINEAR_HASHING */

#define FTC_PRIMES_MIN  7
#define FTC_PRIMES_MAX  13845163

  static const FT_UInt  ftc_primes[] =
  {
    7,
    11,
    19,
    37,
    73,
    109,
    163,
    251,
    367,
    557,
    823,
    1237,
    1861,
    2777,
    4177,
    6247,
    9371,
    14057,
    21089,
    31627,
    47431,
    71143,
    106721,
    160073,
    240101,
    360163,
    540217,
    810343,
    1215497,
    1823231,
    2734867,
    4102283,
    6153409,
    9230113,
    13845163,
  };


  static FT_UFast
  ftc_prime_closest( FT_UFast  num )
  {
    FT_UInt  i;


    for ( i = 0; i < sizeof ( ftc_primes ) / sizeof ( ftc_primes[0] ); i++ )
      if ( ftc_primes[i] > num )
        return ftc_primes[i];

    return FTC_PRIMES_MAX;
  }


#define FTC_CACHE_RESIZE_TEST( c )       \
          ( (c)->nodes*3 < (c)->size  || \
            (c)->size*3  < (c)->nodes )


  static void
  ftc_cache_resize( FTC_Cache  cache )
  {
    FT_UFast  new_size;


    new_size = ftc_prime_closest( cache->nodes );
    if ( new_size != cache->size )
    {
      FT_Memory  memory = cache->memory;
      FT_Error   error;
      FTC_Node*  new_buckets ;
      FT_ULong   i;


      /* no need to report an error; we'll simply keep using the same */
      /* buckets number / size                                        */
      if ( FT_NEW_ARRAY( new_buckets, new_size ) )
        return;

      for ( i = 0; i < cache->size; i++ )
      {
        FTC_Node  node, next, *pnode;
        FT_UFast  hash;


        node = cache->buckets[i];
        while ( node )
        {
          next  = node->link;
          hash  = node->hash % new_size;
          pnode = new_buckets + hash;

          node->link = pnode[0];
          pnode[0]   = node;

          node = next;
        }
      }

      if ( cache->buckets )
        FT_FREE( cache->buckets );

      cache->buckets = new_buckets;
      cache->size    = new_size;

      FT_UNUSED( error );
    }
  }

#endif /* !FTC_CACHE_USE_LINEAR_HASHING */


  FT_EXPORT_DEF( FT_Error )
  ftc_cache_init( FTC_Cache  cache )
  {
    FT_Memory        memory = cache->memory;
    FTC_Cache_Class  clazz  = cache->clazz;
    FT_Error         error;


#ifdef FTC_CACHE_USE_LINEAR_HASHING

    cache->p     = 0;
    cache->mask  = FTC_HASH_INITIAL_SIZE - 1;
    cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD;

    if ( FT_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 ) )
      goto Exit;

#else /* !FTC_CACHE_USE_LINEAR_HASHING */

    cache->nodes = 0;
    cache->size  = FTC_PRIMES_MIN;

    if ( FT_NEW_ARRAY( cache->buckets, cache->size ) )
      goto Exit;

#endif /* !FTC_CACHE_USE_LINEAR_HASHING */

    /* now, initialize the lru list of families for this cache */
    if ( clazz->family_size > 0 )
    {
      FT_LruList_ClassRec*  lru_class = &cache->family_class;


      lru_class->list_size = sizeof( FT_LruListRec );
      lru_class->list_init = NULL;
      lru_class->list_done = NULL;

      lru_class->node_size    = clazz->family_size;
      lru_class->node_init    = (FT_LruNode_InitFunc)   clazz->family_init;
      lru_class->node_done    = (FT_LruNode_DoneFunc)   clazz->family_done;
      lru_class->node_flush   = (FT_LruNode_FlushFunc)  NULL;
      lru_class->node_compare = (FT_LruNode_CompareFunc)clazz->family_compare;

      error = FT_LruList_New( (FT_LruList_Class) lru_class,
                              0,    /* max items == 0 => unbounded list */
                              cache,
                              memory,
                              &cache->families );
      if ( error )
        FT_FREE( cache->buckets );
    }

  Exit:
    return error;
  }


  FT_EXPORT_DEF( void )
  ftc_cache_clear( FTC_Cache  cache )
  {
    if ( cache )
    {
      FT_Memory        memory  = cache->memory;
      FTC_Cache_Class  clazz   = cache->clazz;
      FTC_Manager      manager = cache->manager;
      FT_UFast         i;
      FT_UInt          count;

#ifdef FTC_CACHE_USE_LINEAR_HASHING
      count = cache->p + cache->mask + 1;
#else
      count = cache->size;
#endif

      for ( i = 0; i < count; i++ )
      {
        FTC_Node  *pnode = cache->buckets + i, next, node = *pnode;


        while ( node )
        {
          next        = node->link;
          node->link  = NULL;

          /* remove node from mru list */
          ftc_node_mru_unlink( node, manager );

          /* now finalize it */
          manager->cur_weight -= clazz->node_weight( node, cache );

          if ( clazz->node_done )
            clazz->node_done( node, cache );

          FT_FREE( node );
          node = next;
        }
        cache->buckets[i] = NULL;
      }

#ifdef FTC_CACHE_USE_LINEAR_HASHING
      cache->p = 0;
#else
      cache->nodes = 0;
#endif
      /* destroy the families */
      if ( cache->families )
        FT_LruList_Reset( cache->families );
    }
  }


  FT_EXPORT_DEF( void )
  ftc_cache_done( FTC_Cache  cache )
  {
    if ( cache )
    {
      FT_Memory  memory = cache->memory;


      ftc_cache_clear( cache );

      FT_FREE( cache->buckets );
#ifdef FTC_CACHE_USE_LINEAR_HASHING
      cache->mask  = 0;
      cache->slack = 0;
#else
      cache->size = 0;
#endif

      if ( cache->families )
      {
        FT_LruList_Destroy( cache->families );
        cache->families = NULL;
      }
    }
  }


  /* Look up a node in "top" of its cache's hash table. */
  /* If not found, create a new node.                   */
  /*                                                    */
  FT_EXPORT_DEF( FT_Error )
  ftc_cache_lookup( FTC_Cache   cache,
                    FTC_Query   query,
                    FTC_Node   *anode )
  {
    FT_Error    error = FT_Err_Ok;
    FT_LruNode  lru;


    if ( !cache || !query || !anode )
      return FTC_Err_Invalid_Argument;

    *anode = NULL;

    query->hash   = 0;
    query->family = NULL;

#if 1

    /* XXX: we break encapsulation for the sake of speed! */
    {
      /* first of all, find the relevant family */
      FT_LruList              list    = cache->families;
      FT_LruNode              fam, *pfam;
      FT_LruNode_CompareFunc  compare = list->clazz->node_compare;

      pfam = &list->nodes;
      for (;;)
      {
        fam = *pfam;
        if ( fam == NULL )
        {
          error = FT_LruList_Lookup( list, query, &lru );
          if ( error )
            goto Exit;

          goto Skip;
        }

        if ( compare( fam, query, list->data ) )
          break;

        pfam = &fam->next;
      }

      FT_ASSERT( fam != NULL );

      /* move to top of list when needed */
      if ( fam != list->nodes )
      {
        *pfam       = fam->next;
        fam->next   = list->nodes;
        list->nodes = fam;
      }

      lru = fam;

    Skip:
      ;
    }

#else

    error = FT_LruList_Lookup( cache->families, query, &lru );
    if ( !error )

#endif
    {
      FTC_Family  family = (FTC_Family) lru;
      FT_UFast    hash    = query->hash;
      FTC_Node*   bucket;

#ifdef FTC_CACHE_USE_LINEAR_HASHING

      FT_UInt  index;


      index = hash & cache->mask;
      if ( index < cache->p )
        index = hash & ( cache->mask * 2 + 1 );

      bucket  = cache->buckets + index;

#else

      bucket  = cache->buckets + (hash % cache->size);

#endif


      if ( query->family     != family                        ||
           family->fam_index >= cache->manager->families.size )
      {
        FT_ERROR((
          "ftc_cache_lookup: invalid query (bad 'family' field)\n" ));
        return FTC_Err_Invalid_Argument;
      }

      if ( *bucket )
      {
        FTC_Node*             pnode   = bucket;
        FTC_Node_CompareFunc  compare = cache->clazz->node_compare;


        for ( ;; )
        {
          FTC_Node  node;


          node = *pnode;
          if ( node == NULL )
            break;

          if ( node->hash == hash                            &&
               (FT_UInt)node->fam_index == family->fam_index &&
               compare( node, query, cache ) )
          {
            /* move to head of bucket list */
            if ( pnode != bucket )
            {
              *pnode     = node->link;
              node->link = *bucket;
              *bucket    = node;
            }

            /* move to head of MRU list */
            if ( node != cache->manager->nodes_list )
              ftc_node_mru_up( node, cache->manager );

            *anode = node;
            goto Exit;
          }

          pnode = &node->link;
        }
      }

      /* didn't find a node, create a new one */
      {
        FTC_Cache_Class  clazz   = cache->clazz;
        FTC_Manager      manager = cache->manager;
        FT_Memory        memory  = cache->memory;
        FTC_Node         node;


        if ( FT_ALLOC( node, clazz->node_size ) )
          goto Exit;

        node->fam_index = (FT_UShort) family->fam_index;
        node->hash      = query->hash;
        node->ref_count = 0;

        error = clazz->node_init( node, query, cache );
        if ( error )
        {
          FT_FREE( node );
          goto Exit;
        }

#ifdef FTC_CACHE_USE_LINEAR_HASHING
        error = ftc_node_hash_link( node, cache );
        if ( error )
        {
          clazz->node_done( node, cache );
          FT_FREE( node );
          goto Exit;
        }
#else
        ftc_node_hash_link( node, cache );
#endif

        ftc_node_mru_link( node, cache->manager );

        cache->manager->cur_weight += clazz->node_weight( node, cache );

        /* now try to compress the node pool when necessary */
        if ( manager->cur_weight >= manager->max_weight )
        {
          node->ref_count++;
          FTC_Manager_Compress( manager );
          node->ref_count--;
        }

#ifndef FTC_CACHE_USE_LINEAR_HASHING
        /* try to resize the hash table if appropriate */
        if ( FTC_CACHE_RESIZE_TEST( cache ) )
          ftc_cache_resize( cache );
#endif

        *anode = node;
      }
    }

  Exit:
    return error;
  }


/* END */