Method of memory management

Claim 2

The method according to claim 1 further comprising the steps: allocating a second memory block from a given memory block represented by a given leaf element of said tree structure and partitioning the remaining portion of said given memory block into a second plurality of free memory blocks; associating said second memory block and said second plurality of free memory blocks in a subtree structure wherein said first memory block is represented by a root element of said subtree structure marked as representing an allocated memory block, and wherein said plurality of free memory blocks are represented by leaf element descendants of said subtree root element, each of said last mentioned leaf elements being marked as representing a free memory block; and substituting in said tree structure said subtree structure for said given leaf element.

Claim 3

The method according to claim 2 further comprising the steps: deallocating a given memory block of said computer memory by locating a corresponding element of said tree structure and marking said corresponding tree structure element as representing a free memory block; inspecting descendants of said located corresponding tree structure element; if all descendants of said located corresponding tree structure element are leaf elements, removing from said tree structure a subtree structure having said located corresponding tree structure element as its root element and replacing said last mentioned subtree structure with a new leaf element marked as representing a free memory block corresponding to memory represented by said last mentioned subtree structure.

Claim 4

The method according to claim 3 further comprising the step of inspecting within said tree structure the siblings of said new leaf element and if all such siblings are leaf elements then removing from said tree structure a subtree structure having as its root element the parent of said last mentioned leaf element siblings and replacing therefor a leaf element marked as representing available memory corresponding to the memory represented by said last mentioned subtree structure.

Claim 5

The method according to claim 1 wherein said step of allocating a first memory block of said computer memory and partitioning the remaining portion of said computer memory comprises the step of selectively partitioning such remaining portion to maximize selected dimensions of ones of said plurality of free memory blocks.

Claim 6

The method according to claim 5 wherein said remaining portions are partitioned to maximize selected dimensions of said plurality of free memory blocks relative to the dimensions of said computer memory.

Claim 7

The method according to claim 6 wherein said computer memory is memory having dimensions Xs, Ys and Zs, and said step of selectively partitioning comprises the steps: receiving an allocation request for a block of memory having dimensions Xa, Ya and Za; partitioning said computer memory into three contiguous major blocks each having a first two of its X, Y and Z dimensions equal to corresponding dimensions of said computer memory, a first major block having a remaining one of its X, Y and Z dimensions the corresponding one of dimensions Xa, Ya and Za; partitioning the first major block into five minor blocks, the first minor block having X, Y and Z dimensions equal to Xa, Ya and Za, respectively, the second and third minor blocks having one of said first two dimensions equal to the corresponding one of dimensions Xs, Ys and Zs, the fourth and fifth minor blocks occupying the remainder of said computer memory; and allocating the first minor block in response to said allocation request.

Claim 8

The method according to claim 1 wherein at least one of said plurality of memory blocks is a null memory block.

Claim 10

The method according to claim 9 further comprising the steps: allocating a second memory block from a given memory block represented by a given leaf element of said tree structure marked as representing free memory and partitioning the remaining portion of said given memory block into a second plurality of free memory blocks; associating said second memory block and said second plurality of free memory blocks with corresponding tree structure leaf elements attached as descendent to said given leaf element, said leaf element corresponding to said second memory block being marked as representing an allocated memory block, said leaf elements corresponding to said second plurality of memory blocks being marked as representing free memory;

Claim 11

The method according to claim 10 further comprising the steps: deallocating an identified memory block of said computer memory by locating a corresponding tree structure leaf element and marking said corresponding tree structure element as representing free memory; inspecting within said tree structure siblings of said leaf element corresponding to said identified memory block and if all siblings thereof represent free memory space then removing such sibling from said tree structure and marking the parent tree structure element as representing free memory.

Claim 12

The method according to claim 9 wherein said step of allocating a first memory block of said computer memory and partitioning the remaining portion of said computer memory comprises the step of selectively partitioning such remaining portion to maximize selected dimensions of ones of said plurality of free memory blocks.

Claim 13

The method according to claim 12 wherein said remaining portions are partitioned to maximize selected dimensions of said plurality of free memory blocks relative to the dimensions Xs, Ys and Zs.

Claim 14

The method according to claim 13 wherein said computer memory is a memory having dimensions Xs, Ys and Zs, and said step of selectively partitioning comprises the steps: receiving an allocation request for a block of memory having dimensions Xa, Ya and Za; partitioning said computer memory into three contiguous major blocks each having a first two of its X, Y and Z dimensions equal to corresponding dimensions of said computer memory, a first major block having a remaining one of its X, Y and Z dimensions the corresponding one of dimensions Xa, Ya and Za; partitioning the first major block into five minor blocks, the first minor block having X, Y and Z dimensions equal to Xa, Ya and Za, respectively, the second and third minor blocks having one of said first two dimensions equal to the corresponding one of dimensions Xs, Ys and Zs, the fourth and fifth minor blocks occupying the remainder of said computer memory of dimensions Xs, Ys and Zs; and allocating the first minor block in response to said allocation request.

Claim 15

The method according to claim 9 wherein at least one of said plurality of memory blocks is a null memory block.

Claim 17

The method according to claim 16 further comprising the step of associating said blocks, said associating step comprising representing the first minor block as a root element of a tree structure and associating each of the second and third major blocks and each of the second, third, fourth and fifth minor blocks with representative corresponding leaf elements as dependents of said root element.

Claim 18

The method according to claim 17 wherein said leaf elements are siblings within said tree structure, each being a direct descendent of said root element.

Claim 19

The method according to claim 16 further comprising the step of associating said blocks, said associating step comprising representing said free memory space as a root element of a tree structure and attaching leaf element descendants thereto each corresponding to one said second and third major blocks and said minor blocks.

Claim 20

The method according to claim 19 wherein said leaf elements are siblings within said tree structure, each being a direct descendant of said root element.

Claim 21

The method according to claim 20 further comprising the step of marking the leaf element corresponding to said allocated memory block as representing allocated memory, and marking the remaining leaf elements as representing free memory.

Claim 22

The method according to claim 16 wherein at least one of said major and minor blocks is a null block.