Allocating Storage for Extendible Arrays

ABSTRACT

Arrays are among the best understood and most widely used data structures. Yet even now, there are no satisfactory techniques for handling algorithms involving extendible arrays (where, e.g., rows and/or columns can be appended dynamically). In this paper, the problem of allocating storage for extendible arrays is examined in the light of the author's earlier work on data graphs and addressing schemes. A formal analog of the assertion that simplicity of array extension precludes simplicity of traversal (marching along rows/columns) is proved. Two strategies for constructing extendible realizations of arrays are formulated, and certain inherent limitations of such realizations are established.

REFERENCES

• 1: BIRKHOFF, G., AND MACLANE, S. A Survey of Modern Algebra. Macmillan, New York, 1961.
• 2: Jay Earley, Toward an understanding of data structures, Communications of the ACM, v.14 n.10, p.617-627, Oct. 1971 [doi>10.1145/362759.362764]
• 3: FALKOFF, A. D., aND IVERSON, K.E. The design of APL. IBM J. I~es. Dev. 17 (1973), 324-334.
• 4: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 5: Andrew Mercer , Azriel Rosenfeld, An array grammar programming system, Communications of the ACM, v.16 n.5, p.299-305, May 1973 [doi>10.1145/362041.362198]
• 6: MILGRAM, D. L., AND P~OSENFELD, A. Array automata and array grammars. Proc. IFIP Congress 1971, North-Holland, Amsterdam, 1971, Booklet TA-2, pp. 166-173.
• 7: ROSENBERG, A.L. Data graphs and addressing schemes. J. Comput. Syst. Sci. 5 (1971), 193-238.
• 8: ROSENBERG, A. L. Exploiting addressability in data graphs. In Computational Complexity, Courant Computer Science Symposium 7, R. Rustin, Ed., Algorithmics Press, New York, 1973, pp. 161-183.
• 9: ROSENBERG, A.L. Generalized addressing schemes for data graphs. Math. Systems Theory (to appear).
• 10: ROSENBERG, A.L. Inherent limitations of extendible array realizations. IBM Rep. RC-4433, 1973; also submitted h)r publication.
• 11: ROSENBERG, A.L. On storing extendible arrays of specified shapes. IBM Rep. RC-4450, 1973; also submitted for publication.
• 12: ROSENBERG, A. L., AND STRONG, JR., H: R. Addressing arrays by shells. IBM Tech. Discl. Bull. 14 (1972), 3026-3028.
• 13: STOCKMEYER, L.J. Extendible array realizations with additive traversal. IBM Rep. RC-4578, 1973.
• 14: TURSKI, W.M. A model for data structures and its applications, I. Acla Informatica I (1971), 26-34.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

General Terms:
Theory, Verification