Method and apparatus for controlling access to trie data structure
OwnerWunBae JEONinventor
Life of this patent
Estimating the term…
Abstract
A technology for controlling an access of a trie by managing node access permissions of processes that access a trie data structure and perform an operation is disclosed. Example embodiments include accessing a window initiating node in a trie, determining whether a next node is an anchor node while visiting lower nodes of the window initiating node in a predetermined traversal order, locking the next node when the next node is an anchor node, releasing a lock of the window initiating node when the window initiating node is an anchor node, and setting the next node as the window initiating node.
Claims20
A method for controlling an access to a trie data structure through an iteration operation that processes at least one window, the method comprising
- accessing, by at least one process driven by a processor, a window initiating node in a trie;
- and
- determining, by the process, whether a next node is an anchor node, while visiting lower nodes of the window initiating node in a predetermined traversal order,
- wherein, when the next node is an anchor node, the method comprises
- locking, by the process, the next node;
- releasing, by the process, a lock of the window initiating node, when the window initiating node is an anchor node;
- and
- setting, by the process, the next node as the window initiating node.
A method for controlling an access to a trie data structure through an iteration operation, the method comprising
- determining, by at least one process driven by a processor, an area type to which a next node belongs among a plurality of area types predetermined for the iteration operation;
- requesting, by the process, a lock on the next node;
- accessing, by the process, the next node, in response to acquiring the lock;
- performing, by the process, a leaf check of the next node depending on the area type;
- and
- performing, by the process, a lower edge scan of the next node, based on a scan range depending on the area type,
- wherein, when the next node is an anchor node, an upper lock is released while the lock is maintained, and when the next node is not an anchor node, the lock is released while the upper lock is maintained.
Dependencies are inferred from the claim text.