Method of managing a data structure for concurrent serial and parallel revision of a work5870764
Abstract
A data structure and associated data management methods for highly flexible storage of data for a wide variety of application programs. Data is stored as a plurality of Blops, each of which has a list of Properties associated with it. Each Property contains zero or more elements. Elements are Values, each of which has a Basic Type and consists of a variable length sequence of bytes. The Basic Type defines the format of the Value, as well as meta-information such as compression and encryption. Elements can also be Compound Types, which nestably refer to another list of Properties. Blops are stored in Containers, which map to the physical medium on which the data is stored. Containers associate respective Container Handlers which are specific to the Container's physical medium. Related Blops in a Container are organized into Pools of Blops. Each Container contains one or more Pools, each Pool having a unique name within the Container. A Pool contains multiple versions of a Blop. Versions of different Blops are grouped together in Layers in a Pool and each Layer contains at most one version of a Blop. Layers are related to each other as an acyclic digraph, where each Layer is above one or more Base Layers and has zero or more Layers above it. Each Layer presents a "view" to a user of the Blops in a pool, and thereby provides a mechanism to manipulate which versions of which Blops are to be used at any given time.
Claims
We claim:
1. A method of managing a data structure for the revision of a work, said data structure supporting a plurality of blops and a plurality of layers each having a view of at least one of said blops, said data structure further supporting the association of a name with each of said layers, comprising the steps of:
preparing a first version of said work in said data structure, said first version of said work being divided into the blops which are in the view of a first one of said layers, each of said blops which are in the view of said first one of said layers having a portion of said first version of said work;
associating a predefined name with said first layer;
revising said work from said first version to create a second version of said work in said data structure, said second version being divided into the blops which are in the view of a second one of said layers, each of said blops in the view of said second layer having a portion of said second version of said work; and
calling a set-layer-name procedure for said second layer with said predefined name and an identification of said first layer, said set-layer-name procedure moving said predefined name from said first layer to said second layer if and only if said predefined name is still assigned to said first layer at the time said set-layer-name procedure is entered.
2. A method according to claim 1, wherein at least one of the blops in the view of said second layer is also in the view of said first layer, and wherein at least one of the blops in the view of said second layer is not in the view of said first layer.
3. A method according to claim 1, wherein said set-layer-name procedure comprises the steps of:
determining whether said predefined name is still assigned to said first layer;
and if so, then moving said predefined name from said first layer to said second layer,
said set-layer-name procedure preventing interruptions between said step of determining and said step of moving, by any procedure which modifies the association of names with said first or second layers.
4. A method according to claim 1, for use in managing parallel revisions of said work further comprising the step of revising said work from said first version to create a third version of said work in said data structure, said third version being divided into the blops which are in the view of a third one of said layers, each of said blops in the view of said third layer having a portion of said third version of said work.
5. A method according to claim 4, further comprising, if said set-layer-name procedure did not move said predefined name from said first layer to said second layer, the step of:
integrating said second version of said work with said third version of said work to create a fourth version of said work being divided into the blops which are in the view of a fourth one of said plurality of layers.
6. A method according to claim 5, further comprising the step of calling said set-layer-name procedure for said fourth layer with said predefined name and an identification of said third layer.
7. A method according to claim 5, wherein said step of integrating said second version of said work with said third version of said work to create a fourth version of said work comprises the step of calling an integrate-layers procedure with a reference to a call-back procedure, said integrate-layers procedure performing the steps of:
determining whether a given blop in the view of said second layer is the same as a corresponding blop in the view of said third layer, but a different version of said corresponding blop;
and if so, then calling said call-back procedure with an identification of said given blop and an identification of said corresponding blop, said call-back procedure returning an identification of a blop to be added to the view of said fourth layer; and
adding said blop identified by said call-back procedure to the view of said fourth layer.
8. A method according to claim 1, further comprising the step of providing on a first data storage medium, all of said blops which are in the view of said first layer,
said step of revising said work comprising the steps of:
preparing a delta pool from said first layer, said second layer being a layer in said delta pool, said second layer initially having in its view all of the blops which are in the view of said first layer; and
performing at least one of the steps of (1) adding an additional blop to the view of said second layer, (2) deleting a blop from the view of said second layer, and (3) creating a copy of a particular one of the blops which are in the view of said first layer to create a second instantiation of said particular blop in the view of said second layer, said second instantiation of said particular blop substituting for said particular blop in the view of said second layer,
said method further comprising the step of providing on a second medium all of the blops which are in the view of said second layer and not in the view of said first layer, and an identification of each of the blops in the view of said first layer which have been deleted from the view of second layer.
9. A method according to claim 8, further comprising the steps:
operatively coupling said first medium to a computer such that all of the blops in the view of said first layer are readable; and subsequently
operatively coupling said second medium to said computer; and
reading blops in the view of said second layer, all of the blops in the view of said second layer which are not in the view of said first layer being read from said second medium, all of the blops in the view of said second layer which have substituted for blops in the view of said first layer being read from said second medium, and all of the blops which are in the view of both said first and second layers being read from said first medium.
10. A method according to claim 1, further comprising the Move-All-Changes-Down steps of:
deleting from the view of said first layer all blops in the view of said first layer which are not in the view of said second layer;
adding to the view of said first layer all of the blops in the view of said second layer which are not already in the view of said first layer; and
substituting in the view of said first layer, for any particular blop in the view of said first layer having a corresponding blop in the view of said second layer which is a revision of said particular blop, said corresponding blop.
11. A method according to claim 1, wherein said step of revising said work from said first version to create a second version comprises the steps of:
processing at least part of the portion of said first version of said work which is in a given one of said blops in the view of said first layer, serially through at least one handler specified in said given blop for said part, said part thereafter being in a processed form; and
revising said part in said processed form.
12. A method according to claim 11, wherein said step of processing comprises the step of processing said part of the portion of said first version of said work which is in a given one of said blops in the view of said first layer, serially through at least two handlers specified in said given blop for said part, the sequence of said handlers also being specified in said given blop for said part.
13. A method of managing a data structure for the revision of a work, said data structure supporting a plurality of blops, a plurality of layers each having a view of at least one of said blops, and a plurality of pools, comprising the steps of:
preparing a first version of said work in said data structure, said first version of said work being divided into the blops which are in the view of a first one of said layers, each of said blops in the view of said first layer having a portion of said first version of said work and being provided in a base one of said pools operatively coupled to a computer, said base pool having a base one of said layers;
copying all of the blops which are in the view of said first layer into a separable one of said pools operatively coupled to said computer;
separating said separable pool from said computer;
revising said work from said copies of said blops in said separable pool while said separable pool is separated from said computer to create a separated version of said work in said data structure, said separated version being divided into the blops which are in the view of a separable one of said layers, each of said blops in the view of said separable layer having a portion of said separated version of said work; and
calling an integrate-pool procedure for said separable layer and said base layer in said base pool, with a reference to a call-back procedure, said integrate-pool procedure performing the steps of:
creating a reconciliation layer in said base pool;
determining whether a given blop in the view of said separable pool is a different version of a corresponding blop in the view of said base layer;
and if so, then calling said call-back procedure with an identification of said given blop and an identification of said corresponding blop, said call-back procedure returning an identification of a blop to be added to the view of said reconciliation layer; and
adding said blop identified by said call-back procedure to the view of said reconciliation layer.
14. A method according to claim 13, wherein said base layer is said first layer.
15. A method according to claim 13, wherein said base layer is above said first layer.
16. A method according to claim 13, wherein said integrate-pool procedure further comprises the step of determining whether a blop in the view of said separable layer is a copy of a source one of said blops in the view of said base layer and if so, then including said source blop in the view of said reconciliation layer.
17. A method according to claim 13, wherein said step of revising includes the step of deleting at least one blop from the view of said separable layer, and wherein said integrate-pool procedure further comprises the steps of:
determining whether a copy of a particular blop in the view of said base layer was deleted from the view of said separable layer;
and if so, then calling said call-back procedure with an identification of said particular blop, said call-back procedure returning an identification of a designated blop to be added to the view of said reconciliation layer; and
adding said designated blop to the view of said reconciliation layer.
18. A method for updating a work from a starting version of said work to prepare a revised version of said work, comprising the steps of:
providing said starting version of said work as a plurality of parts each having an identity which is unique within said starting version, said starting version itself having an identity;
creating a version tree of versions of said work, said tree having a plurality of intermediate versions each having a respective plurality of parts, each part in each one of said intermediate versions having an identity which is unique within the intermediate version, and each of said intermediate versions having an identity which is unique among said intermediate versions; and
reconciling said intermediate versions of said work to create a reconciliation version of said work, said reconciliation version being said revised version of said work and having an identity different from the identities of all of said intermediate versions, said reconciliation version having a plurality of parts each having an identity which is unique within said reconciliation version, the identity of each part in said reconciliation version being the same as the identity of a part in at least one of said intermediate versions.
19. A method according to claim 18, wherein said version tree has at least one branch, said intermediate versions all being on a single one of said branches.
20. A method according to claim 18, wherein said version tree has at least two branches, at least two of said intermediate versions being on different ones of said branches.
21. A method according to claim 18, wherein each part in each of said versions has respective contents, wherein said step of reconciling comprises the step of including in said reconciliation version each part from one of said intermediate versions for which there is a matching part, in both identity and contents, in all others of said intermediate versions.
22. A method according to claim 21, wherein said step of reconciling further comprises the step of including unchanged in said reconciliation version each part which is in exactly one of said intermediate versions.
23. A method according to claim 21, wherein said step of reconciling further comprises the steps of:
identifying a given part in one of said intermediate versions for which a corresponding part exists in another of said intermediate versions, said corresponding part having the same identity as, but different contents from, said given part;
calling a part reconciliation procedure which returns a reconciled part having the identity of said given part; and
including said reconciled part in said reconciliation version.
24. A method according to claim 18, wherein said step of providing marks said starting version of said work with a predetermined mark, further comprising, after said step of reconciling, the atomic steps of:
determining whether said starting version of said work is still marked with said predetermined mark; and
moving said predefined mark from said starting version to said reconciliation version if and only if said starting version of said work is still marked with said predetermined mark.
25. A method for updating a work from a starting version of said work to prepare a revised version of said work, comprising the steps of:
providing said starting version of said work as a plurality of parts each having an identity which is unique within said starting version;
revising said starting version to create a first intermediate version of said work having a plurality of parts, each part in said first intermediate version having an identity which is unique within the first intermediate version;
revising said starting version to create a second intermediate version of said work having a plurality of parts, each part in said second intermediate version having an identity which is unique within the second intermediate version;
revising said starting version to create a third intermediate version of said work having a plurality of parts, each part in said third intermediate version having an identity which is unique within the third intermediate version;
revising said starting version to create a fourth intermediate version of said work having a plurality of parts, each part in said fourth intermediate version having an identity which is unique within the fourth intermediate version;
reconciling said first and second intermediate versions of said work to create a first reconciliation version of said work, said first reconciliation version having a plurality of parts each having an identity which is unique within said first reconciliation version, the identity of each part in said first reconciliation version being the same as the identity of a part in at least one of said first and second intermediate versions;
reconciling said third and fourth intermediate versions of said work to create a second reconciliation version of said work, said second reconciliation version having a plurality of parts each having an identity which is unique within said second reconciliation version, the identity of each part in said second reconciliation version being the same as the identity of a part in at least one of said third and fourth intermediate versions; and subsequently
reconciling said first and second reconciliation versions of said work to create said revised version of said work, said revised version having a plurality of parts each having an identity which is unique within said revised version, the identity of each part in said revised version being the same as the identity of a part in at least one of said first and second reconciliation versions.
Description
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by any one of the patent document or the patent disclosure as it appears in the Patent & Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND
Application programs in a computer system typically need to manage data in a manner that permits frequent updating. Two broad examples of such application programs are a word processor and a database manager. Word processors need to be able to manipulate sections of text and other related information each time the user modifies a document, and a database program needs to insert, delete and modify entries in accordance with a user's requirements.
One issue that often faces developers of these types of application programs is the trade-off between storage space and speed of execution. For example, database programs typically manage data in the form of one or more tables. Each record in a table has the same number of fields, each of which are in the same format, and all of which are described in a separate data structure which the program maintains in conjunction with the table. In such a table, each row might represent a different record, and each column might represent a different field within the record. If the table is maintained as a simple array, then each field is assigned a predetermined maximum length, and storage is allocated for the maximum length of each field in each record. This clearly results in much wasted storage space, since the data in most fields will not occupy the full amount of space allotted. The developer can save space by maintaining variable length fields as merely fixed-byte length offsets into an area of storage which contains the actual data, but this entails a level of indirection which must be invoked every time it is necessary to access the particular data. This can detrimentally impact the speed with which certain operations are performed, such as searching.
Another space utilization issue which database program developers often face when data is stored and maintained as tables, is that very often it is desirable to include a particular field in only one or a few of the records in the table, such field being unnecessary in the vast majority of the records. A large amount of unused space must be allocated to maintain such a field in all of the records, even if the developer seeks to minimize the wasted space through indirection. The database program developer can reduce the amount of wasted space by maintaining the data as a linked list rather than as an array, but again, only with the penalty of extensive additional overhead for operations such as searching. Additionally, linked list implementations often do not save very much space since some storage must still be allocated to indicate that a particular field is empty in a particular record. The developer may be able to reduce the speed penalty by adding cross-pointers in the linked list, but this technique again increases the amount of storage space used.
The trade-off between storage space usage and speed of access becomes more severe as the data being managed, if expressed as an array, becomes more sparse. Accordingly, there is a need for a method of managing data which minimizes both the usage of space and the time required to access the data.
Another issue faced by application program developers is that for many types of application programs, the file structure offered by the operating system is not appropriate to the task. Typical of the data Storage Managers offered by operating systems are those offered by MS-DOS.RTM., Unix.RTM., and by the Apple Macintosh.RTM.. All of these operating systems store data in "files". A file is maintained in a "directory" of files, and directories may be maintained as parts of other directories, thereby creating a tree structure for the files. If the storage apparatus managed by the operating system contains more than one storage medium, such as different hard disks, floppy disks, CD-ROMS, remote storage media accessible via a network, or local volatile memory, then each such medium usually has its own root directory within which all of the files stored on the medium exist. Unix.RTM. and Macintosh.RTM. also support aliasing of files, whereby a file may appear in several different directories, although only one instance contains the data of the file. All the other instances merely refer to the one real instance.
In these file systems, the smallest unit of information supported by the operating system is a file for many of the frequently needed operations. Since the speed penalty involved in operating system calls to open and close files is significant, application programs tend to maintain data in only one or a few files rather than attempt to take advantage of the file system structure supported by the operating system. For example, a database program developer may be able to avoid a large amount of data movement when a record is inserted or deleted, merely by maintaining each record in a separate file. As another example, a database application program may wish to maintain each field of a record in a separate file, thereby inherently implementing variable length fields. Neither of these techniques is practical, however, since they would require enormous numbers of operating system calls to open and close files, thereby imposing a substantial speed penalty.
Since many of the application programs maintain their data in only one or a few files, each such program requires the development and implementation of a proprietary data format which allows the application to quickly store and retrieve the data which the particular application program expects. Developers therefore often maintain large libraries of code for accessing their own proprietary file formats. One example is the MacWrite program, which maintains its own mechanism for moving data to and from memory. The mechanism is optimized for the particular file format used, and is not directly useable by other application programs. Other application programs have essentially similar mechanisms. The result is an immense duplication of effort that could otherwise be directed toward enhanced user functionality.
Accordingly, there is a significant need for operating system support of data storage in a form which is useful to a wide variety of application programs.
Another issue which application developers often face arises when data is stored in different parts of a data storage apparatus, which have different protocols for access. For example, storage apparatus in a computer system may include not only persistent storage such as a hard disk, but also volatile storage such as the computer system's main memory. That is, if an application program wishes to minimize the number of reads and writes to a hard disk, it may maintain some of the data in main memory for as long as possible before the space it occupies in main memory becomes necessary for another purpose. One frequent example is a word processor's need to maintain some portion of a document currently being edited in memory, and other portions of the document out on disk. Such a technique, known as caching, often requires the application program to keep track of which data is currently on which medium, and use the appropriate protocol for accessing that medium. For example, if the data is on disk, the application program typically uses the operating system's read and write calls to access the data. If the data is in main memory, then the application program can avoid all the overhead of the operating system merely by addressing the particular memory locations at which the data may be found. If the data is in ROM, yet a third data access protocol may be necessary. There is a need in the industry to simplify the implementation of application programs by providing a common mechanism by which the application developer can access data regardless of how or where it is stored in the computer system's storage apparatus.
Many application program developers also face yet another issue if the data maintained by the program is intended to be accessible, and modifiable, by more than one user. The term "shared structured storage" can be defined as a mechanism for making data persistent across sessions (invocations) of an application program, with the data being available for collaborative updating. For example, in a word processor, it is often desirable to support the ability of two or more different users to update a single document at the same time. In a database system, it is often desirable to permit different users to update the database data concurrently. Most application programs implement a technique known as "pessimistic concurrency" which, while permitting many users to read and view the data concurrently, permits only one user to modify the data at a time. The system "locks out" all other users from write accesses when one user has the data open for updating. Pessimistic concurrency can be implemented at a file level or, in sophisticated database programs for example, at a record level. That is, for file level locking, only one user may have the file open at a time for writing. This is the typical manner with which word processors implement concurrency. A database program can implement record level locking if, for example, a backend process is the only process which has the data file open for writing, and all other users issue their commands and queries through the backend process.
Some application programs have attempted to implement "optimistic concurrency", in which two or more users can modify data at the same time, subject to subsequent reconciliation. One example is the Macintosh.RTM. Programming Workshop (MPW) Projector available from Apple Computer, Inc., Cupertino, Calif. MPW Projector is described in the MPW 3.1 Reference Manual, and in H. Kanner, "Projector, An Informal Tutorial", available from Apple Computer, Inc. (1989). MPW Projector is an integrated set of tools and scripts whose primary purpose is to maintain control of the development of source code. It preserves in an orderly manner the various revisions of a file, and through the versioning mechanism also prevents one programmer from inadvertently destroying changes made by another. If the underlying data is text, data compression is achieved by storing only one complete copy of a file and storing revisions only as files of differences. Different users of the same set of files can view them differently since each user is given independent control of the mapping between the user's local directory hierarchy, in which the user keeps the files, and the hierarchy used for their storage in the main Projector database. Projector also has a facility for associating a specific set of file revisions with a name, this name being usable as a designator for a particular version, or release, of a product. Thus the name alone can be used to trigger the selection of just those source files that are required to build the desired instance of the product.
MPW Projector maintains versions in a tree structure. When one user desires to modify a file in the main Projector database, the user "checks out" the file, thereby making a copy of the file in the user's own directory. The user can check out a file either as "read-only" or, if no one else has already done so, as "read/write". After modifying the file, the user can then "check in" the file back to the main Projector database, either as a new version in a new branch of the file version tree, or, only if the file was check out as read/write as a new version in the same branch of the version tree. When it is finally desirable to merge a branch of the revision tree back into the main trunk, MPW Projector performs a strict text-based comparison between the two versions of the file and displays the differences in a pair of windows on the computer system display. A user then cuts-and-pastes portions from one window into the other in order to merge them together.
While MPW Projector is a good first step toward optimistic concurrency, significant additional flexibility is highly desirable. For example, its finest level of granularity is still represented by a "file". It would be desirable to support much greater degrees of granularity. As another example, MPW Projector's provisions for merging two versions of a single document together is limited to a single procedure in which the computer identifies strict text differences, and a user indicates how each text difference should be resolved. Significant additional intelligence will be desirable in the comparison procedure, as would significant increased flexibility and automation in the resolution of conflicts, as well as support for comparisons between non-text files.
Some developers of application programs have attempted to use the Resource Manager, available from Apple Computer, to implement structured storage of data. The Resource Manager is described in Apple Computer, "Inside Macintosh: Overview", Chap. 3 (1992), incorporated herein by reference. The Resource Manager does not support concurrent updating of its data, however, and in any event was not designed for this purpose. The Resource Manager therefore fails to provide an adequate solution.
Accordingly, there is a need for much greater flexibility in the support of optimistic concurrency in the maintenance of data.
SUMMARY OF THE INVENTION
Roughly described, the invention includes a data structure for storing data in storage apparatus, in a manner which ameliorates many or all of the above deficiencies in existing storage systems. The invention can also be viewed as a method or set of methods for maintaining and/or implementing a data structure, or as a conglomeration of the data structure and such methods.
In the embodiment described herein, the primary unit of storage in the data structure is a Basic List of Properties (Blop), which stores a list of attributes referred to herein as "Properties". Each Property contains zero or more Values. Each Value has a Type and consists of a variable length sequence of bytes. The Value Type can define the format of the Value, including the data structure as well as meta-information such as compression and encryption.
Blops are stored in Containers. Containers map to the physical medium on which the data is stored. The Storage Manager can access each Container through a standard set of Container Handlers, so Containers can be created in memory, in ROM, on disk, and so on.
Related Blops can be organized into collections referred to herein as Pools. Each Container may contain one or more Pools, each Pool having a unique name within the Container. Each Blop is stored in one and only one Pool (except in Delta Pools and Separable Pools discussed below). However, each Blop may have multiple versions of itself stored in a Pool. Versions of a Blop differ from each other in terms of their Properties, Values or Value Types.
Versions of different Blops may be grouped together in Layers and each Layer can contain at most one version of a Blop. Layers are the Storage Manager's mechanism for manipulating which versions of which Blops are to be used at any given time. Layers are related to each other as an acyclic digraph where each Layer is above (derived from) one or more Base Layers and has zero or more Layers above it. The only exception is the Bottom Layer of a Pool, which has no Base Layer. Thus, every Layer in a Pool is transitively above the Bottom Layer of the Pool.
Each Layer presents a "view" to a user of the Blops in a Pool. Layers can be analogized to a stack of transparencies, in the sense that one can see straight through a Layer into the Layer(s) underneath it. In other words, the contents of any Layer is based on the contents of the Layers from which it is derived. To change the view of a Layer, a user can overwrite Blops, add Blops or remove Blops. Such changes do not affect the views presented by the Layers underneath the current one, but would affect the views of the Layers derived from it. A Layer which has no such changes in it is referred to as an Empty Layer, not in the sense that no Blops are visible from it, but rather in the sense that it is completely transparent.
FIG. 1 symbolically illustrates the logical relationship that might exist between four layers in a Pool 102. The Bottom Layer 104 of the Pool has two names: L1 and Bottom, and it has three Blops in it: A, B and C. Layer L1 has one Layer 106 derived from it: L2. In L2, Blop A has been changed to its second version, but the versions of B and C are unchanged, so the version they had in L1 is still visible (noted in the diagram by the dashed border). Layer L2 has one Layer 108 derived from it: L3. L3 once again changes Blop A, but also tombstones (deletes) Blop C and adds Blop D. Blop B is left unchanged so that the version from Layer L1 is still visible. Layer L4 is derived from L3, but no changes have been made in L4 yet so it can be referred to as an Empty Layer.
The Pool/Layer/Blop data structure permits easy implementation of optimistic concurrency with as fine a granularity as desired. For example, a document can be divided into any number of Blops and stored in a single Pool. Each Layer can then be looked upon as a draft of the document. Since more than one Layer can be derived from a Layer, one can have several Layers whose contents are based on the same base Layer. For example, if a document is stored in a Pool in a disk-file Container and two people would like to work on it at the same time, they can simply create two Layers based on the current Layer.
FIG. 2 symbolically illustrates a Pool 202 in which two Layers 206, 208 are derived from a Base Layer 204. The two Layers 206, 208 can be viewed and edited separately and simultaneously. In this way, more than one user can modify a document without blocking any other users from accessing it. Also, all the changes made by one user are encapsulated in one file. Everyone who has access to this file can inspect the various changes the user made. The user does not need to manage multiple files for multiple drafts.
In addition to Layer branching, the data structure also permits Layer reconciliation. When a Layer is derived from more than one Base Layer, it is referred to as a Reconciliation Layer since it provides a means to reconcile the views of the Layers on which it is based. Any Blops which have different versions visible in the different Base Layers are defined to be Ambiguous and cannot be accessed until their Properties, Values and Value Types have been explicitly set in the Reconciliation Layer. FIG. 3 illustrates a Pool 302 having a bottom Layer L1, two intermediate Layers L2 and L3 immediately above the bottom Layer L1, and a "Reconciliation" Layer immediately above both Layers L2 and L3. In FIG. 3, the reconciliation of Blop A is unambiguous since it was unchanged in both Layers L2 and L3. Likewise, Blop D is not ambiguous since it exists only in L3. Blops B and C however exist as different versions in L2 and L3, and as such are ambiguous in the reconciliation Layer.
The method of resolving conflicts depends on the application program which uses the Storage Manager. The Storage Manager provides a means to identify conflicts by Blop versions, but it does not dictate one particular method of resolving conflicts. One application may choose to take the version of a Blop with the latest modification time while another may want to use the version with the most data. As another example, an application program may allow a user to choose one change over another, ignore both, or replace the Blop with an entirely new Blop. The application program which calls a Storage Manager routine to compare views in two Layers preferably also provides a reference to the application program's procedure for reconciling conflicts.
The data structure can also include Pools which are referred to herein as Delta Pools, which allow several Pools to behave as if they were a single Pool. In a Delta Pool, the Bottom Layer is actually derived from a Layer in a Base Pool. Thus the Layers in the Delta Pool appear as a continuation of the Layers in the Base Pool. FIG. 4 symbolically illustrates an example of how the Layers in a Delta Pool and its Base Pool might be related.
In particular, a Base Pool 402 includes four Layers L1, L2, L3 and L4, and a Delta Pool 404 includes four Layers L5, L6, L7 and L8. As shown in FIG. 4, Layer L5, which is the bottom Layer of Delta Pool 404, is "immediately above" Layer L4 in Base Pool 402.
A given Base Pool may have any number of Pools derived from it, but a Delta Pool can have only one Base Pool. A Delta Pool also can become a Base Pool for other Delta Pools. Attempting to access a Delta Pool triggers an attempt to reconnect to its Base Pool (and its Base Pool's Base Pool and so on). If the Base Pool is unavailable, the Delta Pool cannot be accessed. If the Base Pool is available and has not changed since the Delta Pool was last disconnected, the Delta Pool can be connected to the Base Pool. If the Base Pool has been changed, the Delta Pool cannot be connected to the Base Pool automatically; a reconciliation process needs to be triggered.
The concept of a Delta Pool enables new ways to interact with data on Read-Only media (e.g., CD-ROM). Since a Delta Pool can be derived from a Pool which is stored on a Read-Only medium, a Delta Pool provides a new view to the Read-Only Pool and modification can be made in this view. For example, if one has a movie stored as a Pool on a CD-ROM, one can view the movie and change any frame of the movie with the Delta Pool. Another example is a computer system's internal ROM. With Delta Pools, a computer manufacturer can turn the ROM into a Base Pool and deliver future system releases as Delta Pools on some removable medium such as a floppy disk.
The data structure also supports Pools referred to herein as Separable Pools. Separable Pools are very similar to Delta Pools in that the Bottom Layer is actually derived from a Layer in a Base Pool. Generally, however, in a Separable Pool, all of the Blops visible in the base Layer are copied up into the Bottom Layer of the Separable Pool.
A given Base Pool may have any number of Pools derived from it, but a Separable Pool can be derived from only one Base Pool. Unlike Delta Pools, a Separable Pool can be opened and accessed without the Base Pool being available.
When a Separable Pool is reintegrated with its Base Pool, any conflicts between the two need to be reconciled. One way to resolve the conflicts is to create a Reconciliation Layer in the Base Pool, derived from both the Base Layer and the desired Layer in the Separable Pool. After the reconciliation, the Separable Pool can be destroyed as the changes are incorporated in the Base Pool. FIG. 5 illustrates symbolically the reintegration process 502 of a Separable Pool with its Base Pool. In particular, process 502 first illustrates the creation of a Separable Pool 504 from a Base Pool 506. The Base Pool includes a Layer L1, which forms the base Layer for the bottom Layer L2 of the Separable Pool 504. On reintegration, the Storage Manager creates a reconciliation Layer L3 in the Base Pool to reconcile the differences between the Blops in the view associated with L1 and the Blops in the view associated with L2. This is illustrated in process 502. As with the reconciliation process described above for two Layers in the same Pool, the Storage Manager, on reintegration of a Separable Pool, merely locates conflicts in the Blop versions. It is up to the Application Program to select which version to store in the reconciliation Layer, or to provide a new version.
Separable Pools are extremely useful to work groups in a mobile computing environment. For example, if a user needs to perform certain tasks while away from the office, the user can create a Separable Pool derived from the Base Pool at the office and update the document while on the road. When the user returns, the modified document can be reintegrated with the original document even if the original document has been updated by other members of the work group while the user was away.
In an aspect of the invention, a method, referred to herein as MoveAllChangesDown, is provided to help reduce the storage requirements for Blop versions which are no longer required. MoveAllChangesDown is an operation which allows the changes which exist in one Layer to be moved down into Layers from which it is derived. Specifically, MoveAllChangesDown from Layer A to Layer B make Layer B have the same view of the Blops as Layer A and makes all the Layers above B up through A be empty so that they also have the same view. FIG. 6 illustrates symbolically the results of a MoveAllChangesDown Operation. In FIG. 6, a Pool 602 includes three Layers, L1, L2 and L3. Layer L1 has associated with it a view of version one of each of three Blops A, B and C. Layer L2, which is immediately above Layer L1, has a view of version two of Blop B, but still has within its view version one of each of Blops A and C. Layer L3, which is immediately above Layer L2, has within its view a new version three of Blop B, a new version two of Blop C, and the original version one of Blop A. After the MoveAllChangesDown Operation, all of the changes in Layers L2 and L3 are moved into L1 and Layers L2 and L3 are made empty. Thus the view associated with Layer L1 now consists of version one of Blop A, version three of Blop B, and version two of Blop C. The views associated with Layers L2 and L3 are identical to that of Layer L1.
The MoveAllChangesDown operation removes all the versions of Blops which are no longer required, thus reducing the size of the Container containing the Blops. This is especially useful, for example, for archiving a final or interim draft of a document.
The Storage Manager can also include a method, referred to herein as CollapseLayers, which eliminates unnecessary empty Layers in a portion of the Layer tree of a Pool. Specifically, a CollapseLayers operation from Layer A to Layer B, eliminates all the empty Layers which are (transitively) above Layer B and (transitively) below Layer A, including Layer A (if empty). Any names or non-empty Layers which are above Layers which are eliminated, are moved down to the first non-empty Layer which is below the eliminated Layer.
FIG. 7 illustrates this operation with a Pool 702 which includes a bottom Layer L1, two Layers L2 and L3 which are both immediately above Layer L1, two Layers L4 and L5 which are immediately above Layers L2 and L3, respectively, a reconciliation Layer L6 having a name "version", Layer L6 being immediately above both Layers L4 and L5, and Layers L7 and L8 which are both immediately above Layer L6. In the illustration, Layers L2-L6 are empty, possibly as the result of a MoveAllChangesDown operation from Layers L6 to Layer L1. After the CollapseLayers operation, as shown in FIG. 7, Layers L2-L6 have been eliminated, the named "version" has been moved down to Layer L1, and Layers L7 and L8 are now both immediately above Layer L1. The CollapseLayers operation removes extraneous Layers and further reduces the storage requirements of the Container containing Pool 702.
Preferably, operations such as MoveAllChangesDown and CollapseLayers are facilitated by assigning each Blop a Blop identifier and ensuring that each Blop is "instantiated" in no more than one Layer in the Pool. Different versions of the same Blop have the same Blop identifier, but no two Blops in a Pool with the same Blop identifier are instantiated in the same Layer in the Pool.
Moreover, Blops can refer to other Blops indirectly, either at the Blop level or at the Value level. Indirectly referenced Blops can be in the same or a different Pool, and can be located in the same or a different Container.
Many other features of the invention, including different features of the data structure and different methods for maintaining the data structure or the data stored therein, will be evident from the detailed description set forth below.
DESCRIPTION OF THE DRAWINGS
The invention will be described with respect to particular embodiments thereof, and reference will be made to the drawings, in which:
FIGS. 1-4 and 9 symbolically illustrate logical relationships between Layers in one or more Pools;
FIGS. 5-7, 10 and 11 symbolically illustrate operations which may be performed on Layers in a Pool;
FIG. 8 illustrates the logical organization of a Blop;
FIG. 12 illustrates the structure of a disk container;
FIG. 13 illustrates the structure of a segment;
FIG. 14 illustrates the structure of a Pool Name Index of FIG. 12;
FIG. 15 illustrates the structure of a pool segment;
FIGS. 16a and 16b illustrate the structure of a Layer Matrix of FIG. 15;
FIG. 17 illustrates the structure of a Layer Name Index of FIG. 15;
FIG. 18 illustrates the structure of a Layer Collection of FIG. 15;
FIG. 19 illustrates the structure of a Blop ID Allocator of FIG. 15;
FIG. 20 illustrates the structure of a Layer Segment of FIG. 12;
FIG. 21 illustrates the structure of a Blop of a Compound Type;
FIGS. 22A, 23A and 24A illustrate a Visibility List of FIG. 20 for Layer relationships illustrated symbolically in FIGS. 22B, 23B and 24B respectively;
FIGS. 25 and 26 illustrate the structure of Property Data Blocks;
FIGS. 27, 28, 29A, 29B and 29C illustrate the structure of Data Data Blocks; and
FIG. 30 illustrates the structure of a Path Stack.
DETAILED DESCRIPTION
The embodiment of the invention which is described herein constitutes a Storage Manager and its associated data structures. The structures are described first with respect to their logical organization and subsequently their physical organization in the storage apparatus managed by the Storage Manager. That is, they will be described first with respect to the view which the Storage Manager software provides to an application programmer via an Application Program Interface (API), and subsequently with respect to the way that logical organization is actually implemented in the present embodiment. While many of the advantages of the present invention derive from the logical organization, it will be apparent that such logical organization implies certain physical structures which are required to maintain the metaphor as viewed by the application developer. The physical organization described hereinafter includes many inventive aspects of the invention, but it is by no means the only physical structure which can support the logical organization presented to the application developer.
Preliminarily, as used herein, the terms "container", "pool", "layer" and "blop" are merely names for enclosures of data. The names are chosen for convenience of description of the present embodiment, but the reader should not imply any attributes from their definitions in the present embodiment into their definitions for the purposes of the overall invention. Similarly, the terms "property" and "type" merely represent interpretations of data. The reader should not imply any attributes from their interpretations in the present embodiment into their definitions for the purposes of the overall invention.
I. LOGIC ORGANIZATION OF DATA
The fundamental persistent storage unit in the Storage Manager is a Blop. As illustrated in FIG. 8, a Blop comprises a set of unordered attributes called Properties. Each Property includes a sequence of Values, indexed from 1 to n. Each Value is of a given Type and several Values of the same Property may have the same Type. The Type of a Value is unrelated to its index. Each Value consists of a variable length sequence of bytes.
A Property defines a role for a Value. Properties are similar to field names in a database record, except that they can be freely added to a Blop, and their names are unique within their owning Pool, so that applications can understand them. The data stored in a Blop exists in the Values. Values may be fixed or variable length. The Type of a Value describes the format of that Value. Types record the structure of a Value, whether it is compressed, encrypted, etc. Types share the same name space as Properties and are thus are also unique within their owning Pool. Types can be Basic Types, such as `str` or `long`, or they can be Compound Types, in which case they are further broken down into a set of sub-Properties and Typed Values. Compound Types can be nested.
While Blops are used to contain the information within a Pool, it is often useful to maintain information about the information to assist applications in interpreting the data. In the Storage Manager, such meta-information is maintained in Meta Information Blops which are associated with Types and with Property names. Each Type and each Property name which is used within a Pool has an associated Blop which can be used to store additional information about how the Type/Property should be accessed and used. For instance, Meta Information Blops associated with Types can contain a Property which defines the Handlers (i.e. dynamically loaded routines) to call for reading and writing Values of that Type.
Other than the fact that they are associated with specific components of the Storage Manager, Meta Information Blops are normal Blops, and are accessed in the same way as data Blops. The only other difference is that while the Storage Manager does not define the interpretation of any Properties in regular Blops, it does define the usage of some Properties in Meta Information Blops. Specifically, in Type Meta Information Blops, the "ReadWrite Handler" Property indicates the name of the ReadWrite Handler and the "Superclass" Property indicates which other Type is its Superclass, if any.
Blops can refer to other Blops. These references are embedded in the Values of a Blop as Blop Ids, 32 bit numbers, which are unique within the owning Pool. The referenced Blops can be in the same or a different Pool, and in the same or a different Container.
The Storage Manager supports two kinds of indirection. In one form, a Blop can resolve to a different Blop automatically. The Properties and Values of the referenced Blop will appear to be within the local Blop. In the other form, an individual Value in a Blop can be indirected to a Value in another Blop. When accessing the local Value the referenced Value will actually be returned. The indirect Value can be just a portion of the referenced Value, and it can be moved along the referenced Value like a scrolling window.
Containers map to the physical location of where data is stored. File Containers are normal Macintosh HFS Data Forks or Resource Forks. Memory Containers are in-memory constructs that maintain Pools in a given heap zone. ROM Containers allow for Containers burnt into ROM. Scrap Containers are used to pass Storage Manager structures on the MacIntosh Clipboard.
A Container can contain any number of Pools, and each Pool in a Container can be accessed independently of the others. The Storage Manager supports two standard Container formats: Update-In-Place (UIP) Format and Update-By-Append (UBA) Format. UIP Containers are optimized for random access file devices. UBA Containers are optimized to be written serially, with changes appended at the end, and read randomly. They can use either a file device or an area of memory. File Containers can utilize either the UIP or UBA format. ROM and Scrap Containers usually utilize the UBA format. These formats are implicitly determined by a dynamically linked and loaded Container Handler that is specified at creation of the Container. This Handler defines the format being used as well as the kind of media.
It can be seen that the data storage apparatus managed by the Storage Manager need not be persistent storage, and can include a plurality of different media. The term "data storage apparatus" carries no implication of how the data managed by the Storage Manager is divided among the different media. Even the "Containers" of the present embodiment, which appear to the application program as being entirely present on one particular storage medium, can in fact exist partially on such storage medium and partially in main memory during execution. Additionally, different parts of the data storage apparatus can comprise removable data storage media, such as floppy disks.
Pools, in the simplest case (ignoring Layers, Delta and Separable Pools, which will be described later), are collections of related Blops. Every Blop exists in one and only one "home" Pool (except in the case of Delta Pools). Pools are stored in Containers. Each Pool must be given a name which must be unique within the Container in which it is stored, and which is used to identify that Pool within the Container. Pools in memory are transient, and no effort is made to preserve their contents past the life of the application which created them, while Pools in Files are persistent. Pools in Memory Containers are automatically given a file on disk to use as a backing store, but the purpose of the backing store is only to extend the volume of Blops which can be stored in the Pool (since all of the Blops need not be in physical memory at one time). The Storage Manager allows for virtualization of Blops regardless of the existence of paging hardware. If paging hardware exists it will be used to best advantage by the Storage Manager. Every Pool can have any number of distinguished Blops in the Pool which are marked as persistent. All Blops in the Pool must either be marked persistent or transitively referred to by a persistent Blop. In other words, if one were to follow all of the Embedded Blop Ids in all the persistent Blop Values and then all the Embedded Blop Ids in those Blop Values, and so on, all of the Blops in the Pool must eventually be reached. Any Blop which cannot be so reached will be eliminated from the Pool. This is termed Blop garbage collection.
Pools may not just contain a set of Blops, they may also contain multiple versions of each of those Blops. Different versions of a Blop are identified implicitly by the Container, Pool and Layer in which they are instantiated.
Layers are the Storage Manager's mechanism for manipulating which versions of which Blops are to be used at any given time. Each Layer in a Pool defines a subset of the Blops in the Pool which are visible to that Layer; and for each of those Blops, the Layer defines which version of the Blop is to appear. A Layer is thus said to have associated with it a "view" of the Blops in the Pool. Any application which accesses a Pool must first specify which Layer in that Pool it is operating on before it can begin accessing any of the Blops inside. The parameter used by the application program to specify such a Layer is a predefined data structure referred to herein as a CPL Accessor. It completely describes the context necessary to access a set of Blops. It defines a Container, Pool and Layer context. Given the CPL Accessor context Blops can be accessed without regards to other Layers, Pools, or Containers.
Layers are not completely free-form; but are built into an acyclic digraph where each Layer is "Derived" from some number of other "Base" Layers, and has some number of other Layers derived from it. Each Pool has a single "Bottom" Layer from which all other Layers in the Pool are transitively derived. This "Bottom" Layer is created when the Pool is created and it cannot be deleted. The contents of any Layer is based on the contents of the Layers it is derived from except where changes have explicitly been made in that Layer. Such changes can include overwritten Blops, added Blops, deleted Blops, and even changes to the persistency marking of a Blop.
Layers are sometimes referred to herein as being "above" or "below" other Layers. Aboveness and belowness do not imply any height relationship, but rather merely imply a complementary pair of relationships between Layers. That is, if Layer A is above Layer B, then Layer B is below Layer A. The relationship implied by terms "above" and "below" is physical, however, since the relationship must be stored or available somewhere (for example, in a topology matrix) such that one can determine unambiguously whether one Layer is above, below or neither with respect to another Layer. The terms "above" and "below" are also intended to be interpreted transitively. That is, for example, if Layer A is above Layer B which is above Layer C, then Layer A is also above Layer C. When transitivity is not intended herein, a Layer is referred to as being "immediately above" or "immediately below" another Layer.
Layers can be identified by Layer Names. There is no practical limit to the number of Layer Names that can be associated with a Layer; but any name can be applied to at most one Layer in a given Pool. A Layer can also have no names associated with it. Layer Names are used in two ways in the Storage Manager: First, they are used to find specific Layers in a Pool. For instance, while there is one unique "Bottom" Layer in each Pool, there can be many "top" Layers which are not below any other Layer. If an Application needs to have a single identifiable "top" Layer, then it can use a Layer Name to specify and find it. The second way Layer Names are used in the Storage Manager is to mark atomic transactions between Layers. This use is enabled by Storage Manager calls which require that, in order to set the name of a Layer, the caller must also specify the Layer which previously had that Name (if any). The Storage Manager routine thus provides an atomic test-and-set. This guarantees that another application has not changed the location of a Layer Name unexpectedly.
FIG. 9 is a diagram of what the Layers in a Pool 902 might look like. The "Bottom" Layer 904 of the Pool has two names: "L1" and "Bottom", and it has 3 Blops in it: A, B and C. Blop A is marked as a persistent Blop for the Pool in that Layer (noted in the diagram by the bold lettering). Layer L1 has one Layer 906 immediately above it: L2. In L2, Blop A has been changed to its second version, but the versions of B and C are unchanged, so the version they had in L1 is still visible (noted in the diagram by the dashed border). Layer L2 has 2 Layers 908 and 910 immediately above it: L3 and L5. L3 once again changes Blop A, but also changes Blop C and adds Blop D. Blop B is unchanged so that the version from Layer L1 is still visible. In Layer L5, Blops A, B, and C are deleted, Blops F and G are added, and F is marked as a persistent Blop. Thus the view of the Pool in L5 is completely disjoint of the one in L2 from which it is derived. Layer L6 is derived from L5, but no changes have been made in L6 yet so it can be referred to as an empty Layer.
Reconciliation Layers are described above with respect to FIG. 3.
A basic rule observed by the Storage Manager in manipulating Blops in Layers is that it is illegal to change a Blop in a Layer in such a way as to change what is seen in any other Layer which is not directly involved in the operation. For instance, if the current Layer is below another Layer, it is illegal to create or change any Blops in the current Layer, since doing so would change what is seen in the next Layer without its "permission". Thus, in FIG. 3, Layers L1, L2, and L3 are effectively Read-Only.
If direct manipulation of Blops in Layers was the only way to change Blops, then the lower Layers in a Pool would be useful as only archives. However, this is not the case. The Storage Manager provides several operations which span several Layers; and since these operations "directly involve" multiple Layers, it becomes possible to make changes in base Layers as long as the application can successfully include all of the Layers which are derived from that base Layer. One such operation is SMMoveAllChangesDown which allows the changes which exist in one Layer to be moved down into Layers which is below it. As described above with respect to FIG. 6, SMMoveAllChangesDown from Layer A to Layer B makes Layer B have the same view of the Blops as Layer A, and makes all of the Layers above B up through A be empty so that they also have the same view.
Note that the view of the Blops in L3 in the illustration of FIG. 6 is unchanged by this operation. This is always true of a SMMoveAllChangesDown: the view of the Layer being copied down from is never changed. The views of the Layers below it down to the Layer being copied down to are changed, and so the rule of manipulating Blops in Layers is invoked. Applying this rule, SMMoveAllChangesDown routine will not move changes down from Layer A to Layer B if there are any Layers which are transitively above B which are not either transitively below A or transitively above A.
The operation of this rule can be seen more clearly in FIG. 10. Referring to FIG. 10, in Pool 1002, it is acceptable to SMMoveAllChangesDown from L6 to L1 since L2-L5 are all both (transitively) above L1 and (transitively) below L6, and since the operation will not change the view from L6, L7 and L8. In Pool 1004, however, it is not acceptable since L9 is above L1 but is not below L6. To apply the above-stated rule, the operation would change the view of L9 (by changing L3 and L1), but L9 is not directly involved in the operation. Thus the SMMoveAllChanges Down routine prohibits the operation.
Another Storage Manager operation which spans Layers is the operation which is invoked by calling SMCleanUp with a kSMCCollapseLayers parameter code (hereafter simply CollapseLayers) which is used to eliminate unnecessary empty Layers in a portion of a Layer graph. The bottom Layers of Pools will not be eliminated. As can be seen from the previous examples, the aftermath of a SMMoveAllChangesDown routine is frequently a set of empty Layers which have no effect on what is seen from other Layers. CollapseLayers is used to eliminate such Layers. Specifically, CollapseLayers from Layer A to Layer B eliminates all empty Layers which are (transitively) above B and (transitively) below A, including Layer A, if empty. Any Names or non-empty Layers which are above Layers which are eliminated are moved down to the upper-most non-empty Layer which is below the eliminated Layer. An example of a CollapseLayers operation is shown in FIG. 7 and described above.
The only case in which CollapseLayers does not eliminate an Empty Layer is if doing so would force a name to be applied to more than one Layer. For instance, in the diagram of FIG. 11, empty Layer L6 is immediately above respective non-empty Layers L2 and L3. Since there is no Layer other than L6 to which the Name "version" could be applied and have it result in the same view of Blocks, so L6 can not be eliminated. The result of a CollapseLayers therefore is as shown in FIG. 11: empty Layers L4 and L5 are eliminated but empty Layer L6 remains immediately above Layers L2 and L3.
Delta Pools are also supported by the Storage Manager described herein. Essentially, Delta Pools allow several Pools, perhaps on different media, to behave as if they were a single large Pool. In a Delta Pool, the one Bottom Layer of the Pool is actually derived from Layers in a second "Base" Pool. Thus the Layers in the Delta Pool act as a continuation of the Layer graph in the "Base" Pool. Note that this modifies the statement above that Blops exist in one and only one Pool. In fact, a Blop can exist in several Pools as long as they are part of the same Delta Pool graph. (Note that the different instantiations of the Blop still define different "versions" of the Blop.) FIG. 4, described above, illustrates an example of how the Layers in a Delta Pool and its base might be related. As described above, a given Base Pool may have any number of Pools connected to it. A Delta Pool can be connected to only one Base Pool, and its bottom Layer is derived from one Layer in the Base Pool. Attempting to access a Delta Pool causes an attempt to reconnect it to its base. If the base has not changed since the Delta Pool was last connected the Delta Pool can be used. If the Base Pool has changed an exception will be raised and it will have to be manually reconnected using SMReconnectPool.
When reconnecting a Delta Pool, reconciliation might need to occur due to changes in the base. Reconciliation of Delta Pools is handled by a Reconciliation Handler which is supplied as part of the Storage Manager, but which can be replaced with an application specific Handler.
Separable Pools are also supported by the Storage Manager described herein. Separable Pools are very similar to Delta Pools, but have some additional functionality. Separable Pools are used to separate a Layer of a document from a work group environment. Generally, all of the Blops visible from a selected base Layer will be copied up into the bottom Layer of a newly created Separable Pool. This Pool usually exists in a separate Container and can be opened/accessed without the original Pool/Container being available. After changes are made the Separable Pool can be reintegrated and the user's changes can be reconciled against the Base Pool as changed by other members of the work group.
When reintegrating a Separable Pool reconciliation more than likely will need to occur due to changes in the base and the Separable Pool. Reconciliation of Separable Pools is handled by a supplied Reconciliation Handler that can be replaced with an application specific Handler.
In addition to the above, an embodiment of a Storage Manager can also support Property Prototypes to allow for the creation of prototypes of Properties and their Values. Upon instantiation of a Property that has a Property Prototype the initial Values would be set according to the Prototype. Property Prototypes can be used by multiple instantiations of the Properties with minimum duplication of structure.
A Storage Manager can also support Transactions, which can be started then selectably aborted or committed. These calls expand the guarantee of atomicity from single Layer manipulation calls to multiple calls, e.g. SMMoveAllChangesDown in multiple disjoint Pools.
II. Storage Manager ROUTINES
The logical data structure described above itself provides many advantages over prior structures for storing data in data storage apparatus. Set forth below are a number of routines which are unique in themselves and which also facilitate the use of the above-described data structure. The routines may be provided as part of a Storage Manager product, the data structure being created on an individual computer system as a result of a user's execution of these routines.
Before describing the routines, it will be useful to set forth C language definitions of various constants and data types which are used in the routines:
__________________________________________________________________________
.COPYRGT. 1992 Apple Computer
Constants
#define SMUndefined 0L; /* ignore parameter value */
#define SMUIPFileContHandler "fch";/* provided container handler */
#define SMDefaultReconcileHandler "drh"; /* provided default
reconcile handler */
#define SMBPVAccessorIteratorHandler "bpva"; /* provided iterator
handler */
#define SMStructuredNameIteratorHandler "snit"; /* provided
iterator handler */
#define SMBlopIdIteratorHandler "bidi"; /* provided iterator
handler */
Data Types
typedef void *SMBPVAccessor;
/* blop, property and value context
pointer */
typedef char *SMStructuredName;
/* structured name */
typedef Size SMSize;
/* generic size of data typedef */
typedef void *SMCPLAccessor;
/* container, pool and layer context
pointer */
typedef SMCount SMValueIndex; /* index of a value in a property */
typedef SMStructuredName SMPoolName; /* required for a pool */
typedef SMStructuredName SMLayerName; /* optional for a layer */
typedef unsigned long SMBlopId; /* persistent reference */
typedef unsigned long SMCount; /* generic count typedef */
typedef void *SMStream; /* stream value pointer */
typedef long SMStreamPos; /* value stream position */
typedef void *SMContSpec; /* fully defines a container */
typedef void *SMIterator; /* no guarantee of how stored */
typedef char *SMHandler; /* storage manager handler names */
typedef SMHandler SMContHandler; /* name of container handler */
typedef SMHandler SMReconcileHandler; /* reconcile handler name
typedef SMHandler SMIteratorHandler; /* iterator handler name */
typedef void *SMIterItemptr; /* pointer to an individual item */
typedef const enum {
/* access mode: */
kSMAReadOnly
= 0x001;
/* no update allowed */
kSMAReadWrite
= 0x002;
/* changes allowed */
/* special cpl access mode: */
kSMATransient
= 0x003;
/* no internal access allowed */
} SMAccessorKind;
typedef const enum {
kSMMIType = 0x01;
/* type meta-information */
kSMMIProperty
= 0x02;
/* property meta-information */
} SMMetaInfoKind;
typedef const enum {
/* error returns: */
kSMMRContNotFound
= (-6); /* container was not found */
kSMMRPoolNotFound
= (-5); /* pool was not found */
kSMMRLayerNotFound
= (-4); /* layer was not found */
kSMMRBlopNotFound
= (-3); /* blop was not found */
kSMMRPropNotFound
= (-2); /* property was not found */
kSMMRValueNotFound
= (-1); /* value was not found */
kSMMRNoMovement
= 0x00; /* no movement necessary */
/* success returns: */
kSMMRChild = 0x01; /* a child was positioned to */
kSMMRParent = 0x02; /* a parent was positioned to */
kSMMRSibling = 0x04; /* a sibling was positioned to */
kSMMRDisjoint
= 0x08; /* disjoint positioning occurred */
/* return modifiers: */
kSMMRwrap = 0x100; /* a wrap occurred */
} SMPositionResult;
typedef const enum {
kSMpUndefined
= 0x00;
/* set to undefined */
kSMPSame = 0x01;
/* leave where it is */
kSMPFirstSib = 0x02;
/* first of the given kind */
kSMPLastSib = 0x03;
/* last of the given kind */
kSMPNextSib = 0x04;
/* next of the given kind */
kSMPPrevSib = 0x05;
/* previous of the given kind */
kSMPFirstBelow
= 0x06;
/* first below of current kind */
kSMPLastBelow
= 0x07;
/* last below of current kind */
kSMPFirstAbove
= 0x08;
/* first above of the given kind */
kSMPLastAbove
= 0x09;
/* last above of the given kind */
/* modifiers */
kSMPMwrap = 0x10;
/* allow wrapping */
ksMMNoTypes = 0x20;
/* skip type meta info blops */
kSMMNoProperties
= 0x40;
/* skip property meta info blops */
kSMMNoBlops = 0x80;
/* skip normal blops */
} SMPositionCode;
typedef const enum {
kSMBFalse = (0);
/* false boolean */
kSMBTrue = (-1);
/* true boolean */
} SMBoolean;
/* generic boolean typedef */
typedef const enum }
ksMCIgnore
= 0x01; /* ignore cycle */
kSMCSkip = 0x02; /* skip duplicate blop */
kSMCError
= 0x03; /* raise cycle exception */
} SMSearchOption;
typedef const enum {
kSMRLBlockSwappable
= (-5);
/* most likely to be purged */
kSMRLBlockNormal
= 0;
/* average chance - default */
kSMRLBlockRetain
= 5;
/* will not be purged */
} SMRetentionLevel;
typedef const enum {
kSMSSeekSet = 0x00; /* seek from beginning of value */
kSMSSeekCur = 0x01; /* seek from current position in value */
kSMSSeekEnd = 0x02; /* seek from end of value */
} SMStreamSeekCode;
typedef const enum {
kSMCDisposeInconsistent
= 0x01;
/* disposes of inconsistent
layers */
kSMCCollapseLayers
= 0x02;
/* collapses all layers
possible */
kSMCGarbageCollectPool
= 0x04;
/* garbage collects pool */
kSMCCompactContainer
= 0x08;
/* compact container */
} SMCleanupCode;
typedef const enum {
kSMRConflictingChange
= 0x01;
/* blops different */
ksMRBaseLayerNameMoved
= 0x02;
/* name moved/gone */
ksMRNewBloplnBase
= 0x04;
/* new blop in base */
kSMRDisposeOBlopInBase
= 0x08;
/* blop gone in base */
kSMRNewNameInSeparable
= 0x10;
/* new name in sep */
kSMRNewBlopInSeparable
= 0x20;
/* new blop in sep */
kSMRDisposeOBlopInSeparable
= 0x40;
/* blop gone in sep */
kSMRLayerNameCleanup
= 0x80;
/* same layer name
kSMRMAll = 0XFF;
/* all operators */
} SMReconcileOperator;
typedef const enum {
kSMBoBigEndian
= 0x00;
/* big endian byte order */
kSMBOLittleEndian
= 0x01;
/* little endian byte order */
} SMByteOrder;
typedef struct {
FSSpec fsSpec;
/* hfs file specification */
char permission;
/* open permission to file */
OSType creator;
/* creator of file-used on create */
OSType fileType;
/* file typeof file-used on create */
ScriptCode scriptTag;
/* document name script-used on
create */
SMBoolean dataFork;
/* store data in data or resource fork */
} SMFileSpec;
typedef struct {
SMIteratorHandler
iterHandler;
long reserved;
/* reserved for future use */
union {
Ptr pointer;
SMCount index;
Size offset;
} current; /* how current is accessed */
void *storage;
/* storage area for iterator */
SMSize itemSize;
/* size of current item */
SMCount itemCount;
/* count of current items */
} SMIter, *SMIterPtr;
typedef const enum {
/* operator: parameters: */
kSMIterCreate;
/* SMIterPtr */
kSMIterAdd; /* SMIterPtr, const SMIterItemPtr, Boolean */
kSMIterRemove;
/* SMiterPtr, const SMIterItemPtr */
kSMIterFirst;
/* SMIterPtr, SMIterItemPtr */
kSMIterLast; /* SMIterPtr, SMIterItemPtr */
kSMIterNext; /* SMIterPtr, SMIterItemPtr */
kSMIterPrev; /* SMIterPtr, SMIterItemPtr */
kSMIterCount;
/* SMIterPtr, SMCount * */
kSMIterGetIndex;
/* SMIterPtr, SMCount, SMIterItemPtr */
kSMIterSetIndex;
/* SMIterPtr, SMCount, const SMIterItemPtr */
kSMIterRemoveIndex;
/* SMIterPtr, SMCount */
kSMIterGetSize;
/* SMIterPtr */
kSMIterDelete;
/* SMIterPtr */
kSMIterAdjust;
/* SMIterPtr */
} SMIteratorOperator;
typedef struct {
SMSize *freeSpace;
/* free space in accessor's heap */
} SMWSReadOnlyInfo;
typedef struct {
THz *theHeap; /* heap to allocate from */
SMSize *maxMemory;
/* maximum memory to use */
SMCount *BlopCacheCount;
/* number of blops to cache */
} SMWSReadWriteInfo;
typedef struct {
SMAccessorKind *aKind;
/* kind of bpv accessor
SMAccessorKind owningCPLAKind;
/* owning kind to create */
SMCPLAccessor *owningContext;
/* owning cpl accessor */
SMMetaInfoKind *mKind;
/* kind if meta-info blop */
SMSize maxPropertyNameSize;
/* max size for prop name */
SMStructuredName propertyName;
/* name of property */
SMSize maxTypeNameSize;
/* max size for type name */
SMStructuredName typeName;
/* name of type */
SMValueIndex *valueIndex;
/* current value index */
SMBoolean *embeddedIds;
/* are there embedded ids? */
SMByteOrder *byteOrder;
/* byte order of value */
} SMBPVReadOnlyInfo;
typedef struct {
SMBoolean *persistent;
/* whether persistent */
SMRetentionLevel *retention;
/* blop cache control */
} SMBPVReadWriteInfo;
typedef struct {
SMAccessorKind *aKind;
/* kind of cpl accessor */
SMFileSpec *theFile;
/* associated file spec */
SMAccessorKind basePoolAKind;
/* accessor kind to create */
SMCPLAccessor *basePool;
/* for delta and separable */
SMIterator layerNames;
/* current set of layer */
} SMCPLReadOnlyInfo;
typedef struct {
SMSize *contInfoSize;
/* size of container info */
void *contInfo; /* app container info */
SMSize *maxPoolNameSize;
/* pool name buffer size */
SMStructuredName poolName;
/* pool name */
SMSize *poolInfoSize;
/* size of pool info */
void *poolInfo; /* app pool info */
SMBoolean *consistent;
/* whether layer consistent */
} SMCPLReadWriteInfo;
__________________________________________________________________________
In addition to the above typedefs, set forth below are the C language typedefs for a CPL Accessor and a BPV Accessor:
__________________________________________________________________________
// Container/Pool/Layer Accessor or CPLAccessor
typedef struct {
smContspecHdl contSpec;
// Container specification
BALCRef balcRef; // Reference to persistent storage
PMANPoolRef poolRef;
// Pool being referenced (if any)
PMANLayerRef layerRef;
// Layer being referenced (if any)
SMBPvAccessor bpva;
// Reference to a collection of
// BPVAccessors associated with
// this Layer (if any)
SMAccessorKind permission;
// Access Permission to the Layer
SMCPLAccessor nextBaseLayer;
// Base Layer to this Layer
SMStructuredName poolName;
// Current Pool name (if it exists)
SMStructureName layerName;
// Current Layer name (if it exists)
} CPLA;
// Blop/Property/Value Accessor or BPVAccessor
typedef struct {
SMAccessorKind kind;
// type of accessor
SMCPLAccessor layer;
// Layer that the accessor is created
SMMetaInfoKind mKind;
// meta info
SMValueIndex curValue;
// Index to the current Value
SMStructuredName curProperty;
// Name of the current Property
SMBlopId bid;
// Persistent ID of the Blop
PDBHandle PDB;
// Reference to Persistent Storage for Properties
DDBHandle DDB;
// Reference to Persistent Storage for Values
SMBPVAccessor indirectValue;
// Reference to another
// BPVAccessor for a remote value
SMBpVAccessor indirectedFrom;
// BPVAccessor currently
// referencing this one (if
// this BPVAccessor is referring
// to a remote value)
} BPVA;
__________________________________________________________________________
Also before describing the individual routines, it will be useful to understand certain runtime concepts which the routines use. In particular, two kinds of Accessors are used to move about the hierarchies which the Storage Manager manages. BPV Accessors are used to designate the context of a Blop. A BPV Accessor defines a current Blop, Property and Value. CPL Accessors designate the context of a Container. A CPL Accessor defines a current Container, Pool and Layer. BPV Accessors are inherently owned by a CPL Accessor which defines the Layer being used to access the designated Blop. Both of these Accessors share some common functionality. They can be used to iterate through all of their corresponding contexts. For example, a BPV Accessor can iterate over all Properties within a Blop, and all Values within a Property. BPV and CPL Accessors can also be re-targeted to different Blops and Containers. This allows for all Blops within a Layer to be reached.
Accessors are not persistently stored. They are used by an application to dynamically access the storage space maintained by the Storage Manager. For example, when attempting to access a particular Value of a Blop a BPV Accessor is given as the parameter that defines the Value. The BPV Accessor defines the context of the Value that is to be manipulated.
CPL Accessors define an in-memory Workspace. This defines the heap, cache sizes, etc. where the Storage Manager allocates BPV Accessors and any other CPL Accessor memory allocations necessary for its routines. There is a default Workspace that can be set at initialization that will be used by a CPL Accessor if a specific Workspace is not defined for it.
In addition to the above, it will be helpful to note that there are some routines within the Storage Manager that require a set of elements to be passed. For this reason the Storage Manager provides a robust Iterator mechanism that allows for the definition of sets of elements. The Iterator mechanism is generic and allows for the application program to define sets. Iterators returned by Storage Manager routines are snapshots of the current state, and cannot be used to indirectly change the state. For example, SMOwnedBPVAccessors returns an Iterator that contains all of the BPV Accessors that belong to a given CPL Accessor. Removing items from the Iterator has no effect on the BPV Accessors owned by the CPL Accessor, only the Iterator is changed.
The Storage Manager includes the following application program interface calls.
A. Initialization
______________________________________
void SMInit (SMWSReadWriteInfo * rwInfo);
______________________________________
Initializes the Storage Manager environment and sets the default Workspace info for CPL Accessors.
B. Blop Identification
______________________________________
void SMBindBlopName (SMBPVAccessor blop,
const SMStructuredName theName);
______________________________________
Binds the given name to the Blop designated by the given Accessor. Binding a name to a Blop that already has a name bound to it, or to a Meta Information Blop, is not allowed.
______________________________________
void SMUnBindBlopName (SMCPLAccessor layer,
const SMStructuredName theName);
______________________________________
Removes any name associated with the Blop within the context of the given Layer. This routine is not valid for Meta Information Blops.
______________________________________
SMSize SMGetBlopName (SMBPVAccessor blop,
SMSize maxSize,
SMStructuredName theName);
______________________________________
Returns the name associated with the Blop designated by the given Accessor, if one exists. The size returned is the number of bytes copied into the name parameter. A size of zero indicates that no name is associated. Passing kSMUndefined for the name causes the return of the actual length of any associated name.
______________________________________
SMBPVAccessor SMBPVAccessorFromName (SMCPLAccessor layer,
const SMStructuredName theName,
SMAccessorKind aKind);
______________________________________
Returns the Accessor that designates the Blop that the given name is bound to in the Layer as designated by the given Accessor. A new BPV Accessor is created, of the given kind, that designates the Blop and then is returned. The Blop may be either a normal Blop or a Meta Information Blop.
______________________________________
SMBlopId SMGetBlopId (SMCPLAccessor layer,
SMBPVAccessor blop);
______________________________________
Given a Blop within a given Layer the persistent Blop identifier (Blop Id) is returned. This Id can safely be embedded within another Blops' Value data to create a persistent link. A Blop Id requires a Layer context to be useful, but with a given Pool a Blop will maintain its Id indefinitely, which means that within any Layer in the Pool the Blop will have the same Id.
C. BPV Accessors
______________________________________
SMBPVAccessor SMNewBPVAccessor (SMAccessorKind a Kind,
SMCPLAccessor layer,
const SMStructuredName blopName,
SMBlopId blopId,
const SMStructuredName propertyName,
SMValueIndex valueIndex,
const SMStructuredName typeName);
______________________________________
Allocates an Accessor to Blop data. Whether or not changes may be made to the data designated by this kind of Accessor is based on the BPV Accessor Kind created. All of the parameters other than BPV Accessor Kind are optional, and are used to set the initial Accessor location. To define the initial Blop that the Accessor is designating, Layer and blopName, or Layer and blopId must be specified. Names always take precedence. To define the initial Property of the initial Blop the propertyName must be specified. The initial Value of the initial Property can be specified either by the valueIndex or by the Type of the Value. If specified by Type, then the first Value Index with the given Type will be designated. If any of the parameters are invalid, e.g. an invalid Blop name, an exception is raised.
Every BPV Accessor is created within the context of a CPL Accessor. In other words, a CPL Accessor owns all the BPV Accessors created using it. BPV Accessors cannot be shared even among different CPL Accessors of the same process.
______________________________________
void SMDisposeBPVAccessor (SMBPVAccessor accessor, SMBoolean
commit);
______________________________________
Dispose of the indicated BPV Accessor. Any changes made with a ReadWrite BPV Accessor to Blop data are committed if commit is kSMBTrue. If commit is kSMBFalse any changes made to the Blop data are aborted. commit is ignored for ReadOnly BPV Accessors.
______________________________________
void SMTransformBPVAccessor (SMBPVAccessor accessor,
SMAccessorKind aKind,
SMBoolean commit);
______________________________________
Transforms a BPV Accessor from one kind to another. If transforming from ReadOnly to ReadWrite the BPV Accessor must be the only Accessor designating the Blop. When transforming from ReadWrite to ReadOnly any changes are committed if commit is kSMBTrue. If commit is kSMBFalse any changes made to the Blop data are aborted. commit is ignored for ReadOnly transformation to ReadWrite.
______________________________________
SMBPVAccessor SMRetargetBPVAccessor (SMBPVAccessor accessor,
SMAccessorKind aKind,
SMBoolean commit,
SMPositionCode blopPosition,
SMBoolean samePropertyName,
SMBoolean sameValueIndex,
SMBoolean sameTypeName,
SMCycleCode cycleCode);
______________________________________
Re-targets a given BPV Accessor, to a potentially different Blop, based on the given Blop position code. The given Accessor is re-targeted, if the given Accessor Kind is SMUndefined, or a new BPV Accessor is created, of the given kind, and is set to designate the Blop targeted. When re-targeting from a child Blop to a parent with a ReadWrite BPV Accessor the changes made are committed or aborted based on the given commit parameter. The cycleCode determines the result of targeting a Blop that has already been previously reached with the given BPV Accessor. If samePropertyName, sameValueIndex, or sameTypeName are kSMBTrue then the Accessor returned will attempt to designate the same Property as the original, by name, the same Value as the original, by Index or by name. If the attempt to keep the same designated Property or Type fails the corresponding portion of the returned BPV Accessor will be undefined.
Embedded Blop Ids within a Value are considered the current children of a Blop. When positioning to kSMPFirstBelow the first Embedded Blop Id within the current Value is the Blop that is targeted. The Blop Id is resolved within the same Layer as the current Blop, or within the same Layer as the Remote Blop if it is an Indirect Blop. Re-targeting to kSMPFirstAbove or kSMPLastAbove with such an Accessor would resolve back to the Value that was used to find the child. When performing a retargeting to kSMPNextSib the next Embedded Blop Id of the parent is used. If the Blop has no parent, i.e. was positioned to by name, kSMPNextSib positions to the next Blop owned by the Layer. The valid position codes are as follows:
______________________________________
Parameter: blopPosition
Valid Position Code
Meaning
______________________________________
kSMPundefined set Blop to undefined
kSMPSame stay on same Blop
kSMPFirstSib goto first Blop on same level
kSMPLastSib goto last Blop on same level
kSMPNextSib goto next Blop on same level
kSMPPrevSib goto prev Blop on same level
kSMPFirstBelow goto first child of Blop
kSMPLastBelow goto last child of Blop
kSMPFirstAbove goto parent Blop (same as
kSMPLastAbove)
kSMPLastAbove goto parent Blop (same as
kSMPFirstAbove)
kSMPMWrap allow wrapping
kSMPMNoTypes skip Type Meta Information Blops
kSMPMNoProperties
skip Property Meta Information
Blops
kSMPMNoBlops skip normal Blops
SMPositionResult SMPositionBPVAccessor(SMBPVAccessor accessor,
const SMStructuredName propertyName,
SMPositionCode propPosition,
SMValueIndex targetIndex,
SMPositionCode indexPosition,
SMBoolean sameType);
______________________________________
Repositions a given BPV Accessor within a Blop returning the status of the positioning. The return Value, if positive, indicates how the new location of the Accessor is related to the previous location; and if negative, it indicates how far SMPositionBPVAccessor was able to proceed with this process before an error was detected. On failure, the Accessor is left pointing at the closest Property and Value it could find to the ones requested that still satisfies the given parameters. All of the parameters other than the first Accessor are optional, and are used to reset the Accessor location. If a Property name is given the corresponding position code is ignored. If a Value Index is given the corresponding position code is ignored.
The routine positions Property first, either by name or by relative to current Property. The Value is next positioned, by either the given Index or relative to the current Index. The given sameType flag attempts to impose a filter on the Indexes that will be designated. If sameType is kSMBTrue then for example, positioning to the kSMPNextSib Index will attempt to position to the next Value Index with the same Type as the current Index. If the Property is changed, and the Index position code given is relative to current, the Value Index positioned to will be the current Index plus the position code. For example, we are positioned to Value Index four of a Property. The Property is changed by kSMPNextSib and the Value Index is changed by kSMPNextSib. The Property is positioned to the next Property of the Blop. The Index positioned to will be Value Index five, if such an Index exists within the next Property. If it does not, the Value Index will be the highest Index available since that would be the closest that could be found. The valid position codes for each position code argument are as follows:
______________________________________
Valid Position Code
Meaning
______________________________________
Parameter: propPosition
kSMPUndefined set Property to undefined
kSMPSame stay on same Property
kSMPFirstSib goto first Property
kSMPLastSib goto last Property
kSMPNextSib goto next Property
kSMPPrevSib goto previous Property
kSMPMWrap allow wrapping
Parameter: indexPosition
Valid Position Code
Meaning
kSMPUndefined set Index to undefined
kSMPSame stay on same Index
kSMPFirstSib goto first Index
kSMPLastSib goto last Index
kSMPNextSib qoto next Index
kSMPPrevSib goto previous Index
kSMPMWrap allow wrapping
SMCount SMCountBPVAccessor(SMBPVAccessor accessor,
SMPositionCode propertyPosition,
SMPositionCode indexPosition,
SMBoolean sameType);
______________________________________
Returns the number of times that the given Accessor could be moved according to the parameters before stopping. The wrap position code modifier is not allowed for any given position code. The parameters are interpreted the same as in the SMPositionBPVAccessor routine. With this routine it is easy to determine the number of Properties in a Blop, the number of Values in a Property, the number of Values of a given Type within a Property, etc.
______________________________________
void SMSetPreferredPosition (SMBPVAccessor accessor);
______________________________________
Sets the preferred position for the given Blop as indicated by the given Accessor. Whenever a SMBPVAccessor is created for this Blop with undefined parameters, it is automatically positioned at this location.
______________________________________
SMPBAccessor SMCloneBPVAccessor (SMBPVAccessor accessor);
______________________________________
Creates a duplicate of the given BPV Accessor. Only ReadOnly Accessors can be cloned since two ReadWrite Accessors are not allowed to be targeting the same Blop.
______________________________________
void SMGetBPVAccessorInfor (SMBPVAccessor accessor,
SMBPVReadOnlyInfo *roInfo,
SMBPVReadWriteInfor *rwInfo);
______________________________________
Returns the details of what the given BPV Accessor designates. kSMUndefined may be passed as arguments to parameters that are not wanted. kSMUndefined will be returned for elements that are undefined.
______________________________________
void SMSetBPVAccessorInfor (SMBPVAccessor accessor,
SMBPVReadWriteInfor *rwInfo);
______________________________________
Sets the details of the Blop designated by the given BPV Accessor. The default for persistent in SMBPVReadWriteInfo is kSMBTrue.
D. Blop Creation and Removal
______________________________________
SMBPVAccessor SMCreateBlop (SMCPLAccessor layer,
SMAccessorKind aKind);
______________________________________
Creates a new Blop. The Blop is instantiated in the Container, Pool and Layer designated by the given CPL Accessor. A new BPV Accessor, of the given kind, is created that designates the new Blop and then is returned.
______________________________________
SMBPVAccessor SMCreateMetaInfoBlop (SMCPLAccessor layer,
const SMStructureName the Name,
SMMetaInfoKind mKind,
SMAccessorKind aKind);
______________________________________
Creates a new Meta Information Blop. The Meta Information Blop, of the given Meta Information kind, is instantiated with the given name in the Container, Pool and Layer designated by the given CPL Accessor. A new BPV Accessor, of the given kind, is created that designates the new Meta Information Blop and then is returned.
______________________________________
void SMIndirectBlop (SMBPVAccessor localBlop,
SMBPVAccessor remoteBlop,
SMCPLAccessor remoteLayer,
const SMStructuredName remoteBlopName);
______________________________________
Changes an existing Blop into an Indirect Blop which resolves into the Blop indicated by either a remoteBlop or a remoteLayer/remoteBlopName combination. If only remoteBlop is provided, then the Indirection Blop resolves itself by Id. If remoteLayer and remoteBlopName are provided then the Blop is resolved by Name. This routine is valid for Meta Information Blops as well as normal Blops. Any existing Properties are removed from the localBlop. This routine is only valid with a ReadWrite BPV Accessor.
______________________________________
SMBPVAccessor SMGetIndirectBlopInfo (SMBPVAccessor
localBPVAccessor, SMBPVAccessor remoteValue);
______________________________________
Gets information about which Blop a particular, presumably Indirect, Blop resolves into. localBPVAccessor identifies the possible Indirect Blop. remoteValue is repositioned to refer to the target Blop before being returned. This is an optional parameter and if not given the localBPVAccessor is retargeted to the target Blop. If localBPVAccessor does not refer to an Indirect Blop, then remoteValue is positioned to the same Blop. This routine is only valid with a ReadOnly BPV Accessor.
______________________________________
SMBPVAccessor SMCloneBlop (SMCPLAccessor destCPLAccessor,
const SMStructuredName destName,
SMBPVAccessor sourceBPVAccessor,
SMAccessorKind aKind);
______________________________________
Creates a copy of the Blop indicated by sourceBPVAccessor in the Layer indicated by destCPLAccessor and returns a new BPV Accessor, of the given kind, that refers to the copy. If the Blop being cloned currently has a bound name it will have the same name in the destCPLAccessor. A new name may be set by passing destName. The resulting new Blop is an exact copy of the original Blop, except for any Embedded Blop Ids it may contain in its Values. Embedded Blop Ids from the original may need to be changed if the source and destination Layers are in different Pools, and the routine may need to create Indirect Blops in the destination Layer which resolve into the Blops referred to by the Embedded Blop Ids in the original. If the destination Layer is the same as the original Blop, which can be designated by passing kSMUndefined for destCPLAccessor, and the original Blop is named its clone will have no name unless one is given for it. This routine is valid for Meta Information Blops as well as normal Blops.
______________________________________
void SMRemoveBlop (SMBPVAccessor blop);
______________________________________
Removes a Blop designated by the given Accessor. The BPV Accessor is left in an undefined state. No other BPV Accessors can be targeted at the given Blop.
E. Value Manipulation
______________________________________
SMBPVAccessor SMCreateValue (SMBPVAccessor blop,
const SMStructuredName propertyName,
SMValue Index valueIndex,
const SMStructuredName typeName,
SMAccessorKind aKind);
______________________________________
Creates a new Value for the designated Blop, of the given Type in the given Property at the given Value Index. propertyName, valueIndex, and typeName are optional; if any of them is kSMUndefined the corresponding attribute of the Value will be derived from the corresponding attribute of the BPV Accessor. In this case the appropriate elements must be defined on the BPV Accessor.
If propertyName is not kSMUndefined, then a new Property (if necessary), with the given name is added that contains no Values. The new Value is specified by Index and will be of the given Type. Indexes are not sparse, so the Value Index, if passed, must be between one and one more than the current last Index. New Value entries never overwrite existing entries, they are inserted before the Value at the given Index and all other entries are pushed up one entry.
If kSMUndefined is given for the Accessor Kind, the given Accessor is repositioned to designate the new Value and returned. Otherwise a new BPV Accessor is created, of the given kind, and then is returned. The Value at this point has no associated data. The Value data is set with SMWriteValueData, SMInsertValueData, or implicitly by SMIndirectValue or SMCreateContainer (to create an embedded Container).
The Type Meta Information Blop that typeName refers to must exist prior to calling this routine. The Property Meta Information Blop that propertyName refers to does not need to exist prior to calling this routine. If the Property Meta Information Blop does not exist one will automatically be created. In this case the propertyName given must be unique within the Pool.
______________________________________
SMSize SMGetValueSize (SMBPVAccessor value);
______________________________________
The size of the Value data designated by the given BPV Accessor is returned.
______________________________________
void *SMGetReadOnlyValuePtr (SMBPVAccessor value,
SMSize *length);
______________________________________
A pointer to the Value data designated by the given BPV Accessor is returned. If the length parameter is not kSMUndefined the size of the Value data is returned. The pointer which is returned by this routine is valid until either the given Accessor (or its clone) is removed or repositioned from the current Blop. Every attempt will be made to return a pointer to the actual data to minimize copying of data. This routine is only valid with a ReadOnly BPV Accessor.
______________________________________
SMSize SMReadValueData (SMBPVAccessor value,
void *buffer,
SMSize offset,
SMSize maxSize);
______________________________________
The Value data designated by the given BPV Accessor and offset is copied into the buffer given up to maxSize bytes. The length of the Value data that was actually copied is returned.
______________________________________
void SMWriteValueData(SMBPVAccessor value,
void *buffer,
SMSize offset,
SMSize length);
______________________________________
The Value data designated by the given BPV Accessor is changed to the data from the given buffer beginning at offset from the beginning of the Value. The Size of the buffer is passed. If the buffer passed is kSMUndefined then the Value data is set to zeroes from offset to offset plus length. This routine is only valid with a ReadWrite BPV Accessor.
______________________________________
void SMInsertValueDAta (SMBPVAccessor value,
void *buffer,
SMSize offset,
SMSize length);
______________________________________
The data from the given buffer is inserted into the Value designated by the given BPV Accessor at offset from the beginning of the Value. The Size of the buffer is passed. If the buffer passed is kSMUndefined then the Value data is set to zeroes from offset to offset plus length. The resulting Value data will be length bytes longer. This routine is only valid with a ReadWrite BPV Accessor.
______________________________________
void SMRemoveValueData (SMBPVAccessor value,
SMSize offset,
SMSize length);
______________________________________
The Value data, designated by the given BPV Accessor, starting at the given offset for length bytes is removed from the Value. The resulting Value data is length bytes shorter. This routine is only valid with a ReadWrite BPV Accessor.
______________________________________
void SMReoveValue (SMBPVAccessor value);
______________________________________
The Value designated by the given Accessor is removed from the enclosing Property. The Value attribute of the BPV Accessor is left undefined. Only the last Index can be disposed of since sparse multiple Values are not allowed. If the BPV Accessor is positioned at the third Index of a Property with five defined Indexes and this routine is made an exception will be raised. This routine is only valid with a ReadWrite BPV Accessor.
______________________________________
void SMRemoveProperty (SMBPVAccessor property);
______________________________________
The Property, and all of its Values, designated by the given Accessor are removed. The Property and Value attributes of the BPV Accessor are left undefined. This routine is only valid with a ReadWrite BPV Accessor.
______________________________________
void SMCloneProperty (SMBPVAccessor destBlop,
SMBPVAccessor sourceProperty);
______________________________________
Make a copy of the Property indicated by sourceProperty (including all of its Values) at the location indicated by destBlop. The resulting new Property is an exact copy of the original Property, except for any Embedded Blop Ids it may contain in its Values. Embedded Blop Ids from the original may need to be changed if the source and destination Layers are in different Pools, and the routine may need to create Indirect Blops in the destination Layer which resolve into the Blops referred to by the Embedded Blop Ids in the original. Any needed Meta Information Blops are cloned to the destination as well. This routine is only valid with a ReadWrite destination BPV Accessor.
______________________________________
void SMMarkEmbeddedBlopIds (SMBPVAccessor value,
SMSize offset,
SMCount count,
SMBoolean setMark);
______________________________________
In most Values, the location of Embedded Blop Ids in the data are defined by the Type of the Value. However, some uses of the Storage Manager require the structure of a Value to be variable, and therefore the location of Embedded Blop Ids are not well defined. In these cases this routine needs to be used to inform the Storage Manager of where Embedded Blop Ids are and are not stored. If setMark is kSMBTrue, this routine notes that the count longwords in the Value referred to by the BPV Accessor starting at offset contain Embedded Blop Ids. Likewise, if setMark is kSMBFalse, it notes that the indicated longwords do not contain Embedded Blop Ids. This routine is only valid with a ReadWrite BPV Accessor.
F. Value Indirection
______________________________________
void SMIndirectValue (SMBPVAccessor localValue,
SMBPVAccessor remoteValue,
SMSize remoteOffset,
SMSize remoteLength);
______________________________________
Changes an existing Value, indicated by localValue, into an Indirect Value which resolves into (at least part of) the Value indicated by remoteValue. If remoteOffset is not kSMUndefined, then only that part of the remote Value starting at the indicated offset is indirected to. If remoteLength is not kSMUndefined, then only that number of bytes of the remote Value are used. Any existing Value data is removed from the local Value. remoteOffset and remoteLength are automatically pegged to the end of the remote Value. This routine is only valid with a ReadWrite BPV Accessor.
______________________________________
void SMGetIndirectBalueInfo (SMBPVAccessor localValue,
SMBPVAccessor remoteValue,
SMSize *remoteOffset,
SMSize *remoteLength);
______________________________________
Gets information about which Value a particular, presumably Indirect, Value resolves into. localValue indicates the possibly indirect Value. remoteValue (if not kSMUndefined) is repositioned to refer to the Value localValue resolves into, and remoteOffset and remoteLength (if not kSMUndefined) are filled in with the appropriate offset and length. If localValue does not refer to an Indirect Value, then remoteValue is repositioned to refer to the same Value as localValue and *remoteOffset and *remoteLength are set to kSMUndefined.
______________________________________
void SMChangeIndirectValue (SMBPVAccessor localValue,
SMSize remoteOffsetChange,
SMSize remoteLengthChange);
______________________________________
An existing Indirect Value indicated by localValue is changed to resolve into a different area of its Remote Value. remoteOffsetChange and remoteLengthChange are added to the current offset and length of the Indirect Value. The window on the Remote Value is automatically kept within the data of the Remote Value, i.e. the offset will be kept above zero and the offset plus the length won't extend past the end of the Value. This routine is only valid with a ReadWrite BPV Accessor.
G. Value Stream I/O
______________________________________
SMStream SMStreamOpen (SmBPVAccessor value);
______________________________________
Use SMStreamOpen to open the Value whose location is specified by the given BPV Accessor and associate a stream with it. The stream is opened with in ReadOnly or ReadWrite mode based on how the Accessor was acquired. If the Value is successfully opened, SMStreamOpen returns a pointer to a stream data structure that controls the stream.
______________________________________
int SMStreamClose (SMStream stream);
______________________________________
Use SMStreamClose to close the stream specified by stream. If the stream was open for writing, the content of the buffer associated with the stream is written to the Value ("flushed") before the Value is closed. If it was open for reading, unread data in the buffer are discarded.
______________________________________
SMSize SMStreamRead (void *ptr,
SMSize size,
SMSize count,
SMStream stream);
______________________________________
Use SMStreamRead to read the number of data items specified by count, each of a size given by the argument size, from the current position in stream. The current position of stream is updated after the read. The SMStreamRead routine returns the number of items it successfully read.
______________________________________
SMSize SMStreamWrite (const void *ptr,
SMSize size,
SMSize count,
SMStream stream);
______________________________________
Use SMStreamWrite to write the number of data items specified by count, each of a size given by size, from buffer to the current position in stream. The current position of stream is updated after the write. The SMStreamWrite routine returns the number of items it actually wrote.
______________________________________
int SMStreamSeek (SMStream stream,
SMSize offset,
SMStreamSeekCode origin);
______________________________________
Use the SMStreamSeek routine to reposition stream to the location specified by offset with respect to the argument origin. The SMStreamSeek routine returns a non zero value only if it fails to position the stream.
______________________________________
in SMStreamGetPos (SMStream stream,
SMStreamPos pos);
______________________________________
Use SMStreamGetPos to get and save the current position indicator of the stream specified by the argument stream in the SMStreamPos data object pos. This Value is used by the companion routine SMStreamSetPos to reposition the stream at the time of the call to SMStreamGetPos. If successful, SMStreamGetPos returns zero. In case of error, it returns a non zero Value.
______________________________________
int SMStreamSetPos (SMStream stream,
const SMStreamPos pos)
______________________________________
Use SMStreamSetPos to set the position where reading or writing will take place in stream. The new position is specified in an SMStreamPos data object pos. For Value position, use the Value obtained by an earlier call to SMStreamGetPos. If successful, SMStreamSetPos returns a zero. Otherwise, the return Value is non zero.
______________________________________
SMSize SMStreamTell (SMStream stream);
______________________________________
Use SMStreamTell to obtain the current position of stream. The position is expressed as a byte offset from the beginning of the file. If successful, SMStreamTell returns a SMSize containing the number of bytes that the current position of stream is offset from the beginning of the Value. In case of error, SMStreamTell returns -1.
H. CPL Accessors
______________________________________
SMCPLAccessor SMNewCPLAccessor (SMAccessorKind aKind,
SMContSpec contSpec,
SMPoolName poolName,
SMLayerName layerName);
______________________________________
Creates and returns a CPL Accessor, of the given kind, that defines the Container, Pool and Layer context. All parameters other than Accessor kind are optional. The CPL Accessor kind parameter specifies whether or not the Accessor is a ReadWrite, ReadWrite, or Transient, Accessor to the contents of the Layer. A Transient Accessor cannot perform any Container, Pool or Layer manipulation, but can be repositioned to other Pools and Layers from the currently designated position. The Container is implicitly opened if necessary during this call.
Each Layer can have many Reader-Processes but it can only have one Process modifying a Layer at a time. Therefore, a Process cannot acquire write-permission to the Layer if there is another Process reading or modifying a Layer. Each CPL Accessor maintains its current permission to the Layer. The permission is called the Layer Mode. There are three Layer Modes--Read/Write, Read-Only and None. Read/Write Mode gives the Process which owns the CPL Accessor exclusive right to modify the Layer. Read-Only Mode allows a Process to read from the Layer and at the same time blocking out any attempt from another Process to acquire a Read/Write Mode. None Mode is used for transient repositioning of the Layer Access. For example, the user may want to move a CPL Accessor within a Layer hierarchy with no intention to look at any Blops until the desired Layer is found.
CPL Accessors of the same Process can share the same Layer Mode. For example, a clone of a CPL Accessor has the same Layer Mode as the original. If the original CPL Accessor has Read/Write Mode on a Layer, the clone will have Read- and Write-permission to the Layer too.
______________________________________
void SMDisposeCPLAccessor (SMCPLAccessor accessor);
______________________________________
Disposes of the specified CPL Accessor. If any BPV Accessors are outstanding an error occurs. If this is the last Accessor designating the Container it is implicitly closed.
______________________________________
void SMTransformCPLAccessor (SMCPLAccessor accessor,
SMAccessorKind AKind);
______________________________________
Transforms a CPL Accessor from one kind to another. If transforming from ReadOnly to ReadWrite the CPL Accessor must be the only Accessor designating the Layer. An exception is raised if attempting to reposition a CPL Accessor that has outstanding BPV Accessors.
______________________________________
void SMRetargetCPLAccessor (SMCPLAccessor accessor,
SMContSpec contSpec,
SMBoolean samePool Name,
SMBoolean sameLayerName);
______________________________________
Re-targets the given CPL Accessor, to a potentially different Container, based on the given Container Specification. The given Accessor is retargeted. An exception is raised if attempting to reposition a CPL Accessor that has outstanding BPV Accessors. Since a CPL Accessor provides the context for the BPV Accessor, a CPL Accessor cannot be repositioned if there is a BPV Accessor outstanding. All the BPV Accessors must be `released` first. If samePoolName or sameLayerName are kSMBTrue then the Accessor returned will attempt to designate the same Pool as the original and the same Layer as the original, both by name.
______________________________________
SMPositionResult SMPositionCPLAccessor (SMCPLAccessor accessor,
SMPoolName poolName,
SMPositionCodePoolPosition,
SMLayerName layerName,
SMPositionCode layerPosition);
______________________________________
Repositions a given CPL Accessor within a Container returning the status of the positioning. The return Value, if positive, indicates how the new location of the Accessor is related to the previous location; and if negative, it indicates how far SMPositionCPLAccessor was able to proceed with this process before an error was detected. On failure, the Accessor is left pointing at the closest Pool and Layer it could find to the ones requested that still satisfies the given parameters. Therefore, if the specified LayerName does not exist, the CPL Accessor is positioned to the specified Pool (not to a Layer in the specified Pool). An exception is raised if attempting to reposition a CPL Accessor that has outstanding BPV Accessors. Pools are implicitly opened and closed as necessary during the repositioning.
Layers and Pools are considered upside down graphs. Delta Pools are considered children of their Base Pool. The bottom Layer is the topmost Parent in a Layer hierarchy. From an undefined state positioning the Pool to kSMPFirstSib positions to the first Pool in the Container. Positioning a Layer to kSMPFirstAbove or kSMPFirstBelow from an undefined state positions to the bottom Layer of the Pool.
______________________________________
Valid Position Code
Meaning
______________________________________
Parameter: poolPosition
kSMPUndefined set Pool to undefined
kSMPSame stay on same Pool
kSMPFirstSib goto first Pool in same Container
kSMPLastSib goto last Pool in same Container
kSMPNextSib goto next Pool in same Container
kSMPPrevSib goto previous Pool in same Container
kSMPFirstBelow goto Base Pool (same as
kSMPLastBelow)
kSMPLastBelow goto Base Pool (same as
kSMPFirstBelow)
kSMPFirstAbove goto first connected Delta Pool
kSMPLastAbove goto last connected Delta Pool
kSMPMWrap allow wrapping within a level
Parameter: layerPosition
Valid Position Code
Meaning
kSMPUndefined set Layer to undefined
kSMPSame stay on same Layer
kSMPFirstSib goto first Layer at same level
kSMPLastSib goto last Layer at same level
kSMPNextSib goto next Layer at same level
kSMPPrevSib goto previous Layer at same level
kSMPFirstBelow goto first Base Layer
kSMPLastBelow goto last Base Layer
kSMPFirstAbove goto first Derived Layer
kSMPLastAbove goto last Derived Layer
kSMPMWrap allow wrapping within a level
SMCount SMCountCPLAccessor (SMCPLAccessor accessor,
SMPositionCode poolPosition,
SMPositionCode layerPosition);
______________________________________
Returns the number of times that the given CPL Accessor could be repositioned according to the parameters before stopping. The wrap position code modifier is not allowed for any given position code. The parameters are interpreted the same as in the SMPositionCPLAccessor routine. With this routine it is easy to determine the number of Pools in a Container, the number of Layers in a hierarchy, etc.
______________________________________
SMCPLAccessor SMCloneCPLAccessor (SMCPLAccessor original);
______________________________________
Duplicates the specified CPL Accessor and returns the duplicate. Only ReadOnly and Transient Accessors can be cloned since two ReadWrite Accessors are not allowed to be targeting the same Layer. If the Layer is currently undefined by the Accessor a ReadWrite Accessor can be cloned.
______________________________________
void SMGetCPLAccessorInfo (SMCPLAccessor accessor,
SMCPLReadOnlyInfo *roInfo,
SMCPLReadWriteInfo *rwInfo);
______________________________________
Returns the details of what the given CPL Accessor designates. kSMUndefined may be passed as arguments to parameters that are not wanted. kSMUndefined will be returned for elements that are undefined. theFile parameter is only defined when the Container is a File Container, for all other Containers kSMUndefined will always be returned. Passing kSMUndefined for poolName while still passing maxPoolNameSize will set the parameter to the length of the Pool Name. The basePool parameter will be filled in with a newly created Accessor, of basePoolAKind, if not kSMUndefined and the Pool currently designated is a Separable or Delta Pool. The max info size parameters will return the current size of the corresponding info if kSMUndefined is given for the info parameter. The Layer names Iterator is a snapshot of all of the names currently set for the designated Layer. Changing items within the Iterator has no effect on the Layer.
______________________________________
void SMSetCPLAccessorInfo (SMCPLAccessor accessor,
SMCPLReadWriteInfo *rwInfo);
______________________________________
Sets the details of what the given CPL Accessor designates. kSMUndefined may be passed for poolName if the name is not to be changed. In rwInfo, `consistent` designates the Layer specified by the given Accessor to be consistent or not.
Every Layer has a flag associated with it which indicates if the Layer contains a consistent view of the Blops in the Pool. Since the Storage Manager has no knowledge of the interpretation of data it manages, it assumes that all operations it is asked to do leave the Layers in a consistent state. However, SMSetCPLAccessorInfo allows the application to specify that a Layer is in a consistent or inconsistent State. In addition, since the SMMoveChangesDown routine frequently makes a Layer inconsistent (by copying down a subset of related changes), it has an argument which the caller can supply to indicate whether the resulting Layer is consistent. The main use of this feature is to limit the types of operations which can be performed on a Layer. It is an error for an application to create a Layer which is derived from an inconsistent Layer (although existing Layers which are above it are still OK); and it is an error for an application to SMMoveAllChangesDown from an inconsistent Layer. Thus if an application creates an inconsistent Layer in a shared disk file, then no other application will be able to build a Layer above it (and see its contents) until it is marked as consistent.
|
