Patent ID: 9116625
Filing Date: 2015-08-25
Classification: G06F

Abstract:
1. A method for write command overlap detection in a memory system, comprising: creating a tree data structure comprising a first number of nodes, each of the first number of nodes being associated with a starting logical address and/or an ending logical address of a write command in a queue of write commands, wherein the tree data structure is created in response to the number of write commands in the queue reaching a first threshold number; placing a second number of nodes associated with a starting logical address and/or an ending logical address of an incoming write command in the tree data structure; comparing a node of the second number of nodes that is associated with a starting logical address of the incoming write command to an in-numerical-order predecessor node of the first number of nodes; comparing the node of the second number of nodes that is associated with a starting logical address of the incoming write command to an in-numerical-order successor node of the first number of nodes; comparing a node of the second number of nodes that is associated with an ending logical address of the incoming write command to an in-numerical-order successor node of the first number of nodes; removing the placed second number of nodes associated with the starting logical address and/or the ending logical address of the incoming write command from the tree data structure in response to the logical address of the incoming write command overlapping with a logical address of a write command in the queue; placing the incoming write command in the queue if the in-numerical-order predecessor node is an end node or a start/end node, the in-numerical-order successor node of the node associated with the starting logical address of the incoming write command is the node associated with the ending logical address of the incoming write command, and the in-numerical-order successor node of the node associated with the ending logical address is a start node or a start/end node; executing a portion of the number of command in the queue; and discontinuing use of the tree data structure and performing a linear comparison of the number of write commands in the queue in response to the number of write commands in the queue reaching a second threshold number.