Object <- FixedList <- IntegerList <- HashTable |
|
|
EntryCount HashEntries HashEntrySize HashTableEntryBytesStoredSeparately |
| Field | Type | |
|---|---|---|
| HashTable: | hashEntries: | FixedList |
| hashEntrySize: | Unsigned | |
| lgCount: | Unsigned | |
| entryCount: | Unsigned | |
| firstFreeEntry: | Unsigned | |
| minPercentFull: | UnsignedShort | |
| maxPercentFull: | UnsignedShort |
instance HashTable tag;
hashEntries: nilObject;
hashEntrySize: 0;
lgCount: 0;
entryCount: 0;
firstFreeEntry: 0;
minPercentFull: 0;
maxPercentFull: 0;
end instance;
Define Class HashTable;
inherits from IntegerList;
has no dispatcher hintdata;
field hashEntries: FixedList, getter;
// used by corresponding attribute; set up by Init
field hashEntrySize: Unsigned, getter;
// used by corresponding attribute; set up by Init
field lgCount: Unsigned;
// base-2 logarithm of number of slots in the table (returned by the Count method)
field entryCount: Unsigned, getter;
// number of entries in table
field firstFreeEntry: Unsigned;
// index of first hole in entries
// all holes can be found by following indexes in element headers
field minPercentFull: UnsignedShort;
// table is halved in size when it gets less full than this
field maxPercentFull: UnsignedShort;
// table is doubled in size when it gets more full than this
// adding and removing entries
operation AddHashEntry(newEntry: ReadOnlyPointer): TrackedIndexHack;
// adds <newEntry> to table
// if table is now more full than maxPercentFull, doubles size of table and rehashes
// Return the entry's index, suitable for ReadHashEntryAt, in the table.
// The index becomes invalid as soon as memory is allocated when this hash table isn't fastened.
// override rarely
operation RemoveHashEntryForKey(key: ReadOnlyPointer);
// removes any one hash entry that matches <key>; does not look for more than one
// if table is now less full than minPercentFull, halves size of table and rehashes
// if more than one entry might match key, use RemoveHashEntriesForKey instead
// override rarely
operation RemoveHashEntriesForKey(key: ReadOnlyPointer);
// removes all hash entries that match <key>
// if table is now less full than minPercentFull, halves size of table and rehashes
// if only one entry might match key, use faster RemoveHashEntryForKey instead
// override rarely
// accessing entries
operation FindMatchingHashEntry(key: ReadOnlyPointer; returnEntry: Pointer);
// fills <returnEntry> with any one hash entry that matches <key>
// if more than one entry might match key, use EachMatchingHashEntry instead
// override rarely
operation EachHashEntry(modify: Boolean; functionCanMoveMemory: Boolean; function: EachHashEntryFunction;
parameters: Pointer): Boolean;
// Call function with a pointer to each hash table entry. If modify is true, the function
// can modify the entry. If the function returns erStop or erRemoveStop, terminate the iteration
// immediately and return false; otherwise return true after the iteration completes.
// If the function returns erRemoveContinue or erRemoveStop, remove the entry that was just
// passed to the function.
// The function is not allowed to allocate memory unless functionCanMoveMemory is true.
// The function is not allowed to make any hash table calls on this hash table that would modify the table.
// override rarely
operation EachMatchingHashEntry(key: ReadOnlyPointer; modify: Boolean; functionCanMoveMemory: Boolean;
function: EachHashEntryFunction; parameters: Pointer): Boolean;
// Call function with a pointer to each hash table entry that matches the key. If modify is true, the function
// can modify the entry. If the function returns erStop or erRemoveStop, terminate the iteration
// immediately and return false; otherwise return true after the iteration completes.
// If the function returns erRemoveContinue or erRemoveStop, remove the entry that was just
// passed to the function.
// The function is not allowed to allocate memory unless functionCanMoveMemory is true.
// The function is not allowed to make any hash table calls on this hash table that would modify the table.
// If only one hash entry might match key, use simpler FindMatchingHashEntry instead.
// override rarely
attribute HashEntries: FixedList, readOnly;
// for the default version of CreateHashEntriesList, this field contains a DataList
// each element of list contains a 4-byte header followed by a hashEntry
// header contains index to next element with same hash value
// stride is header size (4 bytes) plus amount of non-object data in each entry
// object data must be kept separately to allow object iteration
// rarely override
// call from overrides of Read/WriteHashEntryAt
attribute EntryCount: Unsigned, readOnly;
// returns the number of used entries in the hash table
attribute HashEntrySize: Unsigned, readOnly;
// returns size of one hash entry, including objects that are stored apart from <entries> field
// size is stored in <hashEntrySize> field
// rarely override (store different number in field instead)
operation ReadHashEntryAt(index: TrackedIndex; returnElement: Pointer; var link: TrackedIndex): Boolean;
// fills in <returnElement> with hash entry at position <index> of entries list
// sets link to the link from the header of entry at this position
// returns true if this entry is deleted
// default implementation assumes all entry data is stored in entries list
// override sometimes to fill in <returnElement> piece-by-piece if some entry data is stored elsewhere,
// or to mask off additional bits in header stored by WriteHashEntryHeaderAt
// must override if entry data includes object references, because they must be stored separately
operation ReadHashEntryHeaderAt(index: TrackedIndex; var link: TrackedIndex): Boolean;
// sets link to the link from the header of entry at position <index> of entries list
// returns true if that entry is deleted
// to get entry data as well as header, call ReadHashEntryAt instead
// override sometimes to mask off additional bits in header stored by WriteHashEntryHeaderAt
operation WriteHashEntryAt(index: TrackedIndex; newElement: ReadOnlyPointer);
// replaces hash entry at position <index> of entries list with <newElement>
// zeroes out the link and deleted flag of this entry
// default implementation stores all entry data in entries list
// override sometimes to store parts of newElement piece-by-piece if some entry data is stored elsewhere
// must override if entry data includes object references, because they must be stored separately
operation WriteHashEntryHeaderAt(index: TrackedIndex; link: TrackedIndex; deleted: Boolean);
// writes header of entry of position <index> of entries list
// high bit of header is used to store deleted-entry bit
// override sometimes to store additional bits in header (thus restricting maximum number of entries)
// creating programmatically
overrides Init;
// sets up size of entries, initial size of table, and min and maxPercentFull from parameters
// uses default values if parameters are not supplied at all, or if parameter fields are zero
// default values are 16 (1<<4) for table size, 8 for entry size, 25 for minPercentFull, and 200 for maxPercentFull
// assumes all entry data is stored in <entries> field, and sets stride accordingly
// must override again if some entry data is stored separately from <entries> field
operation CreateHashEntriesList();
// creates the list of hash entires
// override if your hash table needs to create a different type of list
attribute HashTableEntryBytesStoredSeparately: Unsigned, readOnly;
// returns number of bytes that are stored in separate lists
// defaults to 0, overridden by RenumberableHashTable and others
// hashing and resizing
operation ShouldEnlargeHashTable(): Unsigned;
// returns the base-2 logarithm of the size for table if enlarging it is a good idea
// returns -1 if there is no need to enlarge it
// default implementation returns double current size if table is more than maxPercentFull
// override sometimes to include other criteria
operation ShouldShrinkHashTable(): Unsigned;
// returns the base-2 logarithm of the size for table if shrinking it is a good idea
// returns -1 if there is no need to shrink it
// default implementation returns half current size if table is less than minPercentFull
// and has at least 16 slots
// override sometimes to include other criteria
operation RehashTable(newLgCount: Unsigned; index: TrackedIndexPointer);
// resizes self to <newLgCount>, then rehashes all elements
// usually called when table has grown too large or too small
// empty entries are collapsed out, even if <newLgCount> matches existing lgCount
// override sometimes to adjust other data structures after entries are compacted
// If index is non-nil, it points to an index of an existing hash table entry;
// update that index to reflect the entry's position after the rehash.
// guts often implemented or overridden by subclasses
operation FastHashEntryAccess(): Boolean;
// returns true if the following are all true:
// KeyMatchesHashEntry isn't overriden, and
// ReadHashEntryAt isn't overriden, and
// WriteHashEntryAt isn't overriden.
// override whenever the above conditions aren't satisfied;
// Note, though, that returning false will
// considerably slow down hash table iteration.
operation ComputeHashFromKey(key: ReadOnlyPointer): Unsigned;
// returns hash value computed from key
// default implementation returns first 4 bytes of key
// override often to provide a better hash function
operation ComputeHashFromHashEntry(entry: ReadOnlyPointer): Unsigned;
// returns hash value computed from key
// calls ComputeHashFromKey directly on the entry; assumes key is at start of entry
// override to extract key from entry and call ComputeHashFromKey if key is not at start
operation KeyMatchesHashEntry(key: ReadOnlyPointer; entry: ReadOnlyPointer): Boolean;
// returns true if <key> is same as key of <entry>
// default implementation compares first 4 bytes at key address with the first 4 bytes of entry address
// override if key is not 4 bytes long, or if key is not at start of entry
operation HashEntryIndexChanged(entry: ReadOnlyPointer; fromIndex: TrackedIndex; toIndex: TrackedIndex);
// Called when the hash entry is moved from index fromIndex to index toIndex in the hashEntries
// array. This method can update other data structures outside the hash table to refer to the new
// index.
overrides Compact;
#ifdef TRACKED_INDEX
intrinsic InternalTrackedIndexList(): TrackedIndexPointerReference;
// Returns a pointer to the head of a list used to track all the
// indexes in all packages.
#endif
#ifdef VALIDATE
operation KeyInHashEntry(entry: ReadOnlyPointer): ReadOnlyPointer;
// returns pointer to key that's in <entry> parameter
// used only by Validate
// default implementation assumes key is at beginning of entry
// override to return different pointer if key is elsewhere in entry
// override to return nil if key is not stored in entry (then validate check will be skipped)
// CAUTION: Some implementations use different formats for keys in entries and outside the hash table.
// In that case the returned pointer may point to a global variable, so this routine must not be called
// recursively.
overrides Validate;
// checks that each element in hash entries list can be found with EachMatchingHashEntry
#endif
end class;