Browse Prior Art Database

Forward and Backward Chaining of Data Areas

IP.com Disclosure Number: IPCOM000073428D
Original Publication Date: 1970-Dec-01
Included in the Prior Art Database: 2005-Feb-22
Document File: 3 page(s) / 66K

Publishing Venue

IBM

Related People

Holloman, DR: AUTHOR

Abstract

Described is a chaining technique for storing data in a medium when the amount of data to be stored is not known at the start of the process and allocation of storage area is noncontiguous. For example, a process builds an in-core table from an unknown number of input-records with one data record for each input record. The number of records may be as few as one or as many as 10,000. The average number of records is 300. To request an allocation of core large enough to hold the maximum number possible is wasteful of resources in most cases. To request less may force additional requests with the result that in-core data records are in noncontiguous areas.

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 50% of the total text.

Page 1 of 3

Forward and Backward Chaining of Data Areas

Described is a chaining technique for storing data in a medium when the amount of data to be stored is not known at the start of the process and allocation of storage area is noncontiguous. For example, a process builds an in- core table from an unknown number of input-records with one data record for each input record. The number of records may be as few as one or as many as 10,000. The average number of records is 300. To request an allocation of core large enough to hold the maximum number possible is wasteful of resources in most cases. To request less may force additional requests with the result that in- core data records are in noncontiguous areas.

Some features of the described chaining technique shown in Drawing A are:
1) The chaining technique provides; a. a pointer at the end of each data area to the first data record in the next data area for forward chaining, and b. a pointer at the beginning of each data area to the start of the last data record in the previous data area for backward chaining. 2) A unique value (e.g., 0 or all 9's) in lieu of a chain pointer will signify the end of the chain. 3) A unique bit or pattern of bits in the first portion of each data record must be reserved to signify chaining for variable length records. For fixed length data records, a pattern should be reserved in the first and last portions of the data record. A test for this unique pattern will determine whether what is pointed to is a data record or a pointer to a data record. 4) Once data has been stored in this manner, all that is necessary to locate a desired data record is a pointer to the start of any data record and knowledge whether a scan is to proceed forward or backward. 5) Forward scanning for fixed and variable length data records is; a. Test what is pointed to, to determine if it is a forward pointer or a data record. b. If it is not a chaining pointer, go to c; else, take the value pointed to as the new pointer to a data record, unless it is the end of the chain. c. Test if the data record pointed to is the one desired. d. If it is, the search is ended; else, add the length of the record pointed to, to the pointer and return to a. 6) Backward scanning for fixed length record is; a. Test the last portion of what is pointed to, to determine if it is a chaining pointer. b. If it is not a chaining pointer to go to c; else, take the last portion of what is pointed to as the new pointer to a data record, unless it is the end of the chain as indicated by the unique value. c. Test to see if the data record pointed to is the one desired. d. If it is the one desired, the search is ended; else, subtract the length of a record from the pointer. Note that if the record just pointed to was the first record in the area, the pointer will now be pointing outside any data. However, the last portion of whatever is pointed to will contain a pointer to the last record of the previous data area. Go...