Memory Allocation for High-Dimensional Data Structures

Environment: Windows NT SP5, Windows 95b/98, Visual C++ 6

1. General Methods

For a very large application, dynamic memory allocation is common in C/C++ programming. For example, I ported Basin Modeling application from SUN workstation to PC 486 in 1992, cutting memory usage up to 90%. Generally two types of dynamic memory allocation methods are wildly used to deal with high dimensional data structures. One is to use 1D to represent nD as shown in the follow:
// ignore pointer validation and use malloc and free for instance
Type* p = (Type *)malloc(s1*s2* ... *sn*sizeof(Type));
for(i1 = 0; i1 < s1; i1 ++) 
 for(i2 = 0; i2 < s2; i2 ++)
  //... 
  for(in = 0; in < sn; in ++)
   p[(...((i1*s2+i2)*s3+i3)...)*sn+in] = ...; 
   //do something using p 
free(A);
The other is directly to use nD as shown in the follow:
Type *p1, **p2, ..., **...*pn;
  
p1 = (Type *)malloc(sizeof(Type)*s1*s2*...*sn*sizeof(Type));
p2 = (Type **)malloc(sizeof(Type*)*s1*s2*...*sn-1);
//...
pn = (Type **...*)calloc(sizeof(Type**...*)s1, size);

// need assign address properly
for(i = 0; i < s1*s2*...*sn-1; i ++)
 *(p2+i) = &p1[sn*i*sizeof(Type)];

for(i = 0; i < s1; i ++)
 *(p3+i) = &p2[sn-1*i];
//...

for(i = 0; i < s1*s2*...*sn-2; i ++)
 *(pn+i) = &pn-1[s2*i];

for(i1 = 0; i1 < s1; i1 ++) 
 for(i2 = 0; i2 < s2; i2 ++)
  //...
  for(in = 0; in < sn; in ++)
   pn[i1][i2]...[in] = ...; 
   //do something using pn

free(**...*p);  //(n-1)-dimensional pointer

//...

free(*p);
free(p);

2. Source Code

  1. MemA.h uses C++ template and operator overloading to implement 1D, 2D, and 3D based on method 1. It is easy to extend to high dimension, such as 4D and 5D. It is especially useful to port applications from Fortran to C++.
      Member functions
    • bool CDynArray<Type>::SetSize(int i);
    • bool CDynArray<Type>::SetSize(int i, int j);
    • bool CDynArray<Type>::SetSize(int i, int j, int k);
    • Type& CDynArray<Type>::operator ()(int i);
    • Type& CDynArray<Type>::operator ()(int i, int j);
    • Type& CDynArray<Type>::operator ()(int i, int j, int k);
    • void CDynArray<Type>::Remove();
  2. MemB.h uses C++ template to implement 1D, 2D, and 3D based on method 2.
      Member functions
    • // One dimension
    • Type* CMalloc<Type>::Malloc(int I);
    • void CMalloc<Type>::Free(T*& X);
    • // Two dimension
    • Type** CMalloc<Type>::Malloc(int I, int J);
    • void CMalloc<Type>::Free(T**& X);
    • // Three dimension
    • Type** CMalloc<Type>::Malloc(int I, int J, int K);
      			
    • void CMalloc<Type>::Free(T***& X);
  3. MemC.h and MemC.c only use C to implement 2D and 3D based on method 2.
      Member functions
    • void** Malloc2(int, int, size_t);
    • void*** Malloc3(int, int, int, size_t);
    • void Free2(void**);
    • void Free3(void***);

3. Demo Project

MemDemo.cpp demonstrates how to use memory allocation functions in the above files. It tests both float, double, and data structure types.

Downloads

Download demo project - 6 Kb
Download source - 3 Kb


Comments

  • Wonderfull

    Posted by Legacy on 07/26/2003 12:00am

    Originally posted by: Naresh Prajapati

    I was just handling my data structure as conventional way, got yr artical and made all d.s standard & efficient. Thanks

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Learn How A Global Entertainment Company Saw a 448% ROI Every business today uses software to manage systems, deliver products, and empower employees to do their jobs. But software inevitably breaks, and when it does, businesses lose money -- in the form of dissatisfied customers, missed SLAs or lost productivity. PagerDuty, an operations performance platform, solves this problem by helping operations engineers and developers more effectively manage and resolve incidents across a company's global operations. …

  • Live Event Date: January 7, 2015 @ 1:00 p.m. ET / 10:00 a.m. PT The Flash Visionary Chat series of webinars brings together IT and business leaders as well as thought leading industry analysts to discuss how the flash revolution is eradicating inefficiency, unleashing innovation, and accelerating businesses. Join us for this next episode where we are excited to host not only the 451 Research, who will share their recent industry research, but also one of our top customers, who will share their perspective on …

Most Popular Programming Stories

More for Developers

RSS Feeds