Memory management of striped pipelined data structures

Apparatus for maintaining a set of entries in a set of memory stages each including a set of cell blocks, said apparatus including

• means for maintaining at least one invariant condition for said set of cell blocks in said memory stages, said invariant condition defining a selected number of available entries for allocation within a selected one of said cell blocks;
• means for selecting of a sub-bucket defined using said cell blocks, said selected sub-bucket including said selected one cell block;
• means for allocating of new entries in said selected one cell block;
• and
• wherein said invariant condition includes having exactly one cell block marked sparse for each said memory stage defined for said sub-bucket.

Memory or mass storage including instructions interpretable by a computer or circuit to maintain a set of entries in a set of memory stages each including a set of cell blocks, including instructions to

• maintain at least one invariant condition for said set of cell blocks in said memory stages, said invariant condition defining a selected number of available entries for allocation within a selected one of said cell blocks;
• select a sub-bucket defined using said cell blocks, said selected sub-bucket including said selected one cell block;
• allocate new entries in said selected one cell block;
• and
• wherein said invariant condition includes having exactly one cell block marked sparse for each said memory stage defined for said sub-bucket.

Apparatus for maintaining a set of entries in a set of memory stages each including a set of cell blocks, said apparatus including

• a first circuit responsive to at least one invariant condition for said set of cell blocks in said memory stages, said invariant condition defining a selected number of available entries for allocation within a selected one of said cell blocks;
• a second circuit capable of selecting a sub-bucket defined using said cell blocks, said selected sub-bucket including said selected one cell block, said second circuit being responsive to an output of said first circuit;
• a third circuit capable of allocating new entries in said selected one cell block, said third circuit being responsive to an output of said second circuit;
• and
• wherein said invariant condition includes having exactly one cell block marked sparse for each said memory stage defined for said sub-bucket.