Non-recursive processing of hierarchical data
AssigneeEMC Corporation
InventorNathan Kryger
Life of this patent
Estimating the term…
Abstract
Non-recursive traversal of hierarchical data structures is disclosed. Elements inside a hierarchical data structure are processed beginning at a first level of the hierarchical data structure. In the event that a branch point associated with a second level of the hierarchical data structure is encountered, a marker data associated with a location of the branch point within the hierarchical data structure is stored inside a user allocated data structure, and the marker stored in the user allocated data structure is used to enable elements, if any, in the second level and any remaining elements in the first level, if any, to be processed without recursion.
Claims24
A computer-implemented method for traversing a hierarchical data structure, comprising:
- processing elements inside the hierarchical data structure beginning at a first level of the hierarchical data structure;
- and
- in the event that a branch point associated with a second level of the hierarchical data structure is encountered:
- using a processor to store, inside a user allocated data structure, marker data that includes location information describing the location the branch point was encountered within the hierarchical data structure and excludes at least one of the following:
- a return address, a parameter, or a local variable associated with a function call;
- and
- using the marker data stored in the user allocated data structure to enable any elements in the second level and any remaining elements in the first level to be processed without recursion, comprising:
- processing any elements in the second level associated with the branch point without making a recursive function call;
- retrieving the marker data, using the processor, upon completion of processing elements in the second level;
- and
- using the marker data to resume processing in the first level of the hierarchical data structure at the location with which the marker data is associated.
A computer-implemented method for traversing a hierarchical data structure, comprising:
- processing elements inside the hierarchical data structure beginning at a first level of the hierarchical data structure;
- and
- in the event that a branch point associated with a second level of the hierarchical data structure is encountered:
- using a processor to store, inside a user allocated data structure, marker data that includes location information describing the location the branch point was encountered within the hierarchical data structure and excludes at least one of the following:
- a return address, a parameter, or a local variable associated with a function call;
- and
- using the marker data stored in the user allocated data structure to enable any elements in the second level and any remaining elements in the first level to be processed without recursion, comprising:
- completing the processing of elements in the first level that are not branch points prior to processing the branch point;
- retrieving the marker data using the processor;
- and
- using the marker data to process any elements associated with the branch point.
A system for traversing a hierarchical data structure, comprising:
- a processor configured to process elements inside the hierarchical data structure beginning at a first level of the hierarchical data structure and in the event that a branch point associated with a second level of the hierarchical data structure is encountered:
- store, inside a user allocated data structure, marker data that includes location information describing the location the branch point was encountered within the hierarchical data structure and excludes at least one of the following:
- a return address, a parameter, or a local variable associated with a function call;
- and
- use the marker data stored in the user allocated data structure to enable any elements in the second level and any remaining elements in the first level to be processed without recursion, by:
- processing any elements in the second level associated with the branch point without making a recursive function call;
- retrieving the marker data upon completion of processing elements in the second level;
- and
- using the marker data to resume processing in the first level of the hierarchical data structure at the location with which the marker data is associated;
- and
- a memory configured to store the user allocated data structure.
A computer program product for traversing hierarchical data structure, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:
- processing elements inside the hierarchical data structure beginning at a first level of the hierarchical data structure;
- and
- in the event that a branch point associated with a second level of the hierarchical data structure is encountered:
- storing, inside a user allocated data structure, marker data that includes location information describing the location the branch point was encountered within the hierarchical data structure and excludes at least one of the following:
- a return address, a parameter, or a local variable associated with a function call;
- and
- using the marker data stored in the user allocated data structure to enable any elements in the second level and any remaining elements in the first level to be processed without recursion, comprising:
- completing the processing of elements in the first level that are not branch points prior to processing the branch point;
- retrieving the marker data;
- and
- using the marker data to process any elements associated with the branch point.
Dependencies are inferred from the claim text.