The design of a template structure for a generalized data structure definition facility

A template structure capable of defining the runtime configuration of general data structures, e.g. arrays (homogeneous and non-homogeneous), cells, stacks, queues, trees, and general lists (graphs), for a generalized data structure definition facility that has practical utility in applications where thousands of data structures can be in existence at any given time is described. An important aspect of this template structure organization is that like instances of a data structure allocated at runtime share a common template rather than each allocated instance of a data structure having its own individual template. The motivation for sharing templates is derived from the fact that large numbers of data structures can be active at runtime, and templates can occupy a considerable amount of storage (in some instances a template can occupy as much or more storage than the data structure elements themselves). The importance of template sharing in a paging system, and the capability of the template structure for facilitating the design and implementation of general operations such as insert and delete are discussed.