/*
 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
 * Copyright (c) 1991, 1992 by Xerox Corporation.  All rights reserved.

 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
 * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
 *
 * Permission is hereby granted to copy this garbage collector for any purpose,
 * provided the above notices are retained on all copies.
 */
# define I←HIDE←POINTERS
# include "gc.h"
# include "gc←private.h"
# ifdef ←←STDC←←
    typedef void * void←star;
# else
    typedef char * void←star;
# endif

# define LOG←TSIZE 7
# define TSIZE (1 << LOG←TSIZE)
# define HASH(addr) \
    ((((word)(addr) >> 3) ↑ ((word)(addr) >> (3+LOG←TSIZE))) \
    & (TSIZE - 1))
    
static struct disappearing←link {
    word dl←hidden←base;	/* Pointer to object base	*/
    word dl←offset;	/* byte offset within object.	*/
    struct disappearing←link * dl←next;
} * dl←head[TSIZE] = {0};

static struct finalizable←object {
    word fo←hidden←base;	/* Pointer to object base	*/
    GC←finalization←proc fo←fn;	/* Finalizer.			*/
    ptr←t fo←client←data;
    word fo←object←size;	/* In bytes.			*/
    struct finalizable←object * fo←next;
} * fo←head[TSIZE] = {0};

# define ALLOC(x, t) t *x = (t *)GC←malloc(sizeof (t))

int GC←register←disappearing←link(link)
void←star * link;
{
    ptr←t base;
    unsigned long offset;
    struct disappearing←link *curr←dl;
    int index;
    /* Allocate before acquiring lock */
      ALLOC(new←dl, struct disappearing←link);
    DCL←LOCK←STATE;
      
    DISABLE←SIGNALS();
    LOCK();
    base = (ptr←t)GC←base((void←star)link);
    index = HASH(base);
    offset = (ptr←t)link - base;
    if (base == 0 || ((word)link & (ALIGNMENT-1)))
    		ABORT("Bad arg to GC←register←disappearing←link");
    curr←dl = dl←head[index];
    for (curr←dl = dl←head[index]; curr←dl != 0; curr←dl = curr←dl -> dl←next) {
        if (curr←dl -> dl←hidden←base == HIDE←POINTER(base)
            && curr←dl -> dl←offset == offset) {
            UNLOCK();
    	    ENABLE←SIGNALS();
    	    GC←free((extern←ptr←t)new←dl);
            return(1);
        }
    }
    {
        new←dl -> dl←hidden←base = HIDE←POINTER(base);
        new←dl -> dl←offset = offset;
        new←dl -> dl←next = dl←head[index];
        dl←head[index] = new←dl;
        UNLOCK();
        ENABLE←SIGNALS();
        return(0);
    }
}


int GC←unregister←disappearing←link(link)
void←star * link;
{
    ptr←t base;
    unsigned long offset;
    struct disappearing←link *curr←dl, *prev←dl;
    int index;
    DCL←LOCK←STATE;
    
    DISABLE←SIGNALS();
    LOCK();
    base = (ptr←t)GC←base((void←star)link);
    index = HASH(base);
    offset = (ptr←t)link - base;
    if (base == 0 || ((unsigned long)link & (ALIGNMENT-1)))
    	return(0);
    prev←dl = 0; curr←dl = dl←head[index];
    while (curr←dl != 0) {
        if (curr←dl -> dl←hidden←base == HIDE←POINTER(base)
            && curr←dl -> dl←offset == offset) {
            if (prev←dl == 0) {
                dl←head[index] = curr←dl -> dl←next;
            } else {
               prev←dl -> dl←next = curr←dl -> dl←next;
            }
            UNLOCK();
    	    ENABLE←SIGNALS();
            GC←free((extern←ptr←t)curr←dl);
            return(1);
        }
        curr←dl = curr←dl -> dl←next;
        prev←dl = curr←dl;
    }
    UNLOCK();
    ENABLE←SIGNALS();
    return(0);
}

bool GC←is←marked(p)
ptr←t p;
{
    register struct hblk *h = HBLKPTR(p);
    register hdr * hhdr = HDR(h);
    register int word←no = (word *)p - (word *)h;
    
    return(mark←bit←from←hdr(hhdr, word←no));
}

void GC←set←mark←bit(p)
ptr←t p;
{
    register struct hblk *h = HBLKPTR(p);
    register hdr * hhdr = HDR(h);
    register int word←no = (word *)p - (word *)h;
    
    set←mark←bit←from←hdr(hhdr, word←no);
}

void GC←clear←mark←bit(p)
ptr←t p;
{
    register struct hblk *h = HBLKPTR(p);
    register hdr * hhdr = HDR(h);
    register int word←no = (word *)p - (word *)h;
    
    clear←mark←bit←from←hdr(hhdr, word←no);
}

void GC←register←finalizer(obj, fn, cd, ofn, ocd)
void←star obj;
GC←finalization←proc fn;
void←star cd;
GC←finalization←proc * ofn;
void←star * ocd;
{
    ptr←t base;
    struct finalizable←object * curr←fo, * prev←fo;
    int index;
    /* Allocate before acquiring lock */
      ALLOC(new←fo, struct finalizable←object);
    DCL←LOCK←STATE;
    
    DISABLE←SIGNALS();
    LOCK();
    base = (ptr←t)GC←base((void←star)obj);
    index = HASH(base);
    if (base != obj)
    		ABORT("Bad arg to GC←register←finalizer");
    prev←fo = 0; curr←fo = fo←head[index];
    while (curr←fo != 0) {
        if (curr←fo -> fo←hidden←base == HIDE←POINTER(base)) {
            if (ofn) *ofn = curr←fo -> fo←fn;
            if (ocd) *ocd = (void←star) curr←fo -> fo←client←data;
            if (fn == 0) {
                /* Delete the structure for base. */
                  if (prev←fo == 0) {
                    fo←head[index] = curr←fo -> fo←next;
                  } else {
                    prev←fo -> fo←next = curr←fo -> fo←next;
                  }
                  UNLOCK();
    	    	  ENABLE←SIGNALS();
                  GC←free((extern←ptr←t)curr←fo);
            } else {
                curr←fo -> fo←fn = fn;
                curr←fo -> fo←client←data = (ptr←t)cd;
                UNLOCK();
    	    	ENABLE←SIGNALS();
            }
            GC←free((extern←ptr←t)new←fo);
            return;
        }
        curr←fo = curr←fo -> fo←next;
        prev←fo = curr←fo;
    }
    {
        if (ofn) *ofn = 0;
        if (ocd) *ocd = 0;
        if (fn == 0) {
            UNLOCK();
    	    ENABLE←SIGNALS();
    	    GC←free((extern←ptr←t)new←fo);
            return;
        }
        new←fo -> fo←hidden←base = (word)HIDE←POINTER(base);
        new←fo -> fo←fn = fn;
        new←fo -> fo←client←data = (ptr←t)cd;
        new←fo -> fo←object←size = GC←size(base);
        new←fo -> fo←next = fo←head[index];
        fo←head[index] = new←fo;
    }
    UNLOCK();
    ENABLE←SIGNALS();
}

/* Called with world stopped.  Cause disappearing links to disappear,	*/
/* and invoke finalizers.						*/
void GC←finalize()
{
    struct disappearing←link * curr←dl, * prev←dl, * next←dl;
    struct finalizable←object * curr←fo, * prev←fo, * next←fo;
    ptr←t real←ptr;
    register int i;
    
  /* Make disappearing links disappear */
    for (i = 0; i < TSIZE; i++) {
      curr←dl = dl←head[i];
      prev←dl = 0;
      while (curr←dl != 0) {
        real←ptr = (ptr←t)REVEAL←POINTER(curr←dl -> dl←hidden←base);
        if (!GC←is←marked(real←ptr)) {
            *(word *)(real←ptr + curr←dl -> dl←offset) = 0;
            next←dl = curr←dl -> dl←next;
            if (prev←dl == 0) {
                dl←head[i] = next←dl;
            } else {
                prev←dl -> dl←next = next←dl;
            }
            GC←clear←mark←bit((ptr←t)curr←dl);
            curr←dl = next←dl;
        } else {
            prev←dl = curr←dl;
            curr←dl = curr←dl -> dl←next;
        }
      }
    }
  /* Mark all objects reachable via chains of 1 or more pointers	*/
  /* from finalizable objects.						*/
    for (i = 0; i < TSIZE; i++) {
      for (curr←fo = fo←head[i]; curr←fo != 0; curr←fo = curr←fo -> fo←next) {
        real←ptr = (ptr←t)REVEAL←POINTER(curr←fo -> fo←hidden←base);
        if (!GC←is←marked(real←ptr)) {
            GC←mark←all(real←ptr, real←ptr + curr←fo -> fo←object←size);
        }
        /* 
        if (GC←is←marked(real←ptr)) {
            --> Report finalization cycle here, if desired
        }
        */
      }
    }
  /* Invoke finalization code for all objects that are still		*/
  /* unreachable.							*/
    for (i = 0; i < TSIZE; i++) {
      curr←fo = fo←head[i];
      prev←fo = 0;
      while (curr←fo != 0) {
        real←ptr = (ptr←t)REVEAL←POINTER(curr←fo -> fo←hidden←base);
        if (!GC←is←marked(real←ptr)) {
            (*(curr←fo -> fo←fn))(real←ptr, curr←fo -> fo←client←data);
            GC←set←mark←bit(real←ptr);
            next←fo = curr←fo -> fo←next;
            if (prev←fo == 0) {
                fo←head[i] = next←fo;
            } else {
                prev←fo -> fo←next = next←fo;
            }
            if (!GC←is←marked((ptr←t)curr←fo)) {
                ABORT("GC←finalize: found accessible unmarked object\n");
            }
            GC←clear←mark←bit((ptr←t)curr←fo);
            curr←fo = next←fo;
        } else {
            prev←fo = curr←fo;
            curr←fo = curr←fo -> fo←next;
        }
      }
    }
}

# ifdef ←←STDC←←
    void←star GC←call←with←alloc←lock(GC←fn←type fn, void←star client←data)
# else
    void←star GC←call←with←alloc←lock(fn, client←data)
    GC←fn←type fn;
    void←star client←data;
# endif
{
    DCL←LOCK←STATE;
    
    DISABLE←SIGNALS();
    LOCK();
    (*fn)(client←data);
    UNLOCK();
    ENABLE←SIGNALS();
}