Browse Prior Art Database

An Algorithm for Sorting a Dynamic File

IP.com Disclosure Number: IPCOM000090458D
Original Publication Date: 1969-Apr-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 3 page(s) / 48K

Publishing Venue

IBM

Related People

Biagini, LB: AUTHOR

Abstract

In data collection systems in which each transaction is composed of a plurality of records, with the individual records of all transactions being received intermixed and with the termination of a transaction being received at any time, it is desirable to store all records in the same order as they are received and to dynamically extract from storage, all records pertaining to a completed transaction. To accommodate concentrated receipt of large numbers of records, a section of core storage 1 is supplemented with one or more disk files 2. The entire storage 1 for data is divided into four areas of receive, disk write, transient, resident stores. Each store is composed of a group of chained blocks of storage addresses. Each store is identified by a related control word 3.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

An Algorithm for Sorting a Dynamic File

In data collection systems in which each transaction is composed of a plurality of records, with the individual records of all transactions being received intermixed and with the termination of a transaction being received at any time, it is desirable to store all records in the same order as they are received and to dynamically extract from storage, all records pertaining to a completed transaction. To accommodate concentrated receipt of large numbers of records, a section of core storage 1 is supplemented with one or more disk files 2. The entire storage 1 for data is divided into four areas of receive, disk write, transient, resident stores. Each store is composed of a group of chained blocks of storage addresses. Each store is identified by a related control word 3. This includes the address of the first stored record, the address of the last stored record of the chain and the number of records in the chain. The unassigned blocks of core storage are assigned to empty queue 4. This lists the available blocks in a chained queue indicated by the stored addresses of the first and last blocks of the chain.

In operation, records, as received, are stored in the receive area which stores the records in a block until the block is filled. A new block is requisitioned from the beginning of the empty queue 4 and the control word 3 of the receive block and that of the empty queue are updated. When a predetermined number of records is assembled in the receive area, the block is transferred to the resident area if available or to the transient area if the resident area is occupied or to the disk write area if both higher areas are occupied. Such transfer is accomplished by transfer of the data of control words 3 from one control word to another and the start of a new block of data in the receive area. If additional records are received after the assigned area of core store is utilized, the records in the transient and disk write areas are recorded in chained sectors of disk file 2 with the start and end addresses of the recorded chain being retained in a control word 5 and each sector storing a count of the number of records therein.

When all records of a transaction are recorded, a transaction end signal is received and the identification of the transaction together with the number of records in the transaction is stored in a transaction complete list 6. This starts a sort cycle in which the resident area is read block-by-block down the chain to compare in comparator 7 the transaction identification of the record with that of list 6. When the identifications are the same,...