File: programming/cocoa/DansRuntime.zip/main.cpp


/*
 *  main.c
 *  DansRuntime
 *
 *  Created by Uli Kusterer on 24.03.07.
 *  Copyright 2007 M. Uli Kusterer. All rights reserved.
 *
 */
 
// -----------------------------------------------------------------------------
//	Headers:
// -----------------------------------------------------------------------------
 
#include <stdio.h>
#include <stdlib.h>
// -----------------------------------------------------------------------------
//	Constants:
// -----------------------------------------------------------------------------
 
// Set this to 1 to use the incremental collector, otherwise we scan all objects
//	each time through Collect().
#define	USE_INCREMENTAL_COLLECTOR	0
 
// Flags for instance variable entries in runtime type information:
#define DRIVARFLAG_OBJECT		(1 << 0)	// This instance variable is a reference to an object. Used by the garbage collector.
 
// Flags for objects:
#define DROBJFLAG_MARKER_BUSY	(1 << 0)	// Set on an object to make assignment know the GC's marker is working on it, so we can restart the GC.
 
// The following strings can be compared by pointer-comparison
//	if you always use these globals to refer to them. You could just as well
//	use ints or whatever, but this has the advantage that you can actually
//	printf() these strings during debugging etc.
"Create";
DRSelector		DRSelector_Prepare = "Prepare""Delete";
DRSelector		DRSelector_name = "name";
DRSelector		DRSelector_Object = "Object";
DRSelector		DRSelector_ObjectSubclass = "ObjectSubclass";
 
// If you want to add your own selectors, define a global containing a pointer to that string and use only that.
 
 
// -----------------------------------------------------------------------------
//	Data structures:
// -----------------------------------------------------------------------------
 
// ----- The following data structures are kept once per class: -----
 
// An entry for one instance method of a class:
// Name of this method (introspection, unique lookup).
// Ptr to function that actually implements this method.
} DRVTableEntry;
 
// An entry for one instance variable of a class:
//	Used for runtime introspection. Also used by our garbage collector to find
//	references to other objects.
// Name of this instance variable (introspection, unique lookup).
// Offset of this instance variable relative to class's iVar offset.
// Flags with information about this instance variable.
} DRIVarTableEntry;
 
// This describes a class, its methods, super class, instance variables etc:
// NULL for root classes.
	DRSelector				mClassName;			// Name of this class (debugging, introspection).
// Size of this class's instance vars.
	off_t					mIvarOffset;		// Offset to ivars of this class.
	DRVTableEntry*			mMethods;			// Methods this class implements. Selector/IMP of NULL means end of method list.
	DRIVarTableEntry*		mIVars;				// Instance variables in this class. Selector of NULL means end of ivar list.
// ----- The following data structure is the basis for every object: -----
// Try to keep the number of instance variables in DRObject itself low. They
// are needed for each object, and thus add a lot of overhead to each object.
 
// This describes one object:
//	Except for mClass, all of these instance vars wouldn't be needed if we didn't
//	do garbage collection.
// This object's class (i.e. its "ISA").
// Flags of this object. E.g. the GC uses this to mark our object as busy.
// Last time our GC's marker saw this object.
// Next object in linked list of objects.
// Previous object in linked list of objects.
// Name to show for this object as a debugging aid.
 
	// ivars go here.
} DRObject;
 
 
// -----------------------------------------------------------------------------
//	Globals:
// -----------------------------------------------------------------------------
 
// Doubly linked list of all objects used by garbage collector:
/* Why a linked list? Well, a linked list can be changed while someone is
		iterating through it without too many problems, because all element
		pointers except one that is deleted stay valid. It's also fast to
		add and remove elements (constant-time) and thus faster as re-allocating
		a huge array each time. A doubly-linked list makes this even faster, as
		we don't have to walk the list to find the previous object to update its
		"next" pointer. */
 
// Incremental garbage collector's state information:
// Position inside linked list where garbage collector is currently busy.
// Cycle counter (i.e. "generation year") for the marker part of our incremental garbage collector. This is also used by the mark/sweep-all-at-once collector.
// Cycle counter used for the "sweep" part of our incremental garbage collector. *not* used by the mark/sweep-all-at-once collector.
// The object that serves as the root of our tree of reachable objects.
														//	For a real-world app, you would probably want this to be a list of
														//	objects.
 
 
// -----------------------------------------------------------------------------
//	Forwards:
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
//	Instance methods for classes created using our runtime:
// -----------------------------------------------------------------------------
 
// Class "Object":
"Created Object %s.\n""Deleted Object %s.\n", self->mDebugName );
}
 
 
// Class "ObjectSubclass":
"Calling superclass constructor for %s:\n\t"// Find method in our superclass.
// Run it, if superclass implements it.
"Superclass %s doesn't implement \"Create\".\n""Created ObjectSubclass %s.\n", self->mDebugName );
}
 
 
// -----------------------------------------------------------------------------
//	VTable, IVar table and class info for class "Object":
// -----------------------------------------------------------------------------
 
// Here we look up the actual functions that a particular class overrides or
//	makes available to be overridden:
/* Instead of searching for the selector, you could also just save the
		index of the respective entry, and make a copy of the superclass's
		list of selectors and then append your new methods and replace
		the ones you override. However, such an approach would also suffer
		from the fragile base class problem, and would mean that your program
		could only send messages to objects that actually are of the class you
		expect. OTOH this approach lets any object that understands a particular
		message handle it, even if it's another class than the one you expected. */
 
// This is information about any DRObject* variables that objects of this class
//	contain, so the garbage collector can determine reachability of objects:
// The base class "Object" has no instance vars for now.
};
 
// The actual class information:
// No superclass, this is a root class.
	DRSelector_Object,		// Unique identifier for this class.
	0,						// No instance variables.
	0,						// Placeholder where we'll calculate offset to first iVar.
	gClassObjectVTable,		// Table of virtual functions.
	gClassObjectIVarTable	// Table of object-referencing instance variables.
};
 
 
// Same for our subclass "ObjectSubclass":
// We override "create".
// DRObject*  name;
// A subclass of our "Object" class:
// Superclass "Object".
	DRSelector_ObjectSubclass,		// Unique identifier for this class.
// Size of instance variable data (one object reference).
	0,								// Placeholder for iVar offset.
	gClassObjectSubclassVTable,		// Table of virtual functions.
	gClassObjectSubclassIVarTable	// Table of instance vars.
// Object currently being scanned.
// Index of instance variable being scanned in this object.
};
 
 
// -----------------------------------------------------------------------------
//	Marker Stack:
//		Stack push/peek/pop functions for the stack that our marker phase uses
//		to keep track of what it last marked.
// -----------------------------------------------------------------------------
 
#define	MARKER_STACK_BLOCK_SIZE		16	// We allocate more space for the stack in blocks of this many entries. That way, we don't reallocate for every little "push".
// Storage for stack.
// Actual size of memory in gIncrementalMarkerStack (in entries, not bytes).
// Number of entries currently used in marker stack.
// Pointer returned is invalid as soon as you push/pop the next time.
// Pointer returned is invalid as soon as you push/pop the next time.
// We don't make the actual memory block smaller, we'll probably need the memory again soon.
									// If you're worried about memory usage, you can change that, but then this can't return its last entry as easily.
// -----------------------------------------------------------------------------
//	RewindMarkerStackToObject ()
//		Call this to reset the "mark" phase of our incremental garbage collector
//		when you move an object in the hierarchy. This does nothing if the
//		garbage collector isn't busy with an object, so it's a pretty cheap
//		call.
//
//		During the "sweep" phase that deletes the objects, our garbage collector
//		walks the internal linked list of objects, so there is no way it can
//		change between calls (because the sweep phase is the only one that can
//		delete an object).
//
//		During the "mark" phase, however, we walk the actual object hierarchy
//		as users of this runtime see it. Since the user of this runtime may at
//		any time between calls to MarkNextReachableObject() take the object
//		being marked out of its IVar we reached it by and put another object
//		in the IVar that we may not have marked yet, we need to re-scan the
//		object. We do this by rewinding the stack MarkNextReachableObject()
//		uses to keep track of where in the object hierarchy it currently is.
// -----------------------------------------------------------------------------
// Re-scan IVar we reached the other object by.
// Avoid function call overhead for 90% of the cases using this.
// -----------------------------------------------------------------------------
//	CalculateIvarOffset ()
//		This is used to update the mIVarOffset field of each class, so our code
//		can quickly access instance variables. We could hard-code the offset
//		into the table, but by culating it at runtime, we can avoid the
//		"fragile base class"-problem.
//
//		Fragile Base Class:
//			The instance vars of an object are stored in sequence, with the
//			superclass's instance vars at the top and the ones the class adds
//			below them. We calculate the offsets of each instance variable and
//			use it to access its data. If the superclass is loaded from a
//			dynamic library (e.g. because it is a system library), and that
//			library gets updated and a new instance variable is added to the
//			superclass, all the offsets hard-coded into the subclasses would be
//			wrong.
//			
//		What we do here is we have each class note down its size, and then
//		we can calculate the offset of each class's ivars at runtime, based
//		on the sizes of the classes actually loaded, and not based on the
//		sizes as they were when we compiled. This makes accessing instance
//		variables a tad more complicated, as we need to look up the offset
//		of each iVar at runtime, but it works.
//			
//		Of course we could pre-calculate the offset of each instance variable,
//		but I chose to assemble it from a general "ivar offset" for each class,
//		plus offsets relative to that for each instance variable. By doing this,
//		we could theoretically resize a class at runtime or do other fancy
//		things.
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
//	FindMethodImp ()
//		Each method has a name or "selector" that identifies it relative to
//		its object, as well as an implementation function ("IMP" for short)
//		that actually runs the code for it.
//
//		When you want to call a method on an object, look up the IMP to call
//		using this function. This will look for the method in the specified
//		class and all superclasses, returning NULL if nobody implements the
//		selector.
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
//	AllocObjectOfClass ()
//		Allocates the memory for an object with a particular class and
//		initializes its Class pointer and garbage collector info ("meta-ivars").
// -----------------------------------------------------------------------------
// Zeroes out our new memory.
	
	// Initialize meta-ivars before anyone else gets to see this object:
	theObject->mClass = info;
	theObject->mLastCycleSeen = gCurrGCMarkCycle;	// Start out as reachable so we don't get collected by accident.
	theObject->mDebugName = debugName;
 
	// Insert us at start of linked list:
// -----------------------------------------------------------------------------
//	CreateObjectOfClass ()
//		Creates a new object (allocating its memory using AllocObjectOfClass)
//		and then calls its constructor and its preparation method.
//
//		The preparation method is for initialization stuff that you can't call
//		until you're sure your superclass has been initialized.
// -----------------------------------------------------------------------------
// Send "Create" message:
"Class %s or superclasses don't implement \"Create\".\n", info->mClassName );
	
	// Send "Prepare" message:
"Class %s or superclasses don't implement \"Prepare\".\n"// -----------------------------------------------------------------------------
//	ClassDescendsFromClass ()
//		Introspection method that tells you whether one class is a subclass
//		of another. Since you can ask an object for its class, this can also be
//		used on objects.
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
//	DeleteObject ()
//		Function used internally by the garbage collector to dispose of an
//		object. Unless you decide not to use the garbage collector *at all*,
//		you should never call this method.
// -----------------------------------------------------------------------------
// Call "Delete" method to let object know it's going:
"Class %s or superclasses don't implement \"Delete\".\n", theObject->mClass->mClassName );
	
	// Take us out of our linked list of objects:
// -----------------------------------------------------------------------------
//	MarkAllObjectsUnreachable ()
//		Goes through our linked list of objects and marks each one as not
//		reachable, i.e. eligible for being garbage-collected. Once you have
//		done that, you can call MarkReachableObjects() to mark all objects that
//		are still in use, and then you can ask the garbage collector to delete
//		the unused objects by calling DeleteAllUnreachableObjects().
//
//		This is the classic behaviour of a mark/sweep garbage collector.
//		A disadvantage of this is that your app may take a lunch break while
//		it does all this collecting. And you don't want it to be interrupted
//		in the mean time.
//		See DeleteNextUnreachableObject() if you're interested in doing at
//		least some of this work in the background.
// -----------------------------------------------------------------------------
// See DeleteNextUnreachableObject() for why we need -3 here.
		currObj = currObj->mNext;
	}
}
 
 
// -----------------------------------------------------------------------------
//	MarkAllObjectsReachable ()
//		Goes through our linked list of objects and marks each one as reachable,
//		thus postponing collection of some objects.
//
//		This is used in cases where our gCurrGCMarkCycle counter gets so large
//		that it gets cut off and ends up being zero again. Since now, all old
//		objects would look incredibly young and would never get collected, we
//		use this to re-date them all to the new cycle number (probably 0). That
//		way they will get collected in a few cycles.
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
//	DeleteAllUnreachableObjects ()
//		Loops over our list of objects and deletes all objects that have been
//		determined as unreachable during the last pass of marking using
//		MarkReachableObjects().
//
//		This is used for the sweep phase of our mark/sweep garbage collector.
//		After all objects have been marked as unreachable, we mark those that
//		are actually reachable as such, and what's left over will be the objects
//		that are actually uncreachable, which this function will then delete.
//		
//		We don't use this for our incremental garbage collector.
// -----------------------------------------------------------------------------
// Already go to next object so we have a next pointer even if we delete this object now.
// -----------------------------------------------------------------------------
//	MarkReachableObjects ()
//		Marks all objects hanging off of the object in gReachableRoot as being
//		reachable. This is part of our mark/sweep garbage collector, where we
//		first mark all objects as unreachable, then call this to mark our tree
//		of objects as reachable (you should add all objects to this tree, even
//		ones that currently only have a local variable on the stack pointing
//		at them. I.e. ideally, your programming language's call stack would
//		also be an object in this tree.
//		
//		We don't use this for our incremental garbage collector.
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
//	MarkOneObjectReachable ()
//		Mark one object and all the objects it refers to as reachable so they
//		aren't garbage-collected.
//
//		Used by our mark-sweep garbage collector to mark objects as reachable.
//		We don't use this for our incremental garbage collector.
// -----------------------------------------------------------------------------
// Not an object or we already did it?
// Mark this one reachable.
	
	// Mark all sub-objects, too:
#define	OUT_OF_OBJECTS		((DRObject*) 1)
 
 
// -----------------------------------------------------------------------------
//	GetIndObjectIVarOfObject ()
//		Used by the garbage collector to walk the IVars in each object and
//		thus determine reachability of objects hanging off others.
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
//	SetIndObjectIVarOfObject ()
//		Use this to change object IVars.
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
//	MarkNextReachableObject ()
//		Main bottleneck of our incremental garbage collector's "mark" phase.
//		This does essentially the same as MarkReachableObjects(), just that
//		instead of using recursion and the call stack to keep track of the
//		current object, how we arrived there and which IVar we're currently
//		checking, this uses a stack in a global variable. That way, each call
//		is roughly equivalent to one loop iteration in MarkOneObjectReachable().
//		
//		However, since there may be other code accessing the objects we're
//		scanning between calls to this function, our marker stack sets the
//		DROBJFLAG_MARKER_BUSY flag on each object that gets pushed on it, and
//		removes the flag when it is removed. That way, anyone who changes a
//		reference to an object the garbage collector is currently working with
//		can use RewindMarkerStackToObject() to rewind this function's stack so
//		it will re-scan the modified object.
// -----------------------------------------------------------------------------
// Start a new round.
		currEntry->mObject->mLastCycleSeen = gCurrGCMarkCycle;		// Mark root as reachable.
// Stop once to give IncrementalCollect() a chance to starve us and have the sweeper catch up.
	}
	
	// Find the next object IVar:
// NULL == not an object.
// Hit last IVar without any more objects?
		PopFromMarkerStack();				// Finished with this object.
// Schedule for scanning next round.
// Mark as reachable.
	}
}
 
 
// -----------------------------------------------------------------------------
//	DeleteNextUnreachableObject ()
//		This is our incremental garbage collector's "sweep" phase. While
//		DeleteAllUnreachableObjects() runs in one go and may thus cause
//		noticeable pauses when you have a lot of objects, this function will
//		only check one object in our list of reachable objects and then return,
//		maintaining state in a global.
//
//		When objects are marked, they are marked with the most recent garbage
//		collector cycle number, and not just with a reachable/unreachable flag.
//		This way, we can mark objects while the program is running (even during
//		the sweep phase), and we don't need to loop over all objects to mark
//		them unreachable, as older ones have a different cycle number that
//		indicates they're not marked reachable already. Because objects from one
//		cycle ago might not necessarily be unreachable (they could just be ones
//		the marker hasn't processed yet), we only purge objects from two cycles
//		ago, which guarantees the marker has seen them.
// -----------------------------------------------------------------------------
// No objects? Nothing to collect.
// Start a new GC cycle:
// Stop once to give IncrementalCollect() a chance to starve us and have the marker catch up.
// Already go to next object so we have a next pointer even if we delete this object now.
// Haven't seen it for two cycles or more? Delete it.
// -----------------------------------------------------------------------------
//	IncrementalCollect ()
//		Our flag that we use for garbage collecting is the number of complete
//		cycles we've absolved so far. Problem is, if one of our two phases
//		takes longer than the other, it will do more cycles. So, what we do is
//		make sure one phase waits for the other once it has finished.
// -----------------------------------------------------------------------------
// Only do marking if the "sweep" phase is in the same cycle or ahead of us. Otherwise wait until it catches up:
// Mark phase is in lower or same cycle as sweep.
			|| gCurrGCSweepCycle == 0 && gCurrGCMarkCycle > 10 )	// Sweep phase has already overflowed, but mark hasn't -> Mark in lower cycle than sweep.
			MarkNextReachableObject();
		// Only do sweeping if the "mark" phase is in the same cycle or ahead of us. Otherwise wait until it catches up:
// Sweep phase is in lower or same cycle as mark.
			|| gCurrGCMarkCycle == 0 && gCurrGCSweepCycle > 10 )	// Mark phase has already overflowed, but sweep hasn't -> Sweep in lower cycle than mark.
// -----------------------------------------------------------------------------
//	MarkAndSweepCollect ()
//		This loops over the entire list of objects, marks them all as
//		unreachable and then walks our hierarchy of reachable objects and marks
//		them all as reachable again. After that, we can delete all objects that
//		are still marked reachable.
//
//		Since this processes all objects each time, it can be kinda slow with
//		lots of objects, and cause longer pauses in program execution.
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
//	Collect ()
//		No matter whether you're using the incremental collector or the
//		one-time-mark-and-sweep-everything variant, this function will do
//		the right thing and do a collection, so call this periodically.
// -----------------------------------------------------------------------------
#if USE_INCREMENTAL_COLLECTOR
	IncrementalCollect(10);
	#else
	MarkAndSweepCollect();
	#endif
}
 
 
// -----------------------------------------------------------------------------
//	main ()
//		Very minimal app that creates some collected objects and collects them.
//		
//		We create one Object "First" which we put in gReachableRoot, and
//		this in turn refers to an object named "SubObject". Hence, those two
//		will not be collected.
//		
//		The third object we create, "Dead", is not referred to by any of the
//		objects in gReachableRoot, so it will get collected at first
//		opportunity.
// -----------------------------------------------------------------------------
"First" );
	gReachableRoot = firstObject;	// Add first to our tree, so it doesn't get collected.
"Dead" );	// We don't attach this one to anyone else, so it gets collected.
	DRObject*	subObject = CreateObjectOfClass( &gClassObject, "SubObject"// Attach SubObject to First.
"==========\n");
	
	// The following would usually happen in your event loop:
"==========\n");
 
	// Kill all objects before terminating:
// Deletes all, since we didn't mark any as reachable.
 

This code uses the PclZip Zip File reading code, which is subject to the GNU LGPL. It also uses the GeSHi syntax highlighter, subject to the GPL. Ask if you want this for your own web site, it's free.