JPH0581093A - Duplex chain processing system - Google Patents

Abstract

PURPOSE:To realize the table structure of the duplex chain and to save the memory by securing the only link information storage area in each entry in the duplex chain processing system. CONSTITUTION:The total of the index in front of and behind the entry is stored as link information in link information storage areas 6 to 10 with the index indicating the physical order assigned to each entry 1 to 4 of the duplex table. Accordingly, the memory can be saved since the table structure of the duplex chain can be realized by securing the only link information storage area in each entry. In addition, since an index and addition/subtraction and used it can be used by the computer language which does not deal with address and pool operation, and the table structure of the duplex chain can be constructed while saving the memory.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a bidirectional chain processing system, and more particularly to a bidirectional chain processing system for processing a bidirectional chain using link information.

[0002]

2. Description of the Related Art In a conventional bidirectional chain processing method, in one example, a table structure having a bidirectional chain is used to link index values or address values of preceding and following entries to all entries in forward and backward directions. This is realized by holding each as information.

In another example, the conventional bidirectional chain processing method is performed as follows, as described in "Bidirectional list construction method in table processing (Japanese Patent Laid-Open No. 63-219032)". It is realized with one link information.

An exclusive OR of the addresses of adjacent tables in the forward and backward directions is calculated in advance and stored in the pointer area of each table.

In the forward direction, the exclusive OR of the contents of the pointer area of the table currently being processed and the address of the immediately preceding table in the forward direction is calculated. Ask for the address.

In the reverse direction, the exclusive OR of the contents of the pointer area of the currently processed table and the address of the immediately preceding table in the reverse direction is calculated.
In the reverse direction, the address of the next table is obtained.

[0007]

However, the above-described conventional bidirectional chain processing method requires two link information storage areas in the processing method for storing the forward and backward link information. Therefore, there is a drawback that the memory size occupied by the link information storage area cannot be ignored in a table having a large number of entries.

Further, in the processing method for storing the exclusive OR of the address values of the preceding and succeeding entries, the memory can be saved by making the link information storage area one, but a programming language that can handle the Boolean operation for the address is required. There was a drawback to say.

[0009]

According to the bidirectional chain processing method of the present invention, an index indicating a physical order is attached to each entry of a table having a bidirectional chain, and a total of indexes of preceding and following entries is linked. The information is configured to be stored in the link information storage area.

[0010]

Embodiments of the present invention will now be described in detail with reference to the drawings.

FIG. 1 is a link state diagram showing an embodiment of the present invention.

In the bidirectional chain processing system shown in FIG. 1, entry 1 is an entry at the beginning and has an index value = 1, and entry 2 is an entry at the end and has an index value = 2. Entries 3 to 5 are entries located in the middle.

The link information storage areas 6 to 10 store the link information A which is the result of the equation (1). The index value of the forward entry when calculating the link information storage area 6 is “0”, and the index value of the backward entry when calculating the link information storage area 7 is “0”.
And

Further, the link states a to d indicate the link states in the forward direction between the entries, and the link states e to h indicate the link states in the reverse forward direction between the entries.

The forward chain is entry 1 → entry 4 → entry 3 → entry 5 → entry 2, and the reverse forward chain is the reverse of the forward chain.

In the following description, the index value of the i-th entry in the chain is represented as I (i).

Here, in the case of the normal order search, the entry 1 is set to 1
The second entry is counted as the first entry in the case of reverse search.

The link information A which is the value of the link information storage area of the entry i of the index I (i) is expressed by the following equation (1).

A = I (i−1) + I (i + 1) (1) Further, the index value I (i) of the subsequent entry (i + 1)
+1) is obtained as the link value B shown in the following equation (2).

B = A−I (i−1) (2) Now, the link states a to d are used in the forward order search, but when the index values I (4) of the entries 3 to 5 are obtained. , As shown in equation (3).

Index value of entry 5 of entry 3 of entry 5 = value of link information storage area 8-index = {I (2) + I (4)}-I (2) ... (3) = I (4 In addition, although the reverse order search uses the link states e to h, when the index value I (2) of the entry 3 to the entry 4 is obtained, the expression (4) is obtained.

Index value of entry 4 of entry 4 of entry 4 = value of link information storage area 8-index = {I (2) + I (4)}-I (4) (4) = I (2 It should be noted that it is possible to determine the end of the search by determining whether the link information B represented by the equation (2) is “1” or “2”.

[0023]

According to the bidirectional chain processing method of the present invention, the memory structure can be saved because the bidirectional chain table structure can be realized by securing a unique link information storage area for each entry. At the same time, since indexes and addition / subtraction are used, it is possible to use even in computer languages that cannot handle addresses and pool operations, so that it is possible to construct a bidirectional chain table while saving memory.

[Brief description of drawings]

FIG. 1 is a link state diagram showing an embodiment of the present invention.

[Explanation of symbols]

 1-4 entries 6-10 link information storage area ah link status

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Hiroyuki Ichikawa 4-4 27 Bandai 4-chome, Niigata City, Niigata Prefecture Niigata Nippon Electric Software Co., Ltd.

Claims (2)

[Claims] 1. An index indicating a physical order is attached to each entry of a table having a bidirectional chain, and the total of indexes of the entries of the preceding and following chains is stored in a link information storage area as link information of the entry. A bidirectional chain processing method characterized in that 2. A bidirectional chain processing method, wherein an index value of a subsequent entry is obtained by a difference between link information of the entry and an index value of a preceding entry.