org.abora.gold.collection.sets
Class HashSet

java.lang.Object
  |
  +--org.abora.gold.java.AboraHeaper
        |
        +--org.abora.gold.xpp.basic.Heaper
              |
              +--org.abora.gold.collection.sets.ScruSet
                    |
                    +--org.abora.gold.collection.sets.MuSet
                          |
                          +--org.abora.gold.collection.sets.HashSet

Direct Known Subclasses:

ActualHashSet

public class HashSet

extends MuSet

The HashSet class is an implementation of a MuTable set that can contain arbitrary
Heapers. It uses the hashForEqual member function to get a hash value for the items
contained in the set. The set establishes the equality of objects in the set through the
isEqual: function.
The implemention of HashSet is straightforward. There are primitive tables used to store
pointers to the stored items (myHashEntries), and their corresponding hash values
(myHashValues). The HashSet also maintain a current tally of the number of items in the
set.
definition: preferred location - the location calculated from item hashForEqual mod
tableSize.
The search routine first calculates the preferred location. This is used as the first
location in the myHashEntries table to test for the presence of the item, and the search
proceeds forward (in a linear probe) from there. If there is no object at that position,
the routine assumes the item is not in the table. If there is an item there, the first
test is to check if the item''s hash matches the hash myHashValues at that position. If
the match is successful, a full isEqual: test is performed. If the isEqual: test
succeeds, the item is present in the set. If either test fails, the entry at the desired
location is tested to see if it is closer to its own preferred location than the item (a
test which necessarily fails the first time). If it is closer, the item is not in the
set. (This extra test is what distinguishes an ordered hash set from an ordinary hash
set. It often detects the absense of an item well before an empty slot is encountered,
and the advantage becomes pronounced as the set fills up. Ordered hash sets with linear
probe beat ordinary hash sets with secondary clustering on misses (the big time eater),
yet they preserve linear probe''s easy deletion.)
On insertion to the set, the hash and probe sequence is essentially the same as the
search. The main exception is that on a hash collision, the item bumps down any item that
is no farther than its own preferred position.
An example is perhaps in order:
the set contains items a, b, and c in table locations 3, 4, and 5. Assume that a has
location 2 as its preferred location, while b and c both have location 4 as their
preferred location. Now, if we attempt to add an item d to the table, and item d were to
have a preferred location of 3. Since 3 is already occupied by something that is already
far from its preferred location, we probe for a another location. At location 4, item d
is displaced by one from its preferred location. Since b is in it''s preferred location
(4) d replaces it, and we move item b down. Item c is in location 5 because it had
already been bumped from location 4 when b was inserted previously. B again ties with c,
so it pushes it out of location 5, replacing it there. Item c will end up in location 6.
This probe function minimizes the individual displacement of hash misses, while keeping
the most items in their preferred locations.
Note that, though the choice of which item to bump is obvious when the distances from home
are different, when they are equal we could have given preference to either the new or the
old item. We chose to put the new item closer to its preferred location, on the
assumption that things entered recently are more likely to be looked up than things
entered long ago.
This algorithm was derived from a short discussion with Michael McClary (probably
completely missing his intended design - all mistakes are mine -- heh).
(Unfortunately, I wasn''t clear in the discussion. Since hugh was unavailable when I
discovered this, I''ve taken the opportunity to practice with Smalltalk and corrected both
the explanation and the code rather than sending him a clarification. -- michael)

Field Summary

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

HashSet()

Method Summary

ImmuSet	asImmuSet() Return an immu snapshot of my current state.
MuSet	asMuSet() Return a Mu whose initial state is the same as my current state, but which will now deviate independently of me.
ScruSet	copy() A new one whose initial state is my current state, but that doesn't track changes.
IntegerVar	count() How many elements are currently in the set.
boolean	hasMember(Heaper someone) Is someone a member of the set now?
Stepper	immuStepper()
void	introduce(Heaper anElement) Add anElement to my members, but only if it isn't already a member. If it is already a member, BLAST
boolean	isEmpty() Whether it currently has any elements
static Heaper	make()
static Heaper	make(Heaper something)
static Heaper	make(IntegerVar someSize) someSize is a non-semantic hint about how big the set might get.
void	printInternals(java.io.PrintWriter oo)
void	remove(Heaper anElement) Remove anElement from my members.
Stepper	stepper() Returns a stepper which will enumerate all the elements of the set in some unspecified order
void	store(Heaper anElement) Add anElement to my set of members.
Heaper	theOne() Iff I contain exactly one member, return it.
void	wipe(Heaper anElement) make anElement no longer be one of my members.

Methods inherited from class org.abora.gold.collection.sets.MuSet

actualHashForEqual, fromStepper, initTimeNonInherited, isEqual, make, make, problems, restrictTo, storeAll, wipeAll

Methods inherited from class org.abora.gold.collection.sets.ScruSet

asArray, asOrderedCollection, contentsEqual, contentsHash, dox, inspect, intersects, isEqual, isSubsetOf, printOn, printOnWithSimpleSyntax, printOnWithSyntax

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, cleanupGarbage, 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, destroy, destruct, 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, isUnlocked, linkTimeNonInherited, makeClassTable, makeFillTable, makeRequestTable, mangle, markChildren, markCount, markInstances, mayBecome, mayBecomeAnySubclassOf, new1, newX, nonCopyVariables, notWorking, pack, packageClasses, packagingCategory, parseExportName, passe, pointerToStaticMember, pointerToStaticMember, pointerToVirtualMember, preorderMax, preorderNumber, PROBLEM, promiseClass, promiseDefaultValue, promiseName, promiseNameTable, promiseToAbstract, registerPackageCategory, removeGeneratedCode, removeStubbleMethods, removeSubclassGeneratedCode, removeSubclassStubbleMethods, requestProcedure, requestProceduresFrom, returnTypeFor, rootName, scheduleTermination, sendProxyTo, sendSelfTo, 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, displayString, 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

Constructor Detail

HashSet

public HashSet()

Method Detail

hasMember

public boolean hasMember(Heaper someone)

Description copied from class: ScruSet

Is someone a member of the set now?

Overrides:

hasMember in class MuSet

isEmpty

public boolean isEmpty()

Description copied from class: ScruSet

Whether it currently has any elements

Overrides:

isEmpty in class MuSet

copy

public ScruSet copy()

Description copied from class: ScruSet

A new one whose initial state is my current state, but that doesn't track
changes. Note that there is no implication that these can be 'destroy'ed
separately, because (for example) an ImmuSet just returns itself

Overrides:

copy in class MuSet

count

public IntegerVar count()

Description copied from class: ScruSet

How many elements are currently in the set. Being a set, if the same element is put into
the set twice,
it is only in the set once. 'Same' above is according to 'isEqual'.

Overrides:

count in class MuSet

stepper

public Stepper stepper()

Description copied from class: ScruSet

Returns a stepper which will enumerate all the elements of the set in some unspecified
order

Overrides:

stepper in class MuSet

theOne

public Heaper theOne()

Description copied from class: ScruSet

Iff I contain exactly one member, return it. Otherwise BLAST.
The idea for this message is taken from the THE function of ONTIC
(reference McAllester)

Overrides:

theOne in class ScruSet

introduce

public void introduce(Heaper anElement)

Description copied from class: MuSet

Add anElement to my members, but only if it isn't already a member.
If it is already a member, BLAST

Overrides:

introduce in class MuSet

remove

public void remove(Heaper anElement)

Description copied from class: MuSet

Remove anElement from my members. If it isn't currently a member, then BLAST

Overrides:

remove in class MuSet

store

public void store(Heaper anElement)

Add anElement to my set of members. No semantic effect if anElement is already a member.

Overrides:

store in class MuSet

wipe

public void wipe(Heaper anElement)

make anElement no longer be one of my members. No semantic effect if it already isn't a
member.

Overrides:

wipe in class MuSet

asImmuSet

public ImmuSet asImmuSet()

Description copied from class: ScruSet

Return an immu snapshot of my current state. Should probably be done with a
Converter rather than with a message (for the reasons listed in the Converter
class comment). In terms of the Stamp/Bert analogy mentioned in the class
comment, asImmuSet is like asking for the current Stamp.

Overrides:

asImmuSet in class MuSet

asMuSet

public MuSet asMuSet()

Description copied from class: ScruSet

Return a Mu whose initial state is the same as my current state, but which
will now deviate independently of me. In terms of the Stamp/Bert analogy
mentioned in the class comment, asMuSet is like asking for a new Bert starting
on the current Stamp.

Overrides:

asMuSet in class MuSet

printInternals

public void printInternals(java.io.PrintWriter oo)

immuStepper

public Stepper immuStepper()

Overrides:

immuStepper in class MuSet

make

public static Heaper make()

make

public static Heaper make(Heaper something)

make

public static Heaper make(IntegerVar someSize)

Description copied from class: MuSet

someSize is a non-semantic hint about how big the set might get.