Browse Prior Art Database

"Variable Paged Array" Datatype

IP.com Disclosure Number: IPCOM000113055D
Original Publication Date: 1994-Jul-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 138K

Publishing Venue

IBM

Related People

Chapman, K: AUTHOR

Abstract

The idea minimizes both storage and access time overhead for dynamic data storage. The "variable paged array" datatype is a dynamically allocated collection of data objects whose type is defined by the implementer of the array. The overall structure is a singly linked list. However, the data stored at each node in the list is an array of data elements, rather than a single data element. Each array can be thought of as a "page" in the data structure (as the term is used for virtual memory). However, the size of each page is determined by its position in the linked list. Specifically, given a size for the array in the first node in the linked list, each array contains a user specified fraction of more elements than its predecessor in the list. For purposes of discussion, a growth factor of 50% is used.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 39% of the total text.

"Variable Paged Array" Datatype

      The idea minimizes both storage and access time overhead for
dynamic data storage.  The "variable paged array" datatype is a
dynamically allocated collection of data objects whose type is
defined by the implementer of the array.  The overall structure is a
singly linked list.  However, the data stored at each node in the
list is an array of data elements, rather than a single data element.
Each array can be thought of as a "page" in the data structure (as
the term is used for virtual memory).  However, the size of each page
is determined by its position in the linked list.  Specifically,
given a size for the array in the first node in the linked list, each
array contains a user specified fraction of more elements than its
predecessor in the list.  For purposes of discussion, a growth factor
of 50% is used.

      In normal use, the variable paged array is initially allocated
with a single node storing some small-sized array of elements.  When
more storage is required, new nodes are added one at a time (with
larger and larger arrays of elements) until enough room is allocated.

      There are two main advantages to this hybrid structure.  First,
since a linked list is used, more memory can be allocated without
reallocating the entire structure (requiring that all existing data
be copied into the new structure).  Secondly, the increasing number
of elements stored at each node in the list keeps the number of nodes
in the list small in comparison to a linked list of single elements
or even a linked list of constant-sized arrays.  This structural
advantage minimizes both the access time and memory overhead problems
normally associated with linked list structures.

      The primary disadvantage of the variable paged array datatype
is that as more nodes are allocated in the linked list, the amount of
additional storage allocated for each increase gets very large.  A
request for just one more element could involve the allocation of an
unacceptably large amount of space.  It should be noted, however,
that the impact of this problem is limited by the fact that, as the
structure grows, the amount of space allocated for each new node is
approximately 50% of the total previously-allocated space (different
growth factors will influence this amount).  This behavior guarantees
that as the data structure grows, it is always at least two thirds
full.

      In the language C++, this datatype can be implemented to appear
as an ordinary array, so that it hides from the user of the datatype
all details of the allocation of memory and traversal of the linked
list to locate a specific element.  The appearance to the user is of
an unlimited array (of any specified datatype) that needs neither
allocation nor deallocation.  Attached is a fully documented C++
implementation which can be easily used to store any datatype.  Also
attached is a simple program which uses a variable paged array of
c...