US6016489A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for constructing stable iterators in a shared data collection
Assignee: Oracle America Inc
•
Filing: 1997-12-18
•
Granted: 2000-01-18
•
Expires: 2017-12-18
Abstract
Abstract In a distributed object system, a stable object iterator provides a list of all persistent objects within a collection of objects. A plurality of iterators are supported in another aspect of the invention. An iterator associates a label with each persistent object in a collection of stable objects. The label indicates whether the associated object was added to or deleted from the collection before or after the inception of an iterator. Multiple persistent iterators are supported by providing an indication of which iterators each persistent object is, or is not, "visible" to. Should an element of the persistent object collection be created after one or more iterators is created, that element is "invisible" to those iterators. Objects that exist when one or more iterators are created remain "visible" to those iterators, even if the object is deleted from the collection while those iterators still exist. The system maintains an indication of all extent iterators and of maximum and minimum iterator identifiers which respectively correspond to the most recently created and least recently created iterators.
Inventors
- 👤 Ken M. Cavanaugh
- 👤 Christian J. Callsen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 06:10
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/465; G06F9/44; G06F9/448; G06F9/4488; G06F9/4493; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99938; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
118 words
Apparatus for making stable an iterator which is created to iterate over a collection of elements that is stored in a memory, said collection being shared by a plurality of threads which add such elements and mark such elements in the collection for deletion, the apparatus comprising: a mechanism which associates a label with each element that is added to the collection after the iterator is created wherein the label indicates that the added element is not deleted and invisible to the iterator; and a mechanism for deleting one such element from the collection when the element is marked for deletion and the label for the marked element indicates that the marked element is invisible to the iterator.
Claim 2
Dependent Claim
118 words
Apparatus for making stable an iterator which is created to iterate over a collection of elements that is stored in a memory, said collection being shared by a plurality of threads which add such elements and mark such elements in the collection for deletion, the apparatus comprising: a mechanism which associates a label with each element that is added to the collection after the iterator is created wherein the label indicates that the added element is not deleted and invisible to the iterator; and a mechanism for deleting one such element from the collection when the element is marked for deletion and the label for the marked element indicates that the marked element is invisible to the iterator.
Claim 3
Dependent Claim
25 words
Apparatus according to claim 1 wherein the label comprises a set of iterator identifiers (IDs) associated with the iterator to which the element is visible.
Claim 4
Dependent Claim
18 words
Apparatus according to claim 2 wherein the set of iterator IDs is associated with a range of iterators.
Claim 5
Dependent Claim
28 words
Apparatus according to claim 1 wherein the label comprises a flag which indicates whether the associated element is marked for deletion and is set by one such thread.
Claim 6
Dependent Claim
20 words
Apparatus according to claim 1 wherein the iterator only returns elements of the collection which are visible to the iterator.
Claim 7
Dependent Claim
67 words
Apparatus according to claim 1 wherein the apparatus makes stable a plurality of iterators which are created to iterate over the collection of elements and wherein a label association mechanism associates label with each element that is added to the collection after the plurality of iterators is created, wherein the label indicates the added element is not marked for deletion and invisible to the plurality of iterators.
Claim 8
Dependent Claim
73 words
Apparatus according to claim 1 wherein the apparatus makes stable a plurality of iterators which are created to iterate over the collection of elements wherein said iterators may be deleted and wherein the mechanism for deleting one such element from the collection deletes elements that are marked for deletion and for which the label for the marked element indicates that the marked element is visible to no iterator which has not been deleted.
Claim 9
Dependent Claim
11 words
Apparatus according to claim 1 further comprising an iterator deleting mechanism.
Claim 10
Dependent Claim
26 words
Apparatus according to claim 8 further comprising a list of all iterators created and a mechanism for indicating in the list which iterators have been deleted.
Claim 11
Dependent Claim
54 words
Apparatus according to claim 9 wherein said mechanism for deleting an iterator further comprises a mechanism for deleting all elements from the collection that are marked for deletion and for which the label for the marked element indicates that the marked element will be visible to no valid iterator after the iterator is destroyed.
Claim 12
Dependent Claim
45 words
Apparatus according to claim 1 wherein the apparatus makes stable a plurality of iterators which are created to iterate over the collection of elements and wherein the apparatus further comprises an iterator identifier which assigns a unique identifier to each of the plurality of iterators.
Claim 13
Dependent Claim
113 words
A stable iterator, comprising: an iterator created to iterate over a collection of elements that is stored in memory, threads which share said collection of elements and add such elements to the collection and mark such elements in the collection for deletion, a mechanism which associates a label with each element that is added to the collection after the iterator is created wherein the label indicates that the added element is not deleted and invisible to the iterator; and a mechanism for deleting one such element from the collection when the element is marked for deletion and the label for the marked element indicates that the marked element is invisible to the iterator.
Claim 14
Dependent Claim
113 words
A stable iterator, comprising: an iterator created to iterate over a collection of elements that is stored in memory, threads which share said collection of elements and add such elements to the collection and mark such elements in the collection for deletion, a mechanism which associates a label with each element that is added to the collection after the iterator is created wherein the label indicates that the added element is not deleted and invisible to the iterator; and a mechanism for deleting one such element from the collection when the element is marked for deletion and the label for the marked element indicates that the marked element is invisible to the iterator.
Claim 15
Dependent Claim
142 words
Apparatus for making stable a plurality of iterators which are created to iterate over a collection of objects in a multi-threaded distributed object system having a plurality of threads which add elements and mark elements for deletion, the apparatus comprising: a mechanism which associates a label with each object that is added to the collection after a first of the plurality of iterators is created and before a second of the plurality of iterators is created, wherein the label indicates the added object is not deleted, is invisible to the first plurality of iterators and is visible to the second plurality of iterators; and a mechanism for deleting an object from the collection when the object is marked for deletion and the label for the marked object indicates that the marked object is invisible to all iterators which have not been deleted.
Claim 16
Dependent Claim
142 words
Apparatus for making stable a plurality of iterators which are created to iterate over a collection of objects in a multi-threaded distributed object system having a plurality of threads which add elements and mark elements for deletion, the apparatus comprising: a mechanism which associates a label with each object that is added to the collection after a first of the plurality of iterators is created and before a second of the plurality of iterators is created, wherein the label indicates the added object is not deleted, is invisible to the first plurality of iterators and is visible to the second plurality of iterators; and a mechanism for deleting an object from the collection when the object is marked for deletion and the label for the marked object indicates that the marked object is invisible to all iterators which have not been deleted.
Claim 17
Dependent Claim
39 words
Apparatus of claim 13 wherein said multi-threaded distributed object system further comprises: a marshaling mechanism encoding a persistent object attribute value into a marshal buffer; and an unmarshaling mechanism decoding the persistent object attribute value from the marshal buffer.
Claim 18
Dependent Claim
28 words
Apparatus of claim 14 wherein said distributed object system is a common object request broker architecture (CORBA) system and said marshaling and unmarshaling mechanisms conform to CORBA specifications.
Claim 19
Independent Claim
118 words
A method for making stable an iterator which is created to iterate over a collection of elements that is stored in a memory and is shared by a plurality of threads which add such elements and mark such elements for deletion in the collection, the method comprising the steps of: (a) creating a label associated with each element that is added to the collection after the iterator is created wherein the label indicates that the added element is not deleted and invisible to the iterator; and (b) deleting one such element from the collection when the element is marked for deletion and the label for the marked element indicates that the marked element is invisible to the iterator.
Claim 20
Independent Claim
118 words
A method for making stable an iterator which is created to iterate over a collection of elements that is stored in a memory and is shared by a plurality of threads which add such elements and mark such elements for deletion in the collection, the method comprising the steps of: (a) creating a label associated with each element that is added to the collection after the iterator is created wherein the label indicates that the added element is not deleted and invisible to the iterator; and (b) deleting one such element from the collection when the element is marked for deletion and the label for the marked element indicates that the marked element is invisible to the iterator.
Claim 21
Dependent Claim
26 words
A method according to claim 16 wherein the label comprises a set of iterator identifiers (IDs) associated with the iterator to which the element is visible.
Claim 22
Dependent Claim
19 words
A method according to claim 17 wherein the set of iterator IDs is associated with a range of iterators.
Claim 23
Dependent Claim
22 words
A method according to claim 16 wherein the label comprises a flag which indicates whether the associated element is marked for deletion.
Claim 24
Dependent Claim
20 words
A method according to claim 17 wherein the iterator returns elements of the collection which are visible to the iterator.
Claim 25
Dependent Claim
66 words
A method according to claim 16 wherein the method makes stable a plurality of iterators which are created to iterate over the collection of elements and wherein a label is associated with each element that is added to the collection after the plurality of iterators is created, wherein the label indicates the added element is not marked for deletion and invisible to the plurality of iterators.
Claim 26
Dependent Claim
69 words
A method according to claim 16 wherein the method makes stable a plurality of iterators which are created to iterate over the collection of elements wherein said iterators may be deleted and wherein those elements are deleted from the collection that are marked for deletion and for which the label for the marked element indicates that the marked element is invisible to all iterators that have not been deleted.
Claim 27
Dependent Claim
49 words
A method according to claim 16 wherein a second iterator is created to iterate over the collection of elements and the method further comprises the step of: (c) associating with all elements labels indicating that the elements are not marked for deletion and are visible to the second iterator.
Claim 28
Dependent Claim
15 words
A method according to claim 16 further comprising the step of: (d) deleting an iterator.
Claim 29
Dependent Claim
33 words
A method according to claim 24 further comprising the step of: (e) creating a list of all iterators created whereby said list indicates which iterators have been deleted and are no longer valid.
Claim 30
Dependent Claim
49 words
A method according to claim 25 further comprising the step of: (f) deleting all elements from the collection that are marked for deletion and for which the label for the marked element indicates that the marked element will be visible to no valid iterator after the iterator is destroyed.
Claim 31
Dependent Claim
39 words
A method according to claim 16 whereby a plurality of iterators which are created to iterate over the collection of elements are made stable and an iterator identifier assigns a unique identifier to each of the plurality of iterators.
Claim 32
Independent Claim
145 words
A method for making stable a plurality of iterators which are created to iterate over a collection of objects in a multi-threaded distributed object system having a plurality of threads which add such objects and mark such objects in the collection for deletion, the method comprising the steps of: (a) creating a label associated with each object that is added to the collection after a first of the plurality of iterators is created and before a second of the plurality of iterators is created, wherein the label indicates the added object is not deleted, is invisible to the first iterator and is visible to the second iterator; and (b) deleting an object from the collection when the object is marked for deletion and a label for the marked object indicates that the marked object is invisible to any valid iterator in the plurality of iterators.
Claim 33
Independent Claim
145 words
A method for making stable a plurality of iterators which are created to iterate over a collection of objects in a multi-threaded distributed object system having a plurality of threads which add such objects and mark such objects in the collection for deletion, the method comprising the steps of: (a) creating a label associated with each object that is added to the collection after a first of the plurality of iterators is created and before a second of the plurality of iterators is created, wherein the label indicates the added object is not deleted, is invisible to the first iterator and is visible to the second iterator; and (b) deleting an object from the collection when the object is marked for deletion and a label for the marked object indicates that the marked object is invisible to any valid iterator in the plurality of iterators.
Claim 34
Dependent Claim
76 words
A method according to claim 28 wherein said distributed object system is a common object request broker architecture (CORBA) system and said method further comprises the steps of: (c) encoding a persistent object attribute value into a marshal buffer according to CORBA specification to thereby provide an encoded persistent object attribute value; and (d) decoding the persistent object attribute value from the marshal buffer according to CORBA specifications to thereby provide a decoded persistent attribute value.
Claim 35
Dependent Claim
135 words
A computer program product for constructing a stable iterator to iterate over a collection of elements stored in a memory and shared by a plurality of threads which add such elements and mark such elements for deletion in the collection, the computer program product comprising a computer usable medium having computer readable program code thereon, including: program code for constructing a mechanism which associates a label with each element that is added to the collection after the iterator is created wherein the label indicates that the added element is not deleted and invisible to the iterator; and program code for constructing a mechanism for deleting one such element from the collection when the element is marked for deletion and the label for the marked element indicates that the marked element is invisible to the iterator.
Claim 36
Dependent Claim
135 words
A computer program product for constructing a stable iterator to iterate over a collection of elements stored in a memory and shared by a plurality of threads which add such elements and mark such elements for deletion in the collection, the computer program product comprising a computer usable medium having computer readable program code thereon, including: program code for constructing a mechanism which associates a label with each element that is added to the collection after the iterator is created wherein the label indicates that the added element is not deleted and invisible to the iterator; and program code for constructing a mechanism for deleting one such element from the collection when the element is marked for deletion and the label for the marked element indicates that the marked element is invisible to the iterator.
Claim 37
Dependent Claim
34 words
A computer program product according to claim 30 further comprising computer program code which constructs a list of all iterators created and a mechanism for indicating in the list which iterators have been deleted.
Claim 38
Dependent Claim
66 words
A computer program product according to 31 further comprising computer program code which constructs said mechanism for deleting an iterator such that said mechanism further comprises: a mechanism for deleting all elements from the collection that are marked for deletion and for which the label for the marked element indicates that the marked element will be visible to no valid iterator after the iterator is destroyed.
Claim 39
Dependent Claim
66 words
A computer program product according to 31 further comprising computer program code which constructs said mechanism for deleting an iterator such that said mechanism further comprises: a mechanism for deleting all elements from the collection that are marked for deletion and for which the label for the marked element indicates that the marked element will be visible to no valid iterator after the iterator is destroyed.
Claim 40
Dependent Claim
161 words
A computer program product for making stable a plurality of iterators which are created to iterate over a collection of objects in a multi-threaded distributed object system having a plurality of threads which add elements and mark elements for deletion, the computer program product comprising a computer usable medium having computer readable program code written thereon, including: computer program code for constructing a mechanism which associates a label with each object that is added to the collection after a first of the plurality of iterators is created and before a second of the plurality of iterators is created, wherein the label indicates the added object is not deleted, is invisible to the first iterator and is visible to the second iterator; and computer program code for constructing a mechanism for deleting an object from the collection when the object is marked for deletion and a label for the marked object indicates that the marked object is invisible to a valid iterator.
Claim 41
Dependent Claim
161 words
A computer program product for making stable a plurality of iterators which are created to iterate over a collection of objects in a multi-threaded distributed object system having a plurality of threads which add elements and mark elements for deletion, the computer program product comprising a computer usable medium having computer readable program code written thereon, including: computer program code for constructing a mechanism which associates a label with each object that is added to the collection after a first of the plurality of iterators is created and before a second of the plurality of iterators is created, wherein the label indicates the added object is not deleted, is invisible to the first iterator and is visible to the second iterator; and computer program code for constructing a mechanism for deleting an object from the collection when the object is marked for deletion and a label for the marked object indicates that the marked object is invisible to a valid iterator.
References Cited (Backward Citations)
US4823310A
Cited
US5263160A
Cited
US5758342A
Cited
US5790848A
Cited
US5787447A
Cited
US5835906A
Cited
US5873116A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-17 | 2003-07-19 | 2004-01-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-17 | 2007-07-19 | 2008-01-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-17 | 2011-07-19 | 2012-01-18 | $7700.00 | Window Closed / Lapsed |