Patent US3280948A successfully refreshed from Google Patents.
US4751684A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Search apparatus
Assignee: Fujitsu Services Ltd
•
Filing: 1986-05-19
•
Granted: 1988-06-14
•
Expires: 2006-05-19
Abstract
Abstract Search apparatus is described for locating an item which satisfies a predetermined criterion e.g. an instruction ready for execution or a free block of data. The apparatus uses a tree structure where each terminal node represents one of the items and is set if that item satisfies the criterion. A non-terminal node is set if any of its subordinate nodes is set. In order to locate an item, a path is traced through the tree, starting at the root node and passing through a series of set nodes until a set terminal node is reached.
Inventors
- 👤 Nicholas P. Holt
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 08:13
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4494; Y; Y10; Y10S; Y10S707/00; Y10S707/99931
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
256 words
Search apparatus comprising: (a) means for maintaining a representation of a tree structure comprising a plurality of interconnected nodes including a root node and a plurality of terminal nodes, each node being set to a predetermined state if any one of its subordinate nodes is set in a predetermined state, and (b) means for following a path through the tree, starting from the root node and passing through a series of nodes all of which are set in their predetermined states until a terminal node in its predetermined state is reached, (c) wherein the means for maintaining the representation of the tree structure comprises a random-access memory having a plurality of individually addressable locations each of which holds a plurality of bits, each node of the tree other than the root node being represented by one of said bits, (d) wherein each location in the random-access memory contains b bits, and a node represented by bit y of locations x of the memory has b subordinate nodes represented by the b bits in location bx+y of the memory, (e) and wherein the means for following a path through the tree comprises an address register for addressing the random-access memory with an address x, to read out a word from location x of the memory, means for examining the word read out the memory to determine whether any of its bits is set and means operable in the event that bit y is set to replace the address x in the register by a new address bx+y.
Claim 2
Dependent Claim
256 words
Search apparatus comprising: (a) means for maintaining a representation of a tree structure comprising a plurality of interconnected nodes including a root node and a plurality of terminal nodes, each node being set to a predetermined state if any one of its subordinate nodes is set in a predetermined state, and (b) means for following a path through the tree, starting from the root node and passing through a series of nodes all of which are set in their predetermined states until a terminal node in its predetermined state is reached, (c) wherein the means for maintaining the representation of the tree structure comprises a random-access memory having a plurality of individually addressable locations each of which holds a plurality of bits, each node of the tree other than the root node being represented by one of said bits, (d) wherein each location in the random-access memory contains b bits, and a node represented by bit y of locations x of the memory has b subordinate nodes represented by the b bits in location bx+y of the memory, (e) and wherein the means for following a path through the tree comprises an address register for addressing the random-access memory with an address x, to read out a word from location x of the memory, means for examining the word read out the memory to determine whether any of its bits is set and means operable in the event that bit y is set to replace the address x in the register by a new address bx+y.
Claim 3
Dependent Claim
41 words
Search apparatus according to claim 1 wherein the means for examining the word read out of the memory comprises a priority encoder which produces a code indicating the bit position y of the first set bit, if any, in that word.
Claim 4
Dependent Claim
50 words
Search apparatus according to claim 1 including means for updating the representation of the tree structure, comprising means for dividing the contents bx+y of the address register by b to produce an address x and a remainder y, and for updating bit y of location x of the random-access memory.
Claim 5
Dependent Claim
74 words
Search apparatus according to claim 3 wherein the means for updating includes logic means for detecting a condition wherein either: (a) all the bits in the currently addressed location of the memory were originally unset and the updating means has just set one of them, or (b) all but one of the bits in the currently addressed location of the memory were originally unset and the updating means has just unset that one bit.
Claim 6
Independent Claim
279 words
A method of locating, in a collection of items, an item which satisfies a predetermined criterion, comprising the steps: (a) maintaining a representation of a tree structure comprising a plurality of interconnected nodes including a root node and a plurality of terninal nodes, each terminal node corresponding to one of said items, (b) setting each terminal node to a predetermined state if the corresponding item satisfies said criterion, (c) setting each node other than a terminal node to a predetermined state if any of its subordinate nodes is set in its predetermined state, and (d) following a path through the tree, starting from the root node and passing through a series of nodes all of which are set in their predetermined states until a terminal node in its predetermined state is reached, wherein the representation of the tree structure is maintained in a random-access memory having a plurality of individually addressable locations each of which holds a plurality of bits, each node of the tree other than the root node being represented by one of said bits, wherein each location of the random-access memory contains b bits and a node represented by bit y of location x of the memory has its b subordinate nodes represented by the b bits in location bx+y of the memory, and wherein the stepof following a path through the tree comprises the sub-steps: (i) addressing the random-access memory with an address x to read out a word from location x of the memory, and (ii) examining the work read out of the memory to determine whether any of its bits are set and, if bit y is set, forming a new address bx+y.
Claim 7
Independent Claim
279 words
A method of locating, in a collection of items, an item which satisfies a predetermined criterion, comprising the steps: (a) maintaining a representation of a tree structure comprising a plurality of interconnected nodes including a root node and a plurality of terninal nodes, each terminal node corresponding to one of said items, (b) setting each terminal node to a predetermined state if the corresponding item satisfies said criterion, (c) setting each node other than a terminal node to a predetermined state if any of its subordinate nodes is set in its predetermined state, and (d) following a path through the tree, starting from the root node and passing through a series of nodes all of which are set in their predetermined states until a terminal node in its predetermined state is reached, wherein the representation of the tree structure is maintained in a random-access memory having a plurality of individually addressable locations each of which holds a plurality of bits, each node of the tree other than the root node being represented by one of said bits, wherein each location of the random-access memory contains b bits and a node represented by bit y of location x of the memory has its b subordinate nodes represented by the b bits in location bx+y of the memory, and wherein the stepof following a path through the tree comprises the sub-steps: (i) addressing the random-access memory with an address x to read out a word from location x of the memory, and (ii) examining the work read out of the memory to determine whether any of its bits are set and, if bit y is set, forming a new address bx+y.
Claim 8
Dependent Claim
120 words
A method according to claim 5 inclduing the further steps: (a) dividing an address bx+y by b to produce a new address x and a remainder y (b) using the new address x and the remainder y to access bit y of location x of the memory, to update that bit, and (c) if either: (i) all the bits in location x of the memory were originally unset and one of them has just been set, or (ii) all but one of the bits in location x of the memory were originally unset and that one bit has just been unset, repeating steps (a) and d (b) above, using the new address x in place of the previous address bx+y.
References Cited (Backward Citations)
CA588601A
Cited
US3577141A
Cited
US4103349A
Cited
EP0111689A2
Cited
EP0124097A2
Cited
US4606002A
Cited
EP0148008A2
Cited
EP0170442A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1991-06-14 | 1991-12-14 | 1992-06-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-06-14 | 1995-12-14 | 1996-06-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-06-14 | 1999-12-14 | 2000-06-14 | $7700.00 | Window Closed / Lapsed |