Single-keyed indexed file for TP queue repository

A data processing system comprising a memory device, means for producing data records and means for sequentially storing said records in said memory device to arrange said records in said memory device in an ordered set forming a queue of said records, said means for producing data records including means for generating identifiers for identifier fields in said records so that each of said records includes an identifier field holding a respective identifier different from the respective identifiers in the identifier fields of the other ones of said records, said means for producing data records further including means for producing key values for key fields in said records so that each of said records also includes a key field holding a respective key value having a respective most significant portion indicating a priority level and a less significant portion that is a predetermined function of the respective identifier in the record, and said means for sequentially storing said records including means for ordering said records in said queue so that records having the same priority level are included in respective blocks of said records, the records in each block are ordered sequentially with respect to the less significant portion of the key values and sequentially with respect to the storing of said records in said memory, and the records in said queue are ordered sequentially with respect to the key values but not sequentially with respect to the storing of said records in said memory device.

A data processing system comprising a memory device, means for producing data records and means for sequentially storing said records in said memory device to form a queue of said records in a key-indexed file wherein said key-indexed file has a primary key, said means for producing data records including means for generating time values and processor numbers and combining the time values and processor numbers to form identifiers for identifier fields in said records so that each of said records includes an identifier field holding a respective identifier different from the respective identifiers in the identifier fields of the other ones of said records, said means for producing data records further including means for producing key values for key fields in said records so that each of said records also includes a key field holding a respective key value having a most significant portion indicating a priority level and a less significant portion that is the time value of the respective identifier in the record, and said means for sequentially storing said records including means for ordering said records in said queue so that said key values are values of said primary key of said key-indexed file and records having the same priority level are included in respective blocks of said records, the records in each block are ordered sequentially with respect to the less significant portion of the key values and sequentially with respect to the storing of said data records in said memory, and the records in said queue are ordered sequentially with respect to the key values but not sequentially with respect to the storing of said records in said memory device.

A method of operating a data processor in a data processing system to search a queue for a data record having a requested identifier, said queue being held in a memory device in said data processing system, said queue comprising an ordered set of a multiplicity of records of data stored in said memory device, each of said records of data stored in said memory device, each of said records including an identifier field holding a respective identifier, each of said records also including a key field holding a respective key value having a most significant portion indicating a priority level and a less significant portion that is a predetermined function of the respective identifier in the record, said records being ordered in said queue sequentially with respect to said key values but not sequentially with respect to said less significant portion of the key values whereby records having the same priority level are included in respective blocks of said records, and the records in each block are ordered sequentially with respect to the less significant portion of the key values, said method comprising the steps of:

• a) searching said queue for records having in their respective key fields a less significant portion that is said predetermined function of said requested identifier;
• and
• b) determining whether the identifiers in the respective identifier fields of the records found by said searching in step (a) are the same as the requested identifier.

A method of operating a data processor in a data processing system to search a queue for a data record having a requested identifier, said queue being held in a memory device in said data processing system, said queue comprising an ordered set of a multiplicity of records of data stored in a key-indexed file in said memory device, each of said records including a respective identifier field holding an identifier different from the respective identifiers included in the other ones of the records, each of the identifiers having a respective time value, each of said records also including a key field holding a respective key value having a most significant portion indicating a priority level and a less significant portion that is the time value of the respective identifier in the record, said key values being values of said primary key, said records being ordered in said queue sequentially with respect to said key values but not sequentially with respect to said less significant portion of the key values, whereby records having the same priority level are included in respective blocks of said records, and the records in each block are ordered sequentially with respect to the less significant portion of the key values, said method comprising the steps of:

• a) forming search keys each having a less significant portion that is the time value of said requested identifier;
• b) randomly accessing said key-indexed file with said search keys to search said queue for records having in their respective key fields a less significant portion that is the time value of said requested identifier;
• c) determining whether the identifiers in the respective identifier fields of the records found by the searching in the step (b) are the same as the requested identifier;
• d) sequentially accessing said key-indexed file to search for additional records when said step (c) determines that a record found in step (b) does not have an identifier that is the same as the requested identifier;
• and
• e) determining whether the identifiers in the respective identifier fields of the additional records found by the searching in step (d) are the same as the requested identifier.

A data processing system comprising, in combination,

• a nonvolatile memory device holding a task queue, said queue comprising an ordered set of a multiplicity of records of task data held in said memory device, each of said records including an identifier field holding a respective identifier different from the respective identifiers in the identifier fields of the other of said records, each of said records also including a key field holding a respective key value having a respective most significant portion indicating a priority level and a less significant portion that is a predetermined function of the respective identifier in the record, said records being ordered in said queue sequentially with respect to said key values but not sequentially with respect to said less significant portion of the key values, whereby records having the same priority level are included in respective blocks of said records, and the records in each block are ordered sequentially with respect to the less significant portion of the key values;
• application processor means for performing data processing tasks using said task data;
• queued task initiator means for accessing said queue for task data for an uninitiated task that is next in the queue, and initiating that task by invoking said application processor means;
• and
• task queue searching means for searching said task queue for a record having a requested identifier in its identifier field, said task queue searching means including means for finding records in said task queue having in their key fields a less significant portion that is said predetermined function of said requested identifier, and means for determining whether a record found by said means for finding has an identifier in its identifier field that is the same as the requested identifier.