Hi Andreas, I was not entirely clear. What I meant to say is you cannot do it with a single call to malloc and expect the two C bracket operators to behave like a 2D matrix would if it had been statically allocated (e.g. D[row][col]). For the bracket operators to work, D would have to be an array of row pointers each pointing to an int array (or offset in a flat array as you suggested). The patch in question does not allocate this separate array of pointers. My patch, and the previous mummer-help patches, works similarly to your suggestion, but does the indexing with arithmetic rather than pointers to save space. It allocates a single array D of size nRows*nColumns and then indexes a cell (r,c) by accessing D[r*nColumns+c].
The latest patch that was forwarded did the following to dynamically allocate a 2D matrix of dimension MxN: int * D_buf = (int *) calloc ( M*N, sizeof(int) ) ; int ** D = &D_buf ; This allocates an array of M*N ints pointed to by D_buf. Then it gets a pointer to the D_buf pointer and calls it D. Then to access element (r,c) of the presumed matrix it would call: D[r][c] The pointer arithmetic would work out to: *(*(D+r)+c) If D were allocated as a separate array of int (row) pointers and initialized as you suggest, this would work. But D is not an array here, it is a pointer to the int pointer D_buf. So D+r will be an uninitialized location. This is what lead to the memory errors. Best, -Adam On Tue, Sep 15, 2009 at 4:28 PM, Andreas Tille <[email protected]> wrote: > On Tue, Sep 15, 2009 at 10:26:35AM -0400, Adam Phillippy wrote: > > Hi Charles, > > I tested the patch you forwarded and it was nonfunctional. It attempted > to > > construct a two-dimensional array "D" of dimensions (M+1 x N+1) like so: > > > > * D_buf = (int *) calloc ( (M+1)*(N+1), sizeof(int) ) ; > > ** D = &D_buf ; > > * > > > > > > This compiles, but doesn't work. There is no way to allocate a 2D matrix > > dynamically by only using malloc. > > Well, I do not question whether the patch is right or wrong but this > statement in itself is definitely wrong. You can perfectly allocate a > flat memory area with pointers (to store for instance the data rows of > your aray). Moreover you allocate a vector of pointers with the number > of rows you want to store. Once you have done this you loop over the > pointer elements of this vector and let them point into the flat array > with an offset of (row number)*(number of columns)*(size of array > element). > > The reason why this works is the syntactical equality of > > *(ptr + i) and ptr[i] > > The advantage of this approach is that you can handle all array elements > equally in a flat loop if the context needs no array position. For > instance I have once written an image processing program which needed to > process a negativ of the image which is the same process for any pixel > regardless of the position. That works quite fast with the method > described above and is a very common way to store data on C. At the > same time you always have to make sure that the array is initialised > correctly - in C you aways buy performance by giving away the safety > against memory corruption. > > > To do the proper pointer arithmetic the > > D[row][col] operators used later in this source need to know at least one > > dimension of the matrix. > > As I tried to explain above: The theory says this is not true. > > > This is known for static arrays, but not for > > dynamic arrays. The patch you forwarded always leads to a memory access > > error. > > I can not assure that the patch above might not have some memory access > problems (and I currently have no time to verify). But that's an issue > of the actual implementation - not the general principle. > > > I implemented my own patch that handles the 2D pointer arithmetic in a > small > > wrapper class. This new version is tested and dynamically allocates the > > memory, so it should fit your needs. You can find the new version of the > > "annotate.cc" file here: > > > > > http://mummer.cvs.sourceforge.net/viewvc/mummer/MUMmer/src/tigr/annotate.cc?revision=1.3&view=markup > > > > This is included in a new MUMmer release (v3.22) I cut last week. > > It is fine for me if it works - so there is no need for sticking to the > solution I suggested above. I just wanted to correct general statements > about C here on a public list. Thanks for working on MUMmer and I > think it is fine to fetch the new release once it is released instead of > fiddling around with patches of the old version. > > Kind regards > > Andreas. > > -- > http://fam-tille.de > Klarmachen zum Ändern! >
