org.abora.gold.be.canopy
Class CanopyCrum

java.lang.Object
  |
  +--org.abora.gold.java.AboraHeaper
        |
        +--org.abora.gold.xpp.basic.Heaper
              |
              +--org.abora.gold.snarf.Abraham
                    |
                    +--org.abora.gold.be.canopy.CanopyCrum

Direct Known Subclasses:

BertCrum, SensorCrum

public class CanopyCrum

extends Abraham

CanopyCrums form binary trees that acrete in a balanced fashion. No rebalancing ever
happens. Things are simply added to the tree up to the point thta the tree is balanced,
then the height of the tree gets extended at the root.
Essentially, when the join of two trees is asked for, if the two trees aren''t already
parts of a larger tree, the algorithm attempts to find a place in one tree into which the
other tree could completely fit without violating the depth constraint on the tree. It
then returns the nearest root that contains both trees. If it can''t put one tree into
the other, then it makes a new node that joins the two trees (probably with room to add
other stuff deeper down).
myRefCount is only the count of Loafs or HCrums that point at the CanopyCrum. It doesn''t
include other CanopyCrums.
12/2/92 Ravi
PropJoints have been suspended, and their function has been replaced by flag words in the
CanopyCrum. Any interesting Club or endorsement gets a bit, and there is a bit for "any
other Club" and "any other endorsement". Any criteria not given a bit of their own require
an exhaustive search. These flags are widded by ORing up the canopy. When we start using
more sophisticated hashing strategies, we will probably need to reanimate PropJoints.

Field Summary

protected CanopyCrum	child1
protected CanopyCrum	child2
protected static PtrArray	FlagEndorsements
protected IntegerVar	maxH
protected IntegerVar	minH
protected int	myFlags
protected int	myOwnFlags
protected IntegerVar	myRefCount
protected static IDRegion	OtherClubs
protected static CrossRegion	OtherEndorsements
protected CanopyCrum	parent
protected static Heaper2UInt32Cache	TheEFlagsCache
protected static Heaper2UInt32Cache	ThePFlagsCache

Fields inherited from class org.abora.gold.snarf.Abraham

DismantleStatistics, myHash, myInfo, myToken, TheTokenSource

Fields inherited from class org.abora.gold.xpp.basic.Heaper

AllBlasts, BecomeMap, GarbageCount, InGC, InitializedClasses, InitializingClasses, LastMemory, NextClientRequestNumber, NotOneElementSignal, PackageTable, PromiseNameTable, StringHashSBoxes

Fields inherited from class org.abora.gold.java.AboraHeaper

ActiveClubs, CurrentAuthor, CurrentBertCanopyCache, CurrentBertCrum, CurrentChunk, CurrentGrandMap, CurrentKeyMaster, CurrentPacker, CurrentSensorCanopyCache, CurrentServer, CurrentSession, CurrentSessions, CurrentTrace, InitialEditClub, InitialOwner, InitialReadClub, InitialSponsor, InsideTransactionFlag

Constructor Summary

CanopyCrum(int flags)
Make a canopyCrum for a root: it has no children.

CanopyCrum(int flags, CanopyCrum first, CanopyCrum second)
prop must be empty

CanopyCrum(Rcvr receiver)

Method Summary

void	addPointer(Heaper ignored) Keep a refcount of diskful pointers to myself for disk space management.
CanopyCrum	another() Return another instance of the same class for testing purposes.
CanopyCache	canopyCache()
boolean	changeCanopy() Figure out new props, etc.
boolean	changeCanopy(PropChange change) Figure out new height, props, etc.
boolean	changeHeight() Figure out new height.
Array	childArray()
Array	children()
CanopyCrum	computeJoin(CanopyCrum otherBCrum) Find a canopyCrum that is an anscestor to both the receiver and otherBCrum.
int	contentsHash() This is only used by the TestPacker, so it includes all persistent state whether or not it is semantically interesting--myRefCount is not semantically interesting.
void	dismantle() Disconnect me from the universe and throw me off the disk. For GC safety, we keep a strongptr to ourself -- is this still necessary?
java.lang.String	displayString()
static int	endorsementFlagLimit() Max number of special endorsement flags
static int	endorsementsFlags(CrossRegion endorsements) Flag bits corresponding to endorsements
Pair	expand() split into two if possible, return the two leaves
CanopyCrum	fetchChild1()
CanopyCrum	fetchChild2()
CanopyCrum	fetchParent()
static int	firstEndorsementsFlag() Rightmost flag for interesting endorsements
int	flags()
PropChange	fullChange()
IntegerVar	heightDiff()
void	includeCanopy(CanopyCrum otherCanopy) Install otherCanopy at or below the receiver.
static void	initTimeNonInherited()
void	inspect()
void	inspectSubCanopy(java.lang.Object start)
boolean	isLE(CanopyCrum other) Return true if other is equal to the receiver or an anscestor (through the parent links). Use caches for efficiency.
boolean	isLeaf()
PropJoint	joint() Return the abstracted information necessary to determine whether anything leafward may pass the filtering criteria.
static void	linkTimeNonInherited()
CanopyCrum	makeJoin(CanopyCrum otherCanopy) Install otherCanopy as a subtree in the canopy containing the receiver.
CanopyCrum	makeNew()
CanopyCrum	makeNewParent(CanopyCrum first, CanopyCrum second) Make a new crum that contains both first and second. This method just makes a new parent whose properties are empty.
IntegerVar	maxHeight()
IntegerVar	minHeight()
static int	otherClubsFlag() The flag for any other Clubs
static int	otherEndorsementsFlag() Flag for all uninteresting endorsements
int	ownFlags()
static int	permissionsFlags(IDRegion permissions) Flag bits corresponding to permissions
AgendaItem	propChanger(PropChange change, Prop prop) Return an AgendaItem to propagate properties. NOTE: The AgendaItem returned is not yet scheduled.
static int	publicClubFlag() The flag for the Universal Public Club
IntegerVar	refCount()
void	removePointer(Heaper ignored) Keep a refcount of diskful pointers to myself for disk space management.
void	sendSelfTo(Xmtr xmtr) do nothing
void	setOwnFlags(int newFlags)
void	setParent(CanopyCrum p)
static void	useEndorsementFlags(PtrArray endorsements) Use a special flag to look for any of the these endorsements
CanopyCrum	verify1() BertCrum create verify1
CanopyCrum	verify2() BertCrum create verify2.
CanopyCrum	verifyHeight(IntegerVar height) Create a tree with maxHeight = height and minHeight = 2.

Methods inherited from class org.abora.gold.snarf.Abraham

actualHashForEqual, becomeStub, cleanupGarbage, destroy, destruct, diskUpdate, dismantleStatistics, fetchInfo, fetchShepherd, flockInfo, forget, getInfo, getShepherdStubCategory, isConstructed, isDestructed, isEqual, isKindOf, isPurgeable, isShepherd, isStub, isUnlocked, newShepherd, remember, restartAbraham, restartAbraham, returnToken, staticTimeNonInherited, token

Methods inherited from class org.abora.gold.xpp.basic.Heaper

abstractDeclarationFor, abstractTypeFor, addMethodAttributeToInOf, addPackage, addPackageCategory, allClientProtocolOn, argumentTypesFor, arrow, blast, blast, BLAST, cachePromiseNameTable, cachePromiseNameTableIn, canYouBecome, cast, cleanPromiseClasses, clientClassesDo, clientFunctionsOn, clientMethodsOn, clientProtocol, clientProtocolDo, clientProtocolOn, clientProtocolOn, collectibleClasses, compare, compileClientSubclasses, compileConstantPromiseMethods, compileCreateFromRcvr, compileEQ, compileGeneratedClassMethod, compileGeneratedMethod, compileHook, compilePromise, compilePromiseDefaultMethods, compilePromiseFluidDeclarations, compilePromiseHandlers, compilePromiseMethods, compileRequestCreateMsgInArguments, compileRequestEvaluateMsgInReturningArguments, compileRPCSpecialistEvaluateMsgForReturningArguments, compileSendSelfTo, compileSendSelfToSendHook, compileStubbleMethods, compileSubclassStubbleMethods, computeMangle, computePreorder, constantTypeValue, convert, convertCopyDeclarations, convertDeferredDeclarations, convertProxyDeclarations, convertSubclassCopyDeclarations, convertSubclassDeferredDeclarations, convertSubclassProxyDeclarations, copyReferencesToType, create, create, create, create, create, create, create, create, create, create, createRequestClassArguments, definesProxyMethods, delete, deref, destructor, enum, enumFlags, equals, exportName, fetchAttribute, fetchPackage, fetchSuperCategory, fileOutClientProtocol, findCategory, findSenderAndReceiverMethods, findTailInto, flushPromiseNameTable, foo, freezeClientClasses, freezeClientProtocol, freezeStProtocol, frozenClasses, garbageCollect, garbageCollectFrom, gcOpportunity, gcOpportunity, generatedCategory, generatePromiseNames, getCategory, getOrMakePackage, getSuperCategory, handlerSignaturesFrom, hash, hashForEqual, hasProxyMethods, info_clientClasses, info_clientSideClasses, info_promiseClasses, info_stProtocol, inGC, initializedClasses, initializingClasses, initPackages, initStringHashSBoxes, inspectPieces, instanceSize, IntegerVar, isByProxy, isConstructed, isDestructed, isEqualOrSubclassOf, isGenerated, isIntType, isKindOf, isRawType, make, makeClassTable, makeFillTable, makeRequestTable, mangle, markChildren, markCount, markInstances, mayBecome, mayBecomeAnySubclassOf, new1, newX, nonCopyVariables, notWorking, pack, packageClasses, packagingCategory, parseExportName, passe, pointerToStaticMember, pointerToStaticMember, pointerToVirtualMember, preorderMax, preorderNumber, printOn, PROBLEM, problems, promiseClass, promiseDefaultValue, promiseName, promiseNameTable, promiseToAbstract, registerPackageCategory, removeGeneratedCode, removeStubbleMethods, removeSubclassGeneratedCode, removeSubclassStubbleMethods, requestProcedure, requestProceduresFrom, returnTypeFor, rootName, scheduleTermination, sendProxyTo, serverNameFor, setGC, signal, signals, smalltalkSelector, stClientProtocol, stubbleSelectorTokenReturnsArguments, subclassNonCopyVariables, takeOop, togglePromiseName, togglePromiseOfParse, unimplemented, unmangle, verifyFreeze, wipeStubble

Methods inherited from class org.abora.gold.java.AboraHeaper

asOop, basicInspect, error, hack, halt, knownBug, mightNotImplement, REQUIRES, shouldImplement, shouldNotImplement, stubbleForSubclassResponsibility, thingToDo, willNotImplement

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

child1

protected CanopyCrum child1

child2

protected CanopyCrum child2

parent

protected CanopyCrum parent

minH

protected IntegerVar minH

maxH

protected IntegerVar maxH

myOwnFlags

protected int myOwnFlags

myFlags

protected int myFlags

myRefCount

protected IntegerVar myRefCount

FlagEndorsements

protected static PtrArray FlagEndorsements

OtherClubs

protected static IDRegion OtherClubs

OtherEndorsements

protected static CrossRegion OtherEndorsements

TheEFlagsCache

protected static Heaper2UInt32Cache TheEFlagsCache

ThePFlagsCache

protected static Heaper2UInt32Cache ThePFlagsCache

Constructor Detail

CanopyCrum

public CanopyCrum(int flags)

Make a canopyCrum for a root: it has no children.

CanopyCrum

public CanopyCrum(int flags,
                  CanopyCrum first,
                  CanopyCrum second)

prop must be empty

CanopyCrum

public CanopyCrum(Rcvr receiver)

Method Detail

computeJoin

public CanopyCrum computeJoin(CanopyCrum otherBCrum)

Find a canopyCrum that is an anscestor to
both the receiver and otherBCrum. otherBCrum
is added to the canopy in a pseudo-balanced fashion.
This demonstrates the beauty and power of caching
in object-oriented systems.

expand

public Pair expand()

split into two if possible, return the two leaves

includeCanopy

public void includeCanopy(CanopyCrum otherCanopy)

Install otherCanopy at or below the receiver. If the otherCanopy fits in a lower branch,
put it there. Otherwise, replace the shortest child with a new child that contains the
shortest child and otherCanopy.

isLE

public boolean isLE(CanopyCrum other)

Return true if other is equal to the receiver
or an anscestor (through the parent links).
Use caches for efficiency.

addPointer

public void addPointer(Heaper ignored)

Keep a refcount of diskful pointers to myself for disk space management. (Maybe
backpointers later.)

fetchParent

public CanopyCrum fetchParent()

flags

public int flags()

heightDiff

public IntegerVar heightDiff()

isLeaf

public boolean isLeaf()

maxHeight

public IntegerVar maxHeight()

minHeight

public IntegerVar minHeight()

removePointer

public void removePointer(Heaper ignored)

Keep a refcount of diskful pointers to myself for disk space management. (Maybe
backpointers later.)
Forget the object if it goes to zero.

setParent

public void setParent(CanopyCrum p)

canopyCache

public CanopyCache canopyCache()

dismantle

public void dismantle()

Description copied from class: Abraham

Disconnect me from the universe and throw me off the disk.
For GC safety, we keep a strongptr to ourself -- is this still necessary?

Overrides:

dismantle in class Abraham

fetchChild1

public CanopyCrum fetchChild1()

fetchChild2

public CanopyCrum fetchChild2()

makeNew

public CanopyCrum makeNew()

ownFlags

public int ownFlags()

setOwnFlags

public void setOwnFlags(int newFlags)

another

public CanopyCrum another()

Return another instance of the same
class for testing purposes.

refCount

public IntegerVar refCount()

verify1

public CanopyCrum verify1()

BertCrum create verify1

verify2

public CanopyCrum verify2()

BertCrum create verify2.

verifyHeight

public CanopyCrum verifyHeight(IntegerVar height)

Create a tree with maxHeight = height and minHeight = 2.

childArray

public Array childArray()

children

public Array children()

displayString

public java.lang.String displayString()

Overrides:

displayString in class AboraHeaper

inspect

public void inspect()

Overrides:

inspect in class AboraHeaper

inspectSubCanopy

public void inspectSubCanopy(java.lang.Object start)

propChanger

public AgendaItem propChanger(PropChange change,
                              Prop prop)

Return an AgendaItem to propagate properties.
NOTE: The AgendaItem returned is not yet scheduled. Doing so is up to my caller.

contentsHash

public int contentsHash()

This is only used by the TestPacker, so it includes all persistent state whether or not
it is semantically interesting--myRefCount is not semantically interesting.

Overrides:

contentsHash in class Abraham

changeCanopy

public boolean changeCanopy()

Figure out new props, etc. Return true if any changes may require further propagation

changeHeight

public boolean changeHeight()

Figure out new height. Return true if changes may require further propagation

makeNewParent

public CanopyCrum makeNewParent(CanopyCrum first,
                                CanopyCrum second)

Make a new crum that contains both first and second.
This method just makes a new parent whose properties are empty. My client must bring my
properties up to date

makeJoin

public CanopyCrum makeJoin(CanopyCrum otherCanopy)

Install otherCanopy as a subtree in the canopy containing the receiver. Look below
the receiver and then in successively higher branches for a branch that has
enough height difference to contain otherCanopy.

changeCanopy

public boolean changeCanopy(PropChange change)

Figure out new height, props, etc. Return true if any changes may require further
propagation

fullChange

public PropChange fullChange()

joint

public PropJoint joint()

Return the abstracted information necessary to determine whether anything leafward may
pass the filtering criteria.

sendSelfTo

public void sendSelfTo(Xmtr xmtr)

Description copied from class: Heaper

do nothing

Overrides:

sendSelfTo in class Abraham

initTimeNonInherited

public static void initTimeNonInherited()

linkTimeNonInherited

public static void linkTimeNonInherited()

endorsementsFlags

public static int endorsementsFlags(CrossRegion endorsements)

Flag bits corresponding to endorsements

permissionsFlags

public static int permissionsFlags(IDRegion permissions)

Flag bits corresponding to permissions

endorsementFlagLimit

public static int endorsementFlagLimit()

Max number of special endorsement flags

firstEndorsementsFlag

public static int firstEndorsementsFlag()

Rightmost flag for interesting endorsements

otherClubsFlag

public static int otherClubsFlag()

The flag for any other Clubs

otherEndorsementsFlag

public static int otherEndorsementsFlag()

Flag for all uninteresting endorsements

publicClubFlag

public static int publicClubFlag()

The flag for the Universal Public Club

useEndorsementFlags

public static void useEndorsementFlags(PtrArray endorsements)

Use a special flag to look for any of the these endorsements