Linked data structure integrity verification system which verifies actual node information with expected node information stored in a table

A method for simultaneously verifying integrity of at least one linked data structure comprising:

• cataloging node information for a plurality of nodes associated with each of said least one linked data structure on a memory device;
• retrieving each of said plurality of nodes seriatim from said memory device in an optimal memory device access order that facilitates optimal node retrieval performance independent of any logical linked data structure traversal and independent of any position of said plurality of nodes within any of said at least one linked data structure;
• and
• verifying node pointer integrity for each of said plurality of nodes based on a minimal store of node information knowledge.

A linked data structure verification system in a computing device, said computing device having access to a memory device on which at least one linked data structure resides, each of said at least one linked data structure having a membership of a plurality of nodes, said system comprising:

• a verification setup phase operable in real time during normal linked data structure processing, said verification setup phase includes:
• means for generating a node address table having a node address entry for each of said plurality of nodes in said at least one linked data structure;
• and
• means for ordering said node address table in a physical memory location retrieval order;
• and
• an integrity verification phase operable upon completion of said verification setup phase, said integrity verification phase includes:
• means for retrieving each of said plurality of nodes seriatim from said memory device in said physical memory location retrieval order that facilitates optimal memory device retrieval performance;
• means for comparing actual node information from a retrieved one of said plurality of nodes against expected node information already known about said plurality of nodes in any one of said at least one linked data structure;
• means for reporting any inconsistency between said actual node information and said expected node information in response to said comparing means;
• means for updating said expected node information with valid parts of said actual node information;
• and
• means for removing any parts of said actual node information that are duplicative of said expected node information in response to said updating means.

A linked data structure verification system comprising:

• means for cataloging node information during normal linked data structure processing for each of a plurality nodes associated with at least one linked data structure on a memory device;
• means for retrieving actual node information for each of said plurality of nodes seriatim from said memory device in an optimal memory device access order that facilitates optimal node information retrieval performance independent of any logical node ordering in any of said at least one linked data structure;
• means for verifying said actual node information against a minimized store of expected node information related to any one of said plurality of nodes from any one of said at least one linked data structure;
• means for hashing at least one component of node information corresponding to a secondary index linked data structure into a secondary index hash table to verify any existing secondary index linked data structure node information.