/* GLIB - Library of useful routines for C programming

  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald

  *

  * This library is free software; you can redistribute it and/or

  * modify it under the terms of the GNU Lesser General Public

  * License as published by the Free Software Foundation; either

  * version 2 of the License, or (at your option) any later version.

  *

  * This library is distributed in the hope that it will be useful,

  * but WITHOUT ANY WARRANTY; without even the implied warranty of

  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

  * Lesser General Public License for more details.

  *

  * You should have received a copy of the GNU Lesser General Public

  * License along with this library; if not, write to the

  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,

  * Boston, MA 02111-1307, USA.

  */

 /*

  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS

  * file for a list of people on the GLib Team.  See the ChangeLog

  * files for a list of changes.  These files are distributed with

  * GLib at ftp://ftp.gtk.org/pub/gtk/. 

  */

 /* 

  * MT safe

  */

 #include "config.h"

 #include <stdlib.h>

 #include <string.h>

 #include <signal.h>

 #include "glib.h"

 /* notes on macros:

  * if ENABLE_GC_FRIENDLY is defined, freed memory should be 0-wiped.

  */

 #define MEM_PROFILE_TABLE_SIZE 4096

 #define MEM_AREA_SIZE 4L

 static guint mem_chunk_recursion = 0;

 #  define MEM_CHUNK_ROUTINE_COUNT()	(mem_chunk_recursion)

 #  define ENTER_MEM_CHUNK_ROUTINE()	(mem_chunk_recursion = MEM_CHUNK_ROUTINE_COUNT () + 1)

 #  define LEAVE_MEM_CHUNK_ROUTINE()	(mem_chunk_recursion = MEM_CHUNK_ROUTINE_COUNT () - 1)

 /* --- old memchunk prototypes --- */

 void            old_mem_chunks_init     (void);

 GMemChunk*      old_mem_chunk_new       (const gchar  *name,

                                          gint          atom_size,

                                          gulong        area_size,

                                          gint          type);

 void            old_mem_chunk_destroy   (GMemChunk *mem_chunk);

 gpointer        old_mem_chunk_alloc     (GMemChunk *mem_chunk);

 gpointer        old_mem_chunk_alloc0    (GMemChunk *mem_chunk);

 void            old_mem_chunk_free      (GMemChunk *mem_chunk,

                                          gpointer   mem);

 void            old_mem_chunk_clean     (GMemChunk *mem_chunk);

 void            old_mem_chunk_reset     (GMemChunk *mem_chunk);

 void            old_mem_chunk_print     (GMemChunk *mem_chunk);

 void            old_mem_chunk_info      (void);

 /* --- MemChunks --- */

 #ifndef G_ALLOC_AND_FREE

 typedef struct _GAllocator GAllocator;

 typedef struct _GMemChunk  GMemChunk;

 #define G_ALLOC_ONLY	  1

 #define G_ALLOC_AND_FREE  2

 #endif

 typedef struct _GFreeAtom      GFreeAtom;

 typedef struct _GMemArea       GMemArea;

 struct _GFreeAtom

 {

   GFreeAtom *next;

 };

 struct _GMemArea

 {

   GMemArea *next;            /* the next mem area */

   GMemArea *prev;            /* the previous mem area */

   gulong index;              /* the current index into the "mem" array */

   gulong free;               /* the number of free bytes in this mem area */

   gulong allocated;          /* the number of atoms allocated from this area */

   gulong mark;               /* is this mem area marked for deletion */

   gchar mem[MEM_AREA_SIZE];  /* the mem array from which atoms get allocated

 			      * the actual size of this array is determined by

 			      *  the mem chunk "area_size". ANSI says that it

 			      *  must be declared to be the maximum size it

 			      *  can possibly be (even though the actual size

 			      *  may be less).

 			      */

 };

 struct _GMemChunk

 {

   const gchar *name;         /* name of this MemChunk...used for debugging output */

   gint type;                 /* the type of MemChunk: ALLOC_ONLY or ALLOC_AND_FREE */

   gint num_mem_areas;        /* the number of memory areas */

   gint num_marked_areas;     /* the number of areas marked for deletion */

   guint atom_size;           /* the size of an atom */

   gulong area_size;          /* the size of a memory area */

   GMemArea *mem_area;        /* the current memory area */

   GMemArea *mem_areas;       /* a list of all the mem areas owned by this chunk */

   GMemArea *free_mem_area;   /* the free area...which is about to be destroyed */

   GFreeAtom *free_atoms;     /* the free atoms list */

   GTree *mem_tree;           /* tree of mem areas sorted by memory address */

   GMemChunk *next;           /* pointer to the next chunk */

   GMemChunk *prev;           /* pointer to the previous chunk */

 };

 static gulong old_mem_chunk_compute_size (gulong    size,

                                           gulong    min_size) G_GNUC_CONST;

 static gint   old_mem_chunk_area_compare (GMemArea *a,

                                           GMemArea *b);

 static gint   old_mem_chunk_area_search  (GMemArea *a,

                                           gchar    *addr);

 /* here we can't use StaticMutexes, as they depend upon a working

  * g_malloc, the same holds true for StaticPrivate

  */

 static GMutex        *mem_chunks_lock = NULL;

 static GMemChunk     *mem_chunks = NULL;

 void

 old_mem_chunks_init (void)

 {

   mem_chunks_lock = g_mutex_new ();

 }

 GMemChunk*

 old_mem_chunk_new (const gchar  *name,

                    gint          atom_size,

                    gulong        area_size,

                    gint          type)

 {

   GMemChunk *mem_chunk;

   gulong rarea_size;

   g_return_val_if_fail (atom_size > 0, NULL);

   g_return_val_if_fail (area_size >= atom_size, NULL);

   ENTER_MEM_CHUNK_ROUTINE ();

   area_size = (area_size + atom_size - 1) / atom_size;

   area_size *= atom_size;

   mem_chunk = g_new (GMemChunk, 1);

   mem_chunk->name = name;

   mem_chunk->type = type;

   mem_chunk->num_mem_areas = 0;

   mem_chunk->num_marked_areas = 0;

   mem_chunk->mem_area = NULL;

   mem_chunk->free_mem_area = NULL;

   mem_chunk->free_atoms = NULL;

   mem_chunk->mem_tree = NULL;

   mem_chunk->mem_areas = NULL;

   mem_chunk->atom_size = atom_size;

   if (mem_chunk->type == G_ALLOC_AND_FREE)

     mem_chunk->mem_tree = g_tree_new ((GCompareFunc) old_mem_chunk_area_compare);

   if (mem_chunk->atom_size % G_MEM_ALIGN)

     mem_chunk->atom_size += G_MEM_ALIGN - (mem_chunk->atom_size % G_MEM_ALIGN);

   rarea_size = area_size + sizeof (GMemArea) - MEM_AREA_SIZE;

   rarea_size = old_mem_chunk_compute_size (rarea_size, atom_size + sizeof (GMemArea) - MEM_AREA_SIZE);

   mem_chunk->area_size = rarea_size - (sizeof (GMemArea) - MEM_AREA_SIZE);

   g_mutex_lock (mem_chunks_lock);

   mem_chunk->next = mem_chunks;

   mem_chunk->prev = NULL;

   if (mem_chunks)

     mem_chunks->prev = mem_chunk;

   mem_chunks = mem_chunk;

   g_mutex_unlock (mem_chunks_lock);

   LEAVE_MEM_CHUNK_ROUTINE ();

   return mem_chunk;

 }

 void

 old_mem_chunk_destroy (GMemChunk *mem_chunk)

 {

   GMemArea *mem_areas;

   GMemArea *temp_area;

   g_return_if_fail (mem_chunk != NULL);

   ENTER_MEM_CHUNK_ROUTINE ();

   mem_areas = mem_chunk->mem_areas;

   while (mem_areas)

     {

       temp_area = mem_areas;

       mem_areas = mem_areas->next;

       g_free (temp_area);

     }

   g_mutex_lock (mem_chunks_lock);

   if (mem_chunk->next)

     mem_chunk->next->prev = mem_chunk->prev;

   if (mem_chunk->prev)

     mem_chunk->prev->next = mem_chunk->next;

   if (mem_chunk == mem_chunks)

     mem_chunks = mem_chunks->next;

   g_mutex_unlock (mem_chunks_lock);

   if (mem_chunk->type == G_ALLOC_AND_FREE)

     g_tree_destroy (mem_chunk->mem_tree);  

   g_free (mem_chunk);

   LEAVE_MEM_CHUNK_ROUTINE ();

 }

 gpointer

 old_mem_chunk_alloc (GMemChunk *mem_chunk)

 {

   GMemArea *temp_area;

   gpointer mem;

   ENTER_MEM_CHUNK_ROUTINE ();

   g_return_val_if_fail (mem_chunk != NULL, NULL);

   while (mem_chunk->free_atoms)

     {

       /* Get the first piece of memory on the "free_atoms" list.

        * We can go ahead and destroy the list node we used to keep

        *  track of it with and to update the "free_atoms" list to

        *  point to its next element.

        */

       mem = mem_chunk->free_atoms;

       mem_chunk->free_atoms = mem_chunk->free_atoms->next;

       /* Determine which area this piece of memory is allocated from */

       temp_area = g_tree_search (mem_chunk->mem_tree,

 				 (GCompareFunc) old_mem_chunk_area_search,

 				 mem);

       /* If the area has been marked, then it is being destroyed.

        *  (ie marked to be destroyed).

        * We check to see if all of the segments on the free list that

        *  reference this area have been removed. This occurs when

        *  the ammount of free memory is less than the allocatable size.

        * If the chunk should be freed, then we place it in the "free_mem_area".

        * This is so we make sure not to free the mem area here and then

        *  allocate it again a few lines down.

        * If we don't allocate a chunk a few lines down then the "free_mem_area"

        *  will be freed.

        * If there is already a "free_mem_area" then we'll just free this mem area.

        */

       if (temp_area->mark)

         {

           /* Update the "free" memory available in that area */

           temp_area->free += mem_chunk->atom_size;

           if (temp_area->free == mem_chunk->area_size)

             {

               if (temp_area == mem_chunk->mem_area)

                 mem_chunk->mem_area = NULL;

               if (mem_chunk->free_mem_area)

                 {

                   mem_chunk->num_mem_areas -= 1;

                   if (temp_area->next)

                     temp_area->next->prev = temp_area->prev;

                   if (temp_area->prev)

                     temp_area->prev->next = temp_area->next;

                   if (temp_area == mem_chunk->mem_areas)

                     mem_chunk->mem_areas = mem_chunk->mem_areas->next;

 		  if (mem_chunk->type == G_ALLOC_AND_FREE)

 		    g_tree_remove (mem_chunk->mem_tree, temp_area);

                   g_free (temp_area);

                 }

               else

                 mem_chunk->free_mem_area = temp_area;

 	      mem_chunk->num_marked_areas -= 1;

 	    }

 	}

       else

         {

           /* Update the number of allocated atoms count.

 	   */

           temp_area->allocated += 1;

           /* The area wasn't marked...return the memory

 	   */

 	  goto outa_here;

         }

     }

   /* If there isn't a current mem area or the current mem area is out of space

    *  then allocate a new mem area. We'll first check and see if we can use

    *  the "free_mem_area". Otherwise we'll just malloc the mem area.

    */

   if ((!mem_chunk->mem_area) ||

       ((mem_chunk->mem_area->index + mem_chunk->atom_size) > mem_chunk->area_size))

     {

       if (mem_chunk->free_mem_area)

         {

           mem_chunk->mem_area = mem_chunk->free_mem_area;

 	  mem_chunk->free_mem_area = NULL;

         }

       else

         {

 #ifdef ENABLE_GC_FRIENDLY

 	  mem_chunk->mem_area = (GMemArea*) g_malloc0 (sizeof (GMemArea) -

 						       MEM_AREA_SIZE +

 						       mem_chunk->area_size); 

 #else /* !ENABLE_GC_FRIENDLY */

 	  mem_chunk->mem_area = (GMemArea*) g_malloc (sizeof (GMemArea) -

 						      MEM_AREA_SIZE +

 						      mem_chunk->area_size);

 #endif /* ENABLE_GC_FRIENDLY */

 	  mem_chunk->num_mem_areas += 1;

 	  mem_chunk->mem_area->next = mem_chunk->mem_areas;

 	  mem_chunk->mem_area->prev = NULL;

 	  if (mem_chunk->mem_areas)

 	    mem_chunk->mem_areas->prev = mem_chunk->mem_area;

 	  mem_chunk->mem_areas = mem_chunk->mem_area;

 	  if (mem_chunk->type == G_ALLOC_AND_FREE)

 	    g_tree_insert (mem_chunk->mem_tree, mem_chunk->mem_area, mem_chunk->mem_area);

         }

       mem_chunk->mem_area->index = 0;

       mem_chunk->mem_area->free = mem_chunk->area_size;

       mem_chunk->mem_area->allocated = 0;

       mem_chunk->mem_area->mark = 0;

     }

   /* Get the memory and modify the state variables appropriately.

    */

   mem = (gpointer) &mem_chunk->mem_area->mem[mem_chunk->mem_area->index];

   mem_chunk->mem_area->index += mem_chunk->atom_size;

   mem_chunk->mem_area->free -= mem_chunk->atom_size;

   mem_chunk->mem_area->allocated += 1;

  outa_here:

   LEAVE_MEM_CHUNK_ROUTINE ();

   return mem;

 }

 gpointer

 old_mem_chunk_alloc0 (GMemChunk *mem_chunk)

 {

   gpointer mem;

   mem = old_mem_chunk_alloc (mem_chunk);

   if (mem)

     {

       memset (mem, 0, mem_chunk->atom_size);

     }

   return mem;

 }

 void

 old_mem_chunk_free (GMemChunk *mem_chunk,

                     gpointer   mem)

 {

   GMemArea *temp_area;

   GFreeAtom *free_atom;

   g_return_if_fail (mem_chunk != NULL);

   g_return_if_fail (mem != NULL);

   ENTER_MEM_CHUNK_ROUTINE ();

 #ifdef ENABLE_GC_FRIENDLY

   memset (mem, 0, mem_chunk->atom_size);

 #endif /* ENABLE_GC_FRIENDLY */

   /* Don't do anything if this is an ALLOC_ONLY chunk

    */

   if (mem_chunk->type == G_ALLOC_AND_FREE)

     {

       /* Place the memory on the "free_atoms" list

        */

       free_atom = (GFreeAtom*) mem;

       free_atom->next = mem_chunk->free_atoms;

       mem_chunk->free_atoms = free_atom;

       temp_area = g_tree_search (mem_chunk->mem_tree,

 				 (GCompareFunc) old_mem_chunk_area_search,

 				 mem);

       temp_area->allocated -= 1;

       if (temp_area->allocated == 0)

 	{

 	  temp_area->mark = 1;

 	  mem_chunk->num_marked_areas += 1;

 	}

     }

   LEAVE_MEM_CHUNK_ROUTINE ();

 }

 /* This doesn't free the free_area if there is one */

 void

 old_mem_chunk_clean (GMemChunk *mem_chunk)

 {

   GMemArea *mem_area;

   GFreeAtom *prev_free_atom;

   GFreeAtom *temp_free_atom;

   gpointer mem;

   g_return_if_fail (mem_chunk != NULL);

   ENTER_MEM_CHUNK_ROUTINE ();

   if (mem_chunk->type == G_ALLOC_AND_FREE)

     {

       prev_free_atom = NULL;

       temp_free_atom = mem_chunk->free_atoms;

       while (temp_free_atom)

 	{

 	  mem = (gpointer) temp_free_atom;

 	  mem_area = g_tree_search (mem_chunk->mem_tree,

 				    (GCompareFunc) old_mem_chunk_area_search,

 				    mem);

           /* If this mem area is marked for destruction then delete the

 	   *  area and list node and decrement the free mem.

            */

 	  if (mem_area->mark)

 	    {

 	      if (prev_free_atom)

 		prev_free_atom->next = temp_free_atom->next;

 	      else

 		mem_chunk->free_atoms = temp_free_atom->next;

 	      temp_free_atom = temp_free_atom->next;

 	      mem_area->free += mem_chunk->atom_size;

 	      if (mem_area->free == mem_chunk->area_size)

 		{

 		  mem_chunk->num_mem_areas -= 1;

 		  mem_chunk->num_marked_areas -= 1;

 		  if (mem_area->next)

 		    mem_area->next->prev = mem_area->prev;

 		  if (mem_area->prev)

 		    mem_area->prev->next = mem_area->next;

 		  if (mem_area == mem_chunk->mem_areas)

 		    mem_chunk->mem_areas = mem_chunk->mem_areas->next;

 		  if (mem_area == mem_chunk->mem_area)

 		    mem_chunk->mem_area = NULL;

 		  if (mem_chunk->type == G_ALLOC_AND_FREE)

 		    g_tree_remove (mem_chunk->mem_tree, mem_area);

 		  g_free (mem_area);

 		}

 	    }

 	  else

 	    {

 	      prev_free_atom = temp_free_atom;

 	      temp_free_atom = temp_free_atom->next;

 	    }

 	}

     }

   LEAVE_MEM_CHUNK_ROUTINE ();

 }

 void

 old_mem_chunk_reset (GMemChunk *mem_chunk)

 {

   GMemArea *mem_areas;

   GMemArea *temp_area;

   g_return_if_fail (mem_chunk != NULL);

   ENTER_MEM_CHUNK_ROUTINE ();

   mem_areas = mem_chunk->mem_areas;

   mem_chunk->num_mem_areas = 0;

   mem_chunk->mem_areas = NULL;

   mem_chunk->mem_area = NULL;

   while (mem_areas)

     {

       temp_area = mem_areas;

       mem_areas = mem_areas->next;

       g_free (temp_area);

     }

   mem_chunk->free_atoms = NULL;

   if (mem_chunk->mem_tree)

     {

       g_tree_destroy (mem_chunk->mem_tree);

       mem_chunk->mem_tree = g_tree_new ((GCompareFunc) old_mem_chunk_area_compare);

     }

   LEAVE_MEM_CHUNK_ROUTINE ();

 }

 void

 old_mem_chunk_print (GMemChunk *mem_chunk)

 {

   GMemArea *mem_areas;

   gulong mem;

   g_return_if_fail (mem_chunk != NULL);

   mem_areas = mem_chunk->mem_areas;

   mem = 0;

   while (mem_areas)

     {

       mem += mem_chunk->area_size - mem_areas->free;

       mem_areas = mem_areas->next;

     }

   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO,

 	 "%s: %ld bytes using %d mem areas",

 	 mem_chunk->name, mem, mem_chunk->num_mem_areas);

 }

 void

 old_mem_chunk_info (void)

 {

   GMemChunk *mem_chunk;

   gint count;

   count = 0;

   g_mutex_lock (mem_chunks_lock);

   mem_chunk = mem_chunks;

   while (mem_chunk)

     {

       count += 1;

       mem_chunk = mem_chunk->next;

     }

   g_mutex_unlock (mem_chunks_lock);

   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "%d mem chunks", count);

   g_mutex_lock (mem_chunks_lock);

   mem_chunk = mem_chunks;

   g_mutex_unlock (mem_chunks_lock);

   while (mem_chunk)

     {

       old_mem_chunk_print ((GMemChunk*) mem_chunk);

       mem_chunk = mem_chunk->next;

     }  

 }

 static gulong

 old_mem_chunk_compute_size (gulong size,

                             gulong min_size)

 {

   gulong power_of_2;

   gulong lower, upper;

   power_of_2 = 16;

   while (power_of_2 < size)

     power_of_2 <<= 1;

   lower = power_of_2 >> 1;

   upper = power_of_2;

   if (size - lower < upper - size && lower >= min_size)

     return lower;

   else

     return upper;

 }

 static gint

 old_mem_chunk_area_compare (GMemArea *a,

                             GMemArea *b)

 {

   if (a->mem > b->mem)

     return 1;

   else if (a->mem < b->mem)

     return -1;

   return 0;

 }

 static gint

 old_mem_chunk_area_search (GMemArea *a,

                            gchar    *addr)

 {

   if (a->mem <= addr)

     {

       if (addr < &a->mem[a->index])

 	return 0;

       return 1;

     }

   return -1;

 }