Method of managing memory allocation by association of memory blocks with a tree structure

Claim 3

The method according to claim 1 further comprising the steps: allocating a second memory block from a given memory block selected from said plurality of free memory blocks and 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 with a subtree structure wherein said second memory block is represented by a root element of said subtree structure marked as representing an allocated memory block, and wherein said second 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 said subtree structure for said given leaf element in said tree structure.

Claim 4

The method according to claim 2 further comprising the steps: deallocating an identified, allocated 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 to determine whether all descendants of said located corresponding tree structure element are leaf elements; and, 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 first new leaf element marked as representing a free memory block corresponding to memory represented by said last mentioned subtree structure.

Claim 5

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

Claim 6

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 7

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 8

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, each of the dimensions Xa, Ya, and Za being less than or equal to the corresponding one of the dimensions Xs, Ys, and Zs; 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 equal to 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 9

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

Claim 12

The method according to claim 9 further comprising the steps: allocating a second memory block from a given memory block selected from said plurality of free memory blocks and 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 descendant to said given leaf element, the leaf element representing said second memory block being marked as representing an allocated memory block, the leaf elements representing said second plurality of memory blocks being marked as representing free memory.

Claim 13

The method according to claim 10 further comprising the steps: deallocating an identified, allocated 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 representing said identified memory block to determine whether all such siblings represent free memory space; and, if all such siblings represent free memory space, removing all such siblings from said tree structure and marking the parent tree structure element as representing free memory.

Claim 14

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 15

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 dimensions Xs, Ys and Zs of said computer memory.

Claim 16

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, each of the dimensions Xa, Ya, and Za being less than or equal to the corresponding one of the dimensions Xs, Ys, and Zs; 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 equal to 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 17

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

Claim 20

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 representing each of the second and third major blocks and each of the second, third, fourth and fifth minor blocks with leaf elements, said leaf elements being descendants of said root element.

Claim 21

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 22

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 representing one of said second and third major blocks and said minor blocks.

Claim 23

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 24

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 25

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