comparison src/alloc.c @ 88155:d7ddb3e565de

sync with trunk

88154:8ce476d3ba36

/* Storage allocation and gc for GNU Emacs Lisp interpreter.
   Copyright (C) 1985, 86, 88, 93, 94, 95, 97, 98, 1999, 2000, 2001, 2002, 2003
      Free Software Foundation, Inc.

This file is part of GNU Emacs.

GNU Emacs is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Emacs; see the file COPYING.  If not, write to
the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

#include <config.h>
#include <stdio.h>

#ifdef ALLOC_DEBUG
#undef INLINE
#endif

/* Note that this declares bzero on OSF/1.  How dumb.  */

#include <signal.h>

/* GC_MALLOC_CHECK defined means perform validity checks of malloc'd
   memory.  Can do this only if using gmalloc.c.  */

#if defined SYSTEM_MALLOC || defined DOUG_LEA_MALLOC
#undef GC_MALLOC_CHECK
#endif

/* This file is part of the core Lisp implementation, and thus must
   deal with the real data structures.  If the Lisp implementation is
   replaced, this file likely will not be used.  */

#include "blockinput.h"
#include "charset.h"
#include "syssignal.h"
#include <setjmp.h>

#ifdef HAVE_UNISTD_H
#include <unistd.h>
#else
extern POINTER_TYPE *sbrk ();
#endif

#ifdef DOUG_LEA_MALLOC

#include <malloc.h>
/* malloc.h #defines this as size_t, at least in glibc2.  */
#ifndef __malloc_size_t

extern __malloc_size_t _bytes_used;
extern __malloc_size_t __malloc_extra_blocks;

#endif /* not DOUG_LEA_MALLOC */

/* Macro to verify that storage intended for Lisp objects is not
   out of range to fit in the space for a pointer.
   ADDRESS is the start of the block, and SIZE
   is the amount of space within which objects can start.  */

#define VALIDATE_LISP_STORAGE(address, size)			\
do								\
  {								\
    Lisp_Object val;						\
    XSETCONS (val, (char *) address + size);		\
    if ((char *) XCONS (val) != (char *) address + size)	\
      {								\
	xfree (address);					\
	memory_full ();						\
      }								\
  } while (0)

/* Value of _bytes_used, when spare_memory was freed.  */

static __malloc_size_t bytes_used_when_full;

/* Mark, unmark, query mark bit of a Lisp string.  S must be a pointer
   to a struct Lisp_String.  */

#define MARK_STRING(S)		((S)->size |= MARKBIT)
#define UNMARK_STRING(S)	((S)->size &= ~MARKBIT)
#define STRING_MARKED_P(S)	((S)->size & MARKBIT)

/* Value is the number of bytes/chars of S, a pointer to a struct
   Lisp_String.  This must be used instead of STRING_BYTES (S) or
   S->size during GC, because S->size contains the mark bit for
   strings.  */

#define GC_STRING_BYTES(S)	(STRING_BYTES (S) & ~MARKBIT)
#define GC_STRING_CHARS(S)	((S)->size & ~MARKBIT)

/* Number of bytes of consing done since the last gc.  */

int consing_since_gc;

EMACS_INT string_chars_consed;
EMACS_INT misc_objects_consed;
EMACS_INT intervals_consed;
EMACS_INT strings_consed;

/* Number of bytes of consing since GC before another GC should be done. */

EMACS_INT gc_cons_threshold;

/* Nonzero during GC.  */

int gc_in_progress;

/* Nonzero means display messages at beginning and end of GC.  */

int garbage_collection_messages;

#ifndef VIRT_ADDR_VARIES
extern
#endif /* VIRT_ADDR_VARIES */
int malloc_sbrk_unused;

/* Two limits controlling how much undo information to keep.  */

EMACS_INT undo_limit;
EMACS_INT undo_strong_limit;

/* Number of live and free conses etc.  */

static int total_conses, total_markers, total_symbols, total_vector_size;
static int total_free_conses, total_free_markers, total_free_symbols;
static int total_free_floats, total_floats;

/* Points to memory space allocated as "spare", to be freed if we run
   out of memory.  */

static char *spare_memory;

/* Amount of spare memory to keep in reserve.  */

#define SPARE_MEMORY (1 << 14)

/* Number of extra blocks malloc should get when it needs more core.  */

Lisp_Object Vmemory_full;

#ifndef HAVE_SHM

/* Force it into data space! */

EMACS_INT pure[PURESIZE / sizeof (EMACS_INT)] = {0,};
#define PUREBEG (char *) pure

#else /* HAVE_SHM */

#define pure PURE_SEG_BITS   /* Use shared memory segment */

Lisp_Object Vgc_elapsed;	/* accumulated elapsed time in GC  */
EMACS_INT gcs_done;		/* accumulated GCs  */

static void mark_buffer P_ ((Lisp_Object));
static void mark_kboards P_ ((void));
static void gc_sweep P_ ((void));
static void mark_glyph_matrix P_ ((struct glyph_matrix *));
static void mark_face_cache P_ ((struct face_cache *));

#ifdef HAVE_WINDOW_SYSTEM
static void mark_image P_ ((struct image *));
static void mark_image_cache P_ ((struct frame *));
#endif /* HAVE_WINDOW_SYSTEM */

static struct Lisp_String *allocate_string P_ ((void));

  MEM_TYPE_PROCESS,
  MEM_TYPE_HASH_TABLE,
  MEM_TYPE_FRAME,
  MEM_TYPE_WINDOW
};

#if GC_MARK_STACK || defined GC_MALLOC_CHECK

#if GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES
#include <stdio.h>		/* For fprintf.  */

static void mem_rotate_right P_ ((struct mem_node *));
static void mem_delete P_ ((struct mem_node *));
static void mem_delete_fixup P_ ((struct mem_node *));
static INLINE struct mem_node *mem_find P_ ((void *));

#if GC_MARK_STACK == GC_MARK_STACK_CHECK_GCPROS
static void check_gcpros P_ ((void));
#endif

#endif /* GC_MARK_STACK || GC_MALLOC_CHECK */

/* Recording what needs to be marked for gc.  */

struct gcpro *gcprolist;

/* Addresses of staticpro'd variables.  */

#define NSTATICS 1280
Lisp_Object *staticvec[NSTATICS] = {0};

/* Index of next unused slot in staticvec.  */

int staticidx = 0;

/* Value is SZ rounded up to the next multiple of ALIGNMENT.
   ALIGNMENT must be a power of 2.  */

#define ALIGN(SZ, ALIGNMENT) \
  (((SZ) + (ALIGNMENT) - 1) & ~((ALIGNMENT) - 1))



/************************************************************************
				Malloc

  pending_malloc_warning = 0;
}


#ifdef DOUG_LEA_MALLOC
#  define BYTES_USED (mallinfo ().arena)
#else
#  define BYTES_USED _bytes_used
#endif


/* Called if malloc returns zero.  */

void
memory_full ()
{
  Vmemory_full = Qt;

#ifndef SYSTEM_MALLOC
  bytes_used_when_full = BYTES_USED;
#endif

  /* The first time we get here, free the spare memory.  */
  if (spare_memory)
    {
      free (spare_memory);
      spare_memory = 0;
    }

  /* This used to call error, but if we've run out of memory, we could
     get infinite recursion trying to build the string.  */
  while (1)
    Fsignal (Qnil, Vmemory_signal_data);
}


/* Called if we can't allocate relocatable space for a buffer.  */

void
buffer_memory_full ()
{

#ifndef REL_ALLOC
  memory_full ();
#endif

  Vmemory_full = Qt;

  /* This used to call error, but if we've run out of memory, we could
     get infinite recursion trying to build the string.  */
  while (1)
    Fsignal (Qnil, Vmemory_signal_data);
}


/* Like malloc but check for no memory and block interrupt input..  */

POINTER_TYPE *

  if (!val && size) memory_full ();
  return val;
}


/* Like free but block interrupt input..  */

void
xfree (block)
     POINTER_TYPE *block;
{
  BLOCK_INPUT;
  free (block);
  UNBLOCK_INPUT;
}


/* Like strdup, but uses xmalloc.  */

  bcopy (s, p, len);
  return p;
}


/* Like malloc but used for allocating Lisp data.  NBYTES is the
   number of bytes to allocate, TYPE describes the intended use of the
   allcated memory block (for strings, for conses, ...).  */

static POINTER_TYPE *
lisp_malloc (nbytes, type)
     size_t nbytes;
     enum mem_type type;

  allocated_mem_type = type;
#endif

  val = (void *) malloc (nbytes);

#if GC_MARK_STACK && !defined GC_MALLOC_CHECK
  if (val && type != MEM_TYPE_NON_LISP)
    mem_insert (val, (char *) val + nbytes, type);
#endif

  if (!val && nbytes)
    memory_full ();
  return val;
}


/* Return a new buffer structure allocated from the heap with
   a call to lisp_malloc.  */

struct buffer *
allocate_buffer ()
{
  struct buffer *b
    = (struct buffer *) lisp_malloc (sizeof (struct buffer),
				     MEM_TYPE_BUFFER);
  VALIDATE_LISP_STORAGE (b, sizeof *b);
  return b;
}


/* Free BLOCK.  This must be called to free memory allocated with a
   call to lisp_malloc.  */

static void
lisp_free (block)

  mem_delete (mem_find (block));
#endif
  UNBLOCK_INPUT;
}


/* Arranging to disable input signals while we're in malloc.

   This only works with GNU malloc.  To help out systems which can't
   use GNU malloc, all the calls to malloc, realloc, and free
   elsewhere in the code should be inside a BLOCK_INPUT/UNBLOCK_INPUT
   pairs; unfortunately, we have no idea what C library functions
   might call malloc, so we can't really protect them unless you're
   using GNU malloc.  Fortunately, most of the major operating systems
   can use GNU malloc.  */

#ifndef SYSTEM_MALLOC
#ifndef DOUG_LEA_MALLOC
extern void * (*__malloc_hook) P_ ((size_t));
extern void * (*__realloc_hook) P_ ((void *, size_t));
extern void (*__free_hook) P_ ((void *));
/* Else declared in malloc.h, perhaps with an extra arg.  */
#endif /* DOUG_LEA_MALLOC */
static void * (*old_malloc_hook) ();
static void * (*old_realloc_hook) ();
static void (*old_free_hook) ();

/* This function is used as the hook for free to call.  */

static void
emacs_blocked_free (ptr)
     void *ptr;
{
  BLOCK_INPUT;

#ifdef GC_MALLOC_CHECK
  if (ptr)
    {
      struct mem_node *m;

  free (ptr);

  /* If we released our reserve (due to running out of memory),
     and we have a fair amount free once again,
     try to set aside another reserve in case we run out once more.  */
  if (spare_memory == 0
      /* Verify there is enough space that even with the malloc
	 hysteresis this call won't run out again.
	 The code here is correct as long as SPARE_MEMORY
	 is substantially larger than the block size malloc uses.  */
      && (bytes_used_when_full
	  > BYTES_USED + max (malloc_hysteresis, 4) * SPARE_MEMORY))
    spare_memory = (char *) malloc ((size_t) SPARE_MEMORY);

  __free_hook = emacs_blocked_free;
  UNBLOCK_INPUT;
}


/* If we released our reserve (due to running out of memory),
   and we have a fair amount free once again,
   try to set aside another reserve in case we run out once more.

   This is called when a relocatable block is freed in ralloc.c.  */

void
refill_memory_reserve ()
{
  if (spare_memory == 0)
    spare_memory = (char *) malloc ((size_t) SPARE_MEMORY);
}


/* This function is the malloc hook that Emacs uses.  */

static void *
emacs_blocked_malloc (size)
     size_t size;
{
  void *value;

  BLOCK_INPUT;
  __malloc_hook = old_malloc_hook;
#ifdef DOUG_LEA_MALLOC
    mallopt (M_TOP_PAD, malloc_hysteresis * 4096);
#else
    __malloc_extra_blocks = malloc_hysteresis;

      }
  }
#endif /* GC_MALLOC_CHECK */

  __malloc_hook = emacs_blocked_malloc;
  UNBLOCK_INPUT;

  /* fprintf (stderr, "%p malloc\n", value); */
  return value;
}


/* This function is the realloc hook that Emacs uses.  */

static void *
emacs_blocked_realloc (ptr, size)
     void *ptr;
     size_t size;
{
  void *value;

  BLOCK_INPUT;
  __realloc_hook = old_realloc_hook;

#ifdef GC_MALLOC_CHECK
  if (ptr)
    {

  /* fprintf (stderr, "%p <- realloc\n", value); */
#endif /* GC_MALLOC_CHECK */

  __realloc_hook = emacs_blocked_realloc;
  UNBLOCK_INPUT;

  return value;
}


/* Called from main to set up malloc to use our hooks.  */

void
uninterrupt_malloc ()
{
  if (__free_hook != emacs_blocked_free)
    old_free_hook = __free_hook;
  __free_hook = emacs_blocked_free;

  if (__malloc_hook != emacs_blocked_malloc)

  if (__realloc_hook != emacs_blocked_realloc)
    old_realloc_hook = __realloc_hook;
  __realloc_hook = emacs_blocked_realloc;
}

#endif /* not SYSTEM_MALLOC */



/***********************************************************************

/* Intervals are allocated in chunks in form of an interval_block
   structure.  */

struct interval_block
{
  struct interval_block *next;
  struct interval intervals[INTERVAL_BLOCK_SIZE];
};

/* Current interval block.  Its `next' pointer points to older
   blocks.  */

/* Initialize interval allocation.  */

static void
init_intervals ()
{
  interval_block
    = (struct interval_block *) lisp_malloc (sizeof *interval_block,
					     MEM_TYPE_NON_LISP);
  interval_block->next = 0;
  bzero ((char *) interval_block->intervals, sizeof interval_block->intervals);
  interval_block_index = 0;
  interval_free_list = 0;
  n_interval_blocks = 1;
}


/* Return a new interval.  */

	  register struct interval_block *newi;

	  newi = (struct interval_block *) lisp_malloc (sizeof *newi,
							MEM_TYPE_NON_LISP);

	  VALIDATE_LISP_STORAGE (newi, sizeof *newi);
	  newi->next = interval_block;
	  interval_block = newi;
	  interval_block_index = 0;
	  n_interval_blocks++;
	}
      val = &interval_block->intervals[interval_block_index++];
    }
  consing_since_gc += sizeof (struct interval);
  intervals_consed++;
  RESET_INTERVAL (val);
  return val;
}


/* Mark Lisp objects in interval I. */

static void
mark_interval (i, dummy)
     register INTERVAL i;
     Lisp_Object dummy;
{
  if (XMARKBIT (i->plist))
    abort ();
  mark_object (&i->plist);
  XMARK (i->plist);
}


/* Mark the interval tree rooted in TREE.  Don't call this directly;
   use the macro MARK_INTERVAL_TREE instead.  */

{
  /* No need to test if this tree has been marked already; this
     function is always called through the MARK_INTERVAL_TREE macro,
     which takes care of that.  */

  /* XMARK expands to an assignment; the LHS of an assignment can't be
     a cast.  */
  XMARK (tree->up.obj);

  traverse_intervals_noorder (tree, mark_interval, Qnil);
}


/* Mark the interval tree rooted in I.  */

#define MARK_INTERVAL_TREE(i)				\
  do {							\
    if (!NULL_INTERVAL_P (i)				\
	&& ! XMARKBIT (i->up.obj))			\
      mark_interval_tree (i);				\
  } while (0)


/* The oddity in the call to XUNMARK is necessary because XUNMARK
   expands to an assignment to its argument, and most C compilers
   don't support casts on the left operand of `='.  */

#define UNMARK_BALANCE_INTERVALS(i)			\
  do {							\
   if (! NULL_INTERVAL_P (i))				\
     {							\
       XUNMARK ((i)->up.obj);				\
       (i) = balance_intervals (i);			\
     }							\
  } while (0)


/* Number support.  If NO_UNION_TYPE isn't in effect, we
   can't create number objects in macros.  */
#ifndef make_number
Lisp_Object
make_number (n)
     int n;
{
  Lisp_Object obj;
  obj.s.val = n;
  obj.s.type = Lisp_Int;
  return obj;

};

/* Number of Lisp strings in a string_block structure.  The 1020 is
   1024 minus malloc overhead.  */

#define STRINGS_IN_STRING_BLOCK \
  ((1020 - sizeof (struct string_block *)) / sizeof (struct Lisp_String))

/* Structure describing a block from which Lisp_String structures
   are allocated.  */

struct string_block
{
  struct string_block *next;
  struct Lisp_String strings[STRINGS_IN_STRING_BLOCK];
};

/* Head and tail of the list of sblock structures holding Lisp string
   data.  We always allocate from current_sblock.  The NEXT pointers
   in the sblock structures go from oldest_sblock to current_sblock.  */

#define SDATA_OF_STRING(S) \
     ((struct sdata *) ((S)->data - sizeof (struct Lisp_String *)))

#endif /* not GC_CHECK_STRING_BYTES */

/* Value is the size of an sdata structure large enough to hold NBYTES
   bytes of string data.  The value returned includes a terminating
   NUL byte, the size of the sdata structure, and padding.  */

       + sizeof (EMACS_INT) - 1)		\
      & ~(sizeof (EMACS_INT) - 1))

#endif /* not GC_CHECK_STRING_BYTES */

/* Initialize string allocation.  Called from init_alloc_once.  */

void
init_strings ()
{

int
string_bytes (s)
     struct Lisp_String *s;
{
  int nbytes = (s->size_byte < 0 ? s->size : s->size_byte) & ~MARKBIT;
  if (!PURE_POINTER_P (s)
      && s->data
      && nbytes != SDATA_NBYTES (SDATA_OF_STRING (s)))
    abort ();
  return nbytes;

	nbytes = GC_STRING_BYTES (from->string);
      else
	nbytes = SDATA_NBYTES (from);

      nbytes = SDATA_SIZE (nbytes);
      from_end = (struct sdata *) ((char *) from + nbytes);
    }
}


/* Check validity of Lisp strings' string_bytes member.  ALL_P

    check_sblock (current_sblock);
}

#endif /* GC_CHECK_STRING_BYTES */


/* Return a new Lisp_String.  */

static struct Lisp_String *
allocate_string ()

    {
      struct string_block *b;
      int i;

      b = (struct string_block *) lisp_malloc (sizeof *b, MEM_TYPE_STRING);
      VALIDATE_LISP_STORAGE (b, sizeof *b);
      bzero (b, sizeof *b);
      b->next = string_blocks;
      string_blocks = b;
      ++n_string_blocks;

      for (i = STRINGS_IN_STRING_BLOCK - 1; i >= 0; --i)
	{
	  s = b->strings + i;
	  NEXT_FREE_LISP_STRING (s) = string_free_list;
	  string_free_list = s;
	}

      total_free_strings += STRINGS_IN_STRING_BLOCK;
    }

  /* Pop a Lisp_String off the free-list.  */
  s = string_free_list;
  string_free_list = NEXT_FREE_LISP_STRING (s);

      size_t size = sizeof *b - sizeof (struct sdata) + needed;

#ifdef DOUG_LEA_MALLOC
      /* Prevent mmap'ing the chunk.  Lisp data may not be mmap'ed
	 because mapped region contents are not preserved in
	 a dumped Emacs.  */
      mallopt (M_MMAP_MAX, 0);
#endif

      b = (struct sblock *) lisp_malloc (size, MEM_TYPE_NON_LISP);

#ifdef DOUG_LEA_MALLOC
      /* Back to a reasonable maximum of mmap'ed areas. */
      mallopt (M_MMAP_MAX, MMAP_MAX_AREAS);
#endif

      b->next_free = &b->first_data;
      b->first_data.string = NULL;
      b->next = large_sblocks;
      large_sblocks = b;
    }
  else if (current_sblock == NULL
	   || (((char *) current_sblock + SBLOCK_SIZE
		- (char *) current_sblock->next_free)
	       < needed))
    {
      /* Not enough room in the current sblock.  */
      b = (struct sblock *) lisp_malloc (SBLOCK_SIZE, MEM_TYPE_NON_LISP);
      b->next_free = &b->first_data;
      b->first_data.string = NULL;

  SDATA_NBYTES (data) = nbytes;
#endif
  s->size = nchars;
  s->size_byte = nbytes;
  s->data[nbytes] = '\0';
  b->next_free = (struct sdata *) ((char *) data + needed);

  /* If S had already data assigned, mark that as free by setting its
     string back-pointer to null, and recording the size of the data
     in it.  */
  if (old_data)

      int i, nfree = 0;
      struct Lisp_String *free_list_before = string_free_list;

      next = b->next;

      for (i = 0; i < STRINGS_IN_STRING_BLOCK; ++i)
	{
	  struct Lisp_String *s = b->strings + i;

	  if (s->data)
	    {

	    }
	}

      /* Free blocks that contain free Lisp_Strings only, except
	 the first two of them.  */
      if (nfree == STRINGS_IN_STRING_BLOCK
	  && total_free_strings > STRINGS_IN_STRING_BLOCK)
	{
	  lisp_free (b);
	  --n_string_blocks;
	  string_free_list = free_list_before;
	}

	  b->next = live_blocks;
	  live_blocks = b;
	}
    }

  string_blocks = live_blocks;
  free_large_strings ();
  compact_small_strings ();
}


/* Free dead large strings.  */

	  if (from->string)
	    nbytes = GC_STRING_BYTES (from->string);
	  else
	    nbytes = SDATA_NBYTES (from);

	  nbytes = SDATA_SIZE (nbytes);
	  from_end = (struct sdata *) ((char *) from + nbytes);

	  /* FROM->string non-null means it's alive.  Copy its data.  */
	  if (from->string)
	    {
	      /* If TB is full, proceed with the next sblock.  */
	      to_end = (struct sdata *) ((char *) to + nbytes);
	      if (to_end > tb_end)
		{
		  tb->next_free = to;
		  tb = tb->next;
		  tb_end = (struct sdata *) ((char *) tb + SBLOCK_SIZE);
		  to = &tb->first_data;
		  to_end = (struct sdata *) ((char *) to + nbytes);
		}

	      /* Copy, and update the string's `data' pointer.  */
	      if (from != to)
		{
		  xassert (tb != b || to <= from);
		  safe_bcopy ((char *) from, (char *) to, nbytes);
		  to->string->data = SDATA_DATA (to);
		}

	      /* Advance past the sdata we copied to.  */
	      to = to_end;

  current_sblock = tb;
}


DEFUN ("make-string", Fmake_string, Smake_string, 2, 2, 0,
       doc: /* Return a newly created string of length LENGTH, with each element being INIT.
Both LENGTH and INIT must be numbers.  */)
     (length, init)
     Lisp_Object length, init;
{
  register Lisp_Object val;
  register unsigned char *p, *end;

  int real_init, i;
  int length_in_chars, length_in_elts, bits_per_value;

  CHECK_NATNUM (length);

  bits_per_value = sizeof (EMACS_INT) * BITS_PER_CHAR;

  length_in_elts = (XFASTINT (length) + bits_per_value - 1) / bits_per_value;
  length_in_chars = ((XFASTINT (length) + BITS_PER_CHAR - 1) / BITS_PER_CHAR);

  /* We must allocate one more elements than LENGTH_IN_ELTS for the
     slot `size' of the struct Lisp_Bool_Vector.  */
  val = Fmake_vector (make_number (length_in_elts + 1), Qnil);
  p = XBOOL_VECTOR (val);

  real_init = (NILP (init) ? 0 : -1);
  for (i = 0; i < length_in_chars ; i++)
    p->data[i] = real_init;

  /* Clear the extraneous bits in the last byte.  */
  if (XINT (length) != length_in_chars * BITS_PER_CHAR)
    XBOOL_VECTOR (val)->data[length_in_chars - 1]
      &= (1 << (XINT (length) % BITS_PER_CHAR)) - 1;

  return val;
}

/* Make a string from NCHARS characters occupying NBYTES bytes at
   CONTENTS.  It is a multibyte string if NBYTES != NCHARS.  */

Lisp_Object
make_string_from_bytes (contents, nchars, nbytes)
     char *contents;
     int nchars, nbytes;
{
  register Lisp_Object val;
  val = make_uninit_multibyte_string (nchars, nbytes);
  bcopy (contents, SDATA (val), nbytes);

}


/* Make a string from NCHARS characters occupying NBYTES bytes at
   CONTENTS.  The argument MULTIBYTE controls whether to label the
   string as multibyte.  */

Lisp_Object
make_specified_string (contents, nchars, nbytes, multibyte)
     char *contents;
     int nchars, nbytes;
     int multibyte;
{
  register Lisp_Object val;
  val = make_uninit_multibyte_string (nchars, nbytes);
  bcopy (contents, SDATA (val), nbytes);
  if (!multibyte)
    STRING_SET_UNIBYTE (val);
  return val;

 ***********************************************************************/

/* We store float cells inside of float_blocks, allocating a new
   float_block with malloc whenever necessary.  Float cells reclaimed
   by GC are put on a free list to be reallocated before allocating
   any new float cells from the latest float_block.

   Each float_block is just under 1020 bytes long, since malloc really
   allocates in units of powers of two and uses 4 bytes for its own
   overhead. */

#define FLOAT_BLOCK_SIZE \
  ((1020 - sizeof (struct float_block *)) / sizeof (struct Lisp_Float))

struct float_block
{
  struct float_block *next;
  struct Lisp_Float floats[FLOAT_BLOCK_SIZE];
};

/* Current float_block.  */

struct float_block *float_block;

/* Initialize float allocation.  */

void
init_float ()
{
  float_block = (struct float_block *) lisp_malloc (sizeof *float_block,
						    MEM_TYPE_FLOAT);
  float_block->next = 0;
  bzero ((char *) float_block->floats, sizeof float_block->floats);
  float_block_index = 0;
  float_free_list = 0;
  n_float_blocks = 1;
}


/* Explicitly free a float cell by putting it on the free-list.  */

void
free_float (ptr)
     struct Lisp_Float *ptr;
{
  *(struct Lisp_Float **)&ptr->data = float_free_list;
#if GC_MARK_STACK
  ptr->type = Vdead;
#endif
  float_free_list = ptr;
}


/* Return a new float object with value FLOAT_VALUE.  */

  if (float_free_list)
    {
      /* We use the data field for chaining the free list
	 so that we won't use the same field that has the mark bit.  */
      XSETFLOAT (val, float_free_list);
      float_free_list = *(struct Lisp_Float **)&float_free_list->data;
    }
  else
    {
      if (float_block_index == FLOAT_BLOCK_SIZE)
	{
	  register struct float_block *new;

	  new = (struct float_block *) lisp_malloc (sizeof *new,
						    MEM_TYPE_FLOAT);
	  VALIDATE_LISP_STORAGE (new, sizeof *new);
	  new->next = float_block;
	  float_block = new;
	  float_block_index = 0;
	  n_float_blocks++;
	}
      XSETFLOAT (val, &float_block->floats[float_block_index++]);
    }

  XFLOAT_DATA (val) = float_value;
  XSETFASTINT (XFLOAT (val)->type, 0);	/* bug chasing -wsr */
  consing_since_gc += sizeof (struct Lisp_Float);
  floats_consed++;
  return val;
}

 ***********************************************************************/

/* We store cons cells inside of cons_blocks, allocating a new
   cons_block with malloc whenever necessary.  Cons cells reclaimed by
   GC are put on a free list to be reallocated before allocating
   any new cons cells from the latest cons_block.

   Each cons_block is just under 1020 bytes long,
   since malloc really allocates in units of powers of two
   and uses 4 bytes for its own overhead. */

#define CONS_BLOCK_SIZE \
  ((1020 - sizeof (struct cons_block *)) / sizeof (struct Lisp_Cons))

struct cons_block
{
  struct cons_block *next;
  struct Lisp_Cons conses[CONS_BLOCK_SIZE];
};

/* Current cons_block.  */

struct cons_block *cons_block;

/* Initialize cons allocation.  */

void
init_cons ()
{
  cons_block = (struct cons_block *) lisp_malloc (sizeof *cons_block,
						  MEM_TYPE_CONS);
  cons_block->next = 0;
  bzero ((char *) cons_block->conses, sizeof cons_block->conses);
  cons_block_index = 0;
  cons_free_list = 0;
  n_cons_blocks = 1;
}


/* Explicitly free a cons cell by putting it on the free-list.  */

void
free_cons (ptr)
     struct Lisp_Cons *ptr;
{
  *(struct Lisp_Cons **)&ptr->cdr = cons_free_list;
#if GC_MARK_STACK
  ptr->car = Vdead;
#endif
  cons_free_list = ptr;
}


DEFUN ("cons", Fcons, Scons, 2, 2, 0,
       doc: /* Create a new cons, give it CAR and CDR as components, and return it.  */)
     (car, cdr)
     Lisp_Object car, cdr;

  if (cons_free_list)
    {
      /* We use the cdr for chaining the free list
	 so that we won't use the same field that has the mark bit.  */
      XSETCONS (val, cons_free_list);
      cons_free_list = *(struct Lisp_Cons **)&cons_free_list->cdr;
    }
  else
    {
      if (cons_block_index == CONS_BLOCK_SIZE)
	{
	  register struct cons_block *new;
	  new = (struct cons_block *) lisp_malloc (sizeof *new,
						   MEM_TYPE_CONS);
	  VALIDATE_LISP_STORAGE (new, sizeof *new);
	  new->next = cons_block;
	  cons_block = new;
	  cons_block_index = 0;
	  n_cons_blocks++;
	}
      XSETCONS (val, &cons_block->conses[cons_block_index++]);
    }

  XSETCAR (val, car);
  XSETCDR (val, cdr);
  consing_since_gc += sizeof (struct Lisp_Cons);
  cons_cells_consed++;
  return val;
}


/* Make a list of 2, 3, 4 or 5 specified objects.  */

Lisp_Object
list2 (arg1, arg2)

#ifdef DOUG_LEA_MALLOC
  /* Prevent mmap'ing the chunk.  Lisp data may not be mmap'ed
     because mapped region contents are not preserved in
     a dumped Emacs.  */
  mallopt (M_MMAP_MAX, 0);
#endif

  nbytes = sizeof *p + (len - 1) * sizeof p->contents[0];
  p = (struct Lisp_Vector *) lisp_malloc (nbytes, type);

#ifdef DOUG_LEA_MALLOC
  /* Back to a reasonable maximum of mmap'ed areas.  */
  mallopt (M_MMAP_MAX, MMAP_MAX_AREAS);
#endif

  VALIDATE_LISP_STORAGE (p, 0);
  consing_since_gc += nbytes;
  vector_cells_consed += len;

  p->next = all_vectors;
  all_vectors = p;

  XSETCHAR_TABLE (vector, XCHAR_TABLE (vector));
  return vector;
}


/* Return a newly created sub char table with default value DEFALT.
   Since a sub char table does not appear as a top level Emacs Lisp
   object, we don't need a Lisp interface to make it.  */

Lisp_Object
make_sub_char_table (defalt)
     Lisp_Object defalt;
{
  Lisp_Object vector
    = Fmake_vector (make_number (SUB_CHAR_TABLE_STANDARD_SLOTS), Qnil);
  XCHAR_TABLE (vector)->top = Qnil;
  XCHAR_TABLE (vector)->defalt = defalt;
  XSETCHAR_TABLE (vector, XCHAR_TABLE (vector));
  return vector;
}

       doc: /* Create a byte-code object with specified arguments as elements.
The arguments should be the arglist, bytecode-string, constant vector,
stack size, (optional) doc string, and (optional) interactive spec.
The first four arguments are required; at most six have any
significance.
usage: (make-byte-code &rest ELEMENTS)  */)
     (nargs, args)
     register int nargs;
     Lisp_Object *args;
{
  register Lisp_Object len, val;

#define SYMBOL_BLOCK_SIZE \
  ((1020 - sizeof (struct symbol_block *)) / sizeof (struct Lisp_Symbol))

struct symbol_block
{
  struct symbol_block *next;
  struct Lisp_Symbol symbols[SYMBOL_BLOCK_SIZE];
};

/* Current symbol block and index of first unused Lisp_Symbol
   structure in it.  */

/* Initialize symbol allocation.  */

void
init_symbol ()
{
  symbol_block = (struct symbol_block *) lisp_malloc (sizeof *symbol_block,
						      MEM_TYPE_SYMBOL);
  symbol_block->next = 0;
  bzero ((char *) symbol_block->symbols, sizeof symbol_block->symbols);
  symbol_block_index = 0;
  symbol_free_list = 0;
  n_symbol_blocks = 1;
}


DEFUN ("make-symbol", Fmake_symbol, Smake_symbol, 1, 1, 0,
       doc: /* Return a newly allocated uninterned symbol whose name is NAME.

  CHECK_STRING (name);

  if (symbol_free_list)
    {
      XSETSYMBOL (val, symbol_free_list);
      symbol_free_list = *(struct Lisp_Symbol **)&symbol_free_list->value;
    }
  else
    {
      if (symbol_block_index == SYMBOL_BLOCK_SIZE)
	{
	  struct symbol_block *new;
	  new = (struct symbol_block *) lisp_malloc (sizeof *new,
						     MEM_TYPE_SYMBOL);
	  VALIDATE_LISP_STORAGE (new, sizeof *new);
	  new->next = symbol_block;
	  symbol_block = new;
	  symbol_block_index = 0;
	  n_symbol_blocks++;
	}
      XSETSYMBOL (val, &symbol_block->symbols[symbol_block_index++]);
    }

  p = XSYMBOL (val);
  p->xname = name;
  p->plist = Qnil;
  p->value = Qunbound;
  p->function = Qunbound;
  p->next = NULL;
  p->interned = SYMBOL_UNINTERNED;
  p->constant = 0;
  p->indirect_variable = 0;
  consing_since_gc += sizeof (struct Lisp_Symbol);
  symbols_consed++;

#define MARKER_BLOCK_SIZE \
  ((1020 - sizeof (struct marker_block *)) / sizeof (union Lisp_Misc))

struct marker_block
{
  struct marker_block *next;
  union Lisp_Misc markers[MARKER_BLOCK_SIZE];
};

struct marker_block *marker_block;
int marker_block_index;

int n_marker_blocks;

void
init_marker ()
{
  marker_block = (struct marker_block *) lisp_malloc (sizeof *marker_block,
						      MEM_TYPE_MISC);
  marker_block->next = 0;
  bzero ((char *) marker_block->markers, sizeof marker_block->markers);
  marker_block_index = 0;
  marker_free_list = 0;
  n_marker_blocks = 1;
}

/* Return a newly allocated Lisp_Misc object, with no substructure.  */

Lisp_Object

      if (marker_block_index == MARKER_BLOCK_SIZE)
	{
	  struct marker_block *new;
	  new = (struct marker_block *) lisp_malloc (sizeof *new,
						     MEM_TYPE_MISC);
	  VALIDATE_LISP_STORAGE (new, sizeof *new);
	  new->next = marker_block;
	  marker_block = new;
	  marker_block_index = 0;
	  n_marker_blocks++;
	}
      XSETMISC (val, &marker_block->markers[marker_block_index++]);
    }

  consing_since_gc += sizeof (union Lisp_Misc);
  misc_objects_consed++;
  return val;
}

/* Return a Lisp_Misc_Save_Value object containing POINTER and
   INTEGER.  This is used to package C values to call record_unwind_protect.
   The unwind function can get the C values back using XSAVE_VALUE.  */

  val = allocate_misc ();
  XMISCTYPE (val) = Lisp_Misc_Save_Value;
  p = XSAVE_VALUE (val);
  p->pointer = pointer;
  p->integer = integer;
  return val;
}

DEFUN ("make-marker", Fmake_marker, Smake_marker, 0, 0, 0,
       doc: /* Return a newly allocated marker which does not point at any place.  */)

  XMISCTYPE (val) = Lisp_Misc_Marker;
  p = XMARKER (val);
  p->buffer = 0;
  p->bytepos = 0;
  p->charpos = 0;
  p->chain = Qnil;
  p->insertion_type = 0;
  return val;
}

/* Put MARKER back on the free list after using it temporarily.  */

void
free_marker (marker)
     Lisp_Object marker;
{
  unchain_marker (marker);

  XMISC (marker)->u_marker.type = Lisp_Misc_Free;
  XMISC (marker)->u_free.chain = marker_free_list;
  marker_free_list = XMISC (marker);

  total_free_markers++;
}


/* Return a newly created vector or string with specified arguments as
   elements.  If all the arguments are characters that can fit

    return result;
  }
}



/************************************************************************
			   C Stack Marking
 ************************************************************************/

      /* P must point to the start of a Lisp_String structure, and it
	 must not be on the free-list.  */
      return (offset >= 0
	      && offset % sizeof b->strings[0] == 0
	      && ((struct Lisp_String *) p)->data != NULL);
    }
  else
    return 0;
}

      /* P must point to the start of a Lisp_Cons, not be
	 one of the unused cells in the current cons block,
	 and not be on the free-list.  */
      return (offset >= 0
	      && offset % sizeof b->conses[0] == 0
	      && (b != cons_block
		  || offset / sizeof b->conses[0] < cons_block_index)
	      && !EQ (((struct Lisp_Cons *) p)->car, Vdead));
    }
  else

      /* P must point to the start of a Lisp_Symbol, not be
	 one of the unused cells in the current symbol block,
	 and not be on the free-list.  */
      return (offset >= 0
	      && offset % sizeof b->symbols[0] == 0
	      && (b != symbol_block
		  || offset / sizeof b->symbols[0] < symbol_block_index)
	      && !EQ (((struct Lisp_Symbol *) p)->function, Vdead));
    }
  else

  if (m->type == MEM_TYPE_FLOAT)
    {
      struct float_block *b = (struct float_block *) m->start;
      int offset = (char *) p - (char *) &b->floats[0];

      /* P must point to the start of a Lisp_Float, not be
	 one of the unused cells in the current float block,
	 and not be on the free-list.  */
      return (offset >= 0
	      && offset % sizeof b->floats[0] == 0
	      && (b != float_block
		  || offset / sizeof b->floats[0] < float_block_index)
	      && !EQ (((struct Lisp_Float *) p)->type, Vdead));
    }
  else
    return 0;
}

      /* P must point to the start of a Lisp_Misc, not be
	 one of the unused cells in the current misc block,
	 and not be on the free-list.  */
      return (offset >= 0
	      && offset % sizeof b->markers[0] == 0
	      && (b != marker_block
		  || offset / sizeof b->markers[0] < marker_block_index)
	      && ((union Lisp_Misc *) p)->u_marker.type != Lisp_Misc_Free);
    }
  else

	  && m->type >= MEM_TYPE_VECTOR
	  && m->type <= MEM_TYPE_WINDOW);
}


/* Value is non-zero of P is a pointer to a live buffer.  M is a
   pointer to the mem_block for P.  */

static INLINE int
live_buffer_p (m, p)
     struct mem_node *m;

	  mark_p = (live_string_p (m, po)
		    && !STRING_MARKED_P ((struct Lisp_String *) po));
	  break;

	case Lisp_Cons:
	  mark_p = (live_cons_p (m, po)
		    && !XMARKBIT (XCONS (obj)->car));
	  break;

	case Lisp_Symbol:
	  mark_p = (live_symbol_p (m, po)
		    && !XMARKBIT (XSYMBOL (obj)->plist));
	  break;

	case Lisp_Float:
	  mark_p = (live_float_p (m, po)
		    && !XMARKBIT (XFLOAT (obj)->type));
	  break;

	case Lisp_Vectorlike:
	  /* Note: can't check GC_BUFFERP before we know it's a
	     buffer because checking that dereferences the pointer
	     PO which might point anywhere.  */
	  if (live_vector_p (m, po))
	    mark_p = (!GC_SUBRP (obj)
		      && !(XVECTOR (obj)->size & ARRAY_MARK_FLAG));
	  else if (live_buffer_p (m, po))
	    mark_p = GC_BUFFERP (obj) && !XMARKBIT (XBUFFER (obj)->name);
	  break;

	case Lisp_Misc:
	  if (live_misc_p (m, po))
	    {
	      switch (XMISCTYPE (obj))
		{
		case Lisp_Misc_Marker:
		  mark_p = !XMARKBIT (XMARKER (obj)->chain);
		  break;

		case Lisp_Misc_Buffer_Local_Value:
		case Lisp_Misc_Some_Buffer_Local_Value:
		  mark_p = !XMARKBIT (XBUFFER_LOCAL_VALUE (obj)->realvalue);
		  break;

		case Lisp_Misc_Overlay:
		  mark_p = !XMARKBIT (XOVERLAY (obj)->plist);
		  break;
		}
	    }
	  break;

	case Lisp_Int:
	case Lisp_Type_Limit:
	  break;

#if GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES
	  if (nzombies < MAX_ZOMBIES)
	    zombies[nzombies] = obj;
	  ++nzombies;
#endif
	  mark_object (&obj);
	}
    }
}

	case MEM_TYPE_NON_LISP:
	  /* Nothing to do; not a pointer to Lisp memory.  */
	  break;

	case MEM_TYPE_BUFFER:
	  if (live_buffer_p (m, p)
	      && !XMARKBIT (((struct buffer *) p)->name))
	    XSETVECTOR (obj, p);
	  break;

	case MEM_TYPE_CONS:
	  if (live_cons_p (m, p)
	      && !XMARKBIT (((struct Lisp_Cons *) p)->car))
	    XSETCONS (obj, p);
	  break;

	case MEM_TYPE_STRING:
	  if (live_string_p (m, p)
	      && !STRING_MARKED_P ((struct Lisp_String *) p))
	    XSETSTRING (obj, p);
	  break;

	case MEM_TYPE_MISC:
	  if (live_misc_p (m, p))
	    {
	      Lisp_Object tem;
	      XSETMISC (tem, p);

	      switch (XMISCTYPE (tem))
		{
		case Lisp_Misc_Marker:
		  if (!XMARKBIT (XMARKER (tem)->chain))
		    obj = tem;
		  break;

		case Lisp_Misc_Buffer_Local_Value:
		case Lisp_Misc_Some_Buffer_Local_Value:
		  if (!XMARKBIT (XBUFFER_LOCAL_VALUE (tem)->realvalue))
		    obj = tem;
		  break;

		case Lisp_Misc_Overlay:
		  if (!XMARKBIT (XOVERLAY (tem)->plist))
		    obj = tem;
		  break;
		}
	    }
	  break;

	case MEM_TYPE_SYMBOL:
	  if (live_symbol_p (m, p)
	      && !XMARKBIT (((struct Lisp_Symbol *) p)->plist))
	    XSETSYMBOL (obj, p);
	  break;

	case MEM_TYPE_FLOAT:
	  if (live_float_p (m, p)
	      && !XMARKBIT (((struct Lisp_Float *) p)->type))
	    XSETFLOAT (obj, p);
	  break;

	case MEM_TYPE_VECTOR:
	case MEM_TYPE_PROCESS:

	case MEM_TYPE_WINDOW:
	  if (live_vector_p (m, p))
	    {
	      Lisp_Object tem;
	      XSETVECTOR (tem, p);
	      if (!GC_SUBRP (tem)
		  && !(XVECTOR (tem)->size & ARRAY_MARK_FLAG))
		obj = tem;
	    }
	  break;

	default:
	  abort ();
	}

      if (!GC_NILP (obj))
	mark_object (&obj);
    }
}


/* Mark Lisp objects referenced from the address range START..END.  */

  int i;

  for (p = gcprolist; p; p = p->next)
    for (i = 0; i < p->nvars; ++i)
      if (!survives_gc_p (p->var[i]))
	abort ();
}

#elif GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES

  volatile int stack_grows_down_p = (char *) &j > (char *) stack_base;
  void *end;

  /* This trick flushes the register windows so that all the state of
     the process is contained in the stack.  */
  /* Fixme: Code in the Boehm GC sugests flushing (with `flushrs') is
     needed on ia64 too.  See mach_dep.c, where it also says inline
     assembler doesn't work with relevant proprietary compilers.  */
#ifdef sparc
  asm ("ta 3");
#endif

#define GC_LISP_OBJECT_ALIGNMENT sizeof (Lisp_Object)
#endif
#endif
  for (i = 0; i < sizeof (Lisp_Object); i += GC_LISP_OBJECT_ALIGNMENT)
    mark_memory ((char *) stack_base + i, end);

#if GC_MARK_STACK == GC_MARK_STACK_CHECK_GCPROS
  check_gcpros ();
#endif
}


#endif /* GC_MARK_STACK != 0 */



/***********************************************************************
		       Pure Storage Management

pure_alloc (size, type)
     size_t size;
     int type;
{
  POINTER_TYPE *result;
  size_t alignment = sizeof (EMACS_INT);

  /* Give Lisp_Floats an extra alignment.  */
  if (type == Lisp_Float)
    {

      alignment = __alignof (struct Lisp_Float);
#else
      alignment = sizeof (struct Lisp_Float);
#endif
    }

 again:
  result = (POINTER_TYPE *) ALIGN ((EMACS_UINT)purebeg + pure_bytes_used, alignment);
  pure_bytes_used = ((char *)result - (char *)purebeg) + size;

  if (pure_bytes_used <= pure_size)
    return result;

			     SBYTES (obj),
			     STRING_MULTIBYTE (obj));
  else if (COMPILEDP (obj) || VECTORP (obj))
    {
      register struct Lisp_Vector *vec;
      register int i, size;

      size = XVECTOR (obj)->size;
      if (size & PSEUDOVECTOR_FLAG)
	size &= PSEUDOVECTOR_SIZE_MASK;
      vec = XVECTOR (make_pure_vector ((EMACS_INT) size));
      for (i = 0; i < size; i++)
	vec->contents[i] = Fpurecopy (XVECTOR (obj)->contents[i]);
      if (COMPILEDP (obj))
	XSETCOMPILED (obj, vec);
      else

    Lisp_Object tag;
    Lisp_Object val;
    struct catchtag *next;
};

struct backtrace
{
  struct backtrace *next;
  Lisp_Object *function;
  Lisp_Object *args;	/* Points to vector of args.  */
  int nargs;		/* Length of vector.  */
  /* If nargs is UNEVALLED, args points to slot holding list of
     unevalled args.  */
  char evalargs;
};



/***********************************************************************
			  Protection from GC
 ***********************************************************************/

}


DEFUN ("garbage-collect", Fgarbage_collect, Sgarbage_collect, 0, 0, "",
       doc: /* Reclaim storage for Lisp objects no longer needed.
Returns info on amount of space in use:
 ((USED-CONSES . FREE-CONSES) (USED-SYMS . FREE-SYMS)
  (USED-MARKERS . FREE-MARKERS) USED-STRING-CHARS USED-VECTOR-SLOTS
  (USED-FLOATS . FREE-FLOATS) (USED-INTERVALS . FREE-INTERVALS)
  (USED-STRINGS . FREE-STRINGS))
Garbage collection happens automatically if you cons more than
`gc-cons-threshold' bytes of Lisp data since previous garbage collection.  */)
     ()
{
  register struct gcpro *tail;
  register struct specbinding *bind;
  struct catchtag *catch;
  struct handler *handler;
  register struct backtrace *backlist;
  char stack_top_variable;
  register int i;
  int message_p;
  Lisp_Object total[8];
  int count = SPECPDL_INDEX ();
  EMACS_TIME t1, t2, t3;

  EMACS_GET_TIME (t1);

  /* Can't GC if pure storage overflowed because we can't determine
     if something is a pure object or not.  */
  if (pure_bytes_used_before_overflow)
    return Qnil;

  /* In case user calls debug_print during GC,
     don't let that cause a recursive GC.  */
  consing_since_gc = 0;

  BLOCK_INPUT;

  shrink_regexp_cache ();

  /* Don't keep undo information around forever.  */
  {
    register struct buffer *nextb = all_buffers;

    while (nextb)
      {
	/* If a buffer's undo list is Qt, that means that undo is
	   turned off in that buffer.  Calling truncate_undo_list on
	   Qt tends to return NULL, which effectively turns undo back on.
	   So don't call truncate_undo_list if undo_list is Qt.  */
	if (! EQ (nextb->undo_list, Qt))
	  nextb->undo_list
	    = truncate_undo_list (nextb->undo_list, undo_limit,
				  undo_strong_limit);

	/* Shrink buffer gaps, but skip indirect and dead buffers.  */
	if (nextb->base_buffer == 0 && !NILP (nextb->name))
	  {
	    /* If a buffer's gap size is more than 10% of the buffer
	       size, or larger than 2000 bytes, then shrink it
	       accordingly.  Keep a minimum size of 20 bytes.  */
	    int size = min (2000, max (20, (nextb->text->z_byte / 10)));

	    if (nextb->text->gap_size > size)
	      {
		struct buffer *save_current = current_buffer;
		current_buffer = nextb;
		make_gap (-(nextb->text->gap_size - size));
		current_buffer = save_current;
	      }
	  }

	nextb = nextb->next;
      }
  }

  gc_in_progress = 1;

  /* clear_marks (); */

  /* Mark all the special slots that serve as the roots of accessibility.

     Usually the special slots to mark are contained in particular structures.
     Then we know no slot is marked twice because the structures don't overlap.
     In some cases, the structures point to the slots to be marked.
     For these, we use MARKBIT to avoid double marking of the slot.  */

  for (i = 0; i < staticidx; i++)
    mark_object (staticvec[i]);

#if (GC_MARK_STACK == GC_MAKE_GCPROS_NOOPS \
     || GC_MARK_STACK == GC_MARK_STACK_CHECK_GCPROS)
  mark_stack ();
#else
  for (tail = gcprolist; tail; tail = tail->next)
    for (i = 0; i < tail->nvars; i++)
      if (!XMARKBIT (tail->var[i]))
	{
	  /* Explicit casting prevents compiler warning about
	     discarding the `volatile' qualifier.  */
	  mark_object ((Lisp_Object *)&tail->var[i]);
	  XMARK (tail->var[i]);
	}
#endif

  mark_byte_stack ();
  for (bind = specpdl; bind != specpdl_ptr; bind++)
    {
      mark_object (&bind->symbol);
      mark_object (&bind->old_value);
    }
  for (catch = catchlist; catch; catch = catch->next)
    {
      mark_object (&catch->tag);
      mark_object (&catch->val);
    }
  for (handler = handlerlist; handler; handler = handler->next)
    {
      mark_object (&handler->handler);
      mark_object (&handler->var);
    }
  for (backlist = backtrace_list; backlist; backlist = backlist->next)
    {
      if (!XMARKBIT (*backlist->function))
	{
	  mark_object (backlist->function);
	  XMARK (*backlist->function);
	}
      if (backlist->nargs == UNEVALLED || backlist->nargs == MANY)
	i = 0;
      else
	i = backlist->nargs - 1;
      for (; i >= 0; i--)
	if (!XMARKBIT (backlist->args[i]))
	  {
	    mark_object (&backlist->args[i]);
	    XMARK (backlist->args[i]);
	  }
    }
  mark_kboards ();

  /* Look thru every buffer's undo list
     for elements that update markers that were not marked,
     and delete them.  */
  {
    register struct buffer *nextb = all_buffers;

	    prev = Qnil;
	    while (CONSP (tail))
	      {
		if (GC_CONSP (XCAR (tail))
		    && GC_MARKERP (XCAR (XCAR (tail)))
		    && ! XMARKBIT (XMARKER (XCAR (XCAR (tail)))->chain))
		  {
		    if (NILP (prev))
		      nextb->undo_list = tail = XCDR (tail);
		    else
		      {

		    prev = tail;
		    tail = XCDR (tail);
		  }
	      }
	  }

	nextb = nextb->next;
      }
  }

#if GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES
  mark_stack ();
#endif

#ifdef USE_GTK
  {
    extern void xg_mark_data ();
    xg_mark_data ();
  }
#endif

  gc_sweep ();

  /* Clear the mark bits that we set in certain root slots.  */

#if (GC_MARK_STACK == GC_USE_GCPROS_AS_BEFORE \
     || GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES)
  for (tail = gcprolist; tail; tail = tail->next)
    for (i = 0; i < tail->nvars; i++)
      XUNMARK (tail->var[i]);
#endif

  unmark_byte_stack ();
  for (backlist = backtrace_list; backlist; backlist = backlist->next)
    {
      XUNMARK (*backlist->function);
      if (backlist->nargs == UNEVALLED || backlist->nargs == MANY)
	i = 0;
      else
	i = backlist->nargs - 1;
      for (; i >= 0; i--)
	XUNMARK (backlist->args[i]);
    }
  XUNMARK (buffer_defaults.name);
  XUNMARK (buffer_local_symbols.name);

#if GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES && 0
  dump_zombies ();
#endif

  UNBLOCK_INPUT;

  /* clear_marks (); */
  gc_in_progress = 0;

  consing_since_gc = 0;
  if (gc_cons_threshold < 10000)
    gc_cons_threshold = 10000;

  if (garbage_collection_messages)
    {
      if (message_p || minibuf_level > 0)
	restore_message ();

  /* Accumulate statistics.  */
  EMACS_GET_TIME (t2);
  EMACS_SUB_TIME (t3, t2, t1);
  if (FLOATP (Vgc_elapsed))
    XSETFLOAT (Vgc_elapsed, make_float (XFLOAT_DATA (Vgc_elapsed) +
					EMACS_SECS (t3) +
					EMACS_USECS (t3) * 1.0e-6));
  gcs_done++;

  return Flist (sizeof total / sizeof *total, total);
}

	    struct glyph *end_glyph = glyph + row->used[area];

	    for (; glyph < end_glyph; ++glyph)
	      if (GC_STRINGP (glyph->object)
		  && !STRING_MARKED_P (XSTRING (glyph->object)))
		mark_object (&glyph->object);
	  }
      }
}

	  struct face *face = FACE_FROM_ID (c->f, i);

	  if (face)
	    {
	      for (j = 0; j < LFACE_VECTOR_SIZE; ++j)
		mark_object (&face->lface[j]);
	    }
	}
    }
}

static void
mark_image (img)
     struct image *img;
{
  mark_object (&img->spec);

  if (!NILP (img->data.lisp_val))
    mark_object (&img->data.lisp_val);
}


/* Mark Lisp objects in image cache of frame F.  It's done this way so
   that we don't have to include xterm.h here.  */

/* Mark reference to a Lisp_Object.
   If the object referred to has not been seen yet, recursively mark
   all the references contained in it.  */

#define LAST_MARKED_SIZE 500
Lisp_Object *last_marked[LAST_MARKED_SIZE];
int last_marked_index;

/* For debugging--call abort when we cdr down this many
   links of a list, in mark_object.  In debugging,
   the call to abort will hit a breakpoint.
   Normally this is zero and the check never goes off.  */
int mark_object_loop_halt;

void
mark_object (argptr)
     Lisp_Object *argptr;
{
  Lisp_Object *objptr = argptr;
  register Lisp_Object obj;
#ifdef GC_CHECK_MARKED_OBJECTS
  void *po;
  struct mem_node *m;
#endif
  int cdr_count = 0;

 loop:
  obj = *objptr;
 loop2:
  XUNMARK (obj);

  if (PURE_POINTER_P (XPNTR (obj)))
    return;

  last_marked[last_marked_index++] = objptr;
  if (last_marked_index == LAST_MARKED_SIZE)
    last_marked_index = 0;

  /* Perform some sanity checks on the objects marked here.  Abort if
     we encounter an object we know is bogus.  This increases GC time

	abort ();
#endif /* GC_CHECK_MARKED_OBJECTS */

      if (GC_BUFFERP (obj))
	{
	  if (!XMARKBIT (XBUFFER (obj)->name))
	    {
#ifdef GC_CHECK_MARKED_OBJECTS
	      if (po != &buffer_defaults && po != &buffer_local_symbols)
		{
		  struct buffer *b;

	{
	  register struct Lisp_Vector *ptr = XVECTOR (obj);
	  register EMACS_INT size = ptr->size;
	  register int i;

	  if (size & ARRAY_MARK_FLAG)
	    break;   /* Already marked */

	  CHECK_LIVE (live_vector_p);
	  ptr->size |= ARRAY_MARK_FLAG; /* Else mark it */
	  size &= PSEUDOVECTOR_SIZE_MASK;
	  for (i = 0; i < size; i++) /* and then mark its elements */
	    {
	      if (i != COMPILED_CONSTANTS)
		mark_object (&ptr->contents[i]);
	    }
	  /* This cast should be unnecessary, but some Mips compiler complains
	     (MIPS-ABI + SysVR4, DC/OSx, etc).  */
	  objptr = (Lisp_Object *) &ptr->contents[COMPILED_CONSTANTS];
	  goto loop;
	}
      else if (GC_FRAMEP (obj))
	{
	  register struct frame *ptr = XFRAME (obj);
	  register EMACS_INT size = ptr->size;

	  if (size & ARRAY_MARK_FLAG) break;   /* Already marked */
	  ptr->size |= ARRAY_MARK_FLAG; /* Else mark it */

	  CHECK_LIVE (live_vector_p);
	  mark_object (&ptr->name);
	  mark_object (&ptr->icon_name);
	  mark_object (&ptr->title);
	  mark_object (&ptr->focus_frame);
	  mark_object (&ptr->selected_window);
	  mark_object (&ptr->minibuffer_window);
	  mark_object (&ptr->param_alist);
	  mark_object (&ptr->scroll_bars);
	  mark_object (&ptr->condemned_scroll_bars);
	  mark_object (&ptr->menu_bar_items);
	  mark_object (&ptr->face_alist);
	  mark_object (&ptr->menu_bar_vector);
	  mark_object (&ptr->buffer_predicate);
	  mark_object (&ptr->buffer_list);
	  mark_object (&ptr->menu_bar_window);
	  mark_object (&ptr->tool_bar_window);
	  mark_face_cache (ptr->face_cache);
#ifdef HAVE_WINDOW_SYSTEM
	  mark_image_cache (ptr);
	  mark_object (&ptr->tool_bar_items);
	  mark_object (&ptr->desired_tool_bar_string);
	  mark_object (&ptr->current_tool_bar_string);
#endif /* HAVE_WINDOW_SYSTEM */
	}
      else if (GC_BOOL_VECTOR_P (obj))
	{
	  register struct Lisp_Vector *ptr = XVECTOR (obj);

	  if (ptr->size & ARRAY_MARK_FLAG)
	    break;   /* Already marked */
	  CHECK_LIVE (live_vector_p);
	  ptr->size |= ARRAY_MARK_FLAG; /* Else mark it */
	}
      else if (GC_WINDOWP (obj))
	{
	  register struct Lisp_Vector *ptr = XVECTOR (obj);
	  struct window *w = XWINDOW (obj);
	  register EMACS_INT size = ptr->size;
	  register int i;

	  /* Stop if already marked.  */
	  if (size & ARRAY_MARK_FLAG)
	    break;

	  /* Mark it.  */
	  CHECK_LIVE (live_vector_p);
	  ptr->size |= ARRAY_MARK_FLAG;

	  /* There is no Lisp data above The member CURRENT_MATRIX in
	     struct WINDOW.  Stop marking when that slot is reached.  */
	  for (i = 0;
	       (char *) &ptr->contents[i] < (char *) &w->current_matrix;
	       i++)
	    mark_object (&ptr->contents[i]);

	  /* Mark glyphs for leaf windows.  Marking window matrices is
	     sufficient because frame matrices use the same glyph
	     memory.  */
	  if (NILP (w->hchild)

	    }
	}
      else if (GC_HASH_TABLE_P (obj))
	{
	  struct Lisp_Hash_Table *h = XHASH_TABLE (obj);
	  EMACS_INT size = h->size;

	  /* Stop if already marked.  */
	  if (size & ARRAY_MARK_FLAG)
	    break;

	  /* Mark it.  */
	  CHECK_LIVE (live_vector_p);
	  h->size |= ARRAY_MARK_FLAG;

	  /* Mark contents.  */
	  /* Do not mark next_free or next_weak.
	     Being in the next_weak chain
	     should not keep the hash table alive.
	     No need to mark `count' since it is an integer.  */
	  mark_object (&h->test);
	  mark_object (&h->weak);
	  mark_object (&h->rehash_size);
	  mark_object (&h->rehash_threshold);
	  mark_object (&h->hash);
	  mark_object (&h->next);
	  mark_object (&h->index);
	  mark_object (&h->user_hash_function);
	  mark_object (&h->user_cmp_function);

	  /* If hash table is not weak, mark all keys and values.
	     For weak tables, mark only the vector.  */
	  if (GC_NILP (h->weak))
	    mark_object (&h->key_and_value);
	  else
	    XVECTOR (h->key_and_value)->size |= ARRAY_MARK_FLAG;

	}
      else
	{
	  register struct Lisp_Vector *ptr = XVECTOR (obj);
	  register EMACS_INT size = ptr->size;
	  register int i;

	  if (size & ARRAY_MARK_FLAG) break; /* Already marked */
	  CHECK_LIVE (live_vector_p);
	  ptr->size |= ARRAY_MARK_FLAG; /* Else mark it */
	  if (size & PSEUDOVECTOR_FLAG)
	    size &= PSEUDOVECTOR_SIZE_MASK;

	  for (i = 0; i < size; i++) /* and then mark its elements */
	    mark_object (&ptr->contents[i]);
	}
      break;

    case Lisp_Symbol:
      {
	register struct Lisp_Symbol *ptr = XSYMBOL (obj);
	struct Lisp_Symbol *ptrx;

	if (XMARKBIT (ptr->plist)) break;
	CHECK_ALLOCATED_AND_LIVE (live_symbol_p);
	XMARK (ptr->plist);
	mark_object ((Lisp_Object *) &ptr->value);
	mark_object (&ptr->function);
	mark_object (&ptr->plist);

	if (!PURE_POINTER_P (XSTRING (ptr->xname)))
	  MARK_STRING (XSTRING (ptr->xname));
	MARK_INTERVAL_TREE (STRING_INTERVALS (ptr->xname));

	   It is safe not to do so because nothing accesses that
	   slot except to check whether it is nil.  */
	ptr = ptr->next;
	if (ptr)
	  {
	    /* For the benefit of the last_marked log.  */
	    objptr = (Lisp_Object *)&XSYMBOL (obj)->next;
	    ptrx = ptr;		/* Use of ptrx avoids compiler bug on Sun */
	    XSETSYMBOL (obj, ptrx);
	    /* We can't goto loop here because *objptr doesn't contain an
	       actual Lisp_Object with valid datatype field.  */
	    goto loop2;
	  }
      }
      break;

    case Lisp_Misc:
      CHECK_ALLOCATED_AND_LIVE (live_misc_p);
      switch (XMISCTYPE (obj))
	{
	case Lisp_Misc_Marker:
	  XMARK (XMARKER (obj)->chain);
	  /* DO NOT mark thru the marker's chain.
	     The buffer's markers chain does not preserve markers from gc;
	     instead, markers are removed from the chain when freed by gc.  */
	  break;

	case Lisp_Misc_Buffer_Local_Value:
	case Lisp_Misc_Some_Buffer_Local_Value:
	  {
	    register struct Lisp_Buffer_Local_Value *ptr
	      = XBUFFER_LOCAL_VALUE (obj);
	    if (XMARKBIT (ptr->realvalue)) break;
	    XMARK (ptr->realvalue);
	    /* If the cdr is nil, avoid recursion for the car.  */
	    if (EQ (ptr->cdr, Qnil))
	      {
		objptr = &ptr->realvalue;
		goto loop;
	      }
	    mark_object (&ptr->realvalue);
	    mark_object (&ptr->buffer);
	    mark_object (&ptr->frame);
	    objptr = &ptr->cdr;
	    goto loop;
	  }

	case Lisp_Misc_Intfwd:
	case Lisp_Misc_Boolfwd:
	case Lisp_Misc_Objfwd:
	case Lisp_Misc_Buffer_Objfwd:

	     since all markable slots in current buffer marked anyway.  */
	  /* Don't need to do Lisp_Objfwd, since the places they point
	     are protected with staticpro.  */
	  break;

	case Lisp_Misc_Overlay:
	  {
	    struct Lisp_Overlay *ptr = XOVERLAY (obj);
	    if (!XMARKBIT (ptr->plist))
	      {
		XMARK (ptr->plist);
		mark_object (&ptr->start);
		mark_object (&ptr->end);
		objptr = &ptr->plist;
		goto loop;
	      }
	  }
	  break;

      break;

    case Lisp_Cons:
      {
	register struct Lisp_Cons *ptr = XCONS (obj);
	if (XMARKBIT (ptr->car)) break;
	CHECK_ALLOCATED_AND_LIVE (live_cons_p);
	XMARK (ptr->car);
	/* If the cdr is nil, avoid recursion for the car.  */
	if (EQ (ptr->cdr, Qnil))
	  {
	    objptr = &ptr->car;
	    cdr_count = 0;
	    goto loop;
	  }
	mark_object (&ptr->car);
	objptr = &ptr->cdr;
	cdr_count++;
	if (cdr_count == mark_object_loop_halt)
	  abort ();
	goto loop;
      }

    case Lisp_Float:
      CHECK_ALLOCATED_AND_LIVE (live_float_p);
      XMARK (XFLOAT (obj)->type);
      break;

    case Lisp_Int:
      break;

static void
mark_buffer (buf)
     Lisp_Object buf;
{
  register struct buffer *buffer = XBUFFER (buf);
  register Lisp_Object *ptr;
  Lisp_Object base_buffer;

  /* This is the buffer's markbit */
  mark_object (&buffer->name);
  XMARK (buffer->name);

  MARK_INTERVAL_TREE (BUF_INTERVALS (buffer));

  if (CONSP (buffer->undo_list))
    {
      Lisp_Object tail;
      tail = buffer->undo_list;

      while (CONSP (tail))
	{
	  register struct Lisp_Cons *ptr = XCONS (tail);

	  if (XMARKBIT (ptr->car))
	    break;
	  XMARK (ptr->car);
	  if (GC_CONSP (ptr->car)
	      && ! XMARKBIT (XCAR (ptr->car))
	      && GC_MARKERP (XCAR (ptr->car)))
	    {
	      XMARK (XCAR_AS_LVALUE (ptr->car));
	      mark_object (&XCDR_AS_LVALUE (ptr->car));
	    }
	  else
	    mark_object (&ptr->car);

	  if (CONSP (ptr->cdr))
	    tail = ptr->cdr;
	  else
	    break;
	}

      mark_object (&XCDR_AS_LVALUE (tail));
    }
  else
    mark_object (&buffer->undo_list);

  for (ptr = &buffer->name + 1;
       (char *)ptr < (char *)buffer + sizeof (struct buffer);
       ptr++)
    mark_object (ptr);

  /* If this is an indirect buffer, mark its base buffer.  */
  if (buffer->base_buffer && !XMARKBIT (buffer->base_buffer->name))
    {
      XSETBUFFER (base_buffer, buffer->base_buffer);
      mark_buffer (base_buffer);
    }
}


/* Mark the pointers in the kboard objects.  */

static void
mark_kboards ()
{
  KBOARD *kb;
  Lisp_Object *p;
  for (kb = all_kboards; kb; kb = kb->next_kboard)
    {
      if (kb->kbd_macro_buffer)
	for (p = kb->kbd_macro_buffer; p < kb->kbd_macro_ptr; p++)
	  mark_object (p);
      mark_object (&kb->Voverriding_terminal_local_map);
      mark_object (&kb->Vlast_command);
      mark_object (&kb->Vreal_last_command);
      mark_object (&kb->Vprefix_arg);
      mark_object (&kb->Vlast_prefix_arg);
      mark_object (&kb->kbd_queue);
      mark_object (&kb->defining_kbd_macro);
      mark_object (&kb->Vlast_kbd_macro);
      mark_object (&kb->Vsystem_key_alist);
      mark_object (&kb->system_key_syms);
      mark_object (&kb->Vdefault_minibuffer_frame);
      mark_object (&kb->echo_string);
    }
}


/* Value is non-zero if OBJ will survive the current GC because it's

    case Lisp_Int:
      survives_p = 1;
      break;

    case Lisp_Symbol:
      survives_p = XMARKBIT (XSYMBOL (obj)->plist);
      break;

    case Lisp_Misc:
      switch (XMISCTYPE (obj))
	{
	case Lisp_Misc_Marker:
	  survives_p = XMARKBIT (obj);
	  break;

	case Lisp_Misc_Buffer_Local_Value:
	case Lisp_Misc_Some_Buffer_Local_Value:
	  survives_p = XMARKBIT (XBUFFER_LOCAL_VALUE (obj)->realvalue);
	  break;

	case Lisp_Misc_Intfwd:
	case Lisp_Misc_Boolfwd:
	case Lisp_Misc_Objfwd:
	case Lisp_Misc_Buffer_Objfwd:
	case Lisp_Misc_Kboard_Objfwd:
	  survives_p = 1;
	  break;

	case Lisp_Misc_Overlay:
	  survives_p = XMARKBIT (XOVERLAY (obj)->plist);
	  break;

	default:
	  abort ();
	}
      break;

    case Lisp_String:
      {
	struct Lisp_String *s = XSTRING (obj);
	survives_p = STRING_MARKED_P (s);
      }
      break;

    case Lisp_Vectorlike:
      if (GC_BUFFERP (obj))
	survives_p = XMARKBIT (XBUFFER (obj)->name);
      else if (GC_SUBRP (obj))
	survives_p = 1;
      else
	survives_p = XVECTOR (obj)->size & ARRAY_MARK_FLAG;
      break;

    case Lisp_Cons:
      survives_p = XMARKBIT (XCAR (obj));
      break;

    case Lisp_Float:
      survives_p = XMARKBIT (XFLOAT (obj)->type);
      break;

    default:
      abort ();
    }

    for (cblk = cons_block; cblk; cblk = *cprev)
      {
	register int i;
	int this_free = 0;
	for (i = 0; i < lim; i++)
	  if (!XMARKBIT (cblk->conses[i].car))
	    {
	      this_free++;
	      *(struct Lisp_Cons **)&cblk->conses[i].cdr = cons_free_list;
	      cons_free_list = &cblk->conses[i];
#if GC_MARK_STACK
	      cons_free_list->car = Vdead;
#endif
	    }
	  else
	    {
	      num_used++;
	      XUNMARK (cblk->conses[i].car);
	    }
	lim = CONS_BLOCK_SIZE;
	/* If this block contains only free conses and we have already
	   seen more than two blocks worth of free conses then deallocate
	   this block.  */
	if (this_free == CONS_BLOCK_SIZE && num_free > CONS_BLOCK_SIZE)
	  {
	    *cprev = cblk->next;
	    /* Unhook from the free list.  */
	    cons_free_list = *(struct Lisp_Cons **) &cblk->conses[0].cdr;
	    lisp_free (cblk);
	    n_cons_blocks--;
	  }
	else
	  {
	    num_free += this_free;

    for (fblk = float_block; fblk; fblk = *fprev)
      {
	register int i;
	int this_free = 0;
	for (i = 0; i < lim; i++)
	  if (!XMARKBIT (fblk->floats[i].type))
	    {
	      this_free++;
	      *(struct Lisp_Float **)&fblk->floats[i].data = float_free_list;
	      float_free_list = &fblk->floats[i];
#if GC_MARK_STACK
	      float_free_list->type = Vdead;
#endif
	    }
	  else
	    {
	      num_used++;
	      XUNMARK (fblk->floats[i].type);
	    }
	lim = FLOAT_BLOCK_SIZE;
	/* If this block contains only free floats and we have already
	   seen more than two blocks worth of free floats then deallocate
	   this block.  */
	if (this_free == FLOAT_BLOCK_SIZE && num_free > FLOAT_BLOCK_SIZE)
	  {
	    *fprev = fblk->next;
	    /* Unhook from the free list.  */
	    float_free_list = *(struct Lisp_Float **) &fblk->floats[0].data;
	    lisp_free (fblk);
	    n_float_blocks--;
	  }
	else
	  {
	    num_free += this_free;

	register int i;
	int this_free = 0;

	for (i = 0; i < lim; i++)
	  {
	    if (! XMARKBIT (iblk->intervals[i].plist))
	      {
		SET_INTERVAL_PARENT (&iblk->intervals[i], interval_free_list);
		interval_free_list = &iblk->intervals[i];
		this_free++;
	      }
	    else
	      {
		num_used++;
		XUNMARK (iblk->intervals[i].plist);
	      }
	  }
	lim = INTERVAL_BLOCK_SIZE;
	/* If this block contains only free intervals and we have already
	   seen more than two blocks worth of free intervals then

	    /* Check if the symbol was created during loadup.  In such a case
	       it might be pointed to by pure bytecode which we don't trace,
	       so we conservatively assume that it is live.  */
	    int pure_p = PURE_POINTER_P (XSTRING (sym->xname));

	    if (!XMARKBIT (sym->plist) && !pure_p)
	      {
		*(struct Lisp_Symbol **) &sym->value = symbol_free_list;
		symbol_free_list = sym;
#if GC_MARK_STACK
		symbol_free_list->function = Vdead;
#endif
		++this_free;

	    else
	      {
		++num_used;
		if (!pure_p)
		  UNMARK_STRING (XSTRING (sym->xname));
		XUNMARK (sym->plist);
	      }
	  }

	lim = SYMBOL_BLOCK_SIZE;
	/* If this block contains only free symbols and we have already

	   this block.  */
	if (this_free == SYMBOL_BLOCK_SIZE && num_free > SYMBOL_BLOCK_SIZE)
	  {
	    *sprev = sblk->next;
	    /* Unhook from the free list.  */
	    symbol_free_list = *(struct Lisp_Symbol **)&sblk->symbols[0].value;
	    lisp_free (sblk);
	    n_symbol_blocks--;
	  }
	else
	  {

    for (mblk = marker_block; mblk; mblk = *mprev)
      {
	register int i;
	int this_free = 0;
	EMACS_INT already_free = -1;

	for (i = 0; i < lim; i++)
	  {
	    Lisp_Object *markword;
	    switch (mblk->markers[i].u_marker.type)
	      {
	      case Lisp_Misc_Marker:
		markword = &mblk->markers[i].u_marker.chain;
		break;
	      case Lisp_Misc_Buffer_Local_Value:
	      case Lisp_Misc_Some_Buffer_Local_Value:
		markword = &mblk->markers[i].u_buffer_local_value.realvalue;
		break;
	      case Lisp_Misc_Overlay:
		markword = &mblk->markers[i].u_overlay.plist;
		break;
	      case Lisp_Misc_Free:
		/* If the object was already free, keep it
		   on the free list.  */
		markword = (Lisp_Object *) &already_free;
		break;
	      default:
		markword = 0;
		break;
	      }
	    if (markword && !XMARKBIT (*markword))
	      {
		Lisp_Object tem;
		if (mblk->markers[i].u_marker.type == Lisp_Misc_Marker)
		  {
		    /* tem1 avoids Sun compiler bug */
		    struct Lisp_Marker *tem1 = &mblk->markers[i].u_marker;
		    XSETMARKER (tem, tem1);
		    unchain_marker (tem);
		  }
		/* Set the type of the freed object to Lisp_Misc_Free.
		   We could leave the type alone, since nobody checks it,
		   but this might catch bugs faster.  */
		mblk->markers[i].u_marker.type = Lisp_Misc_Free;
		mblk->markers[i].u_free.chain = marker_free_list;

		this_free++;
	      }
	    else
	      {
		num_used++;
		if (markword)
		  XUNMARK (*markword);
	      }
	  }
	lim = MARKER_BLOCK_SIZE;
	/* If this block contains only free markers and we have already
	   seen more than two blocks worth of free markers then deallocate

  /* Free all unmarked buffers */
  {
    register struct buffer *buffer = all_buffers, *prev = 0, *next;

    while (buffer)
      if (!XMARKBIT (buffer->name))
	{
	  if (prev)
	    prev->next = buffer->next;
	  else
	    all_buffers = buffer->next;

	  lisp_free (buffer);
	  buffer = next;
	}
      else
	{
	  XUNMARK (buffer->name);
	  UNMARK_BALANCE_INTERVALS (BUF_INTERVALS (buffer));
	  prev = buffer, buffer = buffer->next;
	}
  }

  {
    register struct Lisp_Vector *vector = all_vectors, *prev = 0, *next;
    total_vector_size = 0;

    while (vector)
      if (!(vector->size & ARRAY_MARK_FLAG))
	{
	  if (prev)
	    prev->next = vector->next;
	  else
	    all_vectors = vector->next;

	  vector = next;

	}
      else
	{
	  vector->size &= ~ARRAY_MARK_FLAG;
	  if (vector->size & PSEUDOVECTOR_FLAG)
	    total_vector_size += (PSEUDOVECTOR_SIZE_MASK & vector->size);
	  else
	    total_vector_size += vector->size;
	  prev = vector, vector = vector->next;

  purebeg = PUREBEG;
  pure_size = PURESIZE;
  pure_bytes_used = 0;
  pure_bytes_used_before_overflow = 0;

#if GC_MARK_STACK || defined GC_MALLOC_CHECK
  mem_init ();
  Vdead = make_pure_string ("DEAD", 4, 4, 0);
#endif

  malloc_hysteresis = 32;
#else
  malloc_hysteresis = 0;
#endif

  spare_memory = (char *) malloc (SPARE_MEMORY);

  ignore_warnings = 0;
  gcprolist = 0;
  byte_stack_list = 0;
  staticidx = 0;
  consing_since_gc = 0;
  gc_cons_threshold = 100000 * sizeof (Lisp_Object);
#ifdef VIRT_ADDR_VARIES
  malloc_sbrk_unused = 1<<22;	/* A large number */
  malloc_sbrk_used = 100000;	/* as reasonable as any number */
#endif /* VIRT_ADDR_VARIES */
}

allocated since the last garbage collection.  All data types count.

Garbage collection happens automatically only when `eval' is called.

By binding this temporarily to a large number, you can effectively
prevent garbage collection during a part of the program.  */);

  DEFVAR_INT ("pure-bytes-used", &pure_bytes_used,
	      doc: /* Number of bytes of sharable Lisp data allocated so far.  */);

  DEFVAR_INT ("cons-cells-consed", &cons_cells_consed,

	      doc: /* Number of strings that have been consed so far.  */);

  DEFVAR_LISP ("purify-flag", &Vpurify_flag,
	       doc: /* Non-nil means loading Lisp code in order to dump an executable.
This means that certain objects should be allocated in shared (pure) space.  */);

  DEFVAR_INT ("undo-limit", &undo_limit,
	      doc: /* Keep no more undo information once it exceeds this size.
This limit is applied when garbage collection happens.
The size is counted as the number of bytes occupied,
which includes both saved text and other data.  */);
  undo_limit = 20000;

  DEFVAR_INT ("undo-strong-limit", &undo_strong_limit,
	      doc: /* Don't keep more than this much size of undo information.
A command which pushes past this size is itself forgotten.
This limit is applied when garbage collection happens.
The size is counted as the number of bytes occupied,
which includes both saved text and other data.  */);
  undo_strong_limit = 30000;

  DEFVAR_BOOL ("garbage-collection-messages", &garbage_collection_messages,
	       doc: /* Non-nil means display messages at start and end of garbage collection.  */);
  garbage_collection_messages = 0;

  Vmemory_signal_data
    = list2 (Qerror,
	     build_string ("Memory exhausted--use M-x save-some-buffers then exit and restart Emacs"));

  DEFVAR_LISP ("memory-full", &Vmemory_full,
	       doc: /* Non-nil means we are handling a memory-full error.  */);
  Vmemory_full = Qnil;

  staticpro (&Qgc_cons_threshold);
  Qgc_cons_threshold = intern ("gc-cons-threshold");

  staticpro (&Qchar_table_extra_slots);
  Qchar_table_extra_slots = intern ("char-table-extra-slots");

  DEFVAR_LISP ("gc-elapsed", &Vgc_elapsed,
	       doc: /* Accumulated time elapsed in garbage collections.
The time is in seconds as a floating point value.
Programs may reset this to get statistics in a specific period.  */);
  DEFVAR_INT ("gcs-done", &gcs_done,
	      doc: /* Accumulated number of garbage collections done.
Programs may reset this to get statistics in a specific period.  */);

  defsubr (&Scons);
  defsubr (&Slist);
  defsubr (&Svector);
  defsubr (&Smake_byte_code);

#if GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES
  defsubr (&Sgc_status);
#endif
}

88155:d7ddb3e565de

/* Storage allocation and gc for GNU Emacs Lisp interpreter.
   Copyright (C) 1985, 1986, 1988, 1993, 1994, 1995, 1997, 1998, 1999,
      2000, 2001, 2002, 2003, 2004, 2005  Free Software Foundation, Inc.

This file is part of GNU Emacs.

GNU Emacs is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Emacs; see the file COPYING.  If not, write to
the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
Boston, MA 02110-1301, USA.  */

#include <config.h>
#include <stdio.h>
#include <limits.h>		/* For CHAR_BIT.  */

#ifdef ALLOC_DEBUG
#undef INLINE
#endif

/* Note that this declares bzero on OSF/1.  How dumb.  */

#include <signal.h>

#ifdef HAVE_GTK_AND_PTHREAD
#include <pthread.h>
#endif

/* This file is part of the core Lisp implementation, and thus must
   deal with the real data structures.  If the Lisp implementation is
   replaced, this file likely will not be used.  */

#include "blockinput.h"
#include "charset.h"
#include "syssignal.h"
#include <setjmp.h>

/* GC_MALLOC_CHECK defined means perform validity checks of malloc'd
   memory.  Can do this only if using gmalloc.c.  */

#if defined SYSTEM_MALLOC || defined DOUG_LEA_MALLOC
#undef GC_MALLOC_CHECK
#endif

#ifdef HAVE_UNISTD_H
#include <unistd.h>
#else
extern POINTER_TYPE *sbrk ();
#endif

#ifdef HAVE_FCNTL_H
#define INCLUDED_FCNTL
#include <fcntl.h>
#endif
#ifndef O_WRONLY
#define O_WRONLY 1
#endif

#ifdef DOUG_LEA_MALLOC

#include <malloc.h>
/* malloc.h #defines this as size_t, at least in glibc2.  */
#ifndef __malloc_size_t

extern __malloc_size_t _bytes_used;
extern __malloc_size_t __malloc_extra_blocks;

#endif /* not DOUG_LEA_MALLOC */

#if ! defined (SYSTEM_MALLOC) && defined (HAVE_GTK_AND_PTHREAD)

/* When GTK uses the file chooser dialog, different backends can be loaded
   dynamically.  One such a backend is the Gnome VFS backend that gets loaded
   if you run Gnome.  That backend creates several threads and also allocates
   memory with malloc.

   If Emacs sets malloc hooks (! SYSTEM_MALLOC) and the emacs_blocked_*
   functions below are called from malloc, there is a chance that one
   of these threads preempts the Emacs main thread and the hook variables
   end up in an inconsistent state.  So we have a mutex to prevent that (note
   that the backend handles concurrent access to malloc within its own threads
   but Emacs code running in the main thread is not included in that control).

   When UNBLOCK_INPUT is called, reinvoke_input_signal may be called.  If this
   happens in one of the backend threads we will have two threads that tries
   to run Emacs code at once, and the code is not prepared for that.
   To prevent that, we only call BLOCK/UNBLOCK from the main thread.  */

static pthread_mutex_t alloc_mutex;

#define BLOCK_INPUT_ALLOC                       \
  do                                            \
    {                                           \
      pthread_mutex_lock (&alloc_mutex);        \
      if (pthread_self () == main_thread)       \
        BLOCK_INPUT;                            \
    }                                           \
  while (0)
#define UNBLOCK_INPUT_ALLOC                     \
  do                                            \
    {                                           \
      if (pthread_self () == main_thread)       \
        UNBLOCK_INPUT;                          \
      pthread_mutex_unlock (&alloc_mutex);      \
    }                                           \
  while (0)

#else /* SYSTEM_MALLOC || not HAVE_GTK_AND_PTHREAD */

#define BLOCK_INPUT_ALLOC BLOCK_INPUT
#define UNBLOCK_INPUT_ALLOC UNBLOCK_INPUT

#endif /* SYSTEM_MALLOC || not HAVE_GTK_AND_PTHREAD */

/* Value of _bytes_used, when spare_memory was freed.  */

static __malloc_size_t bytes_used_when_full;

static __malloc_size_t bytes_used_when_reconsidered;

/* Mark, unmark, query mark bit of a Lisp string.  S must be a pointer
   to a struct Lisp_String.  */

#define MARK_STRING(S)		((S)->size |= ARRAY_MARK_FLAG)
#define UNMARK_STRING(S)	((S)->size &= ~ARRAY_MARK_FLAG)
#define STRING_MARKED_P(S)	(((S)->size & ARRAY_MARK_FLAG) != 0)

#define VECTOR_MARK(V)		((V)->size |= ARRAY_MARK_FLAG)
#define VECTOR_UNMARK(V)	((V)->size &= ~ARRAY_MARK_FLAG)
#define VECTOR_MARKED_P(V)	(((V)->size & ARRAY_MARK_FLAG) != 0)

/* Value is the number of bytes/chars of S, a pointer to a struct
   Lisp_String.  This must be used instead of STRING_BYTES (S) or
   S->size during GC, because S->size contains the mark bit for
   strings.  */

#define GC_STRING_BYTES(S)	(STRING_BYTES (S))
#define GC_STRING_CHARS(S)	((S)->size & ~ARRAY_MARK_FLAG)

/* Number of bytes of consing done since the last gc.  */

int consing_since_gc;

EMACS_INT string_chars_consed;
EMACS_INT misc_objects_consed;
EMACS_INT intervals_consed;
EMACS_INT strings_consed;

/* Minimum number of bytes of consing since GC before next GC. */

EMACS_INT gc_cons_threshold;

/* Similar minimum, computed from Vgc_cons_percentage.  */

EMACS_INT gc_relative_threshold;

static Lisp_Object Vgc_cons_percentage;

/* Minimum number of bytes of consing since GC before next GC,
   when memory is full.  */

EMACS_INT memory_full_cons_threshold;

/* Nonzero during GC.  */

int gc_in_progress;

/* Nonzero means abort if try to GC.
   This is for code which is written on the assumption that
   no GC will happen, so as to verify that assumption.  */

int abort_on_gc;

/* Nonzero means display messages at beginning and end of GC.  */

int garbage_collection_messages;

#ifndef VIRT_ADDR_VARIES
extern
#endif /* VIRT_ADDR_VARIES */
int malloc_sbrk_unused;

/* Number of live and free conses etc.  */

static int total_conses, total_markers, total_symbols, total_vector_size;
static int total_free_conses, total_free_markers, total_free_symbols;
static int total_free_floats, total_floats;

/* Points to memory space allocated as "spare", to be freed if we run
   out of memory.  We keep one large block, four cons-blocks, and
   two string blocks.  */

char *spare_memory[7];

/* Amount of spare memory to keep in large reserve block.  */

#define SPARE_MEMORY (1 << 14)

/* Number of extra blocks malloc should get when it needs more core.  */

Lisp_Object Vmemory_full;

#ifndef HAVE_SHM

/* Initialize it to a nonzero value to force it into data space
   (rather than bss space).  That way unexec will remap it into text
   space (pure), on some systems.  We have not implemented the
   remapping on more recent systems because this is less important
   nowadays than in the days of small memories and timesharing.  */

EMACS_INT pure[PURESIZE / sizeof (EMACS_INT)] = {1,};
#define PUREBEG (char *) pure

#else /* HAVE_SHM */

#define pure PURE_SEG_BITS   /* Use shared memory segment */

Lisp_Object Vgc_elapsed;	/* accumulated elapsed time in GC  */
EMACS_INT gcs_done;		/* accumulated GCs  */

static void mark_buffer P_ ((Lisp_Object));
extern void mark_kboards P_ ((void));
extern void mark_backtrace P_ ((void));
static void gc_sweep P_ ((void));
static void mark_glyph_matrix P_ ((struct glyph_matrix *));
static void mark_face_cache P_ ((struct face_cache *));

#ifdef HAVE_WINDOW_SYSTEM
extern void mark_fringe_data P_ ((void));
static void mark_image P_ ((struct image *));
static void mark_image_cache P_ ((struct frame *));
#endif /* HAVE_WINDOW_SYSTEM */

static struct Lisp_String *allocate_string P_ ((void));

  MEM_TYPE_PROCESS,
  MEM_TYPE_HASH_TABLE,
  MEM_TYPE_FRAME,
  MEM_TYPE_WINDOW
};

static POINTER_TYPE *lisp_align_malloc P_ ((size_t, enum mem_type));
static POINTER_TYPE *lisp_malloc P_ ((size_t, enum mem_type));
void refill_memory_reserve ();


#if GC_MARK_STACK || defined GC_MALLOC_CHECK

#if GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES
#include <stdio.h>		/* For fprintf.  */

static void mem_rotate_right P_ ((struct mem_node *));
static void mem_delete P_ ((struct mem_node *));
static void mem_delete_fixup P_ ((struct mem_node *));
static INLINE struct mem_node *mem_find P_ ((void *));


#if GC_MARK_STACK == GC_MARK_STACK_CHECK_GCPROS
static void check_gcpros P_ ((void));
#endif

#endif /* GC_MARK_STACK || GC_MALLOC_CHECK */

/* Recording what needs to be marked for gc.  */

struct gcpro *gcprolist;

/* Addresses of staticpro'd variables.  Initialize it to a nonzero
   value; otherwise some compilers put it into BSS.  */

#define NSTATICS 1280
Lisp_Object *staticvec[NSTATICS] = {&Vpurify_flag};

/* Index of next unused slot in staticvec.  */

int staticidx = 0;

/* Value is SZ rounded up to the next multiple of ALIGNMENT.
   ALIGNMENT must be a power of 2.  */

#define ALIGN(ptr, ALIGNMENT) \
  ((POINTER_TYPE *) ((((EMACS_UINT)(ptr)) + (ALIGNMENT) - 1) \
		     & ~((ALIGNMENT) - 1)))



/************************************************************************
				Malloc

  pending_malloc_warning = 0;
}


#ifdef DOUG_LEA_MALLOC
#  define BYTES_USED (mallinfo ().uordblks)
#else
#  define BYTES_USED _bytes_used
#endif

/* Called if we can't allocate relocatable space for a buffer.  */

void
buffer_memory_full ()
{

#ifndef REL_ALLOC
  memory_full ();
#endif

  /* This used to call error, but if we've run out of memory, we could
     get infinite recursion trying to build the string.  */
  while (1)
    Fsignal (Qnil, Vmemory_signal_data);
}


#ifdef XMALLOC_OVERRUN_CHECK

/* Check for overrun in malloc'ed buffers by wrapping a 16 byte header
   and a 16 byte trailer around each block.

   The header consists of 12 fixed bytes + a 4 byte integer contaning the
   original block size, while the trailer consists of 16 fixed bytes.

   The header is used to detect whether this block has been allocated
   through these functions -- as it seems that some low-level libc
   functions may bypass the malloc hooks.
*/


#define XMALLOC_OVERRUN_CHECK_SIZE 16

static char xmalloc_overrun_check_header[XMALLOC_OVERRUN_CHECK_SIZE-4] =
  { 0x9a, 0x9b, 0xae, 0xaf,
    0xbf, 0xbe, 0xce, 0xcf,
    0xea, 0xeb, 0xec, 0xed };

static char xmalloc_overrun_check_trailer[XMALLOC_OVERRUN_CHECK_SIZE] =
  { 0xaa, 0xab, 0xac, 0xad,
    0xba, 0xbb, 0xbc, 0xbd,
    0xca, 0xcb, 0xcc, 0xcd,
    0xda, 0xdb, 0xdc, 0xdd };

/* Macros to insert and extract the block size in the header.  */

#define XMALLOC_PUT_SIZE(ptr, size)	\
  (ptr[-1] = (size & 0xff),		\
   ptr[-2] = ((size >> 8) & 0xff),	\
   ptr[-3] = ((size >> 16) & 0xff),	\
   ptr[-4] = ((size >> 24) & 0xff))

#define XMALLOC_GET_SIZE(ptr)			\
  (size_t)((unsigned)(ptr[-1])		|	\
	   ((unsigned)(ptr[-2]) << 8)	|	\
	   ((unsigned)(ptr[-3]) << 16)	|	\
	   ((unsigned)(ptr[-4]) << 24))


/* The call depth in overrun_check functions.  For example, this might happen:
   xmalloc()
     overrun_check_malloc()
       -> malloc -> (via hook)_-> emacs_blocked_malloc
          -> overrun_check_malloc
             call malloc  (hooks are NULL, so real malloc is called).
             malloc returns 10000.
             add overhead, return 10016.
      <- (back in overrun_check_malloc)
      add overhead again, return 10032
   xmalloc returns 10032.

   (time passes).

   xfree(10032)
     overrun_check_free(10032)
       decrease overhed
       free(10016)  <-  crash, because 10000 is the original pointer.  */

static int check_depth;

/* Like malloc, but wraps allocated block with header and trailer.  */

POINTER_TYPE *
overrun_check_malloc (size)
     size_t size;
{
  register unsigned char *val;
  size_t overhead = ++check_depth == 1 ? XMALLOC_OVERRUN_CHECK_SIZE*2 : 0;

  val = (unsigned char *) malloc (size + overhead);
  if (val && check_depth == 1)
    {
      bcopy (xmalloc_overrun_check_header, val, XMALLOC_OVERRUN_CHECK_SIZE - 4);
      val += XMALLOC_OVERRUN_CHECK_SIZE;
      XMALLOC_PUT_SIZE(val, size);
      bcopy (xmalloc_overrun_check_trailer, val + size, XMALLOC_OVERRUN_CHECK_SIZE);
    }
  --check_depth;
  return (POINTER_TYPE *)val;
}


/* Like realloc, but checks old block for overrun, and wraps new block
   with header and trailer.  */

POINTER_TYPE *
overrun_check_realloc (block, size)
     POINTER_TYPE *block;
     size_t size;
{
  register unsigned char *val = (unsigned char *)block;
  size_t overhead = ++check_depth == 1 ? XMALLOC_OVERRUN_CHECK_SIZE*2 : 0;

  if (val
      && check_depth == 1
      && bcmp (xmalloc_overrun_check_header,
	       val - XMALLOC_OVERRUN_CHECK_SIZE,
	       XMALLOC_OVERRUN_CHECK_SIZE - 4) == 0)
    {
      size_t osize = XMALLOC_GET_SIZE (val);
      if (bcmp (xmalloc_overrun_check_trailer,
		val + osize,
		XMALLOC_OVERRUN_CHECK_SIZE))
	abort ();
      bzero (val + osize, XMALLOC_OVERRUN_CHECK_SIZE);
      val -= XMALLOC_OVERRUN_CHECK_SIZE;
      bzero (val, XMALLOC_OVERRUN_CHECK_SIZE);
    }

  val = (unsigned char *) realloc ((POINTER_TYPE *)val, size + overhead);

  if (val && check_depth == 1)
    {
      bcopy (xmalloc_overrun_check_header, val, XMALLOC_OVERRUN_CHECK_SIZE - 4);
      val += XMALLOC_OVERRUN_CHECK_SIZE;
      XMALLOC_PUT_SIZE(val, size);
      bcopy (xmalloc_overrun_check_trailer, val + size, XMALLOC_OVERRUN_CHECK_SIZE);
    }
  --check_depth;
  return (POINTER_TYPE *)val;
}

/* Like free, but checks block for overrun.  */

void
overrun_check_free (block)
     POINTER_TYPE *block;
{
  unsigned char *val = (unsigned char *)block;

  ++check_depth;
  if (val
      && check_depth == 1
      && bcmp (xmalloc_overrun_check_header,
	       val - XMALLOC_OVERRUN_CHECK_SIZE,
	       XMALLOC_OVERRUN_CHECK_SIZE - 4) == 0)
    {
      size_t osize = XMALLOC_GET_SIZE (val);
      if (bcmp (xmalloc_overrun_check_trailer,
		val + osize,
		XMALLOC_OVERRUN_CHECK_SIZE))
	abort ();
#ifdef XMALLOC_CLEAR_FREE_MEMORY
      val -= XMALLOC_OVERRUN_CHECK_SIZE;
      memset (val, 0xff, osize + XMALLOC_OVERRUN_CHECK_SIZE*2);
#else
      bzero (val + osize, XMALLOC_OVERRUN_CHECK_SIZE);
      val -= XMALLOC_OVERRUN_CHECK_SIZE;
      bzero (val, XMALLOC_OVERRUN_CHECK_SIZE);
#endif
    }

  free (val);
  --check_depth;
}

#undef malloc
#undef realloc
#undef free
#define malloc overrun_check_malloc
#define realloc overrun_check_realloc
#define free overrun_check_free
#endif


/* Like malloc but check for no memory and block interrupt input..  */

POINTER_TYPE *

  if (!val && size) memory_full ();
  return val;
}


/* Like free but block interrupt input.  */

void
xfree (block)
     POINTER_TYPE *block;
{
  BLOCK_INPUT;
  free (block);
  UNBLOCK_INPUT;
  /* We don't call refill_memory_reserve here
     because that duplicates doing so in emacs_blocked_free
     and the criterion should go there.  */
}


/* Like strdup, but uses xmalloc.  */

  bcopy (s, p, len);
  return p;
}


/* Unwind for SAFE_ALLOCA */

Lisp_Object
safe_alloca_unwind (arg)
     Lisp_Object arg;
{
  register struct Lisp_Save_Value *p = XSAVE_VALUE (arg);

  p->dogc = 0;
  xfree (p->pointer);
  p->pointer = 0;
  free_misc (arg);
  return Qnil;
}


/* Like malloc but used for allocating Lisp data.  NBYTES is the
   number of bytes to allocate, TYPE describes the intended use of the
   allcated memory block (for strings, for conses, ...).  */

#ifndef USE_LSB_TAG
static void *lisp_malloc_loser;
#endif

static POINTER_TYPE *
lisp_malloc (nbytes, type)
     size_t nbytes;
     enum mem_type type;

  allocated_mem_type = type;
#endif

  val = (void *) malloc (nbytes);

#ifndef USE_LSB_TAG
  /* If the memory just allocated cannot be addressed thru a Lisp
     object's pointer, and it needs to be,
     that's equivalent to running out of memory.  */
  if (val && type != MEM_TYPE_NON_LISP)
    {
      Lisp_Object tem;
      XSETCONS (tem, (char *) val + nbytes - 1);
      if ((char *) XCONS (tem) != (char *) val + nbytes - 1)
	{
	  lisp_malloc_loser = val;
	  free (val);
	  val = 0;
	}
    }
#endif

#if GC_MARK_STACK && !defined GC_MALLOC_CHECK
  if (val && type != MEM_TYPE_NON_LISP)
    mem_insert (val, (char *) val + nbytes, type);
#endif

  if (!val && nbytes)
    memory_full ();
  return val;
}

/* Free BLOCK.  This must be called to free memory allocated with a
   call to lisp_malloc.  */

static void
lisp_free (block)

  mem_delete (mem_find (block));
#endif
  UNBLOCK_INPUT;
}

/* Allocation of aligned blocks of memory to store Lisp data.              */
/* The entry point is lisp_align_malloc which returns blocks of at most    */
/* BLOCK_BYTES and guarantees they are aligned on a BLOCK_ALIGN boundary.  */


/* BLOCK_ALIGN has to be a power of 2.  */
#define BLOCK_ALIGN (1 << 10)

/* Padding to leave at the end of a malloc'd block.  This is to give
   malloc a chance to minimize the amount of memory wasted to alignment.
   It should be tuned to the particular malloc library used.
   On glibc-2.3.2, malloc never tries to align, so a padding of 0 is best.
   posix_memalign on the other hand would ideally prefer a value of 4
   because otherwise, there's 1020 bytes wasted between each ablocks.
   In Emacs, testing shows that those 1020 can most of the time be
   efficiently used by malloc to place other objects, so a value of 0 can
   still preferable unless you have a lot of aligned blocks and virtually
   nothing else.  */
#define BLOCK_PADDING 0
#define BLOCK_BYTES \
  (BLOCK_ALIGN - sizeof (struct ablock *) - BLOCK_PADDING)

/* Internal data structures and constants.  */

#define ABLOCKS_SIZE 16

/* An aligned block of memory.  */
struct ablock
{
  union
  {
    char payload[BLOCK_BYTES];
    struct ablock *next_free;
  } x;
  /* `abase' is the aligned base of the ablocks.  */
  /* It is overloaded to hold the virtual `busy' field that counts
     the number of used ablock in the parent ablocks.
     The first ablock has the `busy' field, the others have the `abase'
     field.  To tell the difference, we assume that pointers will have
     integer values larger than 2 * ABLOCKS_SIZE.  The lowest bit of `busy'
     is used to tell whether the real base of the parent ablocks is `abase'
     (if not, the word before the first ablock holds a pointer to the
     real base).  */
  struct ablocks *abase;
  /* The padding of all but the last ablock is unused.  The padding of
     the last ablock in an ablocks is not allocated.  */
#if BLOCK_PADDING
  char padding[BLOCK_PADDING];
#endif
};

/* A bunch of consecutive aligned blocks.  */
struct ablocks
{
  struct ablock blocks[ABLOCKS_SIZE];
};

/* Size of the block requested from malloc or memalign.  */
#define ABLOCKS_BYTES (sizeof (struct ablocks) - BLOCK_PADDING)

#define ABLOCK_ABASE(block) \
  (((unsigned long) (block)->abase) <= (1 + 2 * ABLOCKS_SIZE)   \
   ? (struct ablocks *)(block)					\
   : (block)->abase)

/* Virtual `busy' field.  */
#define ABLOCKS_BUSY(abase) ((abase)->blocks[0].abase)

/* Pointer to the (not necessarily aligned) malloc block.  */
#ifdef HAVE_POSIX_MEMALIGN
#define ABLOCKS_BASE(abase) (abase)
#else
#define ABLOCKS_BASE(abase) \
  (1 & (long) ABLOCKS_BUSY (abase) ? abase : ((void**)abase)[-1])
#endif

/* The list of free ablock.   */
static struct ablock *free_ablock;

/* Allocate an aligned block of nbytes.
   Alignment is on a multiple of BLOCK_ALIGN and `nbytes' has to be
   smaller or equal to BLOCK_BYTES.  */
static POINTER_TYPE *
lisp_align_malloc (nbytes, type)
     size_t nbytes;
     enum mem_type type;
{
  void *base, *val;
  struct ablocks *abase;

  eassert (nbytes <= BLOCK_BYTES);

  BLOCK_INPUT;

#ifdef GC_MALLOC_CHECK
  allocated_mem_type = type;
#endif

  if (!free_ablock)
    {
      int i;
      EMACS_INT aligned; /* int gets warning casting to 64-bit pointer.  */

#ifdef DOUG_LEA_MALLOC
      /* Prevent mmap'ing the chunk.  Lisp data may not be mmap'ed
	 because mapped region contents are not preserved in
	 a dumped Emacs.  */
      mallopt (M_MMAP_MAX, 0);
#endif

#ifdef HAVE_POSIX_MEMALIGN
      {
	int err = posix_memalign (&base, BLOCK_ALIGN, ABLOCKS_BYTES);
	if (err)
	  base = NULL;
	abase = base;
      }
#else
      base = malloc (ABLOCKS_BYTES);
      abase = ALIGN (base, BLOCK_ALIGN);
#endif

      if (base == 0)
	{
	  UNBLOCK_INPUT;
	  memory_full ();
	}

      aligned = (base == abase);
      if (!aligned)
	((void**)abase)[-1] = base;

#ifdef DOUG_LEA_MALLOC
      /* Back to a reasonable maximum of mmap'ed areas.  */
      mallopt (M_MMAP_MAX, MMAP_MAX_AREAS);
#endif

#ifndef USE_LSB_TAG
      /* If the memory just allocated cannot be addressed thru a Lisp
	 object's pointer, and it needs to be, that's equivalent to
	 running out of memory.  */
      if (type != MEM_TYPE_NON_LISP)
	{
	  Lisp_Object tem;
	  char *end = (char *) base + ABLOCKS_BYTES - 1;
	  XSETCONS (tem, end);
	  if ((char *) XCONS (tem) != end)
	    {
	      lisp_malloc_loser = base;
	      free (base);
	      UNBLOCK_INPUT;
	      memory_full ();
	    }
	}
#endif

      /* Initialize the blocks and put them on the free list.
	 Is `base' was not properly aligned, we can't use the last block.  */
      for (i = 0; i < (aligned ? ABLOCKS_SIZE : ABLOCKS_SIZE - 1); i++)
	{
	  abase->blocks[i].abase = abase;
	  abase->blocks[i].x.next_free = free_ablock;
	  free_ablock = &abase->blocks[i];
	}
      ABLOCKS_BUSY (abase) = (struct ablocks *) (long) aligned;

      eassert (0 == ((EMACS_UINT)abase) % BLOCK_ALIGN);
      eassert (ABLOCK_ABASE (&abase->blocks[3]) == abase); /* 3 is arbitrary */
      eassert (ABLOCK_ABASE (&abase->blocks[0]) == abase);
      eassert (ABLOCKS_BASE (abase) == base);
      eassert (aligned == (long) ABLOCKS_BUSY (abase));
    }

  abase = ABLOCK_ABASE (free_ablock);
  ABLOCKS_BUSY (abase) = (struct ablocks *) (2 + (long) ABLOCKS_BUSY (abase));
  val = free_ablock;
  free_ablock = free_ablock->x.next_free;

#if GC_MARK_STACK && !defined GC_MALLOC_CHECK
  if (val && type != MEM_TYPE_NON_LISP)
    mem_insert (val, (char *) val + nbytes, type);
#endif

  UNBLOCK_INPUT;
  if (!val && nbytes)
    memory_full ();

  eassert (0 == ((EMACS_UINT)val) % BLOCK_ALIGN);
  return val;
}

static void
lisp_align_free (block)
     POINTER_TYPE *block;
{
  struct ablock *ablock = block;
  struct ablocks *abase = ABLOCK_ABASE (ablock);

  BLOCK_INPUT;
#if GC_MARK_STACK && !defined GC_MALLOC_CHECK
  mem_delete (mem_find (block));
#endif
  /* Put on free list.  */
  ablock->x.next_free = free_ablock;
  free_ablock = ablock;
  /* Update busy count.  */
  ABLOCKS_BUSY (abase) = (struct ablocks *) (-2 + (long) ABLOCKS_BUSY (abase));

  if (2 > (long) ABLOCKS_BUSY (abase))
    { /* All the blocks are free.  */
      int i = 0, aligned = (long) ABLOCKS_BUSY (abase);
      struct ablock **tem = &free_ablock;
      struct ablock *atop = &abase->blocks[aligned ? ABLOCKS_SIZE : ABLOCKS_SIZE - 1];

      while (*tem)
	{
	  if (*tem >= (struct ablock *) abase && *tem < atop)
	    {
	      i++;
	      *tem = (*tem)->x.next_free;
	    }
	  else
	    tem = &(*tem)->x.next_free;
	}
      eassert ((aligned & 1) == aligned);
      eassert (i == (aligned ? ABLOCKS_SIZE : ABLOCKS_SIZE - 1));
      free (ABLOCKS_BASE (abase));
    }
  UNBLOCK_INPUT;
}

/* Return a new buffer structure allocated from the heap with
   a call to lisp_malloc.  */

struct buffer *
allocate_buffer ()
{
  struct buffer *b
    = (struct buffer *) lisp_malloc (sizeof (struct buffer),
				     MEM_TYPE_BUFFER);
  return b;
}


#ifndef SYSTEM_MALLOC

/* Arranging to disable input signals while we're in malloc.

   This only works with GNU malloc.  To help out systems which can't
   use GNU malloc, all the calls to malloc, realloc, and free
   elsewhere in the code should be inside a BLOCK_INPUT/UNBLOCK_INPUT
   pair; unfortunately, we have no idea what C library functions
   might call malloc, so we can't really protect them unless you're
   using GNU malloc.  Fortunately, most of the major operating systems
   can use GNU malloc.  */

#ifndef SYNC_INPUT

#ifndef DOUG_LEA_MALLOC
extern void * (*__malloc_hook) P_ ((size_t, const void *));
extern void * (*__realloc_hook) P_ ((void *, size_t, const void *));
extern void (*__free_hook) P_ ((void *, const void *));
/* Else declared in malloc.h, perhaps with an extra arg.  */
#endif /* DOUG_LEA_MALLOC */
static void * (*old_malloc_hook) P_ ((size_t, const void *));
static void * (*old_realloc_hook) P_ ((void *,  size_t, const void*));
static void (*old_free_hook) P_ ((void*, const void*));

/* This function is used as the hook for free to call.  */

static void
emacs_blocked_free (ptr, ptr2)
     void *ptr;
     const void *ptr2;
{
  EMACS_INT bytes_used_now;

  BLOCK_INPUT_ALLOC;

#ifdef GC_MALLOC_CHECK
  if (ptr)
    {
      struct mem_node *m;

  free (ptr);

  /* If we released our reserve (due to running out of memory),
     and we have a fair amount free once again,
     try to set aside another reserve in case we run out once more.  */
  if (! NILP (Vmemory_full)
      /* Verify there is enough space that even with the malloc
	 hysteresis this call won't run out again.
	 The code here is correct as long as SPARE_MEMORY
	 is substantially larger than the block size malloc uses.  */
      && (bytes_used_when_full
	  > ((bytes_used_when_reconsidered = BYTES_USED)
	     + max (malloc_hysteresis, 4) * SPARE_MEMORY)))
    refill_memory_reserve ();

  __free_hook = emacs_blocked_free;
  UNBLOCK_INPUT_ALLOC;
}


/* This function is the malloc hook that Emacs uses.  */

static void *
emacs_blocked_malloc (size, ptr)
     size_t size;
     const void *ptr;
{
  void *value;

  BLOCK_INPUT_ALLOC;
  __malloc_hook = old_malloc_hook;
#ifdef DOUG_LEA_MALLOC
    mallopt (M_TOP_PAD, malloc_hysteresis * 4096);
#else
    __malloc_extra_blocks = malloc_hysteresis;

      }
  }
#endif /* GC_MALLOC_CHECK */

  __malloc_hook = emacs_blocked_malloc;
  UNBLOCK_INPUT_ALLOC;

  /* fprintf (stderr, "%p malloc\n", value); */
  return value;
}


/* This function is the realloc hook that Emacs uses.  */

static void *
emacs_blocked_realloc (ptr, size, ptr2)
     void *ptr;
     size_t size;
     const void *ptr2;
{
  void *value;

  BLOCK_INPUT_ALLOC;
  __realloc_hook = old_realloc_hook;

#ifdef GC_MALLOC_CHECK
  if (ptr)
    {

  /* fprintf (stderr, "%p <- realloc\n", value); */
#endif /* GC_MALLOC_CHECK */

  __realloc_hook = emacs_blocked_realloc;
  UNBLOCK_INPUT_ALLOC;

  return value;
}


#ifdef HAVE_GTK_AND_PTHREAD
/* Called from Fdump_emacs so that when the dumped Emacs starts, it has a
   normal malloc.  Some thread implementations need this as they call
   malloc before main.  The pthread_self call in BLOCK_INPUT_ALLOC then
   calls malloc because it is the first call, and we have an endless loop.  */

void
reset_malloc_hooks ()
{
  __free_hook = 0;
  __malloc_hook = 0;
  __realloc_hook = 0;
}
#endif /* HAVE_GTK_AND_PTHREAD */


/* Called from main to set up malloc to use our hooks.  */

void
uninterrupt_malloc ()
{
#ifdef HAVE_GTK_AND_PTHREAD
  pthread_mutexattr_t attr;

  /*  GLIBC has a faster way to do this, but lets keep it portable.
      This is according to the Single UNIX Specification.  */
  pthread_mutexattr_init (&attr);
  pthread_mutexattr_settype (&attr, PTHREAD_MUTEX_RECURSIVE);
  pthread_mutex_init (&alloc_mutex, &attr);
#endif /* HAVE_GTK_AND_PTHREAD */

  if (__free_hook != emacs_blocked_free)
    old_free_hook = __free_hook;
  __free_hook = emacs_blocked_free;

  if (__malloc_hook != emacs_blocked_malloc)

  if (__realloc_hook != emacs_blocked_realloc)
    old_realloc_hook = __realloc_hook;
  __realloc_hook = emacs_blocked_realloc;
}

#endif /* not SYNC_INPUT */
#endif /* not SYSTEM_MALLOC */



/***********************************************************************

/* Intervals are allocated in chunks in form of an interval_block
   structure.  */

struct interval_block
{
  /* Place `intervals' first, to preserve alignment.  */
  struct interval intervals[INTERVAL_BLOCK_SIZE];
  struct interval_block *next;
};

/* Current interval block.  Its `next' pointer points to older
   blocks.  */

/* Initialize interval allocation.  */

static void
init_intervals ()
{
  interval_block = NULL;
  interval_block_index = INTERVAL_BLOCK_SIZE;
  interval_free_list = 0;
  n_interval_blocks = 0;
}


/* Return a new interval.  */

	  register struct interval_block *newi;

	  newi = (struct interval_block *) lisp_malloc (sizeof *newi,
							MEM_TYPE_NON_LISP);

	  newi->next = interval_block;
	  interval_block = newi;
	  interval_block_index = 0;
	  n_interval_blocks++;
	}
      val = &interval_block->intervals[interval_block_index++];
    }
  consing_since_gc += sizeof (struct interval);
  intervals_consed++;
  RESET_INTERVAL (val);
  val->gcmarkbit = 0;
  return val;
}


/* Mark Lisp objects in interval I. */

static void
mark_interval (i, dummy)
     register INTERVAL i;
     Lisp_Object dummy;
{
  eassert (!i->gcmarkbit);		/* Intervals are never shared.  */
  i->gcmarkbit = 1;
  mark_object (i->plist);
}


/* Mark the interval tree rooted in TREE.  Don't call this directly;
   use the macro MARK_INTERVAL_TREE instead.  */

{
  /* No need to test if this tree has been marked already; this
     function is always called through the MARK_INTERVAL_TREE macro,
     which takes care of that.  */

  traverse_intervals_noorder (tree, mark_interval, Qnil);
}


/* Mark the interval tree rooted in I.  */

#define MARK_INTERVAL_TREE(i)				\
  do {							\
    if (!NULL_INTERVAL_P (i) && !i->gcmarkbit)		\
      mark_interval_tree (i);				\
  } while (0)


#define UNMARK_BALANCE_INTERVALS(i)			\
  do {							\
   if (! NULL_INTERVAL_P (i))				\
     (i) = balance_intervals (i);			\
  } while (0)


/* Number support.  If NO_UNION_TYPE isn't in effect, we
   can't create number objects in macros.  */
#ifndef make_number
Lisp_Object
make_number (n)
     EMACS_INT n;
{
  Lisp_Object obj;
  obj.s.val = n;
  obj.s.type = Lisp_Int;
  return obj;

};

/* Number of Lisp strings in a string_block structure.  The 1020 is
   1024 minus malloc overhead.  */

#define STRING_BLOCK_SIZE \
  ((1020 - sizeof (struct string_block *)) / sizeof (struct Lisp_String))

/* Structure describing a block from which Lisp_String structures
   are allocated.  */

struct string_block
{
  /* Place `strings' first, to preserve alignment.  */
  struct Lisp_String strings[STRING_BLOCK_SIZE];
  struct string_block *next;
};

/* Head and tail of the list of sblock structures holding Lisp string
   data.  We always allocate from current_sblock.  The NEXT pointers
   in the sblock structures go from oldest_sblock to current_sblock.  */

#define SDATA_OF_STRING(S) \
     ((struct sdata *) ((S)->data - sizeof (struct Lisp_String *)))

#endif /* not GC_CHECK_STRING_BYTES */


#ifdef GC_CHECK_STRING_OVERRUN

/* We check for overrun in string data blocks by appending a small
   "cookie" after each allocated string data block, and check for the
   presence of this cookie during GC.  */

#define GC_STRING_OVERRUN_COOKIE_SIZE	4
static char string_overrun_cookie[GC_STRING_OVERRUN_COOKIE_SIZE] =
  { 0xde, 0xad, 0xbe, 0xef };

#else
#define GC_STRING_OVERRUN_COOKIE_SIZE 0
#endif

/* Value is the size of an sdata structure large enough to hold NBYTES
   bytes of string data.  The value returned includes a terminating
   NUL byte, the size of the sdata structure, and padding.  */

       + sizeof (EMACS_INT) - 1)		\
      & ~(sizeof (EMACS_INT) - 1))

#endif /* not GC_CHECK_STRING_BYTES */

/* Extra bytes to allocate for each string.  */

#define GC_STRING_EXTRA (GC_STRING_OVERRUN_COOKIE_SIZE)

/* Initialize string allocation.  Called from init_alloc_once.  */

void
init_strings ()
{

int
string_bytes (s)
     struct Lisp_String *s;
{
  int nbytes = (s->size_byte < 0 ? s->size & ~ARRAY_MARK_FLAG : s->size_byte);
  if (!PURE_POINTER_P (s)
      && s->data
      && nbytes != SDATA_NBYTES (SDATA_OF_STRING (s)))
    abort ();
  return nbytes;

	nbytes = GC_STRING_BYTES (from->string);
      else
	nbytes = SDATA_NBYTES (from);

      nbytes = SDATA_SIZE (nbytes);
      from_end = (struct sdata *) ((char *) from + nbytes + GC_STRING_EXTRA);
    }
}


/* Check validity of Lisp strings' string_bytes member.  ALL_P

    check_sblock (current_sblock);
}

#endif /* GC_CHECK_STRING_BYTES */

#ifdef GC_CHECK_STRING_FREE_LIST

/* Walk through the string free list looking for bogus next pointers.
   This may catch buffer overrun from a previous string.  */

static void
check_string_free_list ()
{
  struct Lisp_String *s;

  /* Pop a Lisp_String off the free-list.  */
  s = string_free_list;
  while (s != NULL)
    {
      if ((unsigned)s < 1024)
	abort();
      s = NEXT_FREE_LISP_STRING (s);
    }
}
#else
#define check_string_free_list()
#endif

/* Return a new Lisp_String.  */

static struct Lisp_String *
allocate_string ()

    {
      struct string_block *b;
      int i;

      b = (struct string_block *) lisp_malloc (sizeof *b, MEM_TYPE_STRING);
      bzero (b, sizeof *b);
      b->next = string_blocks;
      string_blocks = b;
      ++n_string_blocks;

      for (i = STRING_BLOCK_SIZE - 1; i >= 0; --i)
	{
	  s = b->strings + i;
	  NEXT_FREE_LISP_STRING (s) = string_free_list;
	  string_free_list = s;
	}

      total_free_strings += STRING_BLOCK_SIZE;
    }

  check_string_free_list ();

  /* Pop a Lisp_String off the free-list.  */
  s = string_free_list;
  string_free_list = NEXT_FREE_LISP_STRING (s);

      size_t size = sizeof *b - sizeof (struct sdata) + needed;

#ifdef DOUG_LEA_MALLOC
      /* Prevent mmap'ing the chunk.  Lisp data may not be mmap'ed
	 because mapped region contents are not preserved in
	 a dumped Emacs.

         In case you think of allowing it in a dumped Emacs at the
         cost of not being able to re-dump, there's another reason:
         mmap'ed data typically have an address towards the top of the
         address space, which won't fit into an EMACS_INT (at least on
         32-bit systems with the current tagging scheme).  --fx  */
      BLOCK_INPUT;
      mallopt (M_MMAP_MAX, 0);
      UNBLOCK_INPUT;
#endif

      b = (struct sblock *) lisp_malloc (size + GC_STRING_EXTRA, MEM_TYPE_NON_LISP);

#ifdef DOUG_LEA_MALLOC
      /* Back to a reasonable maximum of mmap'ed areas. */
      BLOCK_INPUT;
      mallopt (M_MMAP_MAX, MMAP_MAX_AREAS);
      UNBLOCK_INPUT;
#endif

      b->next_free = &b->first_data;
      b->first_data.string = NULL;
      b->next = large_sblocks;
      large_sblocks = b;
    }
  else if (current_sblock == NULL
	   || (((char *) current_sblock + SBLOCK_SIZE
		- (char *) current_sblock->next_free)
	       < (needed + GC_STRING_EXTRA)))
    {
      /* Not enough room in the current sblock.  */
      b = (struct sblock *) lisp_malloc (SBLOCK_SIZE, MEM_TYPE_NON_LISP);
      b->next_free = &b->first_data;
      b->first_data.string = NULL;

  SDATA_NBYTES (data) = nbytes;
#endif
  s->size = nchars;
  s->size_byte = nbytes;
  s->data[nbytes] = '\0';
#ifdef GC_CHECK_STRING_OVERRUN
  bcopy (string_overrun_cookie, (char *) data + needed,
	 GC_STRING_OVERRUN_COOKIE_SIZE);
#endif
  b->next_free = (struct sdata *) ((char *) data + needed + GC_STRING_EXTRA);

  /* If S had already data assigned, mark that as free by setting its
     string back-pointer to null, and recording the size of the data
     in it.  */
  if (old_data)

      int i, nfree = 0;
      struct Lisp_String *free_list_before = string_free_list;

      next = b->next;

      for (i = 0; i < STRING_BLOCK_SIZE; ++i)
	{
	  struct Lisp_String *s = b->strings + i;

	  if (s->data)
	    {

	    }
	}

      /* Free blocks that contain free Lisp_Strings only, except
	 the first two of them.  */
      if (nfree == STRING_BLOCK_SIZE
	  && total_free_strings > STRING_BLOCK_SIZE)
	{
	  lisp_free (b);
	  --n_string_blocks;
	  string_free_list = free_list_before;
	}

	  b->next = live_blocks;
	  live_blocks = b;
	}
    }

  check_string_free_list ();

  string_blocks = live_blocks;
  free_large_strings ();
  compact_small_strings ();

  check_string_free_list ();
}


/* Free dead large strings.  */

	  if (from->string)
	    nbytes = GC_STRING_BYTES (from->string);
	  else
	    nbytes = SDATA_NBYTES (from);

	  if (nbytes > LARGE_STRING_BYTES)
	    abort ();

	  nbytes = SDATA_SIZE (nbytes);
	  from_end = (struct sdata *) ((char *) from + nbytes + GC_STRING_EXTRA);

#ifdef GC_CHECK_STRING_OVERRUN
	  if (bcmp (string_overrun_cookie,
		    ((char *) from_end) - GC_STRING_OVERRUN_COOKIE_SIZE,
		    GC_STRING_OVERRUN_COOKIE_SIZE))
	    abort ();
#endif

	  /* FROM->string non-null means it's alive.  Copy its data.  */
	  if (from->string)
	    {
	      /* If TB is full, proceed with the next sblock.  */
	      to_end = (struct sdata *) ((char *) to + nbytes + GC_STRING_EXTRA);
	      if (to_end > tb_end)
		{
		  tb->next_free = to;
		  tb = tb->next;
		  tb_end = (struct sdata *) ((char *) tb + SBLOCK_SIZE);
		  to = &tb->first_data;
		  to_end = (struct sdata *) ((char *) to + nbytes + GC_STRING_EXTRA);
		}

	      /* Copy, and update the string's `data' pointer.  */
	      if (from != to)
		{
		  xassert (tb != b || to <= from);
		  safe_bcopy ((char *) from, (char *) to, nbytes + GC_STRING_EXTRA);
		  to->string->data = SDATA_DATA (to);
		}

	      /* Advance past the sdata we copied to.  */
	      to = to_end;

  current_sblock = tb;
}


DEFUN ("make-string", Fmake_string, Smake_string, 2, 2, 0,
       doc: /* Return a newly created string of length LENGTH, with INIT in each element.
LENGTH must be an integer.
INIT must be an integer that represents a character.  */)
     (length, init)
     Lisp_Object length, init;
{
  register Lisp_Object val;
  register unsigned char *p, *end;

  int real_init, i;
  int length_in_chars, length_in_elts, bits_per_value;

  CHECK_NATNUM (length);

  bits_per_value = sizeof (EMACS_INT) * BOOL_VECTOR_BITS_PER_CHAR;

  length_in_elts = (XFASTINT (length) + bits_per_value - 1) / bits_per_value;
  length_in_chars = ((XFASTINT (length) + BOOL_VECTOR_BITS_PER_CHAR - 1)
		     / BOOL_VECTOR_BITS_PER_CHAR);

  /* We must allocate one more elements than LENGTH_IN_ELTS for the
     slot `size' of the struct Lisp_Bool_Vector.  */
  val = Fmake_vector (make_number (length_in_elts + 1), Qnil);
  p = XBOOL_VECTOR (val);

  real_init = (NILP (init) ? 0 : -1);
  for (i = 0; i < length_in_chars ; i++)
    p->data[i] = real_init;

  /* Clear the extraneous bits in the last byte.  */
  if (XINT (length) != length_in_chars * BOOL_VECTOR_BITS_PER_CHAR)
    XBOOL_VECTOR (val)->data[length_in_chars - 1]
      &= (1 << (XINT (length) % BOOL_VECTOR_BITS_PER_CHAR)) - 1;

  return val;
}

/* Make a string from NCHARS characters occupying NBYTES bytes at
   CONTENTS.  It is a multibyte string if NBYTES != NCHARS.  */

Lisp_Object
make_string_from_bytes (contents, nchars, nbytes)
     const char *contents;
     int nchars, nbytes;
{
  register Lisp_Object val;
  val = make_uninit_multibyte_string (nchars, nbytes);
  bcopy (contents, SDATA (val), nbytes);

}


/* Make a string from NCHARS characters occupying NBYTES bytes at
   CONTENTS.  The argument MULTIBYTE controls whether to label the
   string as multibyte.  If NCHARS is negative, it counts the number of
   characters by itself.  */

Lisp_Object
make_specified_string (contents, nchars, nbytes, multibyte)
     const char *contents;
     int nchars, nbytes;
     int multibyte;
{
  register Lisp_Object val;

  if (nchars < 0)
    {
      if (multibyte)
	nchars = multibyte_chars_in_text (contents, nbytes);
      else
	nchars = nbytes;
    }
  val = make_uninit_multibyte_string (nchars, nbytes);
  bcopy (contents, SDATA (val), nbytes);
  if (!multibyte)
    STRING_SET_UNIBYTE (val);
  return val;

 ***********************************************************************/

/* We store float cells inside of float_blocks, allocating a new
   float_block with malloc whenever necessary.  Float cells reclaimed
   by GC are put on a free list to be reallocated before allocating
   any new float cells from the latest float_block.  */

#define FLOAT_BLOCK_SIZE					\
  (((BLOCK_BYTES - sizeof (struct float_block *)		\
     /* The compiler might add padding at the end.  */		\
     - (sizeof (struct Lisp_Float) - sizeof (int))) * CHAR_BIT) \
   / (sizeof (struct Lisp_Float) * CHAR_BIT + 1))

#define GETMARKBIT(block,n)				\
  (((block)->gcmarkbits[(n) / (sizeof(int) * CHAR_BIT)]	\
    >> ((n) % (sizeof(int) * CHAR_BIT)))		\
   & 1)

#define SETMARKBIT(block,n)				\
  (block)->gcmarkbits[(n) / (sizeof(int) * CHAR_BIT)]	\
  |= 1 << ((n) % (sizeof(int) * CHAR_BIT))

#define UNSETMARKBIT(block,n)				\
  (block)->gcmarkbits[(n) / (sizeof(int) * CHAR_BIT)]	\
  &= ~(1 << ((n) % (sizeof(int) * CHAR_BIT)))

#define FLOAT_BLOCK(fptr) \
  ((struct float_block *)(((EMACS_UINT)(fptr)) & ~(BLOCK_ALIGN - 1)))

#define FLOAT_INDEX(fptr) \
  ((((EMACS_UINT)(fptr)) & (BLOCK_ALIGN - 1)) / sizeof (struct Lisp_Float))

struct float_block
{
  /* Place `floats' at the beginning, to ease up FLOAT_INDEX's job.  */
  struct Lisp_Float floats[FLOAT_BLOCK_SIZE];
  int gcmarkbits[1 + FLOAT_BLOCK_SIZE / (sizeof(int) * CHAR_BIT)];
  struct float_block *next;
};

#define FLOAT_MARKED_P(fptr) \
  GETMARKBIT (FLOAT_BLOCK (fptr), FLOAT_INDEX ((fptr)))

#define FLOAT_MARK(fptr) \
  SETMARKBIT (FLOAT_BLOCK (fptr), FLOAT_INDEX ((fptr)))

#define FLOAT_UNMARK(fptr) \
  UNSETMARKBIT (FLOAT_BLOCK (fptr), FLOAT_INDEX ((fptr)))

/* Current float_block.  */

struct float_block *float_block;

/* Initialize float allocation.  */

void
init_float ()
{
  float_block = NULL;
  float_block_index = FLOAT_BLOCK_SIZE; /* Force alloc of new float_block.   */
  float_free_list = 0;
  n_float_blocks = 0;
}


/* Explicitly free a float cell by putting it on the free-list.  */

void
free_float (ptr)
     struct Lisp_Float *ptr;
{
  ptr->u.chain = float_free_list;
  float_free_list = ptr;
}


/* Return a new float object with value FLOAT_VALUE.  */

  if (float_free_list)
    {
      /* We use the data field for chaining the free list
	 so that we won't use the same field that has the mark bit.  */
      XSETFLOAT (val, float_free_list);
      float_free_list = float_free_list->u.chain;
    }
  else
    {
      if (float_block_index == FLOAT_BLOCK_SIZE)
	{
	  register struct float_block *new;

	  new = (struct float_block *) lisp_align_malloc (sizeof *new,
							  MEM_TYPE_FLOAT);
	  new->next = float_block;
	  bzero ((char *) new->gcmarkbits, sizeof new->gcmarkbits);
	  float_block = new;
	  float_block_index = 0;
	  n_float_blocks++;
	}
      XSETFLOAT (val, &float_block->floats[float_block_index]);
      float_block_index++;
    }

  XFLOAT_DATA (val) = float_value;
  eassert (!FLOAT_MARKED_P (XFLOAT (val)));
  consing_since_gc += sizeof (struct Lisp_Float);
  floats_consed++;
  return val;
}

 ***********************************************************************/

/* We store cons cells inside of cons_blocks, allocating a new
   cons_block with malloc whenever necessary.  Cons cells reclaimed by
   GC are put on a free list to be reallocated before allocating
   any new cons cells from the latest cons_block.  */

#define CONS_BLOCK_SIZE \
  (((BLOCK_BYTES - sizeof (struct cons_block *)) * CHAR_BIT) \
   / (sizeof (struct Lisp_Cons) * CHAR_BIT + 1))

#define CONS_BLOCK(fptr) \
  ((struct cons_block *)(((EMACS_UINT)(fptr)) & ~(BLOCK_ALIGN - 1)))

#define CONS_INDEX(fptr) \
  ((((EMACS_UINT)(fptr)) & (BLOCK_ALIGN - 1)) / sizeof (struct Lisp_Cons))

struct cons_block
{
  /* Place `conses' at the beginning, to ease up CONS_INDEX's job.  */
  struct Lisp_Cons conses[CONS_BLOCK_SIZE];
  int gcmarkbits[1 + CONS_BLOCK_SIZE / (sizeof(int) * CHAR_BIT)];
  struct cons_block *next;
};

#define CONS_MARKED_P(fptr) \
  GETMARKBIT (CONS_BLOCK (fptr), CONS_INDEX ((fptr)))

#define CONS_MARK(fptr) \
  SETMARKBIT (CONS_BLOCK (fptr), CONS_INDEX ((fptr)))

#define CONS_UNMARK(fptr) \
  UNSETMARKBIT (CONS_BLOCK (fptr), CONS_INDEX ((fptr)))

/* Current cons_block.  */

struct cons_block *cons_block;

/* Initialize cons allocation.  */

void
init_cons ()
{
  cons_block = NULL;
  cons_block_index = CONS_BLOCK_SIZE; /* Force alloc of new cons_block.  */
  cons_free_list = 0;
  n_cons_blocks = 0;
}


/* Explicitly free a cons cell by putting it on the free-list.  */

void
free_cons (ptr)
     struct Lisp_Cons *ptr;
{
  ptr->u.chain = cons_free_list;
#if GC_MARK_STACK
  ptr->car = Vdead;
#endif
  cons_free_list = ptr;
}

DEFUN ("cons", Fcons, Scons, 2, 2, 0,
       doc: /* Create a new cons, give it CAR and CDR as components, and return it.  */)
     (car, cdr)
     Lisp_Object car, cdr;

  if (cons_free_list)
    {
      /* We use the cdr for chaining the free list
	 so that we won't use the same field that has the mark bit.  */
      XSETCONS (val, cons_free_list);
      cons_free_list = cons_free_list->u.chain;
    }
  else
    {
      if (cons_block_index == CONS_BLOCK_SIZE)
	{
	  register struct cons_block *new;
	  new = (struct cons_block *) lisp_align_malloc (sizeof *new,
							 MEM_TYPE_CONS);
	  bzero ((char *) new->gcmarkbits, sizeof new->gcmarkbits);
	  new->next = cons_block;
	  cons_block = new;
	  cons_block_index = 0;
	  n_cons_blocks++;
	}
      XSETCONS (val, &cons_block->conses[cons_block_index]);
      cons_block_index++;
    }

  XSETCAR (val, car);
  XSETCDR (val, cdr);
  eassert (!CONS_MARKED_P (XCONS (val)));
  consing_since_gc += sizeof (struct Lisp_Cons);
  cons_cells_consed++;
  return val;
}

/* Get an error now if there's any junk in the cons free list.  */
void
check_cons_list ()
{
#ifdef GC_CHECK_CONS_LIST
  struct Lisp_Cons *tail = cons_free_list;

  while (tail)
    tail = tail->u.chain;
#endif
}

/* Make a list of 2, 3, 4 or 5 specified objects.  */

Lisp_Object
list2 (arg1, arg2)

#ifdef DOUG_LEA_MALLOC
  /* Prevent mmap'ing the chunk.  Lisp data may not be mmap'ed
     because mapped region contents are not preserved in
     a dumped Emacs.  */
  BLOCK_INPUT;
  mallopt (M_MMAP_MAX, 0);
  UNBLOCK_INPUT;
#endif

  nbytes = sizeof *p + (len - 1) * sizeof p->contents[0];
  p = (struct Lisp_Vector *) lisp_malloc (nbytes, type);

#ifdef DOUG_LEA_MALLOC
  /* Back to a reasonable maximum of mmap'ed areas.  */
  BLOCK_INPUT;
  mallopt (M_MMAP_MAX, MMAP_MAX_AREAS);
  UNBLOCK_INPUT;
#endif

  consing_since_gc += nbytes;
  vector_cells_consed += len;

  p->next = all_vectors;
  all_vectors = p;

  XSETCHAR_TABLE (vector, XCHAR_TABLE (vector));
  return vector;
}


/* Return a newly created sub char table with slots initialized by INIT.
   Since a sub char table does not appear as a top level Emacs Lisp
   object, we don't need a Lisp interface to make it.  */

Lisp_Object
make_sub_char_table (init)
     Lisp_Object init;
{
  Lisp_Object vector
    = Fmake_vector (make_number (SUB_CHAR_TABLE_STANDARD_SLOTS), init);
  XCHAR_TABLE (vector)->top = Qnil;
  XCHAR_TABLE (vector)->defalt = Qnil;
  XSETCHAR_TABLE (vector, XCHAR_TABLE (vector));
  return vector;
}

       doc: /* Create a byte-code object with specified arguments as elements.
The arguments should be the arglist, bytecode-string, constant vector,
stack size, (optional) doc string, and (optional) interactive spec.
The first four arguments are required; at most six have any
significance.
usage: (make-byte-code ARGLIST BYTE-CODE CONSTANTS DEPTH &optional DOCSTRING INTERACTIVE-SPEC &rest ELEMENTS)  */)
     (nargs, args)
     register int nargs;
     Lisp_Object *args;
{
  register Lisp_Object len, val;

#define SYMBOL_BLOCK_SIZE \
  ((1020 - sizeof (struct symbol_block *)) / sizeof (struct Lisp_Symbol))

struct symbol_block
{
  /* Place `symbols' first, to preserve alignment.  */
  struct Lisp_Symbol symbols[SYMBOL_BLOCK_SIZE];
  struct symbol_block *next;
};

/* Current symbol block and index of first unused Lisp_Symbol
   structure in it.  */

/* Initialize symbol allocation.  */

void
init_symbol ()
{
  symbol_block = NULL;
  symbol_block_index = SYMBOL_BLOCK_SIZE;
  symbol_free_list = 0;
  n_symbol_blocks = 0;
}


DEFUN ("make-symbol", Fmake_symbol, Smake_symbol, 1, 1, 0,
       doc: /* Return a newly allocated uninterned symbol whose name is NAME.

  CHECK_STRING (name);

  if (symbol_free_list)
    {
      XSETSYMBOL (val, symbol_free_list);
      symbol_free_list = symbol_free_list->next;
    }
  else
    {
      if (symbol_block_index == SYMBOL_BLOCK_SIZE)
	{
	  struct symbol_block *new;
	  new = (struct symbol_block *) lisp_malloc (sizeof *new,
						     MEM_TYPE_SYMBOL);
	  new->next = symbol_block;
	  symbol_block = new;
	  symbol_block_index = 0;
	  n_symbol_blocks++;
	}
      XSETSYMBOL (val, &symbol_block->symbols[symbol_block_index]);
      symbol_block_index++;
    }

  p = XSYMBOL (val);
  p->xname = name;
  p->plist = Qnil;
  p->value = Qunbound;
  p->function = Qunbound;
  p->next = NULL;
  p->gcmarkbit = 0;
  p->interned = SYMBOL_UNINTERNED;
  p->constant = 0;
  p->indirect_variable = 0;
  consing_since_gc += sizeof (struct Lisp_Symbol);
  symbols_consed++;

#define MARKER_BLOCK_SIZE \
  ((1020 - sizeof (struct marker_block *)) / sizeof (union Lisp_Misc))

struct marker_block
{
  /* Place `markers' first, to preserve alignment.  */
  union Lisp_Misc markers[MARKER_BLOCK_SIZE];
  struct marker_block *next;
};

struct marker_block *marker_block;
int marker_block_index;

int n_marker_blocks;

void
init_marker ()
{
  marker_block = NULL;
  marker_block_index = MARKER_BLOCK_SIZE;
  marker_free_list = 0;
  n_marker_blocks = 0;
}

/* Return a newly allocated Lisp_Misc object, with no substructure.  */

Lisp_Object

      if (marker_block_index == MARKER_BLOCK_SIZE)
	{
	  struct marker_block *new;
	  new = (struct marker_block *) lisp_malloc (sizeof *new,
						     MEM_TYPE_MISC);
	  new->next = marker_block;
	  marker_block = new;
	  marker_block_index = 0;
	  n_marker_blocks++;
	  total_free_markers += MARKER_BLOCK_SIZE;
	}
      XSETMISC (val, &marker_block->markers[marker_block_index]);
      marker_block_index++;
    }

  --total_free_markers;
  consing_since_gc += sizeof (union Lisp_Misc);
  misc_objects_consed++;
  XMARKER (val)->gcmarkbit = 0;
  return val;
}

/* Free a Lisp_Misc object */

void
free_misc (misc)
     Lisp_Object misc;
{
  XMISC (misc)->u_marker.type = Lisp_Misc_Free;
  XMISC (misc)->u_free.chain = marker_free_list;
  marker_free_list = XMISC (misc);

  total_free_markers++;
}

/* Return a Lisp_Misc_Save_Value object containing POINTER and
   INTEGER.  This is used to package C values to call record_unwind_protect.
   The unwind function can get the C values back using XSAVE_VALUE.  */

  val = allocate_misc ();
  XMISCTYPE (val) = Lisp_Misc_Save_Value;
  p = XSAVE_VALUE (val);
  p->pointer = pointer;
  p->integer = integer;
  p->dogc = 0;
  return val;
}

DEFUN ("make-marker", Fmake_marker, Smake_marker, 0, 0, 0,
       doc: /* Return a newly allocated marker which does not point at any place.  */)

  XMISCTYPE (val) = Lisp_Misc_Marker;
  p = XMARKER (val);
  p->buffer = 0;
  p->bytepos = 0;
  p->charpos = 0;
  p->next = NULL;
  p->insertion_type = 0;
  return val;
}

/* Put MARKER back on the free list after using it temporarily.  */

void
free_marker (marker)
     Lisp_Object marker;
{
  unchain_marker (XMARKER (marker));
  free_misc (marker);
}


/* Return a newly created vector or string with specified arguments as
   elements.  If all the arguments are characters that can fit

    return result;
  }
}



/************************************************************************
			   Memory Full Handling
 ************************************************************************/


/* Called if malloc returns zero.  */

void
memory_full ()
{
  int i;

  Vmemory_full = Qt;

  memory_full_cons_threshold = sizeof (struct cons_block);

  /* The first time we get here, free the spare memory.  */
  for (i = 0; i < sizeof (spare_memory) / sizeof (char *); i++)
    if (spare_memory[i])
      {
	if (i == 0)
	  free (spare_memory[i]);
	else if (i >= 1 && i <= 4)
	  lisp_align_free (spare_memory[i]);
	else
	  lisp_free (spare_memory[i]);
	spare_memory[i] = 0;
      }

  /* Record the space now used.  When it decreases substantially,
     we can refill the memory reserve.  */
#ifndef SYSTEM_MALLOC
  bytes_used_when_full = BYTES_USED;
#endif

  /* This used to call error, but if we've run out of memory, we could
     get infinite recursion trying to build the string.  */
  while (1)
    Fsignal (Qnil, Vmemory_signal_data);
}

/* If we released our reserve (due to running out of memory),
   and we have a fair amount free once again,
   try to set aside another reserve in case we run out once more.

   This is called when a relocatable block is freed in ralloc.c,
   and also directly from this file, in case we're not using ralloc.c.  */

void
refill_memory_reserve ()
{
#ifndef SYSTEM_MALLOC
  if (spare_memory[0] == 0)
    spare_memory[0] = (char *) malloc ((size_t) SPARE_MEMORY);
  if (spare_memory[1] == 0)
    spare_memory[1] = (char *) lisp_align_malloc (sizeof (struct cons_block),
						  MEM_TYPE_CONS);
  if (spare_memory[2] == 0)
    spare_memory[2] = (char *) lisp_align_malloc (sizeof (struct cons_block),
						  MEM_TYPE_CONS);
  if (spare_memory[3] == 0)
    spare_memory[3] = (char *) lisp_align_malloc (sizeof (struct cons_block),
						  MEM_TYPE_CONS);
  if (spare_memory[4] == 0)
    spare_memory[4] = (char *) lisp_align_malloc (sizeof (struct cons_block),
						  MEM_TYPE_CONS);
  if (spare_memory[5] == 0)
    spare_memory[5] = (char *) lisp_malloc (sizeof (struct string_block),
					    MEM_TYPE_STRING);
  if (spare_memory[6] == 0)
    spare_memory[6] = (char *) lisp_malloc (sizeof (struct string_block),
					    MEM_TYPE_STRING);
  if (spare_memory[0] && spare_memory[1] && spare_memory[5])
    Vmemory_full = Qnil;
#endif
}

/************************************************************************
			   C Stack Marking
 ************************************************************************/

      /* P must point to the start of a Lisp_String structure, and it
	 must not be on the free-list.  */
      return (offset >= 0
	      && offset % sizeof b->strings[0] == 0
	      && offset < (STRING_BLOCK_SIZE * sizeof b->strings[0])
	      && ((struct Lisp_String *) p)->data != NULL);
    }
  else
    return 0;
}

      /* P must point to the start of a Lisp_Cons, not be
	 one of the unused cells in the current cons block,
	 and not be on the free-list.  */
      return (offset >= 0
	      && offset % sizeof b->conses[0] == 0
	      && offset < (CONS_BLOCK_SIZE * sizeof b->conses[0])
	      && (b != cons_block
		  || offset / sizeof b->conses[0] < cons_block_index)
	      && !EQ (((struct Lisp_Cons *) p)->car, Vdead));
    }
  else

      /* P must point to the start of a Lisp_Symbol, not be
	 one of the unused cells in the current symbol block,
	 and not be on the free-list.  */
      return (offset >= 0
	      && offset % sizeof b->symbols[0] == 0
	      && offset < (SYMBOL_BLOCK_SIZE * sizeof b->symbols[0])
	      && (b != symbol_block
		  || offset / sizeof b->symbols[0] < symbol_block_index)
	      && !EQ (((struct Lisp_Symbol *) p)->function, Vdead));
    }
  else

  if (m->type == MEM_TYPE_FLOAT)
    {
      struct float_block *b = (struct float_block *) m->start;
      int offset = (char *) p - (char *) &b->floats[0];

      /* P must point to the start of a Lisp_Float and not be
	 one of the unused cells in the current float block.  */
      return (offset >= 0
	      && offset % sizeof b->floats[0] == 0
	      && offset < (FLOAT_BLOCK_SIZE * sizeof b->floats[0])
	      && (b != float_block
		  || offset / sizeof b->floats[0] < float_block_index));
    }
  else
    return 0;
}

      /* P must point to the start of a Lisp_Misc, not be
	 one of the unused cells in the current misc block,
	 and not be on the free-list.  */
      return (offset >= 0
	      && offset % sizeof b->markers[0] == 0
	      && offset < (MARKER_BLOCK_SIZE * sizeof b->markers[0])
	      && (b != marker_block
		  || offset / sizeof b->markers[0] < marker_block_index)
	      && ((union Lisp_Misc *) p)->u_marker.type != Lisp_Misc_Free);
    }
  else

	  && m->type >= MEM_TYPE_VECTOR
	  && m->type <= MEM_TYPE_WINDOW);
}


/* Value is non-zero if P is a pointer to a live buffer.  M is a
   pointer to the mem_block for P.  */

static INLINE int
live_buffer_p (m, p)
     struct mem_node *m;

	  mark_p = (live_string_p (m, po)
		    && !STRING_MARKED_P ((struct Lisp_String *) po));
	  break;

	case Lisp_Cons:
	  mark_p = (live_cons_p (m, po) && !CONS_MARKED_P (XCONS (obj)));
	  break;

	case Lisp_Symbol:
	  mark_p = (live_symbol_p (m, po) && !XSYMBOL (obj)->gcmarkbit);
	  break;

	case Lisp_Float:
	  mark_p = (live_float_p (m, po) && !FLOAT_MARKED_P (XFLOAT (obj)));
	  break;

	case Lisp_Vectorlike:
	  /* Note: can't check GC_BUFFERP before we know it's a
	     buffer because checking that dereferences the pointer
	     PO which might point anywhere.  */
	  if (live_vector_p (m, po))
	    mark_p = !GC_SUBRP (obj) && !VECTOR_MARKED_P (XVECTOR (obj));
	  else if (live_buffer_p (m, po))
	    mark_p = GC_BUFFERP (obj) && !VECTOR_MARKED_P (XBUFFER (obj));
	  break;

	case Lisp_Misc:
	  mark_p = (live_misc_p (m, po) && !XMARKER (obj)->gcmarkbit);
	  break;

	case Lisp_Int:
	case Lisp_Type_Limit:
	  break;

#if GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES
	  if (nzombies < MAX_ZOMBIES)
	    zombies[nzombies] = obj;
	  ++nzombies;
#endif
	  mark_object (obj);
	}
    }
}

	case MEM_TYPE_NON_LISP:
	  /* Nothing to do; not a pointer to Lisp memory.  */
	  break;

	case MEM_TYPE_BUFFER:
	  if (live_buffer_p (m, p) && !VECTOR_MARKED_P((struct buffer *)p))
	    XSETVECTOR (obj, p);
	  break;

	case MEM_TYPE_CONS:
	  if (live_cons_p (m, p) && !CONS_MARKED_P ((struct Lisp_Cons *) p))
	    XSETCONS (obj, p);
	  break;

	case MEM_TYPE_STRING:
	  if (live_string_p (m, p)
	      && !STRING_MARKED_P ((struct Lisp_String *) p))
	    XSETSTRING (obj, p);
	  break;

	case MEM_TYPE_MISC:
	  if (live_misc_p (m, p) && !((struct Lisp_Free *) p)->gcmarkbit)
	    XSETMISC (obj, p);
	  break;

	case MEM_TYPE_SYMBOL:
	  if (live_symbol_p (m, p) && !((struct Lisp_Symbol *) p)->gcmarkbit)
	    XSETSYMBOL (obj, p);
	  break;

	case MEM_TYPE_FLOAT:
	  if (live_float_p (m, p) && !FLOAT_MARKED_P (p))
	    XSETFLOAT (obj, p);
	  break;

	case MEM_TYPE_VECTOR:
	case MEM_TYPE_PROCESS:

	case MEM_TYPE_WINDOW:
	  if (live_vector_p (m, p))
	    {
	      Lisp_Object tem;
	      XSETVECTOR (tem, p);
	      if (!GC_SUBRP (tem) && !VECTOR_MARKED_P (XVECTOR (tem)))
		obj = tem;
	    }
	  break;

	default:
	  abort ();
	}

      if (!GC_NILP (obj))
	mark_object (obj);
    }
}


/* Mark Lisp objects referenced from the address range START..END.  */

  int i;

  for (p = gcprolist; p; p = p->next)
    for (i = 0; i < p->nvars; ++i)
      if (!survives_gc_p (p->var[i]))
	/* FIXME: It's not necessarily a bug.  It might just be that the
	   GCPRO is unnecessary or should release the object sooner.  */
	abort ();
}

#elif GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES

  volatile int stack_grows_down_p = (char *) &j > (char *) stack_base;
  void *end;

  /* This trick flushes the register windows so that all the state of
     the process is contained in the stack.  */
  /* Fixme: Code in the Boehm GC suggests flushing (with `flushrs') is
     needed on ia64 too.  See mach_dep.c, where it also says inline
     assembler doesn't work with relevant proprietary compilers.  */
#ifdef sparc
  asm ("ta 3");
#endif

#define GC_LISP_OBJECT_ALIGNMENT sizeof (Lisp_Object)
#endif
#endif
  for (i = 0; i < sizeof (Lisp_Object); i += GC_LISP_OBJECT_ALIGNMENT)
    mark_memory ((char *) stack_base + i, end);
  /* Allow for marking a secondary stack, like the register stack on the
     ia64.  */
#ifdef GC_MARK_SECONDARY_STACK
  GC_MARK_SECONDARY_STACK ();
#endif

#if GC_MARK_STACK == GC_MARK_STACK_CHECK_GCPROS
  check_gcpros ();
#endif
}

#endif /* GC_MARK_STACK != 0 */



/* Return 1 if OBJ is a valid lisp object.
   Return 0 if OBJ is NOT a valid lisp object.
   Return -1 if we cannot validate OBJ.
   This function can be quite slow,
   so it should only be used in code for manual debugging.  */

int
valid_lisp_object_p (obj)
     Lisp_Object obj;
{
  void *p;
#if !GC_MARK_STACK
  int fd;
#else
  struct mem_node *m;
#endif

  if (INTEGERP (obj))
    return 1;

  p = (void *) XPNTR (obj);
  if (PURE_POINTER_P (p))
    return 1;

#if !GC_MARK_STACK
  /* We need to determine whether it is safe to access memory at
     address P.  Obviously, we cannot just access it (we would SEGV
     trying), so we trick the o/s to tell us whether p is a valid
     pointer.  Unfortunately, we cannot use NULL_DEVICE here, as
     emacs_write may not validate p in that case.  */
  if ((fd = emacs_open ("__Valid__Lisp__Object__", O_CREAT | O_WRONLY | O_TRUNC, 0666)) >= 0)
    {
      int valid = (emacs_write (fd, (char *)p, 16) == 16);
      emacs_close (fd);
      unlink ("__Valid__Lisp__Object__");
      return valid;
    }

    return -1;
#else

  m = mem_find (p);

  if (m == MEM_NIL)
    return 0;

  switch (m->type)
    {
    case MEM_TYPE_NON_LISP:
      return 0;

    case MEM_TYPE_BUFFER:
      return live_buffer_p (m, p);

    case MEM_TYPE_CONS:
      return live_cons_p (m, p);

    case MEM_TYPE_STRING:
      return live_string_p (m, p);

    case MEM_TYPE_MISC:
      return live_misc_p (m, p);

    case MEM_TYPE_SYMBOL:
      return live_symbol_p (m, p);

    case MEM_TYPE_FLOAT:
      return live_float_p (m, p);

    case MEM_TYPE_VECTOR:
    case MEM_TYPE_PROCESS:
    case MEM_TYPE_HASH_TABLE:
    case MEM_TYPE_FRAME:
    case MEM_TYPE_WINDOW:
      return live_vector_p (m, p);

    default:
      break;
    }

  return 0;
#endif
}




/***********************************************************************
		       Pure Storage Management

pure_alloc (size, type)
     size_t size;
     int type;
{
  POINTER_TYPE *result;
#ifdef USE_LSB_TAG
  size_t alignment = (1 << GCTYPEBITS);
#else
  size_t alignment = sizeof (EMACS_INT);

  /* Give Lisp_Floats an extra alignment.  */
  if (type == Lisp_Float)
    {

      alignment = __alignof (struct Lisp_Float);
#else
      alignment = sizeof (struct Lisp_Float);
#endif
    }
#endif

 again:
  result = ALIGN (purebeg + pure_bytes_used, alignment);
  pure_bytes_used = ((char *)result - (char *)purebeg) + size;

  if (pure_bytes_used <= pure_size)
    return result;

			     SBYTES (obj),
			     STRING_MULTIBYTE (obj));
  else if (COMPILEDP (obj) || VECTORP (obj))
    {
      register struct Lisp_Vector *vec;
      register int i;
      EMACS_INT size;

      size = XVECTOR (obj)->size;
      if (size & PSEUDOVECTOR_FLAG)
	size &= PSEUDOVECTOR_SIZE_MASK;
      vec = XVECTOR (make_pure_vector (size));
      for (i = 0; i < size; i++)
	vec->contents[i] = Fpurecopy (XVECTOR (obj)->contents[i]);
      if (COMPILEDP (obj))
	XSETCOMPILED (obj, vec);
      else

    Lisp_Object tag;
    Lisp_Object val;
    struct catchtag *next;
};


/***********************************************************************
			  Protection from GC
 ***********************************************************************/

}


DEFUN ("garbage-collect", Fgarbage_collect, Sgarbage_collect, 0, 0, "",
       doc: /* Reclaim storage for Lisp objects no longer needed.
Garbage collection happens automatically if you cons more than
`gc-cons-threshold' bytes of Lisp data since previous garbage collection.
`garbage-collect' normally returns a list with info on amount of space in use:
 ((USED-CONSES . FREE-CONSES) (USED-SYMS . FREE-SYMS)
  (USED-MARKERS . FREE-MARKERS) USED-STRING-CHARS USED-VECTOR-SLOTS
  (USED-FLOATS . FREE-FLOATS) (USED-INTERVALS . FREE-INTERVALS)
  (USED-STRINGS . FREE-STRINGS))
However, if there was overflow in pure space, `garbage-collect'
returns nil, because real GC can't be done.  */)
     ()
{
  register struct specbinding *bind;
  struct catchtag *catch;
  struct handler *handler;
  char stack_top_variable;
  register int i;
  int message_p;
  Lisp_Object total[8];
  int count = SPECPDL_INDEX ();
  EMACS_TIME t1, t2, t3;

  if (abort_on_gc)
    abort ();

  /* Can't GC if pure storage overflowed because we can't determine
     if something is a pure object or not.  */
  if (pure_bytes_used_before_overflow)
    return Qnil;

  CHECK_CONS_LIST ();

  /* Don't keep undo information around forever.
     Do this early on, so it is no problem if the user quits.  */
  {
    register struct buffer *nextb = all_buffers;

    while (nextb)
      {
	/* If a buffer's undo list is Qt, that means that undo is
	   turned off in that buffer.  Calling truncate_undo_list on
	   Qt tends to return NULL, which effectively turns undo back on.
	   So don't call truncate_undo_list if undo_list is Qt.  */
	if (! NILP (nextb->name) && ! EQ (nextb->undo_list, Qt))
	  truncate_undo_list (nextb);

	/* Shrink buffer gaps, but skip indirect and dead buffers.  */
	if (nextb->base_buffer == 0 && !NILP (nextb->name))
	  {
	    /* If a buffer's gap size is more than 10% of the buffer
	       size, or larger than 2000 bytes, then shrink it
	       accordingly.  Keep a minimum size of 20 bytes.  */
	    int size = min (2000, max (20, (nextb->text->z_byte / 10)));

	    if (nextb->text->gap_size > size)
	      {
		struct buffer *save_current = current_buffer;
		current_buffer = nextb;
		make_gap (-(nextb->text->gap_size - size));
		current_buffer = save_current;
	      }
	  }

	nextb = nextb->next;
      }
  }

  EMACS_GET_TIME (t1);

  /* In case user calls debug_print during GC,
     don't let that cause a recursive GC.  */
  consing_since_gc = 0;

  BLOCK_INPUT;

  shrink_regexp_cache ();

  gc_in_progress = 1;

  /* clear_marks (); */

  /* Mark all the special slots that serve as the roots of accessibility.  */

  for (i = 0; i < staticidx; i++)
    mark_object (*staticvec[i]);

  for (bind = specpdl; bind != specpdl_ptr; bind++)
    {
      mark_object (bind->symbol);
      mark_object (bind->old_value);
    }
  mark_kboards ();

#ifdef USE_GTK
  {
    extern void xg_mark_data ();
    xg_mark_data ();
  }
#endif

#if (GC_MARK_STACK == GC_MAKE_GCPROS_NOOPS \
     || GC_MARK_STACK == GC_MARK_STACK_CHECK_GCPROS)
  mark_stack ();
#else
  {
    register struct gcpro *tail;
    for (tail = gcprolist; tail; tail = tail->next)
      for (i = 0; i < tail->nvars; i++)
	mark_object (tail->var[i]);
  }
#endif

  mark_byte_stack ();
  for (catch = catchlist; catch; catch = catch->next)
    {
      mark_object (catch->tag);
      mark_object (catch->val);
    }
  for (handler = handlerlist; handler; handler = handler->next)
    {
      mark_object (handler->handler);
      mark_object (handler->var);
    }
  mark_backtrace ();

#ifdef HAVE_WINDOW_SYSTEM
  mark_fringe_data ();
#endif

#if GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES
  mark_stack ();
#endif

  /* Everything is now marked, except for the things that require special
     finalization, i.e. the undo_list.
     Look thru every buffer's undo list
     for elements that update markers that were not marked,
     and delete them.  */
  {
    register struct buffer *nextb = all_buffers;

	    prev = Qnil;
	    while (CONSP (tail))
	      {
		if (GC_CONSP (XCAR (tail))
		    && GC_MARKERP (XCAR (XCAR (tail)))
		    && !XMARKER (XCAR (XCAR (tail)))->gcmarkbit)
		  {
		    if (NILP (prev))
		      nextb->undo_list = tail = XCDR (tail);
		    else
		      {

		    prev = tail;
		    tail = XCDR (tail);
		  }
	      }
	  }
	/* Now that we have stripped the elements that need not be in the
	   undo_list any more, we can finally mark the list.  */
	mark_object (nextb->undo_list);

	nextb = nextb->next;
      }
  }

  gc_sweep ();

  /* Clear the mark bits that we set in certain root slots.  */

  unmark_byte_stack ();
  VECTOR_UNMARK (&buffer_defaults);
  VECTOR_UNMARK (&buffer_local_symbols);

#if GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES && 0
  dump_zombies ();
#endif

  UNBLOCK_INPUT;

  CHECK_CONS_LIST ();

  /* clear_marks (); */
  gc_in_progress = 0;

  consing_since_gc = 0;
  if (gc_cons_threshold < 10000)
    gc_cons_threshold = 10000;

  if (FLOATP (Vgc_cons_percentage))
    { /* Set gc_cons_combined_threshold.  */
      EMACS_INT total = 0;

      total += total_conses  * sizeof (struct Lisp_Cons);
      total += total_symbols * sizeof (struct Lisp_Symbol);
      total += total_markers * sizeof (union Lisp_Misc);
      total += total_string_size;
      total += total_vector_size * sizeof (Lisp_Object);
      total += total_floats  * sizeof (struct Lisp_Float);
      total += total_intervals * sizeof (struct interval);
      total += total_strings * sizeof (struct Lisp_String);

      gc_relative_threshold = total * XFLOAT_DATA (Vgc_cons_percentage);
    }
  else
    gc_relative_threshold = 0;

  if (garbage_collection_messages)
    {
      if (message_p || minibuf_level > 0)
	restore_message ();

  /* Accumulate statistics.  */
  EMACS_GET_TIME (t2);
  EMACS_SUB_TIME (t3, t2, t1);
  if (FLOATP (Vgc_elapsed))
    Vgc_elapsed = make_float (XFLOAT_DATA (Vgc_elapsed) +
			      EMACS_SECS (t3) +
			      EMACS_USECS (t3) * 1.0e-6);
  gcs_done++;

  return Flist (sizeof total / sizeof *total, total);
}

	    struct glyph *end_glyph = glyph + row->used[area];

	    for (; glyph < end_glyph; ++glyph)
	      if (GC_STRINGP (glyph->object)
		  && !STRING_MARKED_P (XSTRING (glyph->object)))
		mark_object (glyph->object);
	  }
      }
}

	  struct face *face = FACE_FROM_ID (c->f, i);

	  if (face)
	    {
	      for (j = 0; j < LFACE_VECTOR_SIZE; ++j)
		mark_object (face->lface[j]);
	    }
	}
    }
}

static void
mark_image (img)
     struct image *img;
{
  mark_object (img->spec);

  if (!NILP (img->data.lisp_val))
    mark_object (img->data.lisp_val);
}


/* Mark Lisp objects in image cache of frame F.  It's done this way so
   that we don't have to include xterm.h here.  */

/* Mark reference to a Lisp_Object.
   If the object referred to has not been seen yet, recursively mark
   all the references contained in it.  */

#define LAST_MARKED_SIZE 500
Lisp_Object last_marked[LAST_MARKED_SIZE];
int last_marked_index;

/* For debugging--call abort when we cdr down this many
   links of a list, in mark_object.  In debugging,
   the call to abort will hit a breakpoint.
   Normally this is zero and the check never goes off.  */
int mark_object_loop_halt;

void
mark_object (arg)
     Lisp_Object arg;
{
  register Lisp_Object obj = arg;
#ifdef GC_CHECK_MARKED_OBJECTS
  void *po;
  struct mem_node *m;
#endif
  int cdr_count = 0;

 loop:

  if (PURE_POINTER_P (XPNTR (obj)))
    return;

  last_marked[last_marked_index++] = obj;
  if (last_marked_index == LAST_MARKED_SIZE)
    last_marked_index = 0;

  /* Perform some sanity checks on the objects marked here.  Abort if
     we encounter an object we know is bogus.  This increases GC time

	abort ();
#endif /* GC_CHECK_MARKED_OBJECTS */

      if (GC_BUFFERP (obj))
	{
	  if (!VECTOR_MARKED_P (XBUFFER (obj)))
	    {
#ifdef GC_CHECK_MARKED_OBJECTS
	      if (po != &buffer_defaults && po != &buffer_local_symbols)
		{
		  struct buffer *b;

	{
	  register struct Lisp_Vector *ptr = XVECTOR (obj);
	  register EMACS_INT size = ptr->size;
	  register int i;

	  if (VECTOR_MARKED_P (ptr))
	    break;   /* Already marked */

	  CHECK_LIVE (live_vector_p);
	  VECTOR_MARK (ptr);	/* Else mark it */
	  size &= PSEUDOVECTOR_SIZE_MASK;
	  for (i = 0; i < size; i++) /* and then mark its elements */
	    {
	      if (i != COMPILED_CONSTANTS)
		mark_object (ptr->contents[i]);
	    }
	  obj = ptr->contents[COMPILED_CONSTANTS];
	  goto loop;
	}
      else if (GC_FRAMEP (obj))
	{
	  register struct frame *ptr = XFRAME (obj);

	  if (VECTOR_MARKED_P (ptr)) break;   /* Already marked */
	  VECTOR_MARK (ptr);		      /* Else mark it */

	  CHECK_LIVE (live_vector_p);
	  mark_object (ptr->name);
	  mark_object (ptr->icon_name);
	  mark_object (ptr->title);
	  mark_object (ptr->focus_frame);
	  mark_object (ptr->selected_window);
	  mark_object (ptr->minibuffer_window);
	  mark_object (ptr->param_alist);
	  mark_object (ptr->scroll_bars);
	  mark_object (ptr->condemned_scroll_bars);
	  mark_object (ptr->menu_bar_items);
	  mark_object (ptr->face_alist);
	  mark_object (ptr->menu_bar_vector);
	  mark_object (ptr->buffer_predicate);
	  mark_object (ptr->buffer_list);
	  mark_object (ptr->menu_bar_window);
	  mark_object (ptr->tool_bar_window);
	  mark_face_cache (ptr->face_cache);
#ifdef HAVE_WINDOW_SYSTEM
	  mark_image_cache (ptr);
	  mark_object (ptr->tool_bar_items);
	  mark_object (ptr->desired_tool_bar_string);
	  mark_object (ptr->current_tool_bar_string);
#endif /* HAVE_WINDOW_SYSTEM */
	}
      else if (GC_BOOL_VECTOR_P (obj))
	{
	  register struct Lisp_Vector *ptr = XVECTOR (obj);

	  if (VECTOR_MARKED_P (ptr))
	    break;   /* Already marked */
	  CHECK_LIVE (live_vector_p);
	  VECTOR_MARK (ptr);	/* Else mark it */
	}
      else if (GC_WINDOWP (obj))
	{
	  register struct Lisp_Vector *ptr = XVECTOR (obj);
	  struct window *w = XWINDOW (obj);
	  register int i;

	  /* Stop if already marked.  */
	  if (VECTOR_MARKED_P (ptr))
	    break;

	  /* Mark it.  */
	  CHECK_LIVE (live_vector_p);
	  VECTOR_MARK (ptr);

	  /* There is no Lisp data above The member CURRENT_MATRIX in
	     struct WINDOW.  Stop marking when that slot is reached.  */
	  for (i = 0;
	       (char *) &ptr->contents[i] < (char *) &w->current_matrix;
	       i++)
	    mark_object (ptr->contents[i]);

	  /* Mark glyphs for leaf windows.  Marking window matrices is
	     sufficient because frame matrices use the same glyph
	     memory.  */
	  if (NILP (w->hchild)

	    }
	}
      else if (GC_HASH_TABLE_P (obj))
	{
	  struct Lisp_Hash_Table *h = XHASH_TABLE (obj);

	  /* Stop if already marked.  */
	  if (VECTOR_MARKED_P (h))
	    break;

	  /* Mark it.  */
	  CHECK_LIVE (live_vector_p);
	  VECTOR_MARK (h);

	  /* Mark contents.  */
	  /* Do not mark next_free or next_weak.
	     Being in the next_weak chain
	     should not keep the hash table alive.
	     No need to mark `count' since it is an integer.  */
	  mark_object (h->test);
	  mark_object (h->weak);
	  mark_object (h->rehash_size);
	  mark_object (h->rehash_threshold);
	  mark_object (h->hash);
	  mark_object (h->next);
	  mark_object (h->index);
	  mark_object (h->user_hash_function);
	  mark_object (h->user_cmp_function);

	  /* If hash table is not weak, mark all keys and values.
	     For weak tables, mark only the vector.  */
	  if (GC_NILP (h->weak))
	    mark_object (h->key_and_value);
	  else
	    VECTOR_MARK (XVECTOR (h->key_and_value));
	}
      else
	{
	  register struct Lisp_Vector *ptr = XVECTOR (obj);
	  register EMACS_INT size = ptr->size;
	  register int i;

	  if (VECTOR_MARKED_P (ptr)) break; /* Already marked */
	  CHECK_LIVE (live_vector_p);
	  VECTOR_MARK (ptr);	/* Else mark it */
	  if (size & PSEUDOVECTOR_FLAG)
	    size &= PSEUDOVECTOR_SIZE_MASK;

	  for (i = 0; i < size; i++) /* and then mark its elements */
	    mark_object (ptr->contents[i]);
	}
      break;

    case Lisp_Symbol:
      {
	register struct Lisp_Symbol *ptr = XSYMBOL (obj);
	struct Lisp_Symbol *ptrx;

	if (ptr->gcmarkbit) break;
	CHECK_ALLOCATED_AND_LIVE (live_symbol_p);
	ptr->gcmarkbit = 1;
	mark_object (ptr->value);
	mark_object (ptr->function);
	mark_object (ptr->plist);

	if (!PURE_POINTER_P (XSTRING (ptr->xname)))
	  MARK_STRING (XSTRING (ptr->xname));
	MARK_INTERVAL_TREE (STRING_INTERVALS (ptr->xname));

	   It is safe not to do so because nothing accesses that
	   slot except to check whether it is nil.  */
	ptr = ptr->next;
	if (ptr)
	  {
	    ptrx = ptr;		/* Use of ptrx avoids compiler bug on Sun */
	    XSETSYMBOL (obj, ptrx);
	    goto loop;
	  }
      }
      break;

    case Lisp_Misc:
      CHECK_ALLOCATED_AND_LIVE (live_misc_p);
      if (XMARKER (obj)->gcmarkbit)
	break;
      XMARKER (obj)->gcmarkbit = 1;

      switch (XMISCTYPE (obj))
	{
	case Lisp_Misc_Buffer_Local_Value:
	case Lisp_Misc_Some_Buffer_Local_Value:
	  {
	    register struct Lisp_Buffer_Local_Value *ptr
	      = XBUFFER_LOCAL_VALUE (obj);
	    /* If the cdr is nil, avoid recursion for the car.  */
	    if (EQ (ptr->cdr, Qnil))
	      {
		obj = ptr->realvalue;
		goto loop;
	      }
	    mark_object (ptr->realvalue);
	    mark_object (ptr->buffer);
	    mark_object (ptr->frame);
	    obj = ptr->cdr;
	    goto loop;
	  }

	case Lisp_Misc_Marker:
	  /* DO NOT mark thru the marker's chain.
	     The buffer's markers chain does not preserve markers from gc;
	     instead, markers are removed from the chain when freed by gc.  */
	  break;

	case Lisp_Misc_Intfwd:
	case Lisp_Misc_Boolfwd:
	case Lisp_Misc_Objfwd:
	case Lisp_Misc_Buffer_Objfwd:

	     since all markable slots in current buffer marked anyway.  */
	  /* Don't need to do Lisp_Objfwd, since the places they point
	     are protected with staticpro.  */
	  break;

	case Lisp_Misc_Save_Value:
#if GC_MARK_STACK
	  {
	    register struct Lisp_Save_Value *ptr = XSAVE_VALUE (obj);
	    /* If DOGC is set, POINTER is the address of a memory
	       area containing INTEGER potential Lisp_Objects.  */
	    if (ptr->dogc)
	      {
		Lisp_Object *p = (Lisp_Object *) ptr->pointer;
		int nelt;
		for (nelt = ptr->integer; nelt > 0; nelt--, p++)
		  mark_maybe_object (*p);
	      }
	  }
#endif
	  break;

	case Lisp_Misc_Overlay:
	  {
	    struct Lisp_Overlay *ptr = XOVERLAY (obj);
	    mark_object (ptr->start);
	    mark_object (ptr->end);
	    mark_object (ptr->plist);
	    if (ptr->next)
	      {
		XSETMISC (obj, ptr->next);
		goto loop;
	      }
	  }
	  break;

      break;

    case Lisp_Cons:
      {
	register struct Lisp_Cons *ptr = XCONS (obj);
	if (CONS_MARKED_P (ptr)) break;
	CHECK_ALLOCATED_AND_LIVE (live_cons_p);
	CONS_MARK (ptr);
	/* If the cdr is nil, avoid recursion for the car.  */
	if (EQ (ptr->u.cdr, Qnil))
	  {
	    obj = ptr->car;
	    cdr_count = 0;
	    goto loop;
	  }
	mark_object (ptr->car);
	obj = ptr->u.cdr;
	cdr_count++;
	if (cdr_count == mark_object_loop_halt)
	  abort ();
	goto loop;
      }

    case Lisp_Float:
      CHECK_ALLOCATED_AND_LIVE (live_float_p);
      FLOAT_MARK (XFLOAT (obj));
      break;

    case Lisp_Int:
      break;

static void
mark_buffer (buf)
     Lisp_Object buf;
{
  register struct buffer *buffer = XBUFFER (buf);
  register Lisp_Object *ptr, tmp;
  Lisp_Object base_buffer;

  VECTOR_MARK (buffer);

  MARK_INTERVAL_TREE (BUF_INTERVALS (buffer));

  /* For now, we just don't mark the undo_list.  It's done later in
     a special way just before the sweep phase, and after stripping
     some of its elements that are not needed any more.  */

  if (buffer->overlays_before)
    {
      XSETMISC (tmp, buffer->overlays_before);
      mark_object (tmp);
    }
  if (buffer->overlays_after)
    {
      XSETMISC (tmp, buffer->overlays_after);
      mark_object (tmp);
    }

  for (ptr = &buffer->name;
       (char *)ptr < (char *)buffer + sizeof (struct buffer);
       ptr++)
    mark_object (*ptr);

  /* If this is an indirect buffer, mark its base buffer.  */
  if (buffer->base_buffer && !VECTOR_MARKED_P (buffer->base_buffer))
    {
      XSETBUFFER (base_buffer, buffer->base_buffer);
      mark_buffer (base_buffer);
    }
}


/* Value is non-zero if OBJ will survive the current GC because it's

    case Lisp_Int:
      survives_p = 1;
      break;

    case Lisp_Symbol:
      survives_p = XSYMBOL (obj)->gcmarkbit;
      break;

    case Lisp_Misc:
      survives_p = XMARKER (obj)->gcmarkbit;
      break;

    case Lisp_String:
      survives_p = STRING_MARKED_P (XSTRING (obj));
      break;

    case Lisp_Vectorlike:
      survives_p = GC_SUBRP (obj) || VECTOR_MARKED_P (XVECTOR (obj));
      break;

    case Lisp_Cons:
      survives_p = CONS_MARKED_P (XCONS (obj));
      break;

    case Lisp_Float:
      survives_p = FLOAT_MARKED_P (XFLOAT (obj));
      break;

    default:
      abort ();
    }

    for (cblk = cons_block; cblk; cblk = *cprev)
      {
	register int i;
	int this_free = 0;
	for (i = 0; i < lim; i++)
	  if (!CONS_MARKED_P (&cblk->conses[i]))
	    {
	      this_free++;
	      cblk->conses[i].u.chain = cons_free_list;
	      cons_free_list = &cblk->conses[i];
#if GC_MARK_STACK
	      cons_free_list->car = Vdead;
#endif
	    }
	  else
	    {
	      num_used++;
	      CONS_UNMARK (&cblk->conses[i]);
	    }
	lim = CONS_BLOCK_SIZE;
	/* If this block contains only free conses and we have already
	   seen more than two blocks worth of free conses then deallocate
	   this block.  */
	if (this_free == CONS_BLOCK_SIZE && num_free > CONS_BLOCK_SIZE)
	  {
	    *cprev = cblk->next;
	    /* Unhook from the free list.  */
	    cons_free_list = cblk->conses[0].u.chain;
	    lisp_align_free (cblk);
	    n_cons_blocks--;
	  }
	else
	  {
	    num_free += this_free;

    for (fblk = float_block; fblk; fblk = *fprev)
      {
	register int i;
	int this_free = 0;
	for (i = 0; i < lim; i++)
	  if (!FLOAT_MARKED_P (&fblk->floats[i]))
	    {
	      this_free++;
	      fblk->floats[i].u.chain = float_free_list;
	      float_free_list = &fblk->floats[i];
	    }
	  else
	    {
	      num_used++;
	      FLOAT_UNMARK (&fblk->floats[i]);
	    }
	lim = FLOAT_BLOCK_SIZE;
	/* If this block contains only free floats and we have already
	   seen more than two blocks worth of free floats then deallocate
	   this block.  */
	if (this_free == FLOAT_BLOCK_SIZE && num_free > FLOAT_BLOCK_SIZE)
	  {
	    *fprev = fblk->next;
	    /* Unhook from the free list.  */
	    float_free_list = fblk->floats[0].u.chain;
	    lisp_align_free (fblk);
	    n_float_blocks--;
	  }
	else
	  {
	    num_free += this_free;

	register int i;
	int this_free = 0;

	for (i = 0; i < lim; i++)
	  {
	    if (!iblk->intervals[i].gcmarkbit)
	      {
		SET_INTERVAL_PARENT (&iblk->intervals[i], interval_free_list);
		interval_free_list = &iblk->intervals[i];
		this_free++;
	      }
	    else
	      {
		num_used++;
		iblk->intervals[i].gcmarkbit = 0;
	      }
	  }
	lim = INTERVAL_BLOCK_SIZE;
	/* If this block contains only free intervals and we have already
	   seen more than two blocks worth of free intervals then

	    /* Check if the symbol was created during loadup.  In such a case
	       it might be pointed to by pure bytecode which we don't trace,
	       so we conservatively assume that it is live.  */
	    int pure_p = PURE_POINTER_P (XSTRING (sym->xname));

	    if (!sym->gcmarkbit && !pure_p)
	      {
		sym->next = symbol_free_list;
		symbol_free_list = sym;
#if GC_MARK_STACK
		symbol_free_list->function = Vdead;
#endif
		++this_free;

	    else
	      {
		++num_used;
		if (!pure_p)
		  UNMARK_STRING (XSTRING (sym->xname));
		sym->gcmarkbit = 0;
	      }
	  }

	lim = SYMBOL_BLOCK_SIZE;
	/* If this block contains only free symbols and we have already

	   this block.  */
	if (this_free == SYMBOL_BLOCK_SIZE && num_free > SYMBOL_BLOCK_SIZE)
	  {
	    *sprev = sblk->next;
	    /* Unhook from the free list.  */
	    symbol_free_list = sblk->symbols[0].next;
	    lisp_free (sblk);
	    n_symbol_blocks--;
	  }
	else
	  {

    for (mblk = marker_block; mblk; mblk = *mprev)
      {
	register int i;
	int this_free = 0;

	for (i = 0; i < lim; i++)
	  {
	    if (!mblk->markers[i].u_marker.gcmarkbit)
	      {
		if (mblk->markers[i].u_marker.type == Lisp_Misc_Marker)
		  unchain_marker (&mblk->markers[i].u_marker);
		/* Set the type of the freed object to Lisp_Misc_Free.
		   We could leave the type alone, since nobody checks it,
		   but this might catch bugs faster.  */
		mblk->markers[i].u_marker.type = Lisp_Misc_Free;
		mblk->markers[i].u_free.chain = marker_free_list;

		this_free++;
	      }
	    else
	      {
		num_used++;
		mblk->markers[i].u_marker.gcmarkbit = 0;
	      }
	  }
	lim = MARKER_BLOCK_SIZE;
	/* If this block contains only free markers and we have already
	   seen more than two blocks worth of free markers then deallocate

  /* Free all unmarked buffers */
  {
    register struct buffer *buffer = all_buffers, *prev = 0, *next;

    while (buffer)
      if (!VECTOR_MARKED_P (buffer))
	{
	  if (prev)
	    prev->next = buffer->next;
	  else
	    all_buffers = buffer->next;

	  lisp_free (buffer);
	  buffer = next;
	}
      else
	{
	  VECTOR_UNMARK (buffer);
	  UNMARK_BALANCE_INTERVALS (BUF_INTERVALS (buffer));
	  prev = buffer, buffer = buffer->next;
	}
  }

  {
    register struct Lisp_Vector *vector = all_vectors, *prev = 0, *next;
    total_vector_size = 0;

    while (vector)
      if (!VECTOR_MARKED_P (vector))
	{
	  if (prev)
	    prev->next = vector->next;
	  else
	    all_vectors = vector->next;

	  vector = next;

	}
      else
	{
	  VECTOR_UNMARK (vector);
	  if (vector->size & PSEUDOVECTOR_FLAG)
	    total_vector_size += (PSEUDOVECTOR_SIZE_MASK & vector->size);
	  else
	    total_vector_size += vector->size;
	  prev = vector, vector = vector->next;

  purebeg = PUREBEG;
  pure_size = PURESIZE;
  pure_bytes_used = 0;
  pure_bytes_used_before_overflow = 0;

  /* Initialize the list of free aligned blocks.  */
  free_ablock = NULL;

#if GC_MARK_STACK || defined GC_MALLOC_CHECK
  mem_init ();
  Vdead = make_pure_string ("DEAD", 4, 4, 0);
#endif

  malloc_hysteresis = 32;
#else
  malloc_hysteresis = 0;
#endif

  refill_memory_reserve ();

  ignore_warnings = 0;
  gcprolist = 0;
  byte_stack_list = 0;
  staticidx = 0;
  consing_since_gc = 0;
  gc_cons_threshold = 100000 * sizeof (Lisp_Object);
  gc_relative_threshold = 0;

#ifdef VIRT_ADDR_VARIES
  malloc_sbrk_unused = 1<<22;	/* A large number */
  malloc_sbrk_used = 100000;	/* as reasonable as any number */
#endif /* VIRT_ADDR_VARIES */
}

allocated since the last garbage collection.  All data types count.

Garbage collection happens automatically only when `eval' is called.

By binding this temporarily to a large number, you can effectively
prevent garbage collection during a part of the program.
See also `gc-cons-percentage'.  */);

  DEFVAR_LISP ("gc-cons-percentage", &Vgc_cons_percentage,
	       doc: /* *Portion of the heap used for allocation.
Garbage collection can happen automatically once this portion of the heap
has been allocated since the last garbage collection.
If this portion is smaller than `gc-cons-threshold', this is ignored.  */);
  Vgc_cons_percentage = make_float (0.1);

  DEFVAR_INT ("pure-bytes-used", &pure_bytes_used,
	      doc: /* Number of bytes of sharable Lisp data allocated so far.  */);

  DEFVAR_INT ("cons-cells-consed", &cons_cells_consed,

	      doc: /* Number of strings that have been consed so far.  */);

  DEFVAR_LISP ("purify-flag", &Vpurify_flag,
	       doc: /* Non-nil means loading Lisp code in order to dump an executable.
This means that certain objects should be allocated in shared (pure) space.  */);

  DEFVAR_BOOL ("garbage-collection-messages", &garbage_collection_messages,
	       doc: /* Non-nil means display messages at start and end of garbage collection.  */);
  garbage_collection_messages = 0;

  Vmemory_signal_data
    = list2 (Qerror,
	     build_string ("Memory exhausted--use M-x save-some-buffers then exit and restart Emacs"));

  DEFVAR_LISP ("memory-full", &Vmemory_full,
	       doc: /* Non-nil means Emacs cannot get much more Lisp memory.  */);
  Vmemory_full = Qnil;

  staticpro (&Qgc_cons_threshold);
  Qgc_cons_threshold = intern ("gc-cons-threshold");

  staticpro (&Qchar_table_extra_slots);
  Qchar_table_extra_slots = intern ("char-table-extra-slots");

  DEFVAR_LISP ("gc-elapsed", &Vgc_elapsed,
	       doc: /* Accumulated time elapsed in garbage collections.
The time is in seconds as a floating point value.  */);
  DEFVAR_INT ("gcs-done", &gcs_done,
	      doc: /* Accumulated number of garbage collections done.  */);

  defsubr (&Scons);
  defsubr (&Slist);
  defsubr (&Svector);
  defsubr (&Smake_byte_code);

#if GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES
  defsubr (&Sgc_status);
#endif
}

/* arch-tag: 6695ca10-e3c5-4c2c-8bc3-ed26a7dda857
   (do not change this comment) */