I6 Template Layer

Find Column.

Columns can be referenced either by their physical column numbers – from 1 to, potentially, 99 – or else by unique ID numbers associated with column names. For instance, if a table has a column called "liquid capacity", then all references to its "liquid capacity entry" are via the ID number associated with this column name, which will be ≥ 100 and on the other hand ≤ TB_COLUMN_NUMBER. At present, this is only 511, so there can be at most 411 different column names across all the tables present in the source text. (It is just about possible to imagine this being a problem on a very large work, so we will probably one day revise the above to make use of the larger word-size in Glulx and so raise this limit. But so far nobody has got even close to it.)

Number of Rows.

The columns in a table can be assumed all to have the same height (i.e., number of rows): thus the number of rows in T can be calculated by looking at column 1, thus...

Blanks.

Each table entry is stored in a single word in memory: indeed, column C row R is at address (T-->C)-->(R+COL_HSIZE).

But this is not sufficient storage in all cases, because each entry can be either a value or can be designated "blank". Since, for some columns at least, the possible values include every number, we find that we have to store 2¹⁶+1 possibilities given only a 16-bit memory word. (Well, or 2³²+1 with a 32-bit word, depending on the virtual machine.) This cannot be done.

We therefore need, at least in some cases, an additional bit of storage for each table entry which indicates whether or not it is blank. If we provided such a bit for every table entry, that would be a fairly simple system to implement, but it would also be wasteful of memory, with an overhead of about 5% in practice: and memory in the virtual machine is in very short supply. The reason such a system would be wasteful is that many columns are known to hold values which are in a narrow range; for instance, a time of day cannot exceed 1440, and there will never be more than 10,000 rulebooks or scenes, and so on. For such columns it would be more efficient and indeed faster to indicate blankness by using an exceptional value in the memory cell which is such that it cannot be valid for the kind of value stored in the column. We therefore provide a "blanks bitmap" for only some columns.

This leads us to define the following dummy value, chosen so that it is both impossible for most kinds of value – which is easy to arrange – and also unlikely for even those kinds of value where it is legal. For instance, -1 would be impossible for enumerative kinds of value such as rulebooks and scenes, but it would be a poor choice for the dummy value because it occurs pretty often as an integer. Instead we use the constant IMPROBABLE_VALUE, whose value depends on the word size of the virtual machine, and which is declared in Definitions.i6t.

An entry is therefore blank if and only if either (a) its column has no blanks bitmap and the stored entry is TABLE_NOVALUE, or (b) its column does have a blanks bitmap, the blanks bit for this entry is set, and the stored entry is also TABLE_NOVALUE.

To look up the blanks bitmap is a little slower than to access the stored entry directly. Most of the time, entries accessed will be non-blank: so it is efficient to have a system where we can quickly determine this. If we look at the entry and find that it is not TABLE_NOVALUE, then we know it is not a blank. If we find that it is TABLE_NOVALUE, on the other hand, then quite often the column has no blanks bitmap and again we have a quick answer: it's blank. Only if the column also has a blanks bitmap do we need to check that we haven't got a false negative. (The more improbable TABLE_NOVALUE is as a stored value, the rarer it is that we have to check the blanks bitmap for a non-blank entry.)

Masks.

The blanks bitmaps are stored as bytes; we therefore need a quick way to test or set whether bit number i of a byte is zero, where 0 ≤ i ≤ 7. I6 provides no very useful operators here, whereas memory lookup is cheap, so we use two arrays of bitmaps:

Testing Blankness.

The following routine is the one which checks that there is no false negative: it should be used when we know that the table entry is TABLE_NOVALUE and we need to check the blank bit, if there is one, to make sure the entry is indeed blank.

The second word in the column table header, C-->2, holds the address of the blanks bitmap: this in turn contains one bit for each row, starting with the least significant bit of the first byte. If the table contains a number of rows which isn't a multiple of 8, the spare bits at the end of the last byte in the blanks bitmap are wasted, but this is an acceptable overhead in practice.

Force Entry Blank.

We blank a table cell by storing TABLE_NOVALUE in its entry word and also setting the relevant bit in the blanks bitmap, if there is one.

We need to be careful if the column holds a kind of value where values are pointers to blocks of allocated memory, because if so then overwriting such a value might lead to a memory leak. So in such cases we call BlkValueFree to free the memory block. (Note that each memory block is pointed to by one and only one I7 value at any given time: we are using them as values, not pointers to values. So if this reference is deleted, it's by definition the only one.) TABLE_NOVALUE is chosen such that it cannot be an address of a memory block, which is convenient here. (The value 0 means "no memory block allocated yet".)

Force Entry Non-Blank.

To unblank a cell, we need to clear the relevant bit in the bitmap. We then go on to write a new value in to the entry – thus overwriting the TABLE_NOVALUE value – but that isn't done here; the expectation is that whoever calls this routine is just about to write a new entry anyway.

The exception is again for columns holding a kind of value pointing to a memory block, where we create a suitable initialised but uninteresting memory block for the KOV in question, and set the entry to that.

Swapping Blank Bits.

When sorting a table, we obviously need to swap rows from time to time; if any of its columns have blanks bitmaps, then the relevant bits in them need to be swapped to match, and the following routine performs this operation for two rows in a given column.

Moving Blank Bits Down.

Another common table operation is to compress it by moving all the blank rows down to the bottom, so that non-blank rows occur in a contiguous block at the top: this means table sorting can be done without having to refer continually to the blanks bitmaps. The following operation is useful for keeping the blanks bitmaps up to date when blank rows are moved down.

Table Row Corresponding.

TableRowCorr(T, C, V) returns the first row on which value V appears in column C of table T, or prints an error if it doesn't.

ExistsTableRowCorr(T, C, V) returns the first row on which V appears in column C of table T, or 0 if V does not occur at all. If the column is a topic, then we match the entry as a snippet against the value as a general parsing routine.

Table Look Up Corresponding Row.

TableLookUpCorr(T, C1, C2, V) finds the first row on which value V appears in column C2, and returns the corresponding value in C1, or prints an error if the value V cannot be found or has no corresponding value in C1.

ExistsTableLookUpCorr(T, C1, C2, V) returns true if the operation TableLookUpCorr(T, C1, C2, V) can be done, false otherwise.

Table Look Up Entry.

TableLookUpEntry(T, C, R) returns the value at column C, row R, printing an error if that doesn't exist.

ExistsTableLookUpEntry(T, C, R) returns true if a value exists at column C, row R, false otherwise.

Blank Rows.

TableRowIsBlank(T, R) returns true if row R of table T is blank. (R must be a legal row number.)

TableBlankOutRow(T, R) fills row R of table T with blanks. (R must be a legal row number.)

TableBlankRows(T) returns the number of blank rows in T.

TableFilledRows(T) returns the number of non-blank rows in T.

TableBlankRow(T) finds the first blank row in T.

Random Row.

TableRandomRow(T) chooses a random non-blank row in T.

Swap Rows.

TableSwapRows(T, R1, R2) exchanges rows R1 and R2.

Compare Rows.

TableCompareRows(T, C, R1, R2, D) returns:

(a) +1 if the entry at row R1 of column C is > the entry at row R2, (b) 0 if they are equal, and (c) -1 if entry at R1 < entry at R2.

When D = +1, a blank value is greater than all other values, so that in an ascending sort the blanks come last; when D = -1, a blank value is less than all others, so that once again blanks are last. Finally, a wholly blank row is always placed after a row in which the entry in C is blank but where other entries are not.

Move Row Down.

Shuffle.

TableShuffle(T) sorts T into random row order.

Next Row.

TableNextRow(T, C, R, D) is used when scanning through a table in order of the values in column C: ascending order if D = 1, descending if D = -1. The current position is row R of column C, or R = 0 if we have not yet found the first row. The return value is the row number for the next value, or 0 if we are already at the final value. Note that if there are several equal values in the column, they will be run through in turn, in order of their physical row numbers - ascending if D = 1, descending if D = -1, so that using the routine with D = -1 always produces the exact reverse ordering from using it with D = 1 and the same parameters. Rows with blank entries in C are skipped.

will perform a loop of valid row numbers in order of column C.

Move Blanks to Back.

Sort.

This is really only a front-end: it calls the sorting code at Sort.i6t.

Print Table Name.

NI fills this in: it's used to say the "table" kind of value.

Print Table to File.

This is how we serialise a table to an external file, though the writing is done by printing characters in the standard way; it's just that the output stream will be an external file rather than the screen when this routine is called.

Read Table from File.

And this is how we unserialise again. It makes sense only on Glulx.

Print Rank.

The table of scoring ranks is a residue from the ancient times of early IF: it gets a tiny amount of special treatment here, even though I7 works tend not to use these now dated conventions.

Debugging.

Routines to print the state of a table, for debugging purposes only.