# File Map
An id-keyed container for the {ref}`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
```pascal
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 {ref}`TFileMap._Grow` keeps the property.


- - -

## TFileMap._Init
```pascal
procedure TFileMap._Init(expectedCount: Integer);
```
Empties the map and sizes its hash table for roughly `expectedCount` entries.

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


- - -

## TFileMap._FindSlot
```pascal
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
```pascal
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 {ref}`TFileMap.Build` left without a table gets one.


- - -

## FileMap.Build
```pascal
procedure TFileMap.Build(const keys: TIntegerArray; count: Integer);
```
Fills the map in one pass with an empty {ref}`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. {ref}`TFileMap._Grow` gives such a map a table if something is
later added to it.


- - -

## TFileMap.Exists
```pascal
function TFileMap.Exists(key: Integer): Boolean;
```
Whether the map holds an entry with this id.


- - -

## TFileMap.IndexOf
```pascal
function TFileMap.IndexOf(key: Integer): Integer;
```
The position of this id in `Values`, or `-1` if it is not in the map.


- - -

## TFileMap.Value
```pascal
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 {ref}`TFileMap.Build` when filling a map
from scratch.


- - -

## TFileMap.Clear
```pascal
procedure TFileMap.Clear();
```
Drops every entry and the hash table with them, leaving the map as if it had never been used.