Browse Prior Art Database

Allocation Scheme for Extendible Arrays of Bounded Size

IP.com Disclosure Number: IPCOM000085141D
Original Publication Date: 1976-Feb-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 26K

Publishing Venue

IBM

Related People

Stockmeyer, LJ: AUTHOR

Abstract

A method for the allocation of storage for 2-dimensional arrays is described. The method is easily extendible, moderate in storage requirements, and computationally tractable. The advantages of this allocation scheme over previous schemes are manifest in situations where a matrix (or table) is being built in a step-by-step fashion by successive catenation of new rows and/or columns, the shape of the final matrix is not known beforehand, but an upper bound on the size (i.e., the number of positions) of the final matrix is known beforehand.

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 56% of the total text.

Page 1 of 3

Allocation Scheme for Extendible Arrays of Bounded Size

A method for the allocation of storage for 2-dimensional arrays is described. The method is easily extendible, moderate in storage requirements, and computationally tractable. The advantages of this allocation scheme over previous schemes are manifest in situations where a matrix (or table) is being built in a step-by-step fashion by successive catenation of new rows and/or columns, the shape of the final matrix is not known beforehand, but an upper bound on the size (i.e., the number of positions) of the final matrix is known beforehand.

An array A of shape <M,N> is viewed as the set of positions:

{ (I,J) 3 0 </- I < M and 0 </- J < N }; the size of A is MúN.

For a given (declared) positive integer p, the scheme allocates storage for any array A of size p or less, irregardless of the shape of A. Similar to References 1, 3, the allocation scheme associates with a given array A a base address BASE(A) and a displacement function D(p) depending only on the given
p. The location assigned to position A(I,J) is then BASE(A) + D(p)(I,J).

For a given p, the function D(p) is specified as follows:

Let k = * log(2)p and c = 2p/2/k/. (* is the APL ceiling function.)(*

(Image Omitted)

)

Then,

D(p)(I,J) = J + * cúREV(k)(I). (*

(Image Omitted)

)

REV(k)(I) is the integer with binary representation b(0)b(1)...b(k - 1), where b(k - 1)...b(1)b(0) is a binary representation of I.

The APL flow chart for the function D(p) is shown in the figure.

The main advantage of the described allocation scheme over previous schemes is that it is simultaneously:

(i) Easily extendible within the limits imposed by the size bound p, (i.e., if an array B is extended to an array A by adjoining new rows and/or columns to B in ...