Device for storage and retrieval of compact contiguous tree index records

• US 5,829,004 A
• Filed: 05/20/1996
• Issued: 10/27/1998
• Est. Priority Date: 05/20/1996
• Status: Expired due to Term

• Current Assignee: Chartoleaux KG LLC (Intellectual Ventures LLC)
• Original Assignee: Lawrence Au
• Inventors: Au, Lawrence
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/650,945
• Time in Patent Office: 890 Days
• Field of Search: 707/3, 707/2, 707/100, 707/101, 711/117, 711/173
• US Class Current: 711/173
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and methods for allocating and traversing tree structured data in contiguous portions of memory by encapsulating lower level subtrees within the memory allocated for their higher level parent trees. These encapsulated memory allocations are encoded with length descriptors at both lowest and highest ends in memory, so that allocated subtrees can be retrieved or skipped when scanning allocated subtrees in either lowest-to-highest or highest-to-lowest directions in memory. The length descriptors themselves are allocated variable amounts of memory by allocating additional multiplier bits to describe larger lengths. Smaller lengths can be described with a smaller number of bits. There is no limit to the size of length which can be described. Extra reserve memory may be allocated within some subtrees to localize the allocation of memory within those subtrees.

Claims

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.

2. The method of claim 1 wherein said accumulator number is initialized to a non-zero number in step a.

3. The method of claim 1 wherein said multiplier number is initialized to a number other than one in step a.

4. The method of claim 1 wherein said multiplier number is fetched from a table indexed by the number of times step b has been performed.

5. The method of claim 1 wherein the multiplication operation on said length number is replaced by a shift-left or shift-right operation on the bits representing said length number.

6. The method of claim 1 wherein the radix number is fetched from a table indexed by the number of times step b has been performed.

7. The method of claim 1 wherein a set of integer values stored in each said bitmap is mapped using a lookup table, so that each of said integer values is mapped to a length number for that bitmap and each of said integer values is mapped to a description for that bitmap of whether that bitmap is last or not last in its sequence of bitmaps.

8. 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.

9. The method of claim 8 wherein supplemental information descriptive of a sequence of sibling sections within said data tree is stored in a supplemental section on the highest end of said sequence of sibling sections, so that in operations to fetch the next higher sibling said supplemental section must not be considered as a sibling, but rather skipped over unless said supplemental information is specifically to be retrieved.

10. The method of claim 8 or 9 wherein in step f, information to indicate that there is no higher sibling branch is returned along with said address of said higher boundary of memory found by step e.

11. The method of claim 10 wherein the sibling address of a next lower sibling section within a stored tree is fetched as part of a method to fetch the address of an enclosing section of memory representing a parent node within a stored data tree, said method employing a lowest bound address number describing the lowest address of data stored in said stored tree, said method to acquire the address of an enclosing section of memory comprising the steps of:

(a) starting with a current address pointing to a bitmap adjacent to the lowest boundary of the current section of memory allocated, proceeding to step b,

(b) fetching the next lower sibling until no more siblings are found, so that said current address is set to point to a bitmap lower than and adjacent to the lowest sibling section of memory, proceeding to step c,

(c) comparing said current address to said lowest bound address, and if said current address is lower, proceeding to step f, otherwise proceeding to step d,

(d) reading the bitmap pointed to by said current address to see if it is part of a sequence of bitmaps of the higher or lower boundary of an allocated section of memory, and if it is of the lower boundary of an allocated section of memory, proceeding to step g, otherwise proceeding to step e,

(e) setting said current address to point to the next lower adjacent bitmap in memory, proceeding to step c,

(f) returning information to indicate that there is no enclosing section of memory,

(g) setting said current address to point to the next higher adjacent bitmap in memory, then returning said current address as the address of the lower boundary of the enclosing section of memory.

12. 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.

13. The method of claim 12 wherein supplemental information descriptive of a sequence of sibling sections within said data tree is stored in a supplemental section on the lowest end of said sequence of sibling sections, so that in operations to fetch the next lower sibling said supplemental section must not be considered as a sibling, but rather skipped over unless the supplemental information is specifically to be retrieved.

14. The method of claim 12 or 13 wherein in step f, information to indicate that there is no lower sibling branch is returned along with said address of said lower boundary of memory found by step e.

15. 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.

16. The method of claim 14 wherein the sibling address of a next higher sibling section within a stored tree is fetched as part of a method to fetch the address of an enclosing section of memory representing a parent node within a stored data tree, said method employing a highest bound address number describing the highest address of data stored in said stored tree, said method to acquire the address of an enclosing section of memory comprising the steps of:

(a) starting with a current address pointing to a bitmap adjacent to the lowest boundary of the current section of memory allocated, proceeding to step b,

(b) fetching the next higher sibling until no more siblings are found, so that said current address is set to point to a bitmap higher than and adjacent to the highest sibling section of memory, proceeding to step c,

(c) comparing said current address to said highest bound address, and if said current address is higher, proceeding to step f, otherwise proceeding to step d,

(d) reading the bitmap pointed to by said current address to see if it is part of a sequence of bitmaps of the higher or lower boundary of an allocated section of memory, and if it is of the lower boundary of an allocated section of memory, proceeding to step g, otherwise proceeding to step e,

(e) setting said current address to point to the next higher adjacent bitmap in memory, proceeding to step c,

(f) returning information to indicate that there is no enclosing section of memory,

(g) setting said current address to point to the next lower adjacent bitmap in memory, then returning said current address as the address of the higher boundary of the enclosing section of memory.

17. 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.

18. 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.