File Map¶

An id-keyed container for the TFile records of one archive.

Values is kept sorted by id and HashSlots is an open-addressed table pointing into it, so lookups are constant time while iteration still comes out in id order.

MapHash¶

function MapHash(key, size: Integer): Integer; static;
function MapHashSize(expectedCount: Integer): Integer; static;

MapHash is the slot a key hashes to in a table of size slots, and MapHashSize is the size to give a table holding roughly expectedCount entries.

Ids are already well spread, so hashing one is only a fold back into range. Table sizes are always powers of two - at least twice the expected count, so probing stays short - which makes that fold a mask rather than a modulo, and lands a negative id in range without a correction. Doubling a power of two leaves a power of two, so TFileMap._Grow keeps the property.

TFileMap._Init¶

procedure TFileMap._Init(expectedCount: Integer);

Empties the map and sizes its hash table for roughly expectedCount entries.

The table is deliberately over-allocated - see MapHashSize - so that probing stays short; TFileMap._Grow doubles it again if it ever fills past 60%.

TFileMap._FindSlot¶

function TFileMap._FindSlot(key: Integer): Integer;

The hash slot belonging to key: either the one already holding it, or the first free one after where it hashes to. Collisions walk forward one slot at a time and wrap around.

TFileMap._Grow¶

procedure TFileMap._Grow();

Resizes the hash table to fit one more entry and reinserts every key into it. Entry order is untouched - only the slots that point at the entries are rebuilt.

It is also how a map that TFileMap.Build left without a table gets one.

FileMap.Build¶

procedure TFileMap.Build(const keys: TIntegerArray; count: Integer);

Fills the map in one pass with an empty TFile per key, sizing the key, value and hash arrays exactly once instead of regrowing them on every insert.

Only the first count entries of keys are used, so callers filling many maps in a row can reuse one buffer. They must be in ascending order, which is how reference tables store them.

Most archives of the cache hold a single file, so a map of one entry - or of none - is left without a hash table at all, HashSize staying 0: the lookups compare against the one key instead of probing, and opening a cache does one allocation less per archive for the hundred thousand odd maps it builds. TFileMap._Grow gives such a map a table if something is later added to it.

TFileMap.Exists¶

function TFileMap.Exists(key: Integer): Boolean;

Whether the map holds an entry with this id.

TFileMap.IndexOf¶

function TFileMap.IndexOf(key: Integer): Integer;

The position of this id in Values, or -1 if it is not in the map.

TFileMap.Value¶

property TFileMap.Value(key: Integer; const val: TFile);
property TFileMap.Value(key: Integer): TFile;

Reads or writes the file stored under key. Reading an id the map does not hold raises.

Writing keeps Values sorted by id. Appending an id above every existing one - which is how reference tables arrive - only costs the append; inserting one in the middle has to shift the entries after it and rebuild the hash table, so prefer TFileMap.Build when filling a map from scratch.

TFileMap.Clear¶

procedure TFileMap.Clear();

Drops every entry and the hash table with them, leaving the map as if it had never been used.