I6 Template Layer

KOV Support.

See the BlockValues.i6t segment for the specification of the following routines.

Other Definitions.

Tunable Parameters.

These constants affect the performance characteristics of the dictionary structures used for relations on the heap. Changing their values may alter the balance between memory consumption and running time.

RRP_MIN_SIZE, RRP_RESIZE_SMALL, and RRP_RESIZE_LARGE must all be powers of two.

Abstract Relations.

As the following shows, we can abstractly use a relation – that is, we can use a relation whose identity we know little about – by calling its handler routine R in the form R.

The task should be one of: RELS_TEST, RELS_ASSERT_TRUE, RELS_ASSERT_FALSE, RELS_SHOW, RELS_ROUTE_FIND, RELS_ROUTE_FIND_COUNT, RELS_COPY, RELS_DESTROY, RELS_LOOKUP_ANY, RELS_LOOKUP_ALL_X, RELS_LOOKUP_ALL_Y, RELS_LIST, or RELS_EMPTY.

RELS_SHOW produces output for the SHOWME testing command. RELS_ROUTE_FIND finds the next step in a route from X to Y, and RELS_ROUTE_FIND_COUNT counts the shortest number of steps or returns -1 if no route exists. RELS_COPY makes a deep copy of the relation by replacing all block values with duplicates, and RELS_DESTROY frees all block values. RELS_LOOKUP_ANY finds any one of the X values related to a given Y, or vice versa, or checks whether such an X or Y value exists. RELS_LOOKUP_ALL_X and RELS_LOOKUP_ALL_Y produce a list of all the X values related to a given Y, or vice versa. RELS_LIST produces a list of all X values for which a corresponding Y exists, or vice versa, or a list of all (X,Y) pairs for which X is related to Y. RELS_EMPTY either makes the relation empty (if X is 1) or non-empty (if X is 0) or makes no change (if X is negative), and in any case returns true or false indicating whether the relation is now empty.

Because not every relation supports all of these operations, the "permissions" word in the block is always a bitmap which is a sum of those operations it does offer.

At present, these permissions are not checked as rigorously as they should be (they're correctly set, but not much monitored).

Empty Relations.

The absolute minimum relation is one which can only be tested, and which is always empty, that is, where no two values are ever related to each other. The necessary handler routine is EmptyRelationHandler.

Creation.

Something we have to be careful about is what we mean by copying, or indeed creating, a relation. For example, if we write

>> let Q be a relation of objects to objects; >> let Q be the containment relation;

...we aren't literally asking for Q to be a duplicate copy of containment, which can then independently evolve – we mean in some sense that Q is a pointer to the one and only containment relation. On the other hand, if we write

>> let Q be a relation of numbers to numbers; >> make Q relate 3 to 7;

then the second line clearly expects Q to be its own relation, newly created.

We cope with this at creation time. If we're invited to create a copy of an existing relation, we look to see if it is empty – which we detect by its use of the EmptyRelationHandler handler. The empty relations are exactly those used as default values for the relation kinds; thus that's what will happen when Q is created. If we find this handler, we intercept and replace it with one of the heap relation handlers, which thus makes the relation a newly constructed data structure which can grow freely from here.

Destruction.

If the relation stores block values on either side, invoke the handler using a special task value to free the memory associated with them.

Copying.

Same as destruction: invoke the handler using a special value to tell it to perform deep copying.

Comparison.

It really isn't clear how to define equality for relations, but we follow the doctrine above. What we don't do is to test its actual state – that would be very slow and might be impossible.

Printing.

Naming.

Choose Relation Handler.

We implement two different various-to-various handler routines for the sake of efficiency. The choice of handler routines is made based on the kinds of value being related. Each handler also has a corresponding wrapper for symmetric relations.

Valency.

"Valency" refers to the number of participants allowed on either side of the relation: various-to-various, one-to-various, various-to-one, or one-to-one. A newly created relation is always various-to-various. We allow the author to change the valency, but only if no entries have been added yet.

Double Hash Set Relation Handler.

This implements relations which are stored as a double-hashed set. The storage comprises a list of three-word entries (F, X, Y), where F is a flags word. The ordering of the list is determined by a probe sequence which depends on the combined hash values of X and Y.

The "storage" word in the header stores one less than the number of entries in the list; the number of entries in the list is always a power of two, so this will always be a bit mask. The "used" and "filled" words store the number of entries which currently hold a value, and the number of entries which have ever held a value (even if it was since deleted), respectively.

The utility routine DoubleHashSetLookUp locates the hash entry for a key/value pair. It returns either the (non-negative) number of the entry where the pair was found, or the (negative) bitwise NOT of the number of the first unused entry where the pair could be inserted. It uses the utility routine DoubleHashSetEntryMatches to compare entries to the sought pair.

The utility routine DoubleHashSetCheckResize checks whether the dictionary has become too full after inserting a pair, and expands it if so.

Hash List Relation Handler.

This implements relations which are stored as a hash table mapping keys to either single values or lists of values. The storage comprises a list of three-word entries, either (F, X, Y) or (F, X, L), where F is a flags word distinguishing between the two cases (among other things). In the latter case, L is a pointer to a list (LIST_OF_TY) containing the values.

The "storage", "used", and "filled" words have the same meanings as above.

HashListRelationHandler is a thin wrapper around HashCoreRelationHandler, which is shared with two other handlers below.

Hash Table Relation Handler.

This is the same as the Hash List Relation Handler above, except that only one value may be stored for each key. This implements various-to-one relations.

Reversed Hash Table Relation Handler.

This is the same as the Hash Table Relation Handler except that the sides are reversed. This implements one-to-various relations.

Symmetric Relation Handlers.

These are simple wrappers around the asymmetric handlers defined above. When a pair is inserted or removed, the wrappers insert or remove the reversed pair as well.

SymDoubleHashSetRelationHandler and SymHashListRelationHandler implement symmetric V-to-V relations. Sym2in1HashTableRelationHandler implements symmetric 1-to-1. ("SymTwoInOneHashTableRelationHandler" would have exceeded Inform 6's 32-character name limit.)

Hash Core Relation Handler.

This implements the core functionality that is shared between HashListRelationHandler, HashTableRelationHandler, and ReversedHashTableRelationHandler. All three handlers are the same except for whether the left or right side is the "key" and whether or not multiple values may be stored for a single key.

As noted above, the table contains three-word entries, (F, X, Y), where F is a flags word. Only the hash code of X is used. If F includes RRF_SINGLE, Y is a single value; otherwise, Y is a list (LIST_OF_TY) of values. If mult is zero, RRF_SINGLE must always be set, allowing only one value per key: a new pair (X, Y') will replace the existing pair (X, Y).

Equivalence Hash Table Relation Handler.

This implements group relations. The table format is identical to that used by HashCoreRelationHandler, but we use it differently. Although the relation appears to relate Xs to Xs as far as the game is concerned, the table actually relates Xs to numbers, where each number identifies a group of related items. Any X not listed in the table is implicitly in a single-member group.

When a pair (X, Y) is inserted, one of four cases occurs:

1. Neither X nor Y has a table entry. We search the table to find the next unused group number, then add both X and Y to that group.

2. Both X and Y have existing table entries. If the group numbers differ, we walk through the table and change all occurrences of the higher number to the lower one.

3. X has an existing table entry but Y does not. We add a Y entry using the group number of X.

4. Y has an existing table entry but X does not. We add an X entry using the group number of Y.

When a pair (X, Y) is removed, we first verify that X and Y are in the same group, then delete the table entry for X. This may leave Y in a single-member group, which could be deleted, but detecting that situation would be inefficient, so we keep the Y entry regardless.

This code uses the Hash Core utility functions defined above.

Two-In-One Hash Table Relation Handler.

This implements one-to-one relations, which are stored as a hash table mapping keys to single values and vice versa. To enforce the one-to-one constraint, we need the ability to quickly check whether a value is present. This could be done with two separate hash tables, one mapping X to Y and one the opposite, but in the interest of conserving memory, we use a single table for both.

Each four-word entry (F, E, K, V) consists of a flags word F, an entry key E (which may be a "key" or "value" in the hash table sense), a corresponding key K (when E is used as a value), and a corresponding value V (when E is used as a key). The pair of related values (X, Y) is represented as two table entries: (F, X, _, Y) and (F, Y, X, _).

To conserve memory when block values are used, we only create one copy of X and/or Y to share between both entries. When adding a key or value which already exists on either side of the relation, the previous copy will be used. Copies are freed when they are no longer used as entry keys.

Each entry's flags word F indicates, in addition to the standard flags RRF_USED and RRF_DELETED, also whether the entry contains a corresponding key K and/or value V (RRF_HASX, RRF_HASY) and whether the entry's key is the same kind of value as X or Y (RRF_ENTKEYX, RRF_ENTKEYY). If both sides of the relation use the same kind of value, or if both sides are word values, both RRF_ENTKEYX and RRF_ENTKEYY will be set on every used entry.

Of particular note for this handler is the utility function TwoInOneDelete, which clears one half of an entry (given its entry key), and optionally clears the corresponding other half stored in a different entry. That is, given the entries (F, X, _, Y) at index i and (F, Y, X, _) elsewhere, TwoInOneDelete(rel, i, kx, ky, RRF_ENTKEYX, 1) will clear both entries and mark them as deleted. If, however, those entries overlap with other pairs – say they're (F, X, A, Y) and (F, Y, X, B) – then the same call to TwoInOneDelete will leave us with (F, X, A, _) and (F, Y, _, B), having cleared the parts corresponding to the pair (X, Y) but not the parts corresponding to the pairs (A, X) and (Y, B), and will not mark either as deleted. (Such overlap is only possible when the domains of X and Y are the same kind of value.)

Empty.

This implements the "empty" adjective. We can always check whether a relation is empty. For most relation types, we can cause the relation to become empty by removing all pairs: but this is impossible for equivalence relations, which are never empty, since any X is equivalent to itself. And we can never force a relation to become non-empty, since that would require making up data.

In any case, the implementation is delegated to the relation handler.