Patent ID: 7209482

Claim:
A reordering device comprising: a reorder buffer configured to store information relating to data items, each of the data items being associated a sequence number chosen from a sequence number space, the sequence number indicating a relative order of the data items; a reorder buffer pointer configured to store a value indicating a rearmost active entry of the reorder buffer relative to the sequence number space; and a reorder engine configured to receive the data items, the reorder engine classifying each of the received data items based on the sequence number of the data item and the value of the reorder buffer pointer, the reorder engine determining whether to store the information relating to the received data items in the reorder buffer based on the classification, the classification using a plurality of regions including a first region corresponding to the sequence number of the data item falling within a sequence number range covered by the reorder buffer, and a second region corresponding to the sequence number of the data item falling within a sequence number range extending from a head of the reorder buffer to a predetermined range beyond the head of the reorder buffer, wherein when the reorder engine classifies the data item as belonging to the second region, the reorder engine shifts the value in the reorder buffer pointer to create a shifted version of the reorder buffer, and invalidates the data items that are no longer in the shifted version of the reorder buffer.