Browse Prior Art Database

A method for quick and scalable access to a widely varying number of array elements. Disclosure Number: IPCOM000016790D
Original Publication Date: 2003-Jul-15
Included in the Prior Art Database: 2003-Jul-15
Document File: 4 page(s) / 76K

Publishing Venue



Disclosed is an array tree hierarchy which grows by cloning its level members, while maintaining fast access to each array element via a context that allows consistent traversal of the tree in just a few linkages.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 4

  A method for quick and scalable access to a widely varying number of array elements.

Many of today's software programs require addressability to a wide number of target entities such as scattered memory blocks. These memory blocks have addresses that can be used to identify and access them, and they are generally grouped into categories via linked lists and/or arrays. When passing the address of such a memory block between programs, however, especially within an operating system's low level kernel, the address may become invalidated, and the act of touching that address may cause catastrophic results such as a crash of the machine. To offset this situation, it is common to validate the address prior to use, without actually accessing the address. This requires that a context other than the actual address be used to identify the memory block. Such a context must be accessible even when the memory block it identifies is no longer valid. One such context that has the most direct binding is a simple index into an array of target addresses. Setting the size of such an array, however, becomes difficult when attempting to predetermine how many memory blocks will eventually need to be addressed. For that reason, a default size for the array is generally created at initialization, which then grows as additional memory blocks are added. As growth continues, however, another issue occurs. If the array is expanded by copying into a larger address space, the act of copying the original array contents hurts performance and duplicates resources. If instead the original array is linked to form a list of arrays, the subsequent accesses into the array list become progressively slower due to the linear traversal of the linkages between the arrays.

A solution is to use an array tree hierarchy which grows by cloning its array level members, but maintains fast access to each array element by defining the context to each target address to be a hybrid set of indexes that can consistently traverse the tree hierarchy in just a few links.

Suppose for example that the default array size is 256 and the maximum number of expected elements in the array is one million. The context can then be an index into a 1st level array which contains pointers of up to 256 2nd level arrays, each containing up to 256 3rd Level arrays, which contain up to 256 target memory block addresses. The actual maximum addressable target control blocks in this case is 16.8 million, which can easily contain the example requirement of one million. The array levels needed at initialization are then: a single 1st level array, a single 2nd level array, and a single 3rd level array as illustrated in Figure 1:


Page 2 of 4

Figure 1

The context for the first memory block can be derived by grouping the individual 8-bit array indexes of each array level into the lower order 24 bits of a single 32 bit integer as illustrated in Figure 2:

Figure 2

So the value of the first memory block'...