gtpd1m2k | Database Reference |
All extended structures inherit from the StructureDasd class. This section describes the following specific types of extended-structure objects provided by TPFCS as they apply to collections created with 4-byte file address format:
Extended structures make use of the following:
TPFCS stores and retrieves data elements for extended-resident collections using data records. Data records are pool records where the actual data elements for the collection are stored. A data record often contains more than one data element for a given collection.
For collections with keys, TPFCS stores and retrieves data elements for extended-resident collections using key (index) records as well. Key records are pool records that are arranged in a tree-like structure by which TPFCS sorts the keys and locates the data record containing the data element that corresponds to each key. The root of the tree is chained to the structure object.
TPFCS also uses directory entries to represent extended-resident collections. Each directory entry that is in use for an extended-resident collection contains the file address of a key (index) or data record as well as its shadow if one exists. TPFCS uses the directory entries for a given collection to locate its key and data records by their relative record number (RRN). Some directory entries are embedded in the extended structure object (StructureDasd) itself, whereas others are kept in pool records, which are called directory records. Just as with key records, TPFCS chains the directory records for a collection in a tree-like structure whose root is chained to the structure object.
A directory entry is not an object itself, but rather an attribute or field in the object in which it is contained. If you read the TPFCS source code, you must not confuse the directory entry with the DIRECTORY object, which is just one of the objects that TPFCS uses to store directory entries. A DIRECTORY object itself contains directory entries and is filed in a directory record.
A directory entry can have either of two formats and always contains a bit flag that identifies which format describes that entry. TPFCS uses directory entries in the first format to locate records on file.
In the first format, the following fields are contained in directory entries:
The second format for a directory entry is used to store a next available RRN that TPFCS will use to represent a collection on DASD.
Each data record and key record (when present) belonging to an extended-resident collection is associated with an RRN. A key or data record relative record number describes the order in which that record occurs in the abstract flat file representation of the collection data and associated control information. You can best understand what is meant by a relative record number, as well as gain a better understanding of extended-resident collections, by considering the following abstract model. Even though it is not the case, you can think of all of the data of a given extended collection, as well as associated control information used to manage or sort through that data, as being stored in one huge continuous flat file. This flat file itself is partitioned into 4-K records:
Figure 37. Abstract View of How Data Is Stored for Extended-Resident Collections
Each of the 4-K records used to contain or manage the data is either a data record or (for keyed collections) a key record. The first record in this file is assigned RRN 0, the next is assigned RRN 1, and so on.
In reality, the flat file of this abstract representation does not exist. The 4-K records comprising the file are scattered across the TPF database in pool records. TPFCS uses directory entries as well as directory records to locate and access each of these records according to its relative record number.
As mentioned earlier, TPFCS uses directory entries and directory records to locate collection data and key records by their relative record number. Directory entries 0-17 are embedded in the collection structure object and TPFCS uses them to locate RRNs 0-17 directly: that is, when one of these RRNs is in use for a collection, the corresponding directory entry of the RRN will contain its file address (for both the primary record and the shadow when present). The directory records are used to locate RRNs 18 and higher. Logically, the directory records are arranged in a tree-like structure with the root of the tree referenced by the Structure_I_DirectoryR attribute of the structure object. Consider the following figure, which shows a directory record tree for a collection containing RRNs 18-30, where RRNs 20, 25, and 29 are not active.
Notes:
Figure 38. How Directory Records Are Used to Locate RRNs 18-26
In Figure 38, the collection associated with directory records A-H is shadowed. Therefore, each of the directory records has both a primary and a shadow copy. For example, record A' is the shadow copy of record A. As with all of the records that TPFCS uses, each shadow record contains the exact same contents as its primary counterpart. (To keep our discussion simple, the contents of the shadow records are not shown in our example and we will assume that TPFCS selects the primary copy.)
To understand how the tree of directory records is used to locate RRNs 18 and higher, consider a condition in which TPFCS needs to access RRN 24 of the associated collection. TPFCS arrives at the root of the tree via StructDasd_I_DirectoryR, which contains the file address of record A as well as the file address of its shadow, record A'. TPFCS reads record A (1) . Given the RRN we want to locate, TPFCS uses an internal algorithm to determine which RRNs each entry locates. This algorithm uses information such as the level of directory record A (which is 2), its number of entries (which is 3), and the RRN for which record A was allocated (RRN 18). In our example, the algorithm would determine that the first entry (2) , which points to record B, is used to locate RRNs 18-26 inclusive. TPFCS reads directory record B (3) and scans it using an algorithm to determine which entry locates RRN 24. In our example, the third entry (4) from the top of the record is used because it locates RRNs 24-26. TPFCS uses this directory entry to read record F (5) . Because directory record F is at level 0, each active entry points directly to a relative record in the associated collection. TPFCS uses the same algorithm used previously to determine that the very first entry (6) in the directory record contains the file addresses of the primary (and shadow) copy of the data or key record with RRN 24. Either file address is used to read information in the record with RRN 24, and both file addresses (when present) are used to update information in that record.
It is also important to note that not every RRN from 0 to the current maximum RRN used by a given collection will be in use. This is normally true when the operations performed by application programs on a given collection have caused a data or key record to be deleted as elements were first added to a collection and later on removed from that collection. For example, assume the current maximum RRN in use for the collection in question is 30. Notice how the directory entries corresponding to RRNs 20, 25, and 29 in records D, F, and G respectively do not contain file address information. Instead of containing file address information, they are marked as available. For the collection in question (whose current maximum RRN in use is 30), if TPFCS needs to allocate another RRN to store additional elements, it can use any of the RRNs that are marked available rather than allocating RRN 31.
You will also notice that in the directory records in Figure 38, some of the entries are marked unused and others are marked as available. The difference between unused and available is as follows: Unused entries have never been used and contain zero. Available entries were previously used and once contained RRN file address information. The information formerly contained in these entries has been removed and the entries have been marked available as the associated RRNs were deleted. TPFCS can choose either unused entries or available entries to store file address information for new RRNs.
Whether or not a directory entry contains file address information is determined by its format. For a general discussion on directory entry format as well as how to determine more information about each format, see Record Types.
The following are the main attributes from the StructureDasd object class that will be contained in the extended-residency structure object:
TPFCS places records on each of these chains in topdown order. This means that each chain is really a stack, and the head of each chain really points to the last record that TPFCS added on that chain rather than the first. That is why the name of each header contains the phrase last allocated. TPFCS always uses the TPF forward chain pointer of each record to point to the next element on the chain. The following figure shows how TPFCS adds a record to one of these chains:
Figure 39. How TPF Collection Support Adds Records to a StructureDasd Chain
The allocated data and allocated key chains also contain records that TPFCS no longer uses to represent the collection associated with the StructureDasd object. As a result, when chasing these chains for the StructureDasd object of a given collection, not every record you find is necessarily being used by TPFCS for that collection. Rather than immediately removing records it no longer needs from the allocated data or allocated key chain, TPFCS chains these records to an associated released chain and schedules them to be released back to the TPF system when the length of the chain exceeds a predetermined threshold. The released chains are just another way of logically chaining the same physical records that are on the allocated chains.
TPFCS uses the following attributes of StructureDasd to manage each released chain:
Records are added to each released chain in topdown order similar to the way in which they are added to the allocated chains. TPFCS uses the TPF backward chain pointer to link records on each released chain. The following figure shows an example of how records are linked on both the allocated and released chains:
Figure 40. How Records Are Linked on Both Allocated and Released Chains
In Figure 40, the count of records on the allocated chain is 4 because the chain contains records A, B, C, and D. However, only records A and C are used for the collection because records B and D are on the released chain.
To insert, retrieve, and delete elements from an extended-resident collection, TPFCS uses the following attributes:
When TPFCS uses key records for a collection, its structure object will be a DASDINDEXPool object. DASDINDEXPool objects currently inherit attributes from the DASDINDEX class, which inherits from StructureDasd. The attributes are:
Figure 41 is a conceptual diagram of a DASDINDEXPool structure object:
Figure 41. DASDINDEXPool Object and Its Associated Records
Note the following in Figure 41:
To understand how the DASDINDEXPool object is used to represent a collection, consider an example in which TPFCS is processing a request of an application to retrieve the data element in the collection that has a key of LEMIE. TPFCS uses the root key pointer (DASDINDEX_I_RootDirEntry) to read the root key record (at file address 1000). (1) A key record contains one or more entries, each of which in turn contains a key value and an RRN. The entries are sorted by key. The root key record is scanned until either the first entry is found whose key is greater than or equal to the requested key (LEMIE), or the entries in the root key record are exhausted. In our example, TPFCS would stop scanning the root key record at the entry containing a key of MILLER and an RRN of 269 (2) .
TPFCS would then try to locate the directory entry for an RRN of 269. Because this RRN (269) is beyond RRN 17 (which is the highest RRN for an embedded directory), TPFCS begins its search for the directory entry to access that RRN by reading the root directory record of the directory record tree. The file address of the root Directory is contained in the root directory (StructDasd_I_DirectoryR) field in the DASDINDEXPool structure object. This address is 2000 in our example (record AAA) (3) . TPFCS reads the directory record (record AAA) from DASD and searches its entries using an internal algorithm to locate the entry that accesses RRN 269. The entry that TPFCS finds contains a primary file address of 2100 (as well as a shadow file address of 2101). 5 (4) TPFCS reads the record (record CCC) at this file address from DASD (5) .
Based on other fields in the record that are not shown, TPFCS knows that record CCC is another directory record, but that the file addresses contained in its directory entries point to key records, not directory records. TPFCS locates the directory entry in directory record CCC that accesses RRN 269 (6) . This entry has file addresses of 1100 and 1101, which point respectively to a primary and a shadow key record. TPFCS reads the key record at file address 1100 (7) (whose RRN is 269). TPFCS then scans this key record until it finds the first entry whose key is greater than or equal to the requested key of LEMIE, or until the entries are exhausted. In our example, the entry that satisfies this request contains MILLER as its key and an RRN of 1 (8) .
Once again, TPFCS attempts to locate the directory entry that accesses RRN. In this example, the search ends quickly because the directory entry that accesses RRN = 1 is the second embedded directory entry (9) . This directory entry points to the data record (record B) at file address 100 as well as its shadow (record B' at file address 101). TPFCS then reads this data record, whose highest key is MILLER (10) . TPFCS then searches this data record for a data element whose key matches LEMIE. If a match is found, the contents of the data element are returned to the requesting application. If no match is found, an appropriate error condition is returned.
We have just illustrated how, conceptually, the various components of a DASDINDEXPool structure object and the various records to which it points represent a keyed collection.
The following sections describe the contents of the structure record (where the DASDINDEXPool structure object is stored) as well as the other records used to store objects to manage the collection data. You will notice that none of these records contain DATXPAGE envelopes to store their objects.
The structure record contains the following in the order listed:
The directory records contain the following in the order listed:
Key records will contain the following in the order listed:
The following example is a representation of a key record that contains five active entries. Note that the entries are sorted using locators in a similar way to how entries were sorted in a MemKey structure.
Figure 42. Example of a Key (Index) Record Containing Five Entries
You can determine the exact format and contents of the NDXPAGE control information preceding its data area from the definition of the NDXPAGE instance attributes in the TPFCS source code. The exact format of the NDXPAGE trailer is defined under the NDXPG_Trailer tag in the same source module. The contents of this trailer include the following:
Each entry in the data area consists solely of a unique key followed immediately by an associated RRN. There is no DSECT that defines these entries in the TPFCS source code because the length of an entry depends on the key length, which varies from collection to collection. The entry length is stored in the NDXPAGE locator for that entry and equals the collection key length plus the length of an RRN (4 bytes). If the NDXPAGE locators are corrupt, you can determine the collection key length in several ways:
The locators are used to sort the entries by key (from lowest to highest) as shown in Figure 42. Each locator consists of 6 bytes in the following format:
Data records contain the following in the order listed:
Notes:
The following example is a representation of a data record that contains four active entries. As with key records, data record entries are sorted using locators.
Figure 43. Example of a Data Record Containing Four Active Entries
You can determine the exact format and contents of the NDXDATAPAGE control information preceding its data area from the definition of the NDXDATAPAGE instance attributes in the TPFCS source code. As mentioned previously, the trailer is the same as the NDXPAGE object and is described under the NDXPG_Trailer tag in the same source module.
Each entry in the data area consists of the following in the order indicated:
The format of the locators used to sort data record entries is the same as for those used to sort key record entries. See Key Records for specific information.
TPFCS uses DASDFLAT structure objects for the same types of collections that it uses for MemFLAT structures. Application programs specify a relative byte position when storing, updating, or retrieving data for those collections. As with MemFLAT structure collections, applications always specify a relative byte position when using DASDFLAT structure collections, either explicitly or as an index, depending on the type of collection the DASDFLAT structure represents.
To understand how DASDFLAT structure collections are stored in the TPF database, it is necessary to understand how TPFCS processes the relative byte position specified by the application to store or retrieve data for those collections. TPFCS takes the relative byte position, decrements it by 1 to make it 0-based, and then divides it by the number of bytes of data that would fit in a data record. TPFCS handles this quotient as an RRN and allocates a data record to hold the data when it is first stored in the collection. Directory entries are updated to locate the data record, and directory records are allocated as they are needed. For information about how directory entries and directory records relate to data records by RRN, see Extended Structures (StructureDasd Class). If the data does not fit in one data record, an additional data record is allocated and the next sequential RRN is assigned to that record.
The structure record contains the following in the order listed:
The directory records for a DASDFLATPool object are the same format as those used for DASDINDEXPool objects. See Directory Records for more information.
The data record for collections that use a DASDFLAT structure will contain a FLATPAGE object immediately following the TPFCS record header. The following are the important attributes of the FLATPAGE object:
TPFCS does not use key records for collections of this structure type.
The best way to understand how a persistent collection is represented on the TPF database using a DASDHASH structure object is to consider the following algorithm:
TPFCS uses relative records 0-66 as anchor records for storing the collection data elements. This is done as follows:
TPFCS performs the following steps to store a data element in a data record:
If there is no room in the current data record, TPFCS will check if there are any additional data records chained to it. If there is another in the chain that contains enough room, TPFCS will store the element and its hash value there.
The following abstract model shows how this algorithm works:
Figure 44. Abstract Model of a DASDHASD Structure Collection
In our model, elements A1, A2, and A3 all produce hash value a. Likewise, elements B1 and B2 produce Hash Value b.
Element C1 does not appear in the figure because it was later deleted.
This record contains the following in the order listed:
The directory records for a DASDHASHprime object are the same format as those used for DASDINDEXPool objects. See Directory Records for more information.
These records contain the following in the order listed:
The following figure represents a VDATPAGE data record that contains four active entries. Notice how the data entries are sorted by their associated hash values using locators that are at the bottom of the data area.
Figure 45. Example of a VDATPAGE Data Record Containing Four Active Entries
For more information about the control information attributes contained in the VDATPAGE object, see the definition for that object class in the TPFCS source code.
Each entry in the data area consists of the following in the order indicated:
Each locator is an 8-byte field consisting of the following:
Notes:
TPFCS does not use key records for collections of this structure type.
TPFCS uses structure objects with DASDLIST attributes to represent collections where the elements have an order determined exclusively by the application. This differs from DASDINDEX structure collections where the order of collection elements is determined by the key associated with each element. For example, in a DASDINDEX structure collection, an element with a key of BAKER would naturally come before an element with a key of COOPER. On the other hand, in a DASDLIST structure collection, an element containing COOPER could precede an element containing BAKER because the application that created the collection has chosen to give COOPER a higher priority than BAKER.
To understand how TPFCS keeps track of arbitrarily ordered collections using the DASDLIST structure, consider the following scenario. Suppose that an application inserts the following elements into a collection in the order described, specifying the priority or order of each element as it is inserted:
Let us assume that each of these elements the application inserted in the collection are large enough to each fill an entire data record. BAKER, the first element inserted, would be filed in relative record number (RRN) 0. COOPER, the next element inserted, would be filed in RRN 1, and so on. The following figure shows how each record that is written in the database would appear:
Figure 46. How Elements of a DASDLIST Structure Collection Are Written in the Database
Notice that how the elements are written in the database differs greatly from a logical diagram of how those elements are ordered, where FOLEY is the first element in the collection, COOPER is the second, and so on:
Figure 47. How Elements of a DASDLIST Structure Collection Are Ordered
TPFCS uses fields in the DASDLIST structure as well as in the data records chained to that structure to keep track of the order of collections with arbitrarily ordered elements. The following are the fields in DASDLIST that are used to keep track of the order:
TPFCS chains the data records in order as well as in reverse by maintaining the following fields in each of the data records:
Figure 48 shows how the DASDLIST structure object, together with the next RRN and previous RRN fields in each of the data records, enables TPFCS to traverse the collection either in order from the first to the last element, or in reverse order from the last element to the first element:
Figure 48. How the Order of a DASDLIST Collection Is Maintained
By using the DASDLIST_I_FirstRRN structure object field (labeled First RRN in the figure), TPFCS can locate the first element in the collection regardless of where it is filed in the TPF database. (For more information about how directory entries and directory records are used to locate the data record corresponding to a given RRN, see Figure 38 and the discussion that follows it). TPFCS can then traverse the entire collection, in order, using the LDATPAGE_NEXTRRN field (labeled Next RRN in the figure) in each data record. Similarly, TPFCS can traverse the entire collection in reverse order, starting with the last element, by using the DASDLIST_I_LastRRN structure object field (labeled Last RRN) and the LDATPAGE_PREVRRN field (labeled Previous RRN) in each data record.
In reality, not every element in a DASDLIST structure collection will fill an entire data record. In a real example of a collection, each of the data records of a DASDLIST structure collection would contain many elements. TPFCS manages the order of elements in these data records by using locators to sort them based on how they were ordered by the applications that added them to the collection. The contents of a data record for DASDLIST structure collections are, therefore, more complex than the example we have just discussed, and data records will contain many more fields to count and sort the elements they contain. See Data Records for a complete discussion of the format of data records for DASDLIST structure collections.
This record contains the following in the order listed:
The directory records for a DASDLISTPool object are the same format as those used for DASDINDEXPool objects. See Directory Records for more information.
These records contain the following in the order listed:
The following example is a representation of a data record that contains four active entries. Notice how the data entries are sorted using locators, which are at the bottom of the data area.
Figure 49. Example of an LDATPAGE Data Record Containing Four Active Entries
We have already discussed two items contained in the LDATPAGE control information: namely, the RRN of the previous data record and the RRN of the next data record in the collection. You can determine the exact format and contents of all the LDATPAGE control information preceding its data area from the definition of the LDATPAGE instance attributes in the TPFCS source code.
Each entry in the data area consists of the following in the order indicated:
Each of the locators used to maintain order among the data entries is a 4-byte field containing the following:
TPFCS does not use key records for collections of this structure type.