Method for reducing the scope of the K node construction lock

• US 7,418,445 B1
• Filed: 07/20/2005
• Issued: 08/26/2008
• Est. Priority Date: 11/08/2004
• Status: Active Grant

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Claar, Jane Van Keuren, Mazzagatti, Jane Campbell, Rajcan, Steven L.
• Primary Examiner(s): Vital; Pierre M.
• Assistant Examiner(s): LIANG, VEI CHUNG
• Application Number:
  US11/185,627
• Time in Patent Office: 1,133 Days
• Field of Search: 707/102, 707/103.Z, 707/201, 711/168, 718/102, 718/106, 718/107, 718/109, 719/315, 706/46, 717/144
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for recording information in an interlocking trees datastore having a plurality of K paths includes receiving an input particle and building a new K node in accordance with the received input particle. A K node is locked in accordance with the building of the new K node to provide a locked node. The locked node can be the Case node of the new K node. The Case bi-directional link between the locked Case node and the new K node is completed while the locked Case node is locked. A pointer is added to the new K node to an asCase list of the locked Case node. The locked node is locked only while adding the pointer to the new K node to the asCase list of the locked Case node. The locked node can also be a Result node of the new K node.

Claims

1. A method executed at least in part on a computer for recording information in an interlocking trees datastore having a plurality of K paths, comprising:

receiving an input particle to provide a received input particle;

recording said received input particle into said interlocking trees datastore by building a new K node to record said received input particle in said interlocking trees datastore, said interlocking trees datastore comprising root nodes and non-root nodes organized into a plurality of connected K paths, wherein the new K node of the interlocking trees datastore comprises a first pointer comprising a Case pointer pointing to a previous node, a second pointer comprising a Result pointer pointing to an elemental root node, a third pointer comprising an asCase List pointer pointing to a list of the subcomponent nodes or end product nodes for which the new K node is the Case node and a fourth pointer comprising an asResult List pointer pointing to a list of subcomponent nodes or end product nodes for which the new K node is the Result node, the plurality of connected K paths of the interlocking trees datastore comprising a first K path of a first tree of the interlocking trees datastore, the first K path comprising a primary root node linked to a subcomponent node with a first Case link, the subcomponent node linked to an end product node with a second Case link, and a second K path of a second tree of the interlocking trees datastore comprising an elemental root node linked to the subcomponent node with a Result link, such that a pointer to the elemental root node comprises the result entry of the subcomponent node and an asResult list of the elemental root node is updated to include the subcomponent node; and

locking a K node in accordance with said building of said new K node to provide a locked node.

2. The method for recording information in an interlocking trees datastore of claim 1, wherein said locked node comprises a Case node of said new K node.

3. The method for recording information in an interlocking trees datastore of claim 2, further comprising completing a Case bi-directional link between said locked Case node and said new K node while said locked Case node is locked.

4. The method for recording information in an interlocking trees datastore of claim 3, further comprising adding a pointer to said new K node to an asCase list of said locked Case node.

5. The method for recording information in an interlocking trees datastore of claim 4, further comprising locking said locked node only while adding said pointer to the new K node to said asCase list of said locked Case node.

6. The method for recording information in an interlocking trees datastore of claim 1, wherein said locked node comprises a Result node of said new K node.

7. The method for recording information in an interlocking trees datastore of claim 6, further comprising adding a pointer to said new K node to an asResult list of said locked Result node while said Result node is locked.

8. The method for recording information in an interlocking trees datastore of claim 7, further comprising locking said locked Result node only while adding said pointer to the new K node to said asResult list of said locked Result node.

9. The method for recording information in an interlocking trees datastore of claim 1, further comprising associating a memory location of a Case node and a memory location of a Result node with said new K node.

10. The method for recording information in an interlocking trees datastore of claim 9, further comprising locking said locked node after said associating of said memory locations with said new K node.

11. The method for recording information in an interlocking trees datastore of claim 10, wherein said locked node is said Case node further comprising adding said new K node to the asCase list of said locked Case node while said locked Case node is locked.

12. The method for recording information in an interlocking trees datastore of claim 11, further comprising:

locking said Result node after locking said locked Case node; and

adding said new K node to the asResult list of said locked Result node while said locked Result node is locked.

13. The method for recording information in an interlocking trees datastore of claim 11, further comprising:

locking said Result node before locking said Case node; and

adding said new K node to the asResult list of said locked Result node while said locked Result node is locked.

14. The method for recording information in an interlocking trees datastore of claim 11, further comprising:

locking said Result node while said Case node is locked; and

adding said new K node to the asCase list of said locked node while said Case node is locked.

15. The method for recording information in an interlocking trees datastore of claim 1, wherein said new K node has a new node count further comprising initializing said new node count.

16. The method for recording information in an interlocking trees datastore of claim 1, further comprising building said new K node in accordance with a determination that a new sequence has been encountered.

17. A computing system having a programmable processor and an attached medium capable of storing encoded data for recording information in an interlocking trees datastore having a plurality of K paths, the computing system comprising:

a received input particle stored within the computing system;

a new K node built in accordance with said received input particle, said new K node recording said received input particle in said interlocking trees datastore; and

a locked node wherein said locked node is locked in accordance with said building of said new K node;

wherein the interlocking trees datastore comprising root nodes and non-root nodes using digitally encoded data stored within the attached storage medium being organized into a plurality of trees comprising connected K paths;

the new K node of the interlocking trees datastore comprises;

a first pointer comprising a Case pointer pointing to a previous node;

a second pointer comprising a Result pointer pointing to an elemental root node;

a third pointer comprising an asCase List pointer pointing to a list of the subcomponent nodes or end product nodes for which the new K node is the Case node; and

a forth pointer comprising an asResultList pointer pointing to a list of subcomponent nodes or end product nodes for which the new K node is the Result node; and

the plurality of connected K paths of the interlocking trees datastore having a plurality of K paths comprises;

a first K path of a first tree of the interlocking trees datastore, the first K path comprising a primary root node linked to a subcomponent node with a first Case link, the subcomponent node linked to an end product node with a second Case link; and

a second K path of a second tree of the interlocking trees datastore comprising an elemental root node linked to the subcomponent node with a Result link, such that a pointer to the elemental root node comprises the result entry of the subcomponent node and an asResult list of the elemental root node is updated to include the subcomponent node.

18. The computing system for recording information in an interlocking trees datastore of claim 17, wherein the attached storage medium comprises random access memory coupled to the programmable processor.

19. The computing system for recording information in an interlocking trees datastore of claim 17, further comprising a Case bi-directional link between said locked Case node and said new K node wherein said Case bi-directional link is completed while said locked Case node is locked and said locked node comprises the Case node of said new K node.

20. The computing system for recording information in an interlocking trees datastore of claim 19, further comprising a pointer to said new K node added to an asCase list of said locked Case node.

21. The computing system for recording information in an interlocking trees datastore of claim 20, wherein said locked node is locked only while adding said pointer to the new K node to said asCase list of said locked Case node.

22. The computing system for recording information in an interlocking trees datastore of claim 17, wherein said locked node comprises a Result node of said new K node.

23. The computing system for recording information in an interlocking trees datastore of claim 22, further comprising a pointer to said new K node added to an asResult list of said locked Result node while said Result node is locked.

24. The computing system for recording information in an interlocking trees datastore of claim 23, wherein said locked Result node is locked only while adding said pointer to said new K node to said asResult list of said locked Result node.

25. The computing system for recording information in an interlocking trees datastore of claim 17, further comprising a memory location of a Case node and a memory location of a Result node associated with said new K node.

26. The computing system for recording information in an interlocking trees datastore of claim 25, wherein said locked node is locked after said associating of said memory locations with said new K node.

27. The computing system for recording information in an interlocking trees datastore of claim 26, wherein said locked node is said Case node and said new K node is added to the asCase list of said locked Case node while said locked Case node is locked.

28. The computing system for recording information in an interlocking trees datastore of claim 27, where said Result node is locked after locking said locked Case node and said new K node is added to the asResult list of said locked Result node while said locked Result node is locked.

29. The computing system for recording information in an interlocking trees datastore of claim 27, wherein said Result node is locked before locking said Case node and said new K node is added to the asResult list of said locked Result node while said locked Result node is locked.

30. The computing system for recording information in an interlocking trees datastore of claim 27, wherein said Result node is locked while said Case node is locked and said new K node is added to the asCase list of said locked node while said Case node is locked.

31. The computing system for recording information in an interlocking trees datastore of claim 17, wherein said new K node has a new node count and said new node count is initialized.

32. The computing system for recording information in an interlocking trees datastore of claim 17, wherein said new K node is built in accordance with a determination that a new sequence has been encountered.