Memory management system and method

Abstract

The memory management system ( 20 ) includes a transform generator ( 22 ) capable of generating an address ( 28 ) and a confirmer ( 30 ) from a key. A controller ( 24 ) is connected to the transform generator ( 22 ) and sends the key to the transform generator ( 22 ) and receives the address ( 28 ) and the confirmer ( 30 ). A store ( 26 ) is connected to the controller ( 24 ) and has a plurality of addresses ( 28 ), each of the plurality of addresses ( 28 ) has a confirmer location ( 30 ), a forward pointer location ( 34 ), a primary flag ( 36 ), an allocated flag ( 38 ) and an association location ( 32 ).

What is claimed is:  
     
         1 . A method of operating a memory management system, comprising the steps of: 
 (a) specifying a store having a plurality of addresses;    (b) defining a confirmer location for each of the plurality of addresses;    (c) defining a forward pointer location for each of the plurality of addresses;    (d) entering a forward address pointer in the forward pointer location for each of the plurality of address;    (e) defining a primary flag for each of the plurality of addresses;    (f) defining an allocated flag, for each of the plurality of addresses;    (g) defining an association for each of the plurality of address; and    (h) entering a reverse address pointer in a free location for each of the plurality of addresses.    
     
     
         2 . The method of  claim 1 , further including the steps of: 
 (i) receiving a key for storage;    (j) performing a transform on the key to determine one of the plurality of addresses and a confirmer;    (k) determining if the allocated flag is set for the one of the plurality of addresses;    (l) when the allocated flag is not set, moving to a reverse address indicated by the reverse pointer address;    (m) updating the forward pointer address at the reverse address to equal the forward pointer address at the one of the plurality of addresses.    
     
     
         3 . The method of  claim 2 , further including the steps of: 
 (n) moving to a forward address indicated by the forward pointer address;    (o) updating the reverse pointer address at the forward address to equal the reverse pointer address at the one of the plurality of addresses.    
     
     
         4 . The method of  claim 3 , further including the steps of: 
 (p) entering the confirmer for the key at the confirmer location for the one of the plurality of addresses;    (q) setting the forward pointer address at the one of the plurality of addresses to the one of the plurality of addresses;    (r) setting the allocated flag for the one of the plurality of addresses;    (s) setting the primary flag for the one of the plurality of addresses.    
     
     
         5 . The method of  claim 2 , further including the steps of: 
 (n) when the allocated flag is set for the one of the plurality of addresses, determining if the primary flag is set for the one of the plurality of addresses;    (o) when the primary flag is set, moving to a next address;    (p) determining if the allocated flag is set at the next address;    (q) when the allocated flag is not set, entering the confirmer in the confirmer location of the next address;    (r) setting the forward pointer address of the next address equal to the one of the plurality of addresses;    (s) setting the allocated flag at the next address.    
     
     
         6 . The method of  claim 5 , further including the step of: 
 (t) setting the forward pointer address of the one of the plurality of addresses to the next address.    
     
     
         7 . The method of  claim 5 , wherein step (q) further includes the steps of: 
 (q1) moving to a reverse address indicated by the reverse pointer address of the next address;    (q2) updating the forward pointer address at the reverse address to equal the forward pointer address at the next address.    (q3) moving to a forward address indicated by the forward pointer address of the next address;    (q4) updating the reverse pointer address at the forward address to equal the reverse pointer address at the next address.    
     
     
         8 . The method of  claim 5 , further including the steps of: 
 (t) when the primary flag is not set for the one of the plurality of addresses, finding a free address;    (u) moving a first confirmer from the one of the plurality of addresses to the confirmer location of the free address;    (v) setting the forward pointer of the free address equal to the forward pointer for the one of the plurality of addresses;    (w) setting the allocated flag for the free address.    
     
     
         9 . The method of  claim 8 , further including the steps of: 
 (x) entering the confirmer in the confirmer location of the one of the plurality of addresses;    (y) setting the forward pointer of the one of the plurality of addresses equal to the one of the plurality of addresses;    (z) setting the primary flag.    
     
     
         10 . A memory management system comprising: 
 a transform generator capable of generating an address and a confirmer from a key;    a controller connected to the transform generator and sending the key to the transform generator and receiving the address and the confirmer; and    a store connected to the controller has a plurality of addresses, each of the plurality of addresses having a confirmer location, a forward pointer location, a primary flag, an allocated flag and an association location.    
     
     
         11 . The memory management system of  claim 10 , wherein a free list of addresses includes a reverse pointer in one of the confirmer location, the association location or primary flag of each of the free list of addresses and a forward pointer in the forward pointer location of each of the free list of addresses.  
     
     
         12 . The memory management system of  claim 11 , wherein the controller has the transform generator determine a first address and a first confirmer upon receiving a first key.  
     
     
         13 . The memory management system of  claim 12 , wherein the controller determines if an allocated flag is set at the first address when the controller receives a lookup command, when the allocated flag is set, the controller determines if the primary flag is set, comparing the first confirmer to a stored confirmer at the first address, when the first confirmer and the stored confirmer are the same, reading a stored association at the first address.  
     
     
         14 . A method of operating a memory management system, comprising the steps of: 
 (a) receiving a key and a command;    (b) when the command is a lookup command;    (c) determining a lookup confirmer and a lookup address from the key;    (d) determining if an allocated flag is set at the lookup address of a store;    (e) when the allocated flag is set, comparing the lookup confirmer with the stored confirmer at the lookup address; and    (f) when the lookup confirmer and the stored confirmer are a same, reading an association at the lookup address.    
     
     
         15 . The method of  claim 14 , further including the steps of: 
 (g) when the lookup confirmer and the stored confirmer are not the same, moving to a second address pointed to by the forward pointer at the lookup address;    (h) determining if a second confirmer at the second address is the same as the lookup confirmer;    (i) when the second confirmer and the lookup confirmer are the same, reading an association at the second address.    
     
     
         16 . The method of  claim 14 , further including the steps of: 
 (g) when the command is a delete command, determining a delete address and a delete confirmer using the key;    (h) comparing a stored confirmer at the delete address to the delete confirmer;    (i) when the stored confirmer is the same as the delete confirmer, deleting the stored confirmer and the stored association at the delete address.    
     
     
         17 . The method of  claim 16 , further including the steps of: 
 (j) unsetting the allocated flag and the primary flag.    
     
     
         18 . The method of  claim 17 , further including the steps of: 
 (k) searching for a next free address having an unset allocated flag;    (m) setting a forward pointer at the delete address equal to the next free address;    (n) setting the confirmer of the delete address equal to the reverse pointer at the next free address;    (o) setting a confirmer at the next free address equal to the delete address;    (p) moving to a previous free address using the confirmer at the delete address;    (q) setting a forward pointer at the previous address equal to the delete address.    
     
     
         19 . The method of  claim 14 , further including the steps of: 
 (g) when the command is a store command, determining a store address and a store confirmer using the key;    (h) determining if an allocated flag is set at the store address;    (i) when the allocated flag is not set at the store address, storing the store confirmer at a confirmer location for the store address;    (j) storing an association in an association location for the store address;    (k) setting the allocated flag for the store address;    (l) setting the primary flag for the store address.    
     
     
         20 . The method of  claim 19 , further including the step of: 
 (m) setting a forward pointer at the store address equal to the store address.    
     
     
         21 . The method of  claim 20 , wherein step (I) further includes the steps of: 
 (i1) moving to a reverse address indicated by the reverse pointer address at the store address;    (i2) updating the forward pointer address at the reverse address to equal the forward pointer address at the store address;    (i3) moving to a forward address indicated by the forward pointer address at the store address;    (i4) updating the reverse pointer address at the forward address to equal the reverse pointer address at the store address.    
     
     
         22 . The method of  claim 19 , further including the steps of: 
 (m) when the allocated flag is set at the store address, determining if a primary flag is set;    (n) when the primary flag is set, moving to a next free address;    (o) setting a forward pointer at the store address equal to the next free address;    (p) moving to a reverse address pointed to by a reverse address pointer at the next free address;    (q) setting a forward pointer address at the reverse address equal to a forward pointer address at the next free address;    (r) moving to a forward address pointed to by a forward address pointer at the next free address;    (s) setting a reverse pointer address at the forward address equal to a reverse pointer address at the next free address.    
     
     
         23 . The method of  claim 19 , further including the steps of: 
 (t) storing the store confirmer at a confirmer location for the next free address;    (j) storing an association in an association location for the next free address;    (k) setting the allocated flag for the next free address.    
     
     
         24 . The method of  claim 22 , further including the steps of: 
 (t) when the primary flag is not set at the store address, determining a next free address;    (w) moving to the reverse address pointed to by the reverse address pointer at the next free address;    (x) setting the forward pointer address at the reverse address equal to the forward pointer address at the next free address;    (y) moving to the forward address pointed to by the forward address pointer at the next free address;    (z) setting the reverse pointer address at the forward address equal to the reverse pointer address at the next free address.    
     
     
         25 . The method of  claim 24 , further including the steps of: 
 (aa) setting a forward pointer address at the primary address pointed to by the forward pointer address of the store address equal to the next free address;    (ab) setting a confirmer at the next free address equal to a stored-confirm at the store address;    (ac) setting a forward pointer at the next free address equal to the forward pointer address at the store address;    (ad) setting an allocated flag at the next free address.    
     
     
         26 . The method of  claim 25 , further including the steps of: 
 (af) storing a store confirmer in a confirmer location of the store address;    (ag) setting the forward pointer at the store address equal to the store address;    (ah) setting the allocated flag and the primary flag;    (aj) storing the store association in an association location of the store address.    
     
     
         27 . A method of operating a memory management system, comprising the steps of: 
 (a) determining a number of required entries;    (b) selecting a transform having a first number of bits;    (c) determining an address number of bits required to cover all the number of required entries;    (d) setting a forward pointer number of bits equal to the address number of bits; and    (e) setting a confirmer number of bits equal to the first number of bits less the forward pointer number of bits.    
     
     
         28 . The method of  claim 27 , wherein a range of numbers defined by the first number of bits is greater than the number of required entries.  
     
     
         29 . The method of  claim 27 , further including the steps of: 
 (f) entering a forward address pointer in a forward pointer location;    (g) entering a reverse address pointer in a free location.    
     
     
         30 . The method of  claim 29 , further including the step of: 
 (h) defining a primary flag for each of a plurality of address;    (i) defining an allocated flag for each of the plurality of address.    
     
     
         31 . The method of  claim 30 , further including setting, the allocated flag to an unallocated state.  
     
     
         32 . A memory management system comprising: 
 a transform generator capable of generating an address and a confirmer from a key;    a controller connected to the transform generator and sending the key to the transform generator and receiving the address and the confirmer; and    a store having a plurality of addresses, each of the plurality of addresses having a confirmer location, a forward pointer location, a primary flag, and an allocated flag.    
     
     
         33 . The memory management system of  claim 32  wherein a number of address bits is equal to a number of confirmer bits plus a number of forward pointer bits.