Concurrent utilization of a document by multiple threads

Patent metadata

Field	Value
Publication number	US-9652440-B2
Application number	US-78880410-A
Country	US
Kind code	B2
Filing date	May 27, 2010
Priority date	May 27, 2010
Publication date	May 16, 2017
Grant date	May 16, 2017

Abstract

A computing system concurrently executes a builder thread and a reader thread. The builder thread modifies a document by modifying an active representation of the document. The reader thread perform operations regarding the document using a non-active representation of the document. The active representation of the document and the non-active representation of the document are stored in a memory of the computing system. The active representation of the document and the non-active representation of the document do not include different copies in the memory of the same data. When reading data in the non-active representation of the document, logical consistency is ensured without locking any data in the non-active representation of the document.

First claim

I claim:

1. A method comprising:
providing a non-active representation of a document, the non-active representation of the document comprising a piece descriptor and a piece descriptor index;
executing, by a computing system, a builder thread to input or modify an element in the document, the builder thread creating a new piece descriptor for indicating a position where the element belongs in the document, the new piece descriptor and the piece descriptor index forming an active representation of the document, wherein the active representation of the document and the non-active representation of the document refer to the same data stored in memory;
providing access to the non-active representation for use by a reader thread while the builder thread modifies the active representation of the document;
after the builder thread modifies the document, updating the non-active representation of the document with the active representation of the document, such that modifications to the element at the position indicated by the new piece descriptor replaces a corresponding element at the position indicated by the piece descriptor in the non-active representation of the document; and
after updating the non-active representation, providing access to the non-active representation of the document including the modifications to the element.

2. The method of claim 1 , wherein the operation performed by the reader thread does not modify the document.

3. The method of claim 2 ,
wherein the builder thread performs an operation that creates a new representation of the document each time the builder thread receives input to modify the document; and
wherein after the builder thread completes the operation, the new representation of the document is available for use by the reader thread.

4. The method of claim 1 , further comprising executing, by the computing system, another reader thread concurrently with the reader thread and the builder thread, the other reader thread performing another operation regarding the document using the non-active representation of the document.

5. The method of claim 1 , further comprising: executing, by the computing system, an application that enables a user to interact with the document, the application waking the builder thread and the reader thread.

6. The method of claim 5 ,
wherein the application is a word processing application and the document is a word processor document; and
wherein the operation performed by the reader thread is a spell check operation.

7. The method of claim 1 ,
wherein the document is internally represented as a document tree, the document tree being a hierarchy of document elements;
wherein the active representation of the document includes a real element array that contains elements that represent each document element in the document tree;
wherein the non-active representation of the document includes the real element array;
wherein the active representation of the document and the non-active representation of the document do not include different copies in the memory of the same elements in the real element array.

8. The method of claim 7 , wherein the builder thread removes a given element from the active representation of the document while concurrently the reader thread reads the given element from the non-active representation of the document, the given element representing the same document element in the document tree.

9. The method of claim 7 ,
wherein the active representation of the document includes an active version of an index tree and an active version of a piece descriptor table, the piece descriptor table comprising a set of piece descriptors, each of the piece descriptors identifying a piece of the real element array, the index tree comprising a hierarchy of index nodes, each of the index nodes indicating one of the piece descriptors;
wherein the non-active representation of the document includes a non-active version of the index tree and a non-active version of the piece descriptor table;
wherein for each index node in the index tree, elements associated with index nodes in a left subtree of the index node have virtual offsets that are less than virtual offsets of elements associated with the index node and elements associated with index nodes in a right subtree of the index node have virtual offsets that are greater than the virtual offsets of the elements associated with the index node, the virtual offsets being offsets from a beginning of a virtual element array, the virtual element array being a one-dimension representation of the document tree;
wherein the active representation of the document and the non-active representation of the document do not have in the memory different copies of the same piece descriptors in the piece descriptor table or the same index nodes in the index tree.

10. The method of claim 9 , wherein data in the index nodes in the non-active version of the index tree and data in the non-active version of the piece descriptor table do not change.

11. The method of claim 9 ,
wherein to modify the document to include an additional document element, the builder thread performs an element insertion operation that generates the active representation of the document by inserting one or more new elements into the real element array, adding a new piece descriptor to the piece descriptor table, and adding one or more new index nodes to the index tree, the one or more new elements representing the additional document element;
wherein after the builder thread completes the element insertion operation, the active representation of the document becomes available for use by the reader thread.

12. The method of claim 1 , wherein parts of the document within the active representation of the document and the non-active representation of the document that are the same refer to a same copy of the data.

13. A computing system comprising:
a processing system comprising a plurality of processing units; and
a memory that comprises computer executable instructions that, when executed by the processing system, cause the computing system to:
provide a non-active representation of a document, the non-active representation of the document comprising a piece descriptor and a piece descriptor index;
execute a builder thread that modifies an element in a document by modifying an active representation of the document, the builder thread creating a new piece descriptor to indicate a position where the element belongs in the document, the new piece descriptor and the piece descriptor index forming an active representation of the document, wherein the active representation of the document and the non-active representation of the document refer to the same data stored in memory;
provide access to the non-active representation for use by a reader thread while the builder thread modifies the active representation of the document;
update the non-active representation of the document with the active representation of the document, such that modifications to the element at the position indicated by the new piece descriptor replaces a corresponding element at the position indicated by the piece descriptor in the non-active representation of the document; and
after updating the non-active representation, providing access to the non-active representation of the document including the modifications to the element.

14. The computing system of claim 13 ,
wherein the builder thread performs an operation that generates a new active representation of the document each time the builder thread receives input to modify the document; and
wherein after the builder thread comp

Assignees

• Parker Charles W
• Microsoft Technology Licensing Llc

Inventors

• Parker Charles W

Classifications

• G06F16/322 Primary

  Trees · CPC title

• G06Q10/101

  Collaborative creation, e.g. joint development of products or services · CPC title

• G06F40/14 Primary

  Tree-structured documents (parsing G06F40/205; validation G06F40/226) · CPC title

• G06F16/2308

  Concurrency control (transaction processing G06F9/466) · CPC title

• G06F40/197

  Version control (for software G06F8/71) · CPC title