Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-30
2002-01-01
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C711S145000, C711S159000, C711S212000, C711S219000
Reexamination Certificate
active
06336113
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a data management method and apparatus for use when entry data is registered in an entry table.
DESCRIPTION OF THE PRIOR ART
FIG. 7
is an example of a conceptual diagram explaining about a conventional data management method.
A high-speed semiconductor memory such as SRAM, for example, is used as an entry table
30
and a predetermined number of entry data
32
are registerable in the entry table
30
. Usually, the number of entry data
32
registerable in the entry table
30
is limited and entry data
32
of 1K (=1,024) are assumed to be registerable in this case. The entry data
32
registered in the entry table
30
can be used by reading out the data as occasion demands.
When a request for the registration of a new entry data
34
is made to the entry table
30
, the new entry data
34
is basically registered at a free entry address in the entry table
30
. In case no free entry address is found, however, an unwanted entry data is detected and deleted out of the entry data
32
of 1K already registered, so that the new entry data
34
is registered at the entry address thus deleted.
In this case, the unwanted entry data is set properly by a user of a data management apparatus as necessary by setting at least one specific condition for the management of the entry data
32
registered in the entry table
30
such that the unwanted entry data is determined by an order of registration or from the fact that it remains less frequently used or unused for a predetermined time, for example.
A description will subsequently be given of an example of the prior art data management method in order to understand problems pertaining thereto. In order to simplify an explanation, it will be assumed that the entry data
32
registered in the entry table
30
are arranged in order of size and when a request for the registration of the new entry data
34
is made, what has the lowest value, for example, among the entry data
32
of 1K registered in the entry table
30
is to be treated as what is unwanted and deleted.
In this case, it becomes necessary to detect an entry address at which the new entry data
34
should be registered and to rearrange the entry data
32
accordingly. By doing a binary search eleven times through the entry data of 1K, for example, the entry address at which the new entry data
34
should be registered can be calculated. The time required for calculating the entry address is 1.1 &mgr;s on the assumption that the time required for doing one binary search is 100 ns.
For rearranging the entry data
32
in order of size, it is necessary that not only reading the entry data
32
whose respective values are smaller than that of the new entry data
34
sequentially but also writing them at destination entry addresses sequentially as shown in FIG.
7
. Assuming that 50 ns is necessary for moving one entry data
32
, the time required to move all of the entry data
32
amounts to 50 &mgr;s (1K×50 ns) when things come to the worst in a case where the new entry data
34
has the largest value (see FIG.
7
).
In the prior art data management method and apparatus so designed as to make a rearrangement of entry data
32
, a relatively long time is needed until the new entry data
34
is registered despite the use of a high-speed semiconductor memory such as SRAM and an objective retrieval operation is unperformable during this time. Although the number of entry data
32
registerable in the entry table
30
has been set at 1K as described above, the time required for the management of entry data increases as the number of entry data increases because there may be a case where more entry data are registered.
Consequently, there is a problem that the prior art data management method and apparatus is unfit for use which requires simultaneous data update and high speed retrieval operation, for example, Internet network addresses.
PROBLEMS TO BE SOLVED BY THE INVENTION
An object of the present invention is to solve the above mentioned prior art problem, and to provide a data management method and apparatus capable of managing entry data at high speed through a simple procedure and with a simple configuration.
In order to accomplish the object above, the present invention provides a data management method for use when a demand for the registration of a new entry data is made in order to register the new entry data by deleting a specific entry data out of a plurality of n-bit (n=a positive integer) entry data registered beforehand, comprises the steps of:
registering the plurality of entry data having n-bit length;
performing match retrieval repeatedly by masking a (n−m(i)) bit (m(i)=a positive integer satisfying n≧m(i)) from the least significant bit side, whereby detecting the value of an m(i) bit from the side of the most significant bit matching the specific entry data;
performing match retrieval by shifting a bit to be masked next by an m(i+1) bit (m(i+1) a positive integer satisfying (n−m(i))≧m(i+1)) toward the low order side and detecting a corresponding value of m(i+1) bit until no bit to be masked exists so as to detect the value of an n bit matching the specific entry data; and
obtaining an entry address at which the specific entry data matching the value of the n bit thus detected has been registered, so that the new entry data is registered at the entry address.
It is preferred that match retrieval is performed again by the use of the value of the n bit matching the specific entry data thus detected so as to detect the entry address of the specific entry data.
Preferably, the specific entry data has the lowest value, the highest value or a value nearest a predetermined value. A condition for the detection of the specific entry data is preferably one of entry data registration order, frequency in use and elapsed time after the registration.
The m(i+1) bit is preferably one bit or two bits.
Also the present invention provides a data management apparatus comprises:
an associative memory having at least one mask register for masking the predetermined bit of retrieval data, and at least a memory array in which a plurality of n-bit (n=a positive integer) entry data are registered, the memory array being used for performing match retrieval of the retrieval data masked by the mask register and the plurality of entry data; and
a control circuit for controlling the associative memory in such a way as performing match retrieval by masking an (n−m(i)) bit (m(i)=a positive integer satisfying n≧m(i)) from the least significant bit side of the retrieval data by means of the mask register, detecting the value of the m(i) bit from the side of the most significant bit matching the specific entry data according to a result of match retrieval, and performing match retrieval repeatedly by shifting a bit to be masked next by an m(i+1) bit (m(i+1)=a positive integer satisfying (n−m(i))≧m(i+1)) toward the low order side and detecting a corresponding value of m(i+1) bit until no bit to be masked exists so as to detect not only the value of n bit matching the specific entry data but also an entry address at which the specific entry data has been registered.
It is preferred that the associative memory feeds to the control circuit a hit detection signal for indicating that at least one entry data matching the retrieval data has been registered in the memory array.
The control circuit is preferably formed of only hardware.
The associative memory and the control circuit are preferably formed of a semiconductor chip.
The control circuit is preferably formed of only software or a combination of software and hardware.
The m(i+1) bit is preferably one bit or two bits.
The mask register preferably has a function of shifting a bit to be masked by the m(i+1) bit each time toward the low order side under the control of the control circuit.
It is preferred that the associative memory further includes an input da
Black Thomas
Kawasaki Steel Corporation
Veillard Jacques
LandOfFree
Data management method and data management apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data management method and data management apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data management method and data management apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2864297