Device for storage and retrieval of compact contiguous tree index records

Claim 1

In a data-processing system, a method executed by a data processor for fetching the size of an allocated contiguous section of memory, by decoding a sequence of bitmaps, said sequence of bitmaps located adjacent to a boundary of said section of memory, each of said bitmaps containing information describing whether that bitmap is last or not last in its sequence of bitmaps, each of said bitmaps containing information describing a length number, said method employing a radix number constant, said method comprising the steps of: (a) designating a bitmap adjacent to a boundary of said section of memory to be the current bitmap, then fetching said length number information contained within said current bitmap, initializing a multiplier number to one, initializing an accumulator number to zero, proceeding to step b, (b) multiplying said length number by said multiplier number and adding the result to an accumulator number, proceeding to step c, (c) reading the current bitmap to see whether or not the current bitmap is last in its sequence, then if the current bitmap is last in its sequence, proceeding to step d, otherwise proceeding to step f, (d) designating the next bitmap in said sequence to be the current bitmap, proceeding to step e, e) reading said current bitmap to fetch said length number information contained within, multiplying said multiplier number by said radix number, proceeding to step b, (f) returning the accumulator number as the size of said section.

Claim 9

The method of claims 1, 2, 3, 4, 5, 6 or 7 wherein said size of an allocated contiguous section of memory is fetched as part of a method to fetch the sibling address of the next higher sibling address among sibling sections of memory stored within a data tree, said method to fetch a sibling address employing bitmaps each containing information describing whether that bitmap is part of a sequence of bitmaps of the higher or the lower boundary of a section of allocated memory, in addition to the information describing whether that bitmap is last or not last in its sequence of bitmaps, and in addition to the information describing its length number, said method to fetch the address of a next higher sibling section comprising the steps of: (a) starting with a current address pointing to a bitmap adjacent to the lowest boundary of the current section of allocated memory allocated, proceeding to step b, (b) fetching the size of the current section of memory, using said size as an offset to said current address to calculate the address of the highest boundary of the current section of memory, proceeding to step c, (c) setting said current address to point to a bitmap adjacent to and higher than the highest boundary of the current section of memory, proceeding to step d, (d) reading said bitmap to see if it is part of a sequence of bitmaps of the higher or lower boundary of an allocated section of memory, proceeding to step e, (e) if said bitmap is part of a sequence of bitmaps of the higher boundary, proceeding to step f, otherwise returning said current address as the address of the lower boundary of the next higher sibling branch, (f) returning information to indicate that there is no higher sibling branch.

Claim 13

The method of claims 1, 2, 3, 4, 5, 6 or 7 wherein said size of an allocated contiguous section of memory is fetched as part of a method to fetch the sibling address of the next lower sibling address among sibling sections of memory stored within a data tree, said method to fetch a sibling address employing bitmaps each containing information describing whether that bitmap is part of a sequence of bitmaps of the higher or the lower boundary of a section of allocated memory, in addition to the information describing whether that bitmap is last or not last in its sequence of bitmaps, and in addition to the information describing its length number, said method to fetch the address of a next lower sibling section comprising the steps of: (a) starting with a current address pointing to a bitmap adjacent to the highest boundary of the current section of allocated memory allocated, proceeding to step b, (b) fetching the size of the current section of memory, using said size as an offset to said current address to calculate the address of the lowest boundary of the current section of memory, proceeding to step c, (c) setting said current address to point to a bitmap adjacent to and lower than the lowest boundary of the current section of memory, proceeding to step d, (d) reading said bitmap to see if it is part of a sequence of bitmaps on the higher or lower boundary of an allocated section of memory, proceeding to step e, (e) if said bitmap is part of a sequence of bitmaps of the lower boundary, proceeding to step f, otherwise returning said current address as the address of the higher boundary of the next lower sibling branch, (f) returning information to indicate that there is no lower sibling branch.

Claim 16

The method of claims 8, 4, 5, 12, 13 or 14 wherein a set of integer values stored in said bitmaps is mapped using a lookup table, so that each of said integer values is mapped to a description for that bitmap of whether that bitmap is part of a sequence of bitmaps of the higher or of the lower boundary of a section of allocated memory.

Claim 18

The method of claims 9 or 13 wherein said supplemental section is used to store supplemental reserve memory, so that memory can be allocated locally by moving memory from said supplemental reserve memory to sibling level sections, and so that memory can be de-allocated locally by moving memory from said sibling level sections to said supplemental reserve memory.

Claim 19

The method of claims 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16 or 17 wherein bitmaps said to be adjacent to each other are positioned close together but not contiguously next to each other, or where bitmaps said to be adjacent to allocated sections of memory are positioned close to but not contiguously next to such allocated sections of memory, so that bitmaps can have memory addresses consistent with memory allocation boundaries or consistent with memory allocation offsets required by the data processing system in which they reside.