Patent US5873078A successfully refreshed from Google Patents.
US5873078A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Radix tree search logic
Assignee: Avaya Inc
•
Filing: 1996-07-19
•
Granted: 1999-02-16
•
Expires: 2016-07-19
Abstract
Abstract In a search method for a radix search tree, a logic circuit for computing the actual offset of an entry in a node in a tree. The logic circuit accepts a pointer to a node in the tree, along with an associated bit mask indicating which entries are present in the node. The logic circuit further receives an entry value, the offset of which from the beginning of the node is to be computed by the logic circuit. The logic circuit utilizes Boolean AND gates to mask off higher order bits in the bit mask above the bit position corresponding to the entry value received by the logic circuit. The lower order bits in the bit mask, up to but not including the bit position corresponding to the entry value, are added together to determine the number of entries that exist at a lower offset in the node than the entry indicated by the entry value. The logic circuit combines the pointer received with the sum computed to calculate the offset memory address at which the entry is located in the node.
Inventors
- 👤 Richard L. Angle
- 👤 Edward S. Harriman, Jr.
- 👤 Geoffrey B. Ladwig
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 12:15
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/31; G06F16/316; G06F16/322; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
127 words
A computer-implemented method for calculating a memory address of an entry in a node in a tree data structure representing a sparse table in a memory of a computer system, the node having a plurality of entries, comprising: a) reading an existence map associated with the node, the existence map indicating which of the plurality of entries exist in the node; b) receiving an entry number; c) producing a bit mask given the entry number; d) masking the existence map with the bit mask to produce a masked existence map; e) calculating an offset for the entry given the masked existence map; and f) adding the offset for the entry to a pointer for the node to yield the memory address of the entry in the node.
Claim 2
Dependent Claim
127 words
A computer-implemented method for calculating a memory address of an entry in a node in a tree data structure representing a sparse table in a memory of a computer system, the node having a plurality of entries, comprising: a) reading an existence map associated with the node, the existence map indicating which of the plurality of entries exist in the node; b) receiving an entry number; c) producing a bit mask given the entry number; d) masking the existence map with the bit mask to produce a masked existence map; e) calculating an offset for the entry given the masked existence map; and f) adding the offset for the entry to a pointer for the node to yield the memory address of the entry in the node.
Claim 3
Dependent Claim
55 words
The computer implemented method of claim 1, wherein calculating a memory address of an entry in a node in a tree data structure in a memory of a computer system comprises calculating a memory address of an entry in a node in a radix search tree data structure in a memory of a computer system.
Claim 4
Dependent Claim
36 words
The computer implemented method of claim 1, wherein reading an existence map associated with the node comprises reading a memory word comprising both a pointer to the node and the existence map associated with the node.
Claim 5
Dependent Claim
40 words
The computer implemented method of claim 1, wherein reading the existence map associated with the node comprieses reading an existence bit mask having a plurality of bits enabled to indicate which of the plurality of entries exist in the node.
Claim 6
Dependent Claim
32 words
The computer implemented method of claim 1, wherein producing a bit mask given the entry number comprises producing a bit mask having enabled only bits for entries less than the entry number.
Claim 7
Dependent Claim
35 words
The computer implemented method of claim 1, wherein producing a bit mask given the entry number comprises producing a bit mask having disabled only bits for entries equal to or greater than the entry number.
Claim 8
Dependent Claim
28 words
The computer implemented method of claim 1, wherein calculating an offset for the entry given the masked existence map comprising summing the bits comprising the masked existence map.
Claim 9
Dependent Claim
206 words
In a radix search tree data structure representing a sparse table in a memory of a computer system, the radix search tree comprising a plurality of nodes each having a plurality of entries, a computer implemented method for determining a memory address of an entry in a son node, comprising: a) reading an entry in a parent node, the entry in the parent node comprising a pointer to the son node and an existence map, the existence map comprising an existence bit mask having a plurality of bits enabled to indicate which of the plurality of entries exist in the son node; b) receiving an entry number corresponding to a symbol value being searched for in the son node; c) producing a bit mask having bits enabled for entries less than the entry number; d) masking the existence bit mask and the bit mask to produce a partial existence bit mask in which bits for entries equal to and greater than the entry number are discarded; e) calculating an offset for the entry by summing the bits in the partial existence bit mask; f) calculating the memory address of the entry in the son node by adding the offset to the pointer for the son node.
Claim 10
Dependent Claim
206 words
In a radix search tree data structure representing a sparse table in a memory of a computer system, the radix search tree comprising a plurality of nodes each having a plurality of entries, a computer implemented method for determining a memory address of an entry in a son node, comprising: a) reading an entry in a parent node, the entry in the parent node comprising a pointer to the son node and an existence map, the existence map comprising an existence bit mask having a plurality of bits enabled to indicate which of the plurality of entries exist in the son node; b) receiving an entry number corresponding to a symbol value being searched for in the son node; c) producing a bit mask having bits enabled for entries less than the entry number; d) masking the existence bit mask and the bit mask to produce a partial existence bit mask in which bits for entries equal to and greater than the entry number are discarded; e) calculating an offset for the entry by summing the bits in the partial existence bit mask; f) calculating the memory address of the entry in the son node by adding the offset to the pointer for the son node.
Claim 11
Dependent Claim
36 words
The method of claim 2, wherein masking the existence bit mask and the bit mask to produce a partial existence bit mask comprises performing a Boolean AND of the existence bit mask and the bit mask.
Claim 12
Independent Claim
127 words
An apparatus providing for a memory address of an entry in a node in a tree data structure representing a sparse table in a memory of a computer system, the node having a plurality of entries, comprising: a register to store an existence map associated with the node; a converter to convert an entry number into a bit mask; a Boolean logic unit to mask the existence map and the bit mask and to provide a masked existence map as an output; a first sum circuit to provide an offset by adding a plurality of bits comprising the masked existence map; and a second sum circuit to provide the memory address of the entry in the node by adding the offset to a pointer for the node.
Claim 13
Independent Claim
127 words
An apparatus providing for a memory address of an entry in a node in a tree data structure representing a sparse table in a memory of a computer system, the node having a plurality of entries, comprising: a register to store an existence map associated with the node; a converter to convert an entry number into a bit mask; a Boolean logic unit to mask the existence map and the bit mask and to provide a masked existence map as an output; a first sum circuit to provide an offset by adding a plurality of bits comprising the masked existence map; and a second sum circuit to provide the memory address of the entry in the node by adding the offset to a pointer for the node.
Claim 14
Dependent Claim
19 words
The apparatus of claim 10, wherein the Boolean logic unit comprises AND logic to provide the masked existence map.
References Cited (Backward Citations)
US4468728A
Cited
US4774657A
Cited
US5333317A
Cited
US5261088A
Cited
US5727201A
Cited
US5487164A
Cited
US5557786A
Cited
US5546390A
Cited
US5651099A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-15 | 2002-08-17 | 2003-02-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-15 | 2006-08-17 | 2007-02-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-15 | 2010-08-17 | 2011-02-16 | $7700.00 | Window Closed / Lapsed |