Method of managing a data structure for concurrent serial and parallel revision of a work

• US 5,870,764 A
• Filed: 05/12/1993
• Issued: 02/09/1999
• Est. Priority Date: 05/12/1993
• Status: Expired due to Term

• Current Assignee: 807735 Ontario Limited, Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Celik, Tantek I., Austin, David J., Szymanski, Steven J., Harris, Jed, Lo, Shui Wing
• Primary Examiner(s): Von Buhr, Maria N.
• Application Number:
  US08/060,809
• Time in Patent Office: 2,099 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 395/155-161, 395/600, 395/619, 707/203, 707/202, 707/100, 707/101, 707/511, 707/513, 707/514, 707/515
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99954 Version management

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

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.