/** 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 therepository/instances directory. For each class, two files are maintained:an index file (with a ".idx" extension) and an instance file which bearsthe 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 tothe 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 inthe "Recovery" section.Creation. During creation, the instance is appended to the instance file andan entry is appended to the index file. If an instance with the same key isfound, 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 (seethe section entitled "Reorganization" for an explanation of how this is done).Modification. To modify an instance, the new modified instance is appended tothe 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 modificationoperations create gaps. A dirty-count is maintained in the index file asdescribed above. When this dirty count reaches m, available space is reclaimed.Reorganization is expensive: the entire file must be rewritten. The timecomplexity 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. Allgaps 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 fileare adjusted accordingly. The index file is also updated: all entries markedas deleted are removed from the index file.<h1>Recovery</h1>To avoid corruption of the instance repository, a simple recovery scheme isprovided. 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>*/