/** Instance Repository

<h1>Synopsis</h1>
    Describes the algorithms and architecture of the instances repository 
    (that part of the repository which deals with instances).

<h1>Layout</h1>

All files belonging to the instance repository are stored under the
repository/instances directory. For each class, two files are maintained:
an index file (with a ".idx" extension) and an instance file which bears
the name of the class whose instances it contains. For example, suppose 
there is a class called "Zebra". Then two files are used to manage its 
instances:

    <pre>
    repository/instances/Zebra.idx (called the index file)
    repository/instances/Zebra (called the instance file)
    </pre>

The first line of the index file indicates how many instances have been 
modified or deleted since the last reorganization of the instance file.
When this number--called a dirty count--reaches a configurable limit, the 
index file and instance file are reorganized to reclaim unused space; 
unused space (or gaps) is left by delete and modify operations (discussed 
later). The dirty count is expressed as eight hex digits (the number had to 
have a fixed size so that it could be updated in place without having to 
rewrite the index file).

Each subsequent line of the index file corresponds to an instance contained 
in the instance file. Each line has the following fields:

    <ul>

    <li>
    deleted-flag - '1' if the corresponding instance was deleted, '0' otherwise.
	When instances are deleted, the corresponding entry in the index file
	is marked as deleted and a gap is left in the instance file until
	reorganization time.
    </li>

    <li>
    hash-code - hash code for the key field below. This field is provided to
	speed lookup of index entries. When looking up an entry, compute the 
	hash code of the key and look for entries with the same hash code.
	It is still necessary to compare the keys when the hash codes are
	the same (since collisions are possible), but only when they are the
	same which is rare and hence this scheme saves many comparisons.
    </li>

    <li>
    offset - offset within the instance file to where the instance begins.
    </li>

    <li>
    size - size in bytes of the instance itself (as it appears in the instance
	file).
    </li>

    <li>
    key - the compound key of the instance (including all key binding pairs). 
	This key is in standard form which we define as follows: all property 
	names are shifted to lower case and the key-bindings are sorted by
	property names (in this way it suffices to compare key expressions to
	determine if two compound keys refer to the same instance).
    </li>

    </ul>

Here is a sample index file:

    <pre>
    00000002
    0 02FB6B6C 0 1427 Y.key1=1001,key2="Hello World 1"
    0 50699A66 1427 1433 Y.key1=1002,key2="Hello World 2"
    1 EB45F85A 2860 1433 Y.key1=1004,key2="Hello World 4"
    1 38B42754 4293 1431 Y.key1=1005,key2="Hello World 5"
    0 F79B5B0A 8583 1427 Y.key1=1666,key2="Hello World N"
    0 38B42754 4293 1431 Y.key1=1005,key2="Hello World 5"
    </pre>

Notice that the dirty count is equal to two and that two entries are marked 
as deleted (these quantities must be equal). This indicates that the instance 
file has two instances which are no longer used. The space used by these 
instances will be reclaimed during reorganization.

The layout of the instance file is trivial. Instances are always appended to
the the instance file. The instances are kept end-to-end in the file.

<h1>Operations</h1>

There are three operations which may be performed on the instance repository.
create, modify, and delete. This section describes how these operations affect 
the index and instance file. Note that the process described below for 
performing the three operations actually contains extra steps described in
the "Recovery" section.

Creation. During creation, the instance is appended to the instance file and
an entry is appended to the index file. If an instance with the same key is
found, then the operation is disallowed.

Deletion. To delete an instance, the corresponding entry in the index file is 
marked as deleted (by changing the first column from '0' to '1'). And then the 
dirty count is incremented and updated. If the dirty count has reached the 
configured threshold, the index and instance files are reogranized (see
the section entitled "Reorganization" for an explanation of how this is 
done).

Modification. To modify an instance, the new modified instance is appended to
the instance file. Next the old entry with the same key is marked as deleted.
Finally, a new entry is inserted into the index file.

<h1>Reorganization</h1>

To improve performance, reclamation of unused space in the instance file 
(called gaps) is postponed until there are m gaps. Deletion and modification
operations create gaps. A dirty-count is maintained in the index file as
described above. When this dirty count reaches m, available space is reclaimed.
Reorganization is expensive: the entire file must be rewritten. The time
complexity is O(n) where n is the number of instances in the file. By 
postponing reorganization, the time complexity may be reduced to O(1).

Reorganization requires rewriting the instance file and the index file. All
gaps are deleted in the instance file. For each gap there is an entry in the 
index file which is marked as deleted. This entry indicates where the gap 
starts in the instance file and how long it is. The offsets in the index file
are adjusted accordingly. The index file is also updated: all entries marked
as deleted are removed from the index file.

<h1>Recovery</h1>

To avoid corruption of the instance repository, a simple recovery scheme is
provided. For all operations (described in the Operations section), the 
following algorithm is used to ensure recoverability.

    <ul>

    <li>Check to see if any rollback files exist for instances of the given
	class. If so then perform rollback (see recoverability algorithm
	for details).
    </li>

    <li>Create a rollback file for the instance file. The rollback file 
	contains the original size of the instance file.
    </li>

    <li>Create a rollback file for the index file. The rollback file is a
	copy of the instance file (this can be optimized later).
    </li>

    <li>Modify the instance file as described in the operations section.
    </li>

    <li>Modify the index file as described in the operations section.
    </li>

    <li>Perform reorganization as described in the reorganization section
	if the dirty-count has reached the threshold. Otherwise, increment
	the dirty count.
    </li>

    <li>Delete the rollback files.
    </li>

    </ul>

The recoverability algorithm itself works as follows:

    <ul>

    <li>Delete the index file.
    </li>

    <li>Rename the index rollback file to have the same name as the
	index file.
    </li>

    <li>Truncate the instance file to have the same number of bytes as
	indicated in the instance rollback file.
    </li>

    <li>Delete the rollback files.
    </li>

    </ul>

*/