#include <ft2build.h>

#include FT_CONFIG_CONFIG_H

#include FT_INTERNAL_DEBUG_H

#include FT_INTERNAL_MEMORY_H

#include FT_SYSTEM_H

#include FT_ERRORS_H

#include FT_TYPES_H

#ifdef FT_DEBUG_MEMORY

#define  KEEPALIVE /* `Keep alive' means that freed blocks aren't released

                    * to the heap.  This is useful to detect double-frees

                    * or weird heap corruption, but it uses large amounts of

                    * memory, however.

                    */

#include FT_CONFIG_STANDARD_LIBRARY_H

  FT_BASE_DEF( const char* )  _ft_debug_file   = NULL;

  FT_BASE_DEF( long )         _ft_debug_lineno = 0;

  extern void

  FT_DumpMemory( FT_Memory  memory );

  typedef struct FT_MemSourceRec_*  FT_MemSource;

  typedef struct FT_MemNodeRec_*    FT_MemNode;

  typedef struct FT_MemTableRec_*   FT_MemTable;

#define FT_MEM_VAL( addr )  ( (FT_PtrDist)(FT_Pointer)( addr ) )

  /*

   */

  typedef struct  FT_MemSourceRec_

  {

    const char*   file_name;

    long          line_no;

    FT_Long       cur_blocks;   /* current number of allocated blocks */

    FT_Long       max_blocks;   /* max. number of allocated blocks    */

    FT_Long       all_blocks;   /* total number of blocks allocated   */

    FT_Long       cur_size;     /* current cumulative allocated size */

    FT_Long       max_size;     /* maximum cumulative allocated size */

    FT_Long       all_size;     /* total cumulative allocated size   */

    FT_Long       cur_max;      /* current maximum allocated size */

    FT_UInt32     hash;

    FT_MemSource  link;

  } FT_MemSourceRec;

  /*

   */

#define FT_MEM_SOURCE_BUCKETS  128

  /*

   */

  typedef struct  FT_MemNodeRec_

  {

    FT_Byte*      address;

    FT_Long       size;     /* < 0 if the block was freed */

    FT_MemSource  source;

#ifdef KEEPALIVE

    const char*   free_file_name;

    FT_Long       free_line_no;

#endif

    FT_MemNode    link;

  } FT_MemNodeRec;

  /*

   */

  typedef struct  FT_MemTableRec_

  {

    FT_Long          size;

    FT_Long          nodes;

    FT_MemNode*      buckets;

    FT_Long          alloc_total;

    FT_Long          alloc_current;

    FT_Long          alloc_max;

    FT_Long          alloc_count;

    FT_Bool          bound_total;

    FT_Long          alloc_total_max;

    FT_Bool          bound_count;

    FT_Long          alloc_count_max;

    FT_MemSource     sources[FT_MEM_SOURCE_BUCKETS];

    FT_Bool          keep_alive;

    FT_Memory        memory;

    FT_Pointer       memory_user;

    FT_Alloc_Func    alloc;

    FT_Free_Func     free;

    FT_Realloc_Func  realloc;

  } FT_MemTableRec;

#define FT_MEM_SIZE_MIN  7

#define FT_MEM_SIZE_MAX  13845163

#define FT_FILENAME( x )  ( (x) ? (x) : "unknown file" )

  /*

   */

  static const FT_Int  ft_mem_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_Long

  ft_mem_closest_prime( FT_Long  num )

  {

    size_t  i;

    for ( i = 0;

          i < sizeof ( ft_mem_primes ) / sizeof ( ft_mem_primes[0] ); i++ )

      if ( ft_mem_primes[i] > num )

        return ft_mem_primes[i];

    return FT_MEM_SIZE_MAX;

  }

  static void

  ft_mem_debug_panic( const char*  fmt,

                      ... )

  {

    va_list  ap;

    printf( "FreeType.Debug: " );

    va_start( ap, fmt );

    vprintf( fmt, ap );

    va_end( ap );

    printf( "\n" );

    exit( EXIT_FAILURE );

  }

  static FT_Pointer

  ft_mem_table_alloc( FT_MemTable  table,

                      FT_Long      size )

  {

    FT_Memory   memory = table->memory;

    FT_Pointer  block;

    memory->user = table->memory_user;

    block = table->alloc( memory, size );

    memory->user = table;

    return block;

  }

  static void

  ft_mem_table_free( FT_MemTable  table,

                     FT_Pointer   block )

  {

    FT_Memory  memory = table->memory;

    memory->user = table->memory_user;

    table->free( memory, block );

    memory->user = table;

  }

  static void

  ft_mem_table_resize( FT_MemTable  table )

  {

    FT_Long  new_size;

    new_size = ft_mem_closest_prime( table->nodes );

    if ( new_size != table->size )

    {

      FT_MemNode*  new_buckets;

      FT_Long      i;

      new_buckets = (FT_MemNode *)

                      ft_mem_table_alloc(

                        table,

                        new_size * (FT_Long)sizeof ( FT_MemNode ) );

      if ( !new_buckets )

        return;

      FT_ARRAY_ZERO( new_buckets, new_size );

      for ( i = 0; i < table->size; i++ )

      {

        FT_MemNode  node, next, *pnode;

        FT_PtrDist  hash;

        node = table->buckets[i];

        while ( node )

        {

          next  = node->link;

          hash  = FT_MEM_VAL( node->address ) % (FT_PtrDist)new_size;

          pnode = new_buckets + hash;

          node->link = pnode[0];

          pnode[0]   = node;

          node = next;

        }

      }

      if ( table->buckets )

        ft_mem_table_free( table, table->buckets );

      table->buckets = new_buckets;

      table->size    = new_size;

    }

  }

  static FT_MemTable

  ft_mem_table_new( FT_Memory  memory )

  {

    FT_MemTable  table;

    table = (FT_MemTable)memory->alloc( memory, sizeof ( *table ) );

    if ( !table )

      goto Exit;

    FT_ZERO( table );

    table->size  = FT_MEM_SIZE_MIN;

    table->nodes = 0;

    table->memory = memory;

    table->memory_user = memory->user;

    table->alloc   = memory->alloc;

    table->realloc = memory->realloc;

    table->free    = memory->free;

    table->buckets = (FT_MemNode *)

                       memory->alloc(

                         memory,

                         table->size * (FT_Long)sizeof ( FT_MemNode ) );

    if ( table->buckets )

      FT_ARRAY_ZERO( table->buckets, table->size );

    else

    {

      memory->free( memory, table );

      table = NULL;

    }

  Exit:

    return table;

  }

  static void

  ft_mem_table_destroy( FT_MemTable  table )

  {

    FT_Long  i;

    FT_Long  leak_count = 0;

    FT_Long  leaks      = 0;

    FT_DumpMemory( table->memory );

    /* remove all blocks from the table, revealing leaked ones */

    for ( i = 0; i < table->size; i++ )

    {

      FT_MemNode  *pnode = table->buckets + i, next, node = *pnode;

      while ( node )

      {

        next       = node->link;

        node->link = NULL;

        if ( node->size > 0 )

        {

          printf(

            "leaked memory block at address %p, size %8ld in (%s:%ld)\n",

            (void*)node->address,

            node->size,

            FT_FILENAME( node->source->file_name ),

            node->source->line_no );

          leak_count++;

          leaks += node->size;

          ft_mem_table_free( table, node->address );

        }

        node->address = NULL;

        node->size    = 0;

        ft_mem_table_free( table, node );

        node = next;

      }

      table->buckets[i] = NULL;

    }

    ft_mem_table_free( table, table->buckets );

    table->buckets = NULL;

    table->size  = 0;

    table->nodes = 0;

    /* remove all sources */

    for ( i = 0; i < FT_MEM_SOURCE_BUCKETS; i++ )

    {

      FT_MemSource  source, next;

      for ( source = table->sources[i]; source != NULL; source = next )

      {

        next = source->link;

        ft_mem_table_free( table, source );

      }

      table->sources[i] = NULL;

    }

    printf( "FreeType: total memory allocations = %ld\n",

            table->alloc_total );

    printf( "FreeType: maximum memory footprint = %ld\n",

            table->alloc_max );

    ft_mem_table_free( table, table );

    if ( leak_count > 0 )

      ft_mem_debug_panic(

        "FreeType: %ld bytes of memory leaked in %ld blocks\n",

        leaks, leak_count );

    printf( "FreeType: no memory leaks detected\n" );

  }

  static FT_MemNode*

  ft_mem_table_get_nodep( FT_MemTable  table,

                          FT_Byte*     address )

  {

    FT_PtrDist   hash;

    FT_MemNode  *pnode, node;

    hash  = FT_MEM_VAL( address );

    pnode = table->buckets + ( hash % (FT_PtrDist)table->size );

    for (;;)

    {

      node = pnode[0];

      if ( !node )

        break;

      if ( node->address == address )

        break;

      pnode = &node->link;

    }

    return pnode;

  }

  static FT_MemSource

  ft_mem_table_get_source( FT_MemTable  table )

  {

    FT_UInt32     hash;

    FT_MemSource  node, *pnode;

    /* cast to FT_PtrDist first since void* can be larger */

    /* than FT_UInt32 and GCC 4.1.1 emits a warning       */

    hash  = (FT_UInt32)(FT_PtrDist)(void*)_ft_debug_file +

              (FT_UInt32)( 5 * _ft_debug_lineno );

    pnode = &table->sources[hash % FT_MEM_SOURCE_BUCKETS];

    for (;;)

    {

      node = *pnode;

      if ( !node )

        break;

      if ( node->file_name == _ft_debug_file   &&

           node->line_no   == _ft_debug_lineno )

        goto Exit;

      pnode = &node->link;

    }

    node = (FT_MemSource)ft_mem_table_alloc( table, sizeof ( *node ) );

    if ( !node )

      ft_mem_debug_panic(

        "not enough memory to perform memory debugging\n" );

    node->file_name = _ft_debug_file;

    node->line_no   = _ft_debug_lineno;

    node->cur_blocks = 0;

    node->max_blocks = 0;

    node->all_blocks = 0;

    node->cur_size = 0;

    node->max_size = 0;

    node->all_size = 0;

    node->cur_max = 0;

    node->link = NULL;

    node->hash = hash;

    *pnode     = node;

  Exit:

    return node;

  }

  static void

  ft_mem_table_set( FT_MemTable  table,

                    FT_Byte*     address,

                    FT_Long      size,

                    FT_Long      delta )

  {

    FT_MemNode  *pnode, node;

    if ( table )

    {

      FT_MemSource  source;

      pnode = ft_mem_table_get_nodep( table, address );

      node  = *pnode;

      if ( node )

      {

        if ( node->size < 0 )

        {

          /* This block was already freed.  Our memory is now completely */