Patent ID: 7536395

Claim:
A compact circuit for reversing a linked list of a plurality of nodes to produce a reversed linked list, the circuit comprising: a decoder for sequentially decoding a plurality of tags to produce a plurality of decoded values; an array for storing the plurality of decoded values; the array receiving the plurality of decoded values one at a time and storing each received one of the plurality of decoded values in a next empty row within the array; a dynamic precharge circuit for reading selected bit values from each one of a plurality of columns of the array to simultaneously generate each one of a plurality of nodes of the reversed linked list; a first circuit comprising: a plurality of first transistors, each one of the plurality of first transistors for receiving one of a plurality of bits from each one of a plurality of columns of the array; the plurality of first transistors used to generate a first logical OR output and a logical OR signal; and the first logical OR output being a first bit of an output; a precharge transistor for receiving a precharge signal, the first circuit being precharged responsive to the precharge signal being asserted, wherein the first circuit does not output the logical OR signal when the precharge signal is asserted; a read enable transistor for receiving a read enable signal, the first circuit outputting the logical OR signal responsive to the read enable signal being asserted and the precharge signal being de-asserted; and a second circuit that includes; a plurality of second transistors, each one of the plurality of second transistors for receiving one of the plurality of bits from each one of the plurality of columns of the array; the plurality of second transistors used to logically OR the received ones of the plurality of bits together to generate a second logical OR output; and the second logical OR output being a second bit of an output tag.