Patent ID: 6366996
Filing Date: 2002-04-02
Classification: G06F

Abstract:
A method of finding, within K clock cycles in a system having X hardware clock cycles where K is a power of two less than X, a next free page contained within an N page memory, comprising:(a) providing a UF Table containing a total of N bits, each one of said bits having either: (i) a value of zero to indicate that a corresponding one of said pages is in use; or, (ii) a value of one to indicate that said corresponding page is free for use; (b) dividing said UF Table into K separate entries, each of said entries containing M=N/K bits; (c) upon receipt of a request for said next free page, sequentially examining said UF Table bits to detect a first one of said bits having a value of one while incrementing a counter value by one after examining each one of said UF Table bits; (d) if one of said bits having a value of one is detected, providing an output value by concatenating said counter value with a bit position value representative of the position of said detected bit within said UF Table entry corresponding to said counter value; and, (e) if no one of said bits having a value of one is detected, providing an error indication as said output value.