[Patches] Updated GC patch

Neil Schemenauer nascheme@enme.ucalgary.ca
Mon, 5 Jun 2000 11:39:27 -0600


On Mon, Jun 05, 2000 at 12:43:45AM -0400, Jeremy Hylton wrote:
> I would like to check the patch in soon but I have had some trouble
> with segfaults.

I found the problem.  Here is a new patch for the current CVS
sources.  Something to note in this version is that with GC
enabled PyObject_{NEW, NEW_VAR, DEL} do not know about objects
prefixed with PyGCInfo.  If an object is involved with GC it must
use PyObject_{New, NewVar, Del} or PyGC_{NEW, NEW_VAR, DEL}.
Extension types should always use the PyObject functions so that
they work with both GC enabled and regular interpreters.

    Neil


Index: 0.6/config.h.in
--- 0.6/config.h.in Mon, 05 Jun 2000 00:51:28 -0600 nas (python/3_config.h.i 1.1.2.2 644)
+++ gc.8(w)/config.h.in Mon, 05 Jun 2000 02:09:43 -0600 nas (python/3_config.h.i 1.1.2.2 644)
@@ -210,6 +210,9 @@
    (shared library plus accessory files). */
 #undef WITH_NEXT_FRAMEWORK
 
+/* Define if you want cycle garbage collection */
+#undef WITH_CYCLE_GC
+
 /* The number of bytes in an off_t. */
 #undef SIZEOF_OFF_T
 
Index: 0.6/configure.in
--- 0.6/configure.in Mon, 05 Jun 2000 00:51:28 -0600 nas (python/5_configure. 1.1.2.2 644)
+++ gc.8(w)/configure.in Mon, 05 Jun 2000 02:09:43 -0600 nas (python/5_configure. 1.1.2.2 644)
@@ -1083,6 +1083,17 @@
 fi],
 [AC_MSG_RESULT(no)])
 
+# Check for GC support
+AC_SUBST(USE_GC_MODULE)
+USE_GC_MODULE="#"
+AC_MSG_CHECKING(for --with-cycle-gc)
+AC_ARG_WITH(cycle-gc, [--with-cycle-gc           enable garbage collection], [
+AC_MSG_RESULT($withval)
+AC_DEFINE(WITH_CYCLE_GC)
+USE_GC_MODULE=
+],
+AC_MSG_RESULT(no))
+
 # THIS MUST BE LAST, IT CAN BREAK OTHER TESTS!
 # Add sys/socket.h to confdefs.h
 cat >> confdefs.h <<\EOF
Index: 0.6/Include/object.h
--- 0.6/Include/object.h Tue, 25 Apr 2000 17:33:19 -0600 nas (python/o/18_object.h 1.1 644)
+++ gc.8(w)/Include/object.h Mon, 05 Jun 2000 02:09:43 -0600 nas (python/o/18_object.h 1.1.1.1 644)
@@ -145,6 +145,8 @@
 typedef int (*getsegcountproc) Py_PROTO((PyObject *, int *));
 typedef int (*getcharbufferproc) Py_PROTO((PyObject *, int, const char **));
 typedef int (*objobjproc) Py_PROTO((PyObject *, PyObject *));
+typedef int (*visitproc) Py_PROTO((PyObject *, void *));
+typedef int (*recurseproc) Py_PROTO((PyObject *, visitproc, void *));
 
 typedef struct {
 	binaryfunc nb_add;
@@ -243,9 +245,13 @@
 
 	char *tp_doc; /* Documentation string */
 
+	/* call function for all accessible objects */
+	recurseproc tp_recurse;
+	
+	/* delete references to contained objects */
+	inquiry tp_clear;
+
 	/* More spares */
-	long tp_xxx5;
-	long tp_xxx6;
 	long tp_xxx7;
 	long tp_xxx8;
 
@@ -318,6 +324,9 @@
 
 /* PySequenceMethods contains sq_contains */
 #define Py_TPFLAGS_HAVE_SEQUENCE_IN (1L<<1)
+
+/* Objects with a GC info prefix (allocated *before* the object itself!) */
+#define Py_TPFLAGS_HAVE_GCINFO (1L<<2)
 
 #define Py_TPFLAGS_DEFAULT  (Py_TPFLAGS_HAVE_GETCHARBUFFER | \
                              Py_TPFLAGS_HAVE_SEQUENCE_IN)
Index: 0.6/Include/objimpl.h
--- 0.6/Include/objimpl.h Mon, 08 May 2000 12:24:03 -0600 nas (python/o/19_objimpl.h 1.1.2.1 644)
+++ gc.8(w)/Include/objimpl.h Mon, 05 Jun 2000 03:53:50 -0600 nas (python/o/19_objimpl.h 1.1.2.1 644)
@@ -233,6 +233,66 @@
    Note that in C++, the use of the new operator usually implies that
    the 1st step is performed automatically for you, so in a C++ class
    constructor you would start directly with PyObject_Init/InitVar. */
+
+
+#ifdef WITH_CYCLE_GC
+
+/*
+ * Garbage Collection Support
+ * ==========================
+ */
+
+/* To make a new object participate in garbage collection use
+   PyObject_{New, VarNew, Del} to manage the memory.  Set the type flag
+   Py_TPFLAGS_HAVE_GCINFO and define the type method tp_recurse.  Call
+   PyGC_Insert after all the pointers followed by tp_recurse become
+   valid (usually just before returning the object from the allocation
+   method.  Call PyGC_Remove before those pointers become invalid
+   (usually at the top of the deallocation method).  Do not use
+   PyObject_{NEW, NEW_VAR, DEL} on GC objects. */
+
+/* These macros should only be used within the interpreter. */
+#define PyGC_NEW(type, typeobj) PyObject_New(type, typeobj)
+#define PyGC_NEW_VAR(type, typeobj, n) PyObject_NewVar(type, typeobj, n)
+#define PyGC_DEL(op) PyObject_Del((PyObject *)(op))
+
+/* Structure *prefixed* to container objects participating in GC */ 
+typedef struct _gcinfo {
+	struct _gcinfo *gc_next;
+	struct _gcinfo *gc_prev;
+	int gc_refs;
+} PyGCInfo;
+
+/* Add the object into the container set */
+extern DL_IMPORT(void) PyGC_Insert Py_PROTO((PyObject *));
+
+/* Remove the object from the container set */
+extern DL_IMPORT(void) PyGC_Remove Py_PROTO((PyObject *));
+
+/* Test if a type has GC info */
+#define PyGC_TYPE_HAS_INFO(t) PyType_HasFeature((t), Py_TPFLAGS_HAVE_GCINFO)
+
+/* Test if an object has GC info */
+#define PyGC_HAS_INFO(o) PyGC_TYPE_HAS_INFO((o)->ob_type)
+
+/* Get an object's GC info -- NULL if the object has none */
+#define PyGC_INFO(o) (PyGC_HAS_INFO(o) ? ((PyGCInfo *)(o)-1) : NULL)
+
+/* Unsafe version of PyGC_INFO() -- only call if PyGC_HAS_INFO(p) is true */
+#define PyGC_INFO_UNSAFE(o) ((PyGCInfo *)(o)-1)
+
+/* Get the object given the PyGCInfo */
+#define PyGC_OBJ(g) ((PyObject *)((g)+1))
+
+#else /* ! WITH_CYCLE_GC */
+
+#define PyGC_NEW PyObject_NEW
+#define PyGC_NEW_VAR PyObject_NEW_VAR
+#define PyGC_DEL PyObject_DEL
+#define PyGC_Insert
+#define PyGC_Remove
+
+#endif /* WITH_CYCLE_GC */
 
 #ifdef __cplusplus
 }
Index: 0.6/Modules/Setup.thread.in
--- 0.6/Modules/Setup.thread.in Tue, 25 Apr 2000 17:33:19 -0600 nas (python/C/19_Setup.thre 1.1 644)
+++ gc.8(w)/Modules/Setup.thread.in Mon, 05 Jun 2000 02:07:03 -0600 nas (python/C/19_Setup.thre 1.1 644)
@@ -9,3 +9,6 @@
 # support threads.
 
 @USE_THREAD_MODULE@thread threadmodule.c
+
+# Garbage collection enabled with --with-cycle-gc
+@USE_GC_MODULE@gc gcmodule.c
Index: 0.6/Modules/cPickle.c
--- 0.6/Modules/cPickle.c Mon, 05 Jun 2000 00:51:28 -0600 nas (python/C/27_cPickle.c 1.1.2.2 644)
+++ gc.8(w)/Modules/cPickle.c Mon, 05 Jun 2000 02:22:18 -0600 nas (python/C/27_cPickle.c 1.1.2.2 644)
@@ -2893,7 +2893,7 @@
                 Py_DECREF(inst);
                 goto err;
               }
-
+              PyGC_Insert((PyObject *)inst);
               return (PyObject *)inst;
             }
           Py_DECREF(__getinitargs__);
Index: 0.6/Modules/newmodule.c
--- 0.6/Modules/newmodule.c Mon, 08 May 2000 12:24:03 -0600 nas (python/D/13_newmodule. 1.1.2.1 644)
+++ gc.8(w)/Modules/newmodule.c Mon, 05 Jun 2000 02:22:37 -0600 nas (python/D/13_newmodule. 1.1.2.1 644)
@@ -56,6 +56,7 @@
 	Py_INCREF(dict);
 	inst->in_class = (PyClassObject *)klass;
 	inst->in_dict = dict;
+	PyGC_Insert((PyObject *)inst);
 	return (PyObject *)inst;
 }
 
Index: 0.6/Objects/classobject.c
--- 0.6/Objects/classobject.c Mon, 08 May 2000 12:24:03 -0600 nas (python/E/16_classobjec 1.1.2.2 644)
+++ gc.8(w)/Objects/classobject.c Mon, 05 Jun 2000 02:09:43 -0600 nas (python/E/16_classobjec 1.1.2.2 644)
@@ -111,7 +111,7 @@
 		}
 		Py_INCREF(bases);
 	}
-	op = PyObject_NEW(PyClassObject, &PyClass_Type);
+	op = PyGC_NEW(PyClassObject, &PyClass_Type);
 	if (op == NULL) {
 		Py_DECREF(bases);
 		return NULL;
@@ -132,6 +132,7 @@
 	Py_XINCREF(op->cl_getattr);
 	Py_XINCREF(op->cl_setattr);
 	Py_XINCREF(op->cl_delattr);
+	PyGC_Insert((PyObject *)op);
 	return (PyObject *) op;
 }
 
@@ -141,13 +142,14 @@
 class_dealloc(op)
 	PyClassObject *op;
 {
+	PyGC_Remove((PyObject *)op);
 	Py_DECREF(op->cl_bases);
 	Py_DECREF(op->cl_dict);
 	Py_XDECREF(op->cl_name);
 	Py_XDECREF(op->cl_getattr);
 	Py_XDECREF(op->cl_setattr);
 	Py_XDECREF(op->cl_delattr);
-	PyObject_DEL(op);
+	PyGC_DEL(op);
 }
 
 static PyObject *
@@ -387,6 +389,21 @@
 	return res;
 }
 
+#ifdef WITH_CYCLE_GC
+static int
+class_recurse(PyClassObject *o, visitproc visit, void *closure)
+{
+	if (o->cl_bases) visit(o->cl_bases, closure);
+	if (o->cl_dict) visit(o->cl_dict, closure);
+	if (o->cl_name) visit(o->cl_name, closure);
+	if (o->cl_getattr) visit(o->cl_getattr, closure);
+	if (o->cl_setattr) visit(o->cl_setattr, closure);
+	if (o->cl_delattr) visit(o->cl_delattr, closure);
+	return 1;
+}
+#endif /* WITH_CYCLE_GC */
+
+
 PyTypeObject PyClass_Type = {
 	PyObject_HEAD_INIT(&PyType_Type)
 	0,
@@ -407,6 +424,12 @@
 	(reprfunc)class_str, /*tp_str*/
 	(getattrofunc)class_getattr, /*tp_getattro*/
 	(setattrofunc)class_setattr, /*tp_setattro*/
+#ifdef WITH_CYCLE_GC
+	0,		/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GCINFO, /*tp_flags*/
+	0,		/* tp_doc */
+	(recurseproc)class_recurse,	/* tp_recurse */
+#endif
 };
 
 int
@@ -445,12 +468,13 @@
 		PyErr_BadInternalCall();
 		return NULL;
 	}
-	inst = PyObject_NEW(PyInstanceObject, &PyInstance_Type);
+	inst = PyGC_NEW(PyInstanceObject, &PyInstance_Type);
 	if (inst == NULL)
 		return NULL;
 	Py_INCREF(class);
 	inst->in_class = (PyClassObject *)class;
 	inst->in_dict = PyDict_New();
+	PyGC_Insert((PyObject *)inst);
 	if (inst->in_dict == NULL) {
 		Py_DECREF(inst);
 		return NULL;
@@ -498,11 +522,12 @@
 	PyObject *error_type, *error_value, *error_traceback;
 	PyObject *del;
 	static PyObject *delstr;
+	extern long _Py_RefTotal;
+	PyGC_Remove((PyObject *)inst);
 	/* Call the __del__ method if it exists.  First temporarily
 	   revive the object and save the current exception, if any. */
 #ifdef Py_TRACE_REFS
 	/* much too complicated if Py_TRACE_REFS defined */
-	extern long _Py_RefTotal;
 	inst->ob_type = &PyInstance_Type;
 	_Py_NewReference((PyObject *)inst);
 	_Py_RefTotal--;		/* compensate for increment in NEWREF */
@@ -550,6 +575,7 @@
 #ifdef COUNT_ALLOCS
 		inst->ob_type->tp_free--;
 #endif
+		PyGC_Insert((PyObject *)inst);
 		return; /* __del__ added a reference; don't delete now */
 	}
 #ifdef Py_TRACE_REFS
@@ -557,11 +583,13 @@
 	inst->ob_type->tp_free--;	/* compensate for increment in UNREF */
 #endif
 	_Py_ForgetReference((PyObject *)inst);
+#ifndef WITH_CYCLE_GC
 	inst->ob_type = NULL;
+#endif
 #endif /* Py_TRACE_REFS */
 	Py_DECREF(inst->in_class);
 	Py_XDECREF(inst->in_dict);
-	PyObject_DEL(inst);
+	PyGC_DEL(inst);
 }
 
 static PyObject *
@@ -849,6 +877,16 @@
 	return outcome;
 }
 
+#ifdef WITH_CYCLE_GC
+static int
+instance_recurse(PyInstanceObject *o, visitproc visit, void *closure)
+{
+	if (o->in_class) visit((PyObject *)(o->in_class), closure);
+	if (o->in_dict) visit(o->in_dict, closure);
+	return 1;
+}
+#endif /* WITH_CYCLE_GC */
+
 static PyObject *getitemstr, *setitemstr, *delitemstr, *lenstr;
 
 static int
@@ -1472,7 +1510,13 @@
 	(getattrofunc)instance_getattr, /*tp_getattro*/
 	(setattrofunc)instance_setattr, /*tp_setattro*/
         0, /* tp_as_buffer */
-	Py_TPFLAGS_DEFAULT, /*tp_flags */
+#ifndef WITH_CYCLE_GC
+	Py_TPFLAGS_DEFAULT, /*tp_flags*/
+#else
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GCINFO, /*tp_flags*/
+	0,		/* tp_doc */
+	(recurseproc)instance_recurse,	/* tp_recurse */
+#endif
 };
 
 
Index: 0.6/Objects/dictobject.c
--- 0.6/Objects/dictobject.c Mon, 08 May 2000 12:24:03 -0600 nas (python/E/19_dictobject 1.1.2.1 644)
+++ gc.8(w)/Objects/dictobject.c Mon, 05 Jun 2000 03:34:06 -0600 nas (python/E/19_dictobject 1.1.2.1 644)
@@ -121,7 +121,7 @@
 		if (dummy == NULL)
 			return NULL;
 	}
-	mp = PyObject_NEW(dictobject, &PyDict_Type);
+	mp = PyGC_NEW(dictobject, &PyDict_Type);
 	if (mp == NULL)
 		return NULL;
 	mp->ma_size = 0;
@@ -129,6 +129,7 @@
 	mp->ma_table = NULL;
 	mp->ma_fill = 0;
 	mp->ma_used = 0;
+	PyGC_Insert((PyObject *)mp);
 	return (PyObject *)mp;
 }
 
@@ -481,6 +482,7 @@
 	register int i;
 	register dictentry *ep;
 	Py_TRASHCAN_SAFE_BEGIN(mp)
+	PyGC_Remove((PyObject *)mp);
 	for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
 		if (ep->me_key != NULL) {
 			Py_DECREF(ep->me_key);
@@ -491,7 +493,7 @@
 	}
 	if (mp->ma_table != NULL)
 		PyMem_DEL(mp->ma_table);
-	PyObject_DEL(mp);
+	PyGC_DEL(mp);
 	Py_TRASHCAN_SAFE_END(mp)
 }
 
@@ -1038,6 +1040,33 @@
 	return Py_None;
 }
 
+#ifdef WITH_CYCLE_GC
+static int
+dict_recurse(PyObject *op, visitproc visit, void *closure)
+{
+	int i = 0;
+	PyObject *pk;
+	PyObject *pv;
+
+	while (PyDict_Next(op, &i, &pk, &pv)) {
+		if (!visit(pk, closure)) {
+			return 0;
+		}
+		if (!visit(pv, closure)) {
+			return 0;
+		}
+	}
+	return 1;
+}
+
+static int
+dict_gc_clear(PyObject *op)
+{
+	PyDict_Clear(op);
+	return 0;
+}
+#endif /* WITH_CYCLE_GC */
+
 static PyMethodDef mapp_methods[] = {
 	{"has_key",	(PyCFunction)dict_has_key,      METH_VARARGS},
 	{"keys",	(PyCFunction)dict_keys},
@@ -1073,6 +1102,18 @@
 	0,			/*tp_as_number*/
 	0,			/*tp_as_sequence*/
 	&dict_as_mapping,	/*tp_as_mapping*/
+#ifdef WITH_CYCLE_GC
+	0,		/* tp_hash */
+	0,		/* tp_call */
+	0,		/* tp_str */
+	0,		/* tp_getattro */
+	0,		/* tp_setattro */
+	0,		/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GCINFO, /*tp_flags*/
+	0,		/* tp_doc */
+	(recurseproc)dict_recurse,	/* tp_recurse */
+	(inquiry)dict_gc_clear,		/* tp_clear */
+#endif
 };
 
 /* For backward compatibility with old dictionary interface */
Index: 0.6/Objects/funcobject.c
--- 0.6/Objects/funcobject.c Mon, 08 May 2000 12:24:03 -0600 nas (python/E/23_funcobject 1.1.2.2 644)
+++ gc.8(w)/Objects/funcobject.c Mon, 05 Jun 2000 03:34:30 -0600 nas (python/E/23_funcobject 1.1.2.2 644)
@@ -40,8 +40,7 @@
 	PyObject *code;
 	PyObject *globals;
 {
-	PyFunctionObject *op = PyObject_NEW(PyFunctionObject,
-					    &PyFunction_Type);
+	PyFunctionObject *op = PyGC_NEW(PyFunctionObject, &PyFunction_Type);
 	if (op != NULL) {
 		PyObject *doc;
 		PyObject *consts;
@@ -63,6 +62,7 @@
 		Py_INCREF(doc);
 		op->func_doc = doc;
 	}
+	PyGC_Insert((PyObject *)op);
 	return (PyObject *)op;
 }
 
@@ -186,12 +186,13 @@
 func_dealloc(op)
 	PyFunctionObject *op;
 {
+	PyGC_Remove((PyObject *)op);
 	Py_DECREF(op->func_code);
 	Py_DECREF(op->func_globals);
 	Py_DECREF(op->func_name);
 	Py_XDECREF(op->func_defaults);
 	Py_XDECREF(op->func_doc);
-	PyObject_DEL(op);
+	PyGC_DEL(op);
 }
 
 static PyObject*
@@ -239,6 +240,19 @@
 	return h;
 }
 
+#ifdef WITH_CYCLE_GC
+static int
+func_recurse(PyFunctionObject *f, visitproc visit, void *closure)
+{
+	if (f->func_code) visit(f->func_code, closure);
+	if (f->func_globals) visit(f->func_globals, closure);
+	if (f->func_defaults) visit(f->func_defaults, closure);
+	if (f->func_doc) visit(f->func_doc, closure);
+	if (f->func_name) visit(f->func_name, closure);
+	return 1;
+}
+#endif /* WITH_CYCLE_GC */
+
 PyTypeObject PyFunction_Type = {
 	PyObject_HEAD_INIT(&PyType_Type)
 	0,
@@ -255,4 +269,14 @@
 	0,		/*tp_as_sequence*/
 	0,		/*tp_as_mapping*/
 	(hashfunc)func_hash, /*tp_hash*/
+#ifdef WITH_CYCLE_GC
+	0,		/*tp_call*/
+	0,		/*tp_str*/
+	0,		/*tp_getattro*/
+	0,		/*tp_setattro*/
+	0,		/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GCINFO, /*tp_flags*/
+	0,		/* tp_doc */
+	(recurseproc)func_recurse,	/* tp_recurse */
+#endif
 };
Index: 0.6/Objects/listobject.c
--- 0.6/Objects/listobject.c Mon, 05 Jun 2000 00:51:28 -0600 nas (python/E/25_listobject 1.1.2.3 644)
+++ gc.8(w)/Objects/listobject.c Mon, 05 Jun 2000 03:33:46 -0600 nas (python/E/25_listobject 1.1.2.3 644)
@@ -71,7 +71,15 @@
 		return PyErr_NoMemory();
 	}
 	/* PyObject_NewVar is inlined */
+#ifdef WITH_CYCLE_GC
+	op = (PyListObject *) PyObject_MALLOC(sizeof(PyGCInfo) + 
+						sizeof(PyListObject));
+	if (op != NULL) {
+		op = (PyListObject *) PyGC_OBJ((PyGCInfo *)op);
+	}
+#else
 	op = (PyListObject *) PyObject_MALLOC(sizeof(PyListObject));
+#endif
 	if (op == NULL) {
 		return PyErr_NoMemory();
 	}
@@ -88,6 +96,7 @@
 	PyObject_INIT_VAR(op, &PyList_Type, size);
 	for (i = 0; i < size; i++)
 		op->ob_item[i] = NULL;
+	PyGC_Insert((PyObject *)op);
 	return (PyObject *) op;
 }
 
@@ -215,6 +224,7 @@
 {
 	int i;
 	Py_TRASHCAN_SAFE_BEGIN(op)
+	PyGC_Remove((PyObject *)op);
 	if (op->ob_item != NULL) {
 		/* Do it backwards, for Christian Tismer.
 		   There's a simple test case where somehow this reduces
@@ -226,7 +236,7 @@
 		}
 		PyMem_FREE(op->ob_item);
 	}
-	PyObject_DEL(op);
+	PyGC_DEL(op);
 	Py_TRASHCAN_SAFE_END(op)
 }
 
@@ -1423,6 +1433,29 @@
 	return NULL;
 }
 
+#ifdef WITH_CYCLE_GC
+static int
+list_recurse(PyListObject *o, visitproc visit, void *closure)
+{
+	int i;
+	PyObject *x;
+
+	for (i = o->ob_size; --i >= 0; ) {
+		x = o->ob_item[i];
+		if (x != NULL && !visit(x, closure))
+			return 0;
+	}
+	return 1;
+}
+
+static int
+list_clear(PyListObject *lp)
+{
+	(void) PyList_SetSlice((PyObject *)lp, 0, lp->ob_size, 0);
+	return 0;
+}
+#endif /* WITH_CYCLE_GC */
+
 static char append_doc[] =
 "L.append(object) -- append object to end";
 static char extend_doc[] =
@@ -1489,6 +1522,18 @@
 	0,		/*tp_as_number*/
 	&list_as_sequence,	/*tp_as_sequence*/
 	0,		/*tp_as_mapping*/
+#ifdef WITH_CYCLE_GC
+	0,		/* tp_hash */
+	0,		/* tp_call */
+	0,		/* tp_str */
+	0,		/* tp_getattro */
+	0,		/* tp_setattro */
+	0,		/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GCINFO,	/* tp_flags */
+	0,		/* tp_doc */
+	(recurseproc)list_recurse,	/* tp_recurse */
+	(inquiry)list_clear,	/* tp_clear */
+#endif
 };
 
 
@@ -1557,5 +1602,16 @@
 	0,		/*tp_as_number*/
 	&immutable_list_as_sequence,	/*tp_as_sequence*/
 	0,		/*tp_as_mapping*/
+#ifdef WITH_CYCLE_GC
+	0,		/* tp_hash */
+	0,		/* tp_call */
+	0,		/* tp_str */
+	0,		/* tp_getattro */
+	0,		/* tp_setattro */
+	0,		/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT,	/* tp_flags */
+	0,		/* tp_doc */
+	(recurseproc)list_recurse,	/* tp_recurse */
+#endif
 };
 
Index: 0.6/Objects/object.c
--- 0.6/Objects/object.c Mon, 08 May 2000 12:24:03 -0600 nas (python/E/29_object.c 1.1.1.1 644)
+++ gc.8(w)/Objects/object.c Mon, 05 Jun 2000 03:17:07 -0600 nas (python/E/29_object.c 1.1.1.1 644)
@@ -151,7 +151,21 @@
 	PyTypeObject *tp;
 {
 	PyObject *op;
-	op = (PyObject *) PyObject_MALLOC(_PyObject_SIZE(tp));
+#ifdef WITH_CYCLE_GC
+	if (PyGC_TYPE_HAS_INFO(tp)) {
+		PyGCInfo *g;
+		g = (PyGCInfo *) PyObject_MALLOC(sizeof(*g) +
+						 _PyObject_SIZE(tp));
+		if (g == NULL) {
+			op = NULL;
+		} else {
+			op = PyGC_OBJ(g);
+		}
+	} else 
+#endif
+	{
+		op = (PyObject *) PyObject_MALLOC(_PyObject_SIZE(tp));
+	}
 	if (op == NULL)
 		return PyErr_NoMemory();
 	return PyObject_INIT(op, tp);
@@ -163,7 +177,22 @@
 	int size;
 {
 	PyVarObject *op;
-	op = (PyVarObject *) PyObject_MALLOC(_PyObject_VAR_SIZE(tp, size));
+#ifdef WITH_CYCLE_GC
+	if (PyGC_TYPE_HAS_INFO(tp)) {
+		PyGCInfo *g;
+		g = (PyGCInfo *) PyObject_MALLOC(sizeof(*g) + 
+						 _PyObject_VAR_SIZE(tp, size));
+		if (g == NULL) {
+			op = NULL;
+		} else {
+			op = (PyVarObject *)PyGC_OBJ(g);
+		}
+	} else
+#endif
+	{
+		op = (PyVarObject *)
+			PyObject_MALLOC(_PyObject_VAR_SIZE(tp, size));
+	}
 	if (op == NULL)
 		return (PyVarObject *)PyErr_NoMemory();
 	return PyObject_INIT_VAR(op, tp, size);
@@ -173,7 +202,15 @@
 _PyObject_Del(op)
 	PyObject *op;
 {
-	PyObject_FREE(op);
+#ifdef WITH_CYCLE_GC
+	if (PyGC_TYPE_HAS_INFO(op->ob_type)) {
+		PyGCInfo *g = PyGC_INFO(op);
+		PyObject_FREE(g);
+	} else
+#endif
+	{
+		PyObject_FREE(op);
+	}
 }
 
 int
@@ -845,8 +882,10 @@
 {
 	destructor dealloc = op->ob_type->tp_dealloc;
 	_Py_ForgetReference(op);
+#ifndef WITH_CYCLE_GC
 	if (_PyTrash_delete_nesting < PyTrash_UNWIND_LEVEL-1)
 		op->ob_type = NULL;
+#endif
 	(*dealloc)(op);
 }
 
Index: 0.6/Objects/tupleobject.c
--- 0.6/Objects/tupleobject.c Mon, 05 Jun 2000 00:51:28 -0600 nas (python/E/33_tupleobjec 1.1.2.3 644)
+++ gc.8(w)/Objects/tupleobject.c Mon, 05 Jun 2000 03:31:21 -0600 nas (python/E/33_tupleobjec 1.1.2.3 644)
@@ -99,10 +99,17 @@
 			return PyErr_NoMemory();
 		}
 		/* PyObject_NewVar is inlined */
+#ifdef WITH_CYCLE_GC
+		op = (PyTupleObject *)
+			PyObject_MALLOC(sizeof(PyGCInfo) + nbytes);
+		if (op != NULL) {
+			op = (PyTupleObject *) PyGC_OBJ((PyGCInfo *)op);
+		}
+#else
 		op = (PyTupleObject *) PyObject_MALLOC(nbytes);
+#endif
 		if (op == NULL)
 			return PyErr_NoMemory();
-
 		PyObject_INIT_VAR(op, &PyTuple_Type, size);
 	}
 	for (i = 0; i < size; i++)
@@ -114,6 +121,7 @@
 		Py_INCREF(op);	/* extra INCREF so that this is never freed */
 	}
 #endif
+	PyGC_Insert((PyObject *)op);
 	return (PyObject *) op;
 }
 
@@ -180,6 +188,7 @@
 	register int i;
 	register int len =  op->ob_size;
 	Py_TRASHCAN_SAFE_BEGIN(op)
+	PyGC_Remove((PyObject *)op);
 	if (len > 0) {
 		i = len;
 		while (--i >= 0)
@@ -193,7 +202,7 @@
 		}
 #endif
 	}
-	PyObject_DEL(op);
+	PyGC_DEL(op);
 done:
 	Py_TRASHCAN_SAFE_END(op)
 }
@@ -420,6 +429,22 @@
 	return (PyObject *) np;
 }
 
+#ifdef WITH_CYCLE_GC
+static int
+tuplerecurse(PyTupleObject *o, visitproc visit, void *closure)
+{
+	int i;
+	PyObject *x;
+
+	for (i = o->ob_size; --i >= 0; ) {
+		x = o->ob_item[i];
+		if (x != NULL && !visit(x, closure))
+			return 0;
+	}
+	return 1;
+}
+#endif /* WITH_CYCLE_GC */
+
 static PySequenceMethods tuple_as_sequence = {
 	(inquiry)tuplelength, /*sq_length*/
 	(binaryfunc)tupleconcat, /*sq_concat*/
@@ -447,6 +472,16 @@
 	&tuple_as_sequence,	/*tp_as_sequence*/
 	0,		/*tp_as_mapping*/
 	(hashfunc)tuplehash, /*tp_hash*/
+#ifdef WITH_CYCLE_GC
+	0,		/* tp_call */
+	0,		/* tp_str */
+	0,		/* tp_getattro */
+	0,		/* tp_setattro */
+	0,		/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GCINFO,	/* tp_flags */
+	0,		/* tp_doc */
+	(recurseproc)tuplerecurse,	/* tp_recurse */
+#endif
 };
 
 /* The following function breaks the notion that tuples are immutable:
@@ -531,12 +566,25 @@
 	} else 
 #endif		
 	{
+#ifdef WITH_CYCLE_GC
+		PyGCInfo *g = PyGC_INFO((PyObject *)v);
+		PyGC_Remove((PyObject *)v);
+		g = PyObject_REALLOC((char *)v, sizeof(*g) +
+			sizeof(PyTupleObject) + newsize * sizeof(PyObject *));
+		if (g == NULL) {
+			sv = NULL;
+		} else {
+			sv = (PyTupleObject *)PyGC_OBJ(g);
+		}
+#else
 		sv = (PyTupleObject *)
 			PyObject_REALLOC((char *)v,
 				sizeof(PyTupleObject) + newsize * sizeof(PyObject *));
+#endif
 		*pv = (PyObject *) sv;
 		if (sv == NULL) {
-			PyObject_DEL(v);
+			PyGC_Insert((PyObject *)v);
+			PyGC_DEL(v);
 			PyErr_NoMemory();
 			return -1;
 		}
@@ -551,6 +599,7 @@
 			sv->ob_item[i - sizediff] = NULL;
 		}
 	}
+	PyGC_Insert((PyObject *)sv);
 	sv->ob_size = newsize;
 	return 0;
 }
@@ -571,7 +620,7 @@
 		while (p) {
 			q = p;
 			p = (PyTupleObject *)(p->ob_item[0]);
-			PyObject_DEL(q);
+			PyGC_DEL(q);
 		}
 	}
 #endif
Index: 0.6/PC/config.c
--- 0.6/PC/config.c Mon, 08 May 2000 12:24:03 -0600 nas (python/E/39_config.c 1.1.2.1 644)
+++ gc.8(w)/PC/config.c Mon, 05 Jun 2000 02:09:43 -0600 nas (python/E/39_config.c 1.1.2.1 644)
@@ -43,6 +43,9 @@
 #endif
 extern void initcmath();
 extern void initerrno();
+#ifdef WITH_CYCLE_GC
+extern void initgc();
+#endif
 #ifndef MS_WIN64
 extern void initimageop();
 #endif
@@ -89,6 +92,9 @@
 #endif
         {"cmath", initcmath},
         {"errno", initerrno},
+#ifdef WITH_CYCLE_GC
+        {"gc", initgc},
+#endif
 #ifndef MS_WIN64
         {"imageop", initimageop},
 #endif
Index: 0.6/PC/config.h
--- 0.6/PC/config.h Mon, 05 Jun 2000 00:51:28 -0600 nas (python/E/40_config.h 1.1.2.2 644)
+++ gc.8(w)/PC/config.h Mon, 05 Jun 2000 02:09:43 -0600 nas (python/E/40_config.h 1.1.2.2 644)
@@ -421,6 +421,9 @@
 /* Define if you want to use the GNU readline library */
 /* #define WITH_READLINE 1 */
 
+/* Define if you want cycle garbage collection */
+#define WITH_CYCLE_GC 1
+
 /* Define if you have clock.  */
 /* #define HAVE_CLOCK */
 
Index: 0.6/PCbuild/python16.dsp
--- 0.6/PCbuild/python16.dsp Mon, 05 Jun 2000 00:51:28 -0600 nas (python/G/1_python16.d 1.1.1.1 644)
+++ gc.8(w)/PCbuild/python16.dsp Mon, 05 Jun 2000 02:09:00 -0600 nas (python/G/1_python16.d 1.1.1.1 644)
@@ -660,6 +660,21 @@
 # End Source File
 # Begin Source File
 
+SOURCE=..\Modules\gcmodule.c
+
+!IF  "$(CFG)" == "python16 - Win32 Release"
+
+!ELSEIF  "$(CFG)" == "python16 - Win32 Debug"
+
+!ELSEIF  "$(CFG)" == "python16 - Win32 Alpha Debug"
+
+!ELSEIF  "$(CFG)" == "python16 - Win32 Alpha Release"
+
+!ENDIF 
+
+# End Source File
+# Begin Source File
+
 SOURCE=..\Python\getargs.c
 
 !IF  "$(CFG)" == "python16 - Win32 Release"
Index: 0.6/Modules/gcmodule.c
--- 0.6/Modules/gcmodule.c Mon, 05 Jun 2000 03:54:11 -0600 nas ()
+++ gc.8(w)/Modules/gcmodule.c Mon, 05 Jun 2000 03:37:11 -0600 nas (python/M/10_gcmodule.c 1.3 644)
@@ -0,0 +1,678 @@
+/*
+ 
+  Reference Cycle Garbage Collection
+  ==================================
+
+  Neil Schemenauer <nascheme@enme.ucalgary.ca>
+
+  Based on a post on the python-dev list.  Ideas from Guido van Rossum,
+  Eric Tiedemann, and various others.
+
+  http://www.enme.calgary.ca/~nascheme/python/gc.html
+  http://www.python.org/pipermail/python-dev/2000-March/003869.html
+  http://www.python.org/pipermail/python-dev/2000-March/004010.html
+  http://www.python.org/pipermail/python-dev/2000-March/004022.html
+
+  For a highlevel view of the collection process, read the collect
+  function.
+
+  TODO:
+	use a different interface for set_debug() (keywords)?
+	inline PyGC_Insert and PyGC_Remove calls?
+	tune parameters
+
+*/
+
+#include "Python.h"
+
+/* #define Py_DEBUG */
+
+#ifndef WITH_CYCLE_GC
+#error "You must define WITH_CYCLE_GC to include this module"
+#endif
+
+/* magic gc_refs value */
+#define GC_MOVED -1
+
+/*** Global GC state ***/
+
+/* linked lists of container objects */
+static PyGCInfo generation0 = {&generation0, &generation0, 0};
+static PyGCInfo generation1 = {&generation1, &generation1, 0};
+static PyGCInfo generation2 = {&generation2, &generation2, 0};
+static int generation = 0; /* current generation being collected */
+
+/* collection frequencies, XXX tune these */
+static int threshold0 = 100; /* net new containers before collection */
+static int threshold1 = 10;  /* generation0 collections before collecting 1 */
+static int threshold2 = 10;  /* generation1 collections before collecting 2 */
+
+/* net new objects allocated since last collection */
+static int allocated = 0;
+
+/* set for debugging information */
+#define DEBUG_STATS		(1<<0) /* print collection statistics */
+#define DEBUG_COLLECTABLE	(1<<1) /* print collectable objects */
+#define DEBUG_UNCOLLECTABLE	(1<<2) /* print uncollectable objects */
+#define DEBUG_INSTANCES		(1<<3) /* print instances */
+#define DEBUG_OBJECTS		(1<<4) /* print other objects */
+#define DEBUG_LEAK		DEBUG_COLLECTABLE | \
+				DEBUG_UNCOLLECTABLE | \
+				DEBUG_INSTANCES | \
+				DEBUG_OBJECTS
+static int debug = DEBUG_LEAK;
+
+/* list of uncollectable objects */
+static PyObject *garbage = NULL;
+
+
+/*** list functions ***/
+
+static void
+list_init(PyGCInfo *list)
+{
+	list->gc_prev = list;
+	list->gc_next = list;
+}
+
+static void
+list_append(PyGCInfo *node, PyGCInfo *list)
+{
+	node->gc_next = list;
+	node->gc_prev = list->gc_prev;
+	node->gc_prev->gc_next = node;
+	list->gc_prev = node;
+}
+
+static void
+list_remove(PyGCInfo *node)
+{
+	node->gc_prev->gc_next = node->gc_next;
+	node->gc_next->gc_prev = node->gc_prev;
+#ifdef Py_DEBUG
+	node->gc_prev = NULL;
+	node->gc_next = NULL;
+#endif
+}
+
+static void 
+list_move(PyGCInfo *from, PyGCInfo *to)
+{
+	if (from->gc_next == from) {
+		/* empty from list */
+		list_init(to);
+	} else {
+		to->gc_next = from->gc_next;
+		to->gc_next->gc_prev = to;
+		to->gc_prev = from->gc_prev;
+		to->gc_prev->gc_next = to;
+	}
+	list_init(from);
+}
+
+/* append a list onto another list */
+static void
+list_lappend(PyGCInfo *from, PyGCInfo *to)
+{
+	PyGCInfo *tail;
+	if (from->gc_next != from) {
+		tail = to->gc_prev;
+		tail->gc_next = from->gc_next;
+		tail->gc_next->gc_prev = tail;
+		to->gc_prev = from->gc_prev;
+		to->gc_prev->gc_next = to;
+	}
+	list_init(from);
+}
+
+static long
+list_size(PyGCInfo *list)
+{
+	PyGCInfo *gc;
+	long n = 0;
+	for (gc = list->gc_next; gc != list; gc = gc->gc_next) {
+		n++;
+	}
+	return n;
+}
+
+/*** end of list stuff ***/
+
+
+/* Set all gc_refs = ob_refcnt */
+static void
+update_refs(PyGCInfo *containers)
+{
+	PyGCInfo *gc = containers->gc_next;
+	for (; gc != containers; gc=gc->gc_next) {
+		gc->gc_refs = PyGC_OBJ(gc)->ob_refcnt;
+	}
+}
+
+static int
+visit_decref(PyObject *op, void *data)
+{
+	if (op && PyGC_HAS_INFO(op)) {
+		PyGC_INFO_UNSAFE(op)->gc_refs--;
+	}
+	return 1;
+}
+
+/* Subtract internal references from gc_refs */
+static void
+subtract_refs(PyGCInfo *containers)
+{
+	recurseproc recurse;
+	PyGCInfo *gc = containers->gc_next;
+	for (; gc != containers; gc=gc->gc_next) {
+		recurse = PyGC_OBJ(gc)->ob_type->tp_recurse;
+		(void) recurse(PyGC_OBJ(gc),
+			       (visitproc)visit_decref,
+			       NULL);
+	}
+}
+
+/* Append objects with gc_refs > 0 to roots list */
+static void
+move_roots(PyGCInfo *containers, PyGCInfo *roots)
+{
+	PyGCInfo *next;
+	PyGCInfo *gc = containers->gc_next;
+	while (gc != containers) {
+		next = gc->gc_next;
+		if (gc->gc_refs > 0) {
+			list_remove(gc);
+			list_append(gc, roots);
+			gc->gc_refs = GC_MOVED;
+		}
+		gc = next;
+	}
+}
+
+static int
+visit_reachable(PyObject *op, PyGCInfo *roots)
+{
+	PyGCInfo *gc = PyGC_INFO(op);
+	if (gc && gc->gc_refs != GC_MOVED) {
+		list_remove(gc);
+		list_append(gc, roots);
+		gc->gc_refs = GC_MOVED;
+	}
+	return 1;
+}
+
+/* Move objects referenced from reachable to reachable set. */
+static void
+move_root_reachable(PyGCInfo *reachable)
+{
+	recurseproc recurse;
+	PyGCInfo *gc = reachable->gc_next;
+	for (; gc != reachable; gc=gc->gc_next) {
+		/* careful, reachable list is growing here */
+		PyObject *op = PyGC_OBJ(gc);
+		recurse = op->ob_type->tp_recurse;
+		(void) recurse(op,
+			       (visitproc)visit_reachable,
+			       (void *)reachable);
+	}
+}
+
+/* move all objects with finalizers (instances with __del__) */
+static void
+move_finalizers(PyGCInfo *unreachable, PyGCInfo *finalizers)
+{
+	PyGCInfo *next;
+	PyGCInfo *gc = unreachable->gc_next;
+	static PyObject *delstr;
+	if (delstr == NULL) {
+		delstr = PyString_InternFromString("__del__");
+	}
+	for (; gc != unreachable; gc=next) {
+		PyObject *op = PyGC_OBJ(gc);
+		next = gc->gc_next;
+		if (PyInstance_Check(op) && PyObject_HasAttr(op, delstr)) {
+			list_remove(gc);
+			list_append(gc, finalizers);
+		}
+	}
+}
+
+
+/* called by tp_recurse */
+static int
+visit_finalizer_reachable(PyObject *op, PyGCInfo *finalizers)
+{
+	PyGCInfo *gc = PyGC_INFO(op);
+	if (gc && gc->gc_refs != GC_MOVED) {
+		list_remove(gc);
+		list_append(gc, finalizers);
+		gc->gc_refs = GC_MOVED;
+	}
+	return 1;
+}
+
+/* Move objects referenced from roots to roots */
+static void
+move_finalizer_reachable(PyGCInfo *finalizers)
+{
+	recurseproc recurse;
+	PyGCInfo *gc = finalizers->gc_next;
+	for (; gc != finalizers; gc=gc->gc_next) {
+		/* careful, finalizers list is growing here */
+		recurse = PyGC_OBJ(gc)->ob_type->tp_recurse;
+		(void) recurse(PyGC_OBJ(gc), 
+			       (visitproc)visit_finalizer_reachable,
+			       (void *)finalizers);
+	}
+}
+
+static void
+debug_instance(PyObject *output, char *msg, PyInstanceObject *inst)
+{
+	char buf[200];
+	char *cname;
+	/* be careful not to create new dictionaries */
+	PyObject *classname = inst->in_class->cl_name;
+	if (classname != NULL && PyString_Check(classname))
+		cname = PyString_AsString(classname);
+	else
+		cname = "?";
+	sprintf(buf, "gc: %s<%.100s instance at %lx>\n", 
+			msg, cname, (long)inst);
+	PyFile_WriteString(buf, output);
+}
+
+static void
+debug_cycle(PyObject *output, char *msg, PyObject *op)
+{
+	if ((debug & DEBUG_INSTANCES) && PyInstance_Check(op)) {
+		debug_instance(output, msg, (PyInstanceObject *)op);
+	} else if (debug & DEBUG_OBJECTS) {
+		char buf[200];
+		sprintf(buf, "gc: %s<%s 0x%x>\n",
+				msg,
+				op->ob_type->tp_name,
+				(long)op);
+		PyFile_WriteString(buf, output);
+	}
+}
+
+/* Handle uncollectable garbage (cycles with finalizers). */
+static void
+handle_finalizers(PyGCInfo *finalizers, PyGCInfo *old)
+{
+	PyGCInfo *gc;
+	if (garbage == NULL) {
+		garbage = PyList_New(0);
+	}
+	for (gc = finalizers->gc_next; gc != finalizers;
+			gc = finalizers->gc_next) {
+		PyObject *op = PyGC_OBJ(gc);
+		/* Add all instances to a Python accessible list of garbage */
+		if (PyInstance_Check(op)) {
+			PyList_Append(garbage, op);
+		}
+		/* We assume that all objects in finalizers are reachable from
+		 * instances.  Once we add the instances to the garbage list
+		 * everything is reachable from Python again. */
+		list_remove(gc);
+		list_append(gc, old);
+	}
+}
+
+/* Break reference cycles by clearing the containers involved.  This is
+ * tricky business as the lists can be changing and we don't know which
+ * objects may be freed.  It is possible I screwed something up here. */
+static void
+delete_garbage(PyGCInfo *unreachable, PyGCInfo *old)
+{
+	inquiry clear;
+
+	while (unreachable->gc_next != unreachable) {
+		PyGCInfo *gc = unreachable->gc_next;
+		PyObject *op = PyGC_OBJ(gc);
+		/*
+		PyList_Append(garbage, op);
+		*/
+		if ((clear = op->ob_type->tp_clear) != NULL) {
+			Py_INCREF(op);
+			clear((PyObject *)op);
+			Py_DECREF(op);
+		}
+		/* only try to call tp_clear once for each object */
+		if (unreachable->gc_next == gc) {
+			/* still alive, move it, it may die later */
+			list_remove(gc);
+			list_append(gc, old);
+		}
+	}
+}
+
+/* This is the main function.  Read this to understand how the
+ * collection process works. */
+static long
+collect(PyGCInfo *young, PyGCInfo *old)
+{
+	long n = 0;
+	long m = 0;
+	PyGCInfo reachable;
+	PyGCInfo unreachable;
+	PyGCInfo finalizers;
+	PyGCInfo *gc;
+	PyObject *output = NULL;
+
+	if (debug) {
+		output = PySys_GetObject("stderr");
+	}
+	if (debug & DEBUG_STATS) {
+		char buf[100];
+		sprintf(buf, "gc: collecting generation %d...\n", generation);
+		PyFile_WriteString(buf,output);
+		sprintf(buf, "gc: objects in each generation: %d %d %d\n",
+			list_size(&generation0),
+			list_size(&generation1),
+			list_size(&generation2));
+		PyFile_WriteString(buf,output);
+	}
+
+	/* Using ob_refcnt and gc_refs, calculate which objects in the
+	 * container set are reachable from outside the set (ie. have a
+	 * refcount greater than 0 when all the references within the
+	 * set are taken into account */
+	update_refs(young);
+	subtract_refs(young);
+
+	/* Move everything reachable from outside the set into the
+	 * reachable set (ie. gc_refs > 0).  Next, move everything
+	 * reachable from objects in the reachable set. */
+	list_init(&reachable);
+	move_roots(young, &reachable);
+	move_root_reachable(&reachable);
+
+	/* move unreachable objects to a temporary list, new objects can be
+	 * allocated after this point */
+	list_init(&unreachable);
+	list_move(young, &unreachable);
+
+	/* move reachable objects to next generation */
+	list_lappend(&reachable, old);
+
+	/* Move objects reachable from finalizers, we can't safely delete
+	 * them.  Python programmers should take care not to create such
+	 * things.  For Python finalizers means instance objects with
+	 * __del__ methods. */
+	list_init(&finalizers);
+	move_finalizers(&unreachable, &finalizers);
+	move_finalizer_reachable(&finalizers);
+
+	/* Collect statistics on collectable objects found and print
+	 * debugging information. */
+	for (gc = unreachable.gc_next; gc != &unreachable;
+			gc = gc->gc_next) {
+		m++;
+		if (output != NULL && (debug & DEBUG_COLLECTABLE)) {
+			debug_cycle(output, "collectable ", PyGC_OBJ(gc));
+		}
+	}
+	/* call tp_clear on objects in the collectable set.  This will cause
+	 * the reference cycles to be broken. It may also cause some objects in
+	 * finalizers to be freed */
+	delete_garbage(&unreachable, old);
+
+	/* Collect statistics on uncollectable objects found and print
+	 * debugging information. */
+	for (gc = finalizers.gc_next; gc != &finalizers;
+			gc = gc->gc_next) {
+		n++;
+		if (output != NULL && (debug & DEBUG_UNCOLLECTABLE)) {
+			debug_cycle(output, "uncollectable ", PyGC_OBJ(gc));
+		}
+	}
+	if (output != NULL && (debug & DEBUG_STATS)) {
+		if (m == 0 && n == 0) {
+			PyFile_WriteString("gc: done.\n", output);
+		} else {
+			char buf[200];
+			sprintf(buf,
+				"gc: done, %d unreachable, %d uncollectable.\n",
+				n+m, n);
+			PyFile_WriteString(buf, output);
+		}
+	}
+
+	/* Append instances in the uncollectable set to a Python
+	 * reachable list of garbage.  The programmer has to deal with
+	 * this if they insist on creating this type of structure. */
+	handle_finalizers(&finalizers, old);
+
+	allocated = 0;
+	PyErr_Clear(); /* in case writing to sys.stderr failed */
+	return n+m;
+}
+
+static long
+collect_generations(void)
+{
+	static long collections0 = 0;
+	static long collections1 = 0;
+	long n;
+
+
+	if (collections1 > threshold2) {
+		generation = 2;
+		list_lappend(&generation0, &generation2);
+		list_lappend(&generation1, &generation2);
+		if (generation2.gc_next != &generation2) {
+			n = collect(&generation2, &generation2);
+		}
+		collections1 = 0;
+	} else if (collections0 > threshold1) {
+		generation = 1;
+		collections1++;
+		list_lappend(&generation0, &generation1);
+		if (generation1.gc_next != &generation1) {
+			n = collect(&generation1, &generation2);
+		}
+		collections0 = 0;
+	} else {
+		generation = 0;
+		collections0++;
+		if (generation0.gc_next != &generation0) {
+			n = collect(&generation0, &generation1);
+		}
+	}
+	return n;
+}
+
+void
+PyGC_Insert(PyObject *op)
+{
+	/* collection lock since collecting may cause allocations */
+	static int collecting = 0;
+
+#ifdef Py_DEBUG
+	if (!PyGC_HAS_INFO(op)) {
+		abort();
+	}
+#endif
+	if (threshold0 && allocated > threshold0 && !collecting) {
+		collecting++;
+		collect_generations();
+		collecting--;
+	}
+	allocated++;
+	list_append(PyGC_INFO(op), &generation0);
+}
+
+void
+PyGC_Remove(PyObject *op)
+{
+	PyGCInfo *g = PyGC_INFO(op);
+#ifdef Py_DEBUG
+	if (!PyGC_HAS_INFO(op)) {
+		abort();
+	}
+#endif
+	list_remove(g);
+	if (allocated > 0) {
+		allocated--;
+	}
+}
+
+
+static char collect__doc__[] =
+"collect() -> n\n"
+"\n"
+"Run a full collection.  The number of unreachable objects is returned.\n"
+;
+
+static PyObject *
+Py_collect(self, args)
+	PyObject *self;
+	PyObject *args;
+{
+	long n;
+
+	if(!PyArg_ParseTuple(args, ""))	/* check no args */
+		return NULL;
+
+	generation = 2;
+	list_lappend(&generation0, &generation2);
+	list_lappend(&generation1, &generation2);
+	n = collect(&generation2, &generation2);
+
+	return Py_BuildValue("i", n);
+}
+
+static char set_debug__doc__[] = 
+"set_debug(flags) -> None\n"
+"\n"
+"Set the garbage collection debugging flags. Debugging information is\n"
+"written to sys.stderr.\n"
+"\n"
+"flags is an integer and can have the following bits turned on:\n"
+"\n"
+"  DEBUG_STATS - Print statistics during collection.\n"
+"  DEBUG_COLLECTABLE - Print collectable objects found.\n"
+"  DEBUG_UNCOLLECTABLE - Print unreachable but uncollectable objects found.\n"
+"  DEBUG_INSTANCES - Print instance objects.\n"
+"  DEBUG_OBJECTS - Print objects other than instances.\n"
+"  DEBUG_LEAK - Debug leaking programs (everything but STATS).\n"
+;
+
+static PyObject *
+Py_set_debug(self, args)
+	PyObject *self;
+	PyObject *args;
+{
+	if (!PyArg_ParseTuple(args, "l", &debug))
+		return NULL;
+
+	Py_INCREF(Py_None);
+	return Py_None;
+}
+
+static char get_debug__doc__[] = 
+"get_debug() -> flags\n"
+"\n"
+"Get the garbage collection debugging flags.\n"
+;
+
+static PyObject *
+Py_get_debug(self, args)
+	PyObject *self;
+	PyObject *args;
+{
+	if(!PyArg_ParseTuple(args, ""))	/* no args */
+		return NULL;
+
+	return Py_BuildValue("i", debug);
+}
+
+static char set_thresh__doc__[] =
+"set_threshold(threshold0, [threhold1, threshold2]) -> None\n"
+"\n"
+"Sets the collection thresholds.  Setting threshold0 to zero disables\n"
+"collection.\n"
+;
+
+static PyObject *
+Py_set_thresh(self, args)
+	PyObject *self;
+	PyObject *args;
+{
+	if (!PyArg_ParseTuple(args, "i|ii", &threshold0, 
+				&threshold1, &threshold2))
+		return NULL;
+
+	Py_INCREF(Py_None);
+	return Py_None;
+}
+
+static char get_thresh__doc__[] =
+"get_threshold() -> (threshold0, threshold1, threshold2)\n"
+"\n"
+"Return the current collection thresholds\n"
+;
+
+static PyObject *
+Py_get_thresh(self, args)
+	PyObject *self;
+	PyObject *args;
+{
+	if(!PyArg_ParseTuple(args, ""))	/* no args */
+		return NULL;
+
+	return Py_BuildValue("(iii)", threshold0, threshold1, threshold2);
+}
+
+
+static char gc__doc__ [] =
+"This module provides access to the garbage collector for reference cycles.\n"
+"\n"
+"collect() -- Do a full collection right now.\n"
+"set_debug() -- Set debugging flags.\n"
+"get_debug() -- Get debugging flags.\n"
+"set_threshold() -- Set the collection thresholds.\n"
+"get_threshold() -- Return the current the collection thresholds.\n"
+;
+
+static PyMethodDef GcMethods[] = {
+	{"set_debug",		Py_set_debug,  METH_VARARGS, set_debug__doc__},
+	{"get_debug",		Py_get_debug,  METH_VARARGS, get_debug__doc__},
+	{"set_threshold",	Py_set_thresh, METH_VARARGS, set_thresh__doc__},
+	{"get_threshold",	Py_get_thresh, METH_VARARGS, get_thresh__doc__},
+	{"collect",		Py_collect,    METH_VARARGS, collect__doc__},
+	{NULL,	NULL}		/* Sentinel */
+};
+
+void
+initgc(void)
+{
+	PyObject *m;
+	PyObject *d;
+
+	m = Py_InitModule4("gc",
+			      GcMethods,
+			      gc__doc__,
+			      NULL,
+			      PYTHON_API_VERSION);
+	d = PyModule_GetDict(m);
+	if (garbage == NULL) {
+		garbage = PyList_New(0);
+	}
+	PyDict_SetItemString(d, "garbage", garbage);
+	PyDict_SetItemString(d, "DEBUG_STATS",
+			PyInt_FromLong(DEBUG_STATS));
+	PyDict_SetItemString(d, "DEBUG_COLLECTABLE",
+			PyInt_FromLong(DEBUG_COLLECTABLE));
+	PyDict_SetItemString(d, "DEBUG_UNCOLLECTABLE",
+			PyInt_FromLong(DEBUG_UNCOLLECTABLE));
+	PyDict_SetItemString(d, "DEBUG_INSTANCES",
+			PyInt_FromLong(DEBUG_INSTANCES));
+	PyDict_SetItemString(d, "DEBUG_OBJECTS",
+			PyInt_FromLong(DEBUG_OBJECTS));
+	PyDict_SetItemString(d, "DEBUG_LEAK",
+			PyInt_FromLong(DEBUG_LEAK));
+}
+
Index: 0.6/Lib/test/test_gc.py
--- 0.6/Lib/test/test_gc.py Mon, 05 Jun 2000 03:54:11 -0600 nas ()
+++ gc.8(w)/Lib/test/test_gc.py Mon, 05 Jun 2000 02:09:43 -0600 nas (python/M/12_test_gc.py 1.1 644)
@@ -0,0 +1,90 @@
+import gc
+
+def test_list():
+    l = []
+    l.append(l)
+    print 'list 0x%x' % id(l)
+    gc.collect()
+    del l
+    assert gc.collect() == 1
+
+def test_dict():
+    d = {}
+    d[1] = d
+    print 'dict 0x%x' % id(d)
+    gc.collect()
+    del d
+    assert gc.collect() == 1
+
+def test_tuple():
+    l = []
+    t = (l,)
+    l.append(t)
+    print 'list 0x%x' % id(l)
+    print 'tuple 0x%x' % id(t)
+    gc.collect()
+    del t
+    del l
+    assert gc.collect() == 2
+
+def test_class():
+    class A:
+        pass
+    A.a = A
+    print 'class 0x%x' % id(A)
+    gc.collect()
+    del A
+    assert gc.collect() > 0
+
+def test_instance():
+    class A:
+        pass
+    a = A()
+    a.a = a
+    print repr(a)
+    gc.collect()
+    del a
+    assert gc.collect() > 0
+
+def test_finalizer():
+    class A:
+        def __del__(self): pass
+    class B:
+        pass
+    a = A()
+    a.a = a
+    id_a = id(a)
+    b = B()
+    b.b = b
+    print 'a', repr(a)
+    print 'b', repr(b)
+    gc.collect()
+    gc.garbage[:] = []
+    del a
+    del b
+    assert gc.collect() > 0
+    assert id(gc.garbage[0]) == id_a
+
+def test_function():
+    d = {}
+    exec("def f(): pass\n") in d
+    print 'dict 0x%x' % id(d)
+    print 'func 0x%x' % id(d['f'])
+    gc.collect()
+    del d
+    assert gc.collect() == 2
+
+
+def test_all():
+    debug = gc.get_debug()
+    gc.set_debug(gc.DEBUG_LEAK | gc.DEBUG_STATS)
+    test_list()
+    test_dict()
+    test_tuple()
+    test_class()
+    test_instance()
+    test_finalizer()
+    test_function()
+    gc.set_debug(debug)
+
+test_all()