 Dynamic 2D Arrays
Vik Rubenfeld, Programmer

Dynamic 2D Arrays
by Vik Rubenfeld
May 15, 2004

This article chronicles a threat on the MacPascal mailing list for implementing dynamically allocated 2D arrays in Pascal.

Contents

The Original Post:

I'm thinking of doing something along these lines to create a dynamically allocated 2D array:

``````Type
PtrToLarge2DArray = ^Large2DArray;
HandleToLarge2DArray =^PtrToLarge2DArray;
Large2DArray = array[1..MaxLongInt] of array[1..MaxLongInt] of str[MaxFieldWidth];

Var
RecordSize, NumberOfRowsNeeded, NumberOfColumnsNeeded : LongInt;

{...}
Begin
{determine array size on the fly at runtime}
NumberOfRowsNeeded:= 75000;
NumberOfColumnsNeeded:= 2000;

RecordSize:= MaxFieldWidth + 1; {+1 for the length byte of a Pascal string}
HandleToLarge2DArray := NewHandle(RecordSize * NumberOfRowsNeeded * NumberOfColumnsNeeded);

FailNil(handle(HandleToLarge2DArray));
MoveHi(handle(HandleToLarge2DArray));
Hlock(handle(HandleToLarge2DArray));

{...}
End;``````

Now here's the interesting part. To get this to map correctly to the ram allocated by the call to NewHandle, do I access this array like this:

HandleToLarge2DArray^^[aRow, aColumn]:= 'a string';

Or like this:

HandleToLarge2DArray^^[aColumn, aRow]:= 'a string';

Thanks very much in advance to all for any info.

-Vik

The Final Post:

```The code is up and running and working well. I took this approach: Data Storage```
• ```Allocated a pointer to a data storage block 10 megs in size.```
• ```Arranged for new data storage blocks to be automatically allocated as needed.```
• ```Data in this case is all strings. Strings are stored in Pascal string (length byte first) format```

``` Pointer Storage```

• ```Allocated a pointer to a pointer storage block of size RequiredRows * RequiredColumns * SizeOf(ptr)```
• ```When a string is stored to the data storage block, a pointer to that string is stored in the pointer storage block at location (((theRow - 1) * TotalColumnsInSpeedFormat) + (theColumn - 1)) * sizeOf(ptr);```

`Access`

• ```Strings in the data storage block are retrieved by reference to their pointers in the pointer storage block.```

``` The data storage block is saved to disk in the same format. I found that this data storage format permits very rapid access, even on disk, versus the tab-text format I had been using. On my system it takes about 90 seconds to parse and read in about 3,000,000 fields in tab-text format, vs. about 9 seconds in the new format. I'm sure most apps that do this sort of thing use a similar format. When the data is in memory, it takes my system around 6 seconds to access 3,000,000 fields in this format using the data structures described above. For my particular application (rapid response to requests coming from a web browser, accessing my system via the net), every second counts, particularly as data comes in weekly, and more data means slower response times. At Bill's request I'm sending to Pascal Central a file containing the text of this thread, and the code I used to implement the data structures described above. Thanks to all here for your help on this! -Vik`````` ```

The Solution:

```After compiling notes from the MacPascal mailing list, a solution was devised. Below is some code that illustrates the solution. ``````Click here to download the code.```

``````
``````{This is the code I used to implement the dynamically allocated 2D arrays.}
{The format of the file I used is:}

{TotalRows stored as a LongInt}
{TotalColumns stored as a LongInt}
{Each string stored as a Pascal string, i.e. length byte first, with no delimiters of any kind between the strings.}

{The code included here is not self-enclosed. It refers to routines that are not provided here, particularly routines that}
{read and write data to and from files. However, most of the code needed for the dynamically allocated 2D arrays is here.}

{The code is provided for information purposes only and has not been strenuously tested at this time. }

{-Vik Rubenfeld}

{cBufferedFile is a file reading and writing object}
``````
``````cBufferedFile = object(cDataFile)
````     ````{.....}
````     ````TotalRowsInSpeedFormat: LongInt;
````     ````TotalColumnsInSpeedFormat: LongInt;

````     ````HeadBlockOfDataStorage:= DataStorageForSpeedFormatFile;
````     ````CurrentBlockOfDataStorage:= DataStorageForSpeedFormatFile;

````     ````itsPointerToSpeedFormatPointerStorage: Ptr;
````     ````{.....}
````     ````end;

DataStorageForSpeedFormatFile = object(cTCL_Object)
````     ````itsDataStorageForSpeedFormatFile: ptr;
````     ````NextFreeByte: LongInt;
````     ````NextDataStorageForSpeedFormatFile: DataStorageForSpeedFormatFile;

````     ````itsBufferedFile: cBufferedFile;

````     ````Procedure InitializeDataStorageForSpeedFormatFile(theCBufferedFile: cBufferedFile);

````     ````Function AddStringToStorage(S: DecStr): ptr;

````     ````Procedure Free; override;
````     ````end;

Procedure cBufferedFile.CreateSpeedFormatDataStructures(RequestedRows, ``````
````               ````RequestedColumns: LongInt);

Var
````     ````thePtrToTheSpeedFormat: ptr;
````     ````theDataStorageForSpeedFormatFile: DataStorageForSpeedFormatFile;
````     ````theBufferedFile: cBufferedFile;

````     ````begin
````     ````if itsPointerToSpeedFormatPointerStorage <> nil then
````          ````FreeSpeedFormat;

````     ````TotalRowsInSpeedFormat:= RequestedRows;
````     ````TotalColumnsInSpeedFormat:= RequestedColumns;

````     ````thePtrToTheSpeedFormat:= NewPtrClear(RequestedRows * RequestedColumns * sizeOf(ptr));
````     ````FailNil(thePtrToTheSpeedFormat);

````     ````itsPointerToSpeedFormatPointerStorage:= thePtrToTheSpeedFormat;

````     ````new(theDataStorageForSpeedFormatFile);
````     ````FailNil(theDataStorageForSpeedFormatFile);
````     ````theBufferedFile:= self;
````     ````theDataStorageForSpeedFormatFile.InitializeDataStorageForSpeedFormatFile(theBufferedFile);

````     ````HeadBlockOfDataStorage:= theDataStorageForSpeedFormatFile;
````     ````CurrentBlockOfDataStorage:= theDataStorageForSpeedFormatFile;
````     ````end;

Function cBufferedFile.FreeDataStorageForSpeedFormatFile;

Var
````     ````theDataStorageForSpeedFormatFile: DataStorageForSpeedFormatFile;
````     ````theNextDataStorageForSpeedFormatFile: DataStorageForSpeedFormatFile;

````     ````begin
````     ````theDataStorageForSpeedFormatFile:= HeadBlockOfDataStorage;

````     ````while theDataStorageForSpeedFormatFile <> nil do
````          ````begin
````          ````theNextDataStorageForSpeedFormatFile:= theDataStorageForSpeedFormatFile.NextDataStorageForSpeedFormatFile;

````          ````theDataStorageForSpeedFormatFile.NextDataStorageForSpeedFormatFile:= nil;
````          ````theDataStorageForSpeedFormatFile.Free;

````          ````theDataStorageForSpeedFormatFile:= theNextDataStorageForSpeedFormatFile;
````          ````end;

````     ````HeadBlockOfDataStorage:= nil;
````     ````CurrentBlockOfDataStorage:= nil;
````     ````end;

Procedure cBufferedFile.FreeSpeedFormat;

Var
````     ````thePtrToTheSpeedFormat: ptr;

````     ````begin
````     ````if itsPointerToSpeedFormatPointerStorage = nil then
````          ````exit(FreeSpeedFormat);

````     ````thePtrToTheSpeedFormat:= itsPointerToSpeedFormatPointerStorage;
````     ````itsPointerToSpeedFormatPointerStorage:= nil;
````     ````ForgetPtr(thePtrToTheSpeedFormat);

````     ````TotalRowsInSpeedFormat:= 0;
````     ````TotalColumnsInSpeedFormat:= 0;

````     ````FreeDataStorageForSpeedFormatFile;
````     ````end;

Function cBufferedFile.StoreFieldToSpeedFormat(theRow, theColumn: LongInt; S: DecStr): ptr;

Var
````     ````thePtrToTheStoredString: Ptr;
````     ````LocationWhereThatPtrWillBeStored: Ptr;

````     ````begin
````     ````{there is no garbage collection in the DataStorageForSpeedFormatFile objects. If you change the contents of a field, the old
````     ````contents remain in memory until FreeDataStorageForSpeedFormatFile is called.}
````     ````thePtrToTheStoredString:= CurrentBlockOfDataStorage.AddStringToStorage(S);

````     ````LocationWhereThatPtrWillBeStored:= GetLocationInRamOfRequestedPtrToItemInSpeedFormatDataStorage(theRow, theColumn);

````     ````BlockMove(@thePtrToTheStoredString, LocationWhereThatPtrWillBeStored, sizeof(ptr));
````     ````end;

Function cBufferedFile.GetFieldFromSpeedFormat(theRow, theColumn: LongInt): DecStr;

Var
````     ````PtrToThePtr, thePtrToTheString: Ptr;
````     ````S: DecStr;
````     ````theLength: byte;

````     ````begin
````     ````PtrToThePtr:= GetLocationInRamOfRequestedPtrToItemInSpeedFormatDataStorage(theRow, theColumn);

````     ````BlockMove(PtrToThePtr, @thePtrToTheString, sizeOf(ptr));

````     ````if thePtrToTheString = nil then
````          ````S:= ''
````     ````else
````          ````begin
````          ````theLength:= byte(thePtrToTheString^);
````          ````BlockMove(thePtrToTheString, @S, theLength + 1);
````          ````end;

````     ````GetFieldFromSpeedFormat:= S;
````     ````end;

Function cBufferedFile.GetLocationInRamOfRequestedPtrToItemInSpeedFormatDataStorage(theRow, theColumn: LongInt): ptr;

Var
````     ````LocationOfThePtr: Ptr;
````     ````theOffset: LongInt;

````     ````begin
````     ````LocationOfThePtr:= itsPointerToSpeedFormatPointerStorage;

````     ````theOffset:= (((theRow - 1) * TotalColumnsInSpeedFormat) + (theColumn - 1)) * sizeOf(ptr);

````     ````LocationOfThePtr := Ptr(LongInt(LocationOfThePtr) + theOffset);

````     ````GetLocationInRamOfRequestedPtrToItemInSpeedFormatDataStorage:= LocationOfThePtr;
````     ````end;

Procedure cBufferedFile.SaveSpeedFormatToDisk;

Var
````     ````LI: LongInt;
````     ````S: DecStr;
````     ````theRow: LongInt;
````     ````theColumn: LongInt;
````     ````theLength: byte;

````     ````begin
````     ````{save length byte of string for faster readin times}
````     ````For theRow:= 1 to TotalRowsInSpeedFormat do
````          ````For theColumn:= 1 to TotalColumnsInSpeedFormat do
````               ````begin
````               ````S:= GetFieldFromSpeedFormat(theRow, theColumn);
````               ````theLength:= byte(S);
````               ````WriteByte(theLength);
````               ````Write(S);
````               ````end;
````     ````end;

Var
````     ````S: DecStr;
````     ````R: Real;
````     ````LI: LongInt;
````     ````theRow: LongInt;
````     ````theColumn: LongInt;
````     ````theByte: byte;
````     ````theLength: LongInt;
````     ````thePtr: Ptr;
````     ````LocationOfThePtr: Ptr;
````     ````TotalRows, TotalColumns: LongInt;

````     ````fi: FailInfo;

````     ````Procedure HandleError (error: integer; message: LongInt);
``````
````          ````begin
````          ````SetFailInfo(kSilentErr, 0);
````          ````UseStatusDoc(DoCleanUp, 'Loading Speed Format Data', '');
````          ````end;

````     ````begin
````     ````{Has data been previously read into memory for this file? This can happen if the file was
````     ````opened and closed, but not freed. This permits SpeedFormat data to remain in memory in
````     ````case it's called for again.}
````     ````if itsPointerToSpeedFormatPointerStorage <> nil then
````          ````exit(ReadInSpeedFormatDataFromDisk);

````     ````CatchFailures(fi, HandleError);

````     ````UseStatusDoc(DoInit, 'Loading Speed Format Data.', '');

````     ````ReadLn(S);

````     ````if S <> StringIdentifyingFileAsASpeedFormatFile then
````          ````begin
````          ````WhoaDude('File is not a SpeedFormat file.');
````          ````Failure(kSilentErr, 0);
````          ````end;

````     ``ReadReal(R); ``{version number}````

````     ````ReadLongInteger(TotalRows);
````     ````TotalRowsInSpeedFormat := TotalRows;

````     ````ReadLongInteger(TotalColumns);
````     ````TotalColumnsInSpeedFormat := TotalColumns;

````     ````CreateSpeedFormatDataStructures(TotalRows, TotalColumns);

````     ````For theRow:= 1 to TotalRowsInSpeedFormat do
````          ````For theColumn:= 1 to TotalColumnsInSpeedFormat do
````               ````begin
````               ````ReadByte(theByte);
````               ````if theByte > 0 then
````                    ````begin
````                    ````theLength:= theByte;
````                    ````ReadPointerOfSpecifiedLength(thePtr, theLength);

````                    ````{get the data into a string}
````                    ````S:= char(theByte);
````                    ````BlockMove(thePtr, @S, theLength);

````                    ````{dispose of the pointer}
````                    ````ForgetPtr(thePtr);

````                    ````{store the string to Data Storage}
````                    ````thePtr:= CurrentBlockOfDataStorage.AddStringToStorage(S);

````                    ````{take the address of the string in Data Storage, and put it in the correct place in the SpeedFormat pointer storage
````                    ````where it's easy to find}
````                    ````LocationOfThePtr := GetLocationInRamOfRequestedPtrToItemInSpeedFormatDataStorage(theRow, theColumn);
````                    ````BlockMove(@thePtr , LocationOfThePtr, sizeof(ptr));
````                    ````end;
````               ````end;

````     ````UseStatusDoc(DoCleanUp, 'Loading Speed Format Data', '');

````     ````Success;
````     ````end;

Procedure cBufferedFile.WriteContentsOfFieldArrayToSpeedFormatFile(theTargetFile: cBufferedFile);

Var
````     ````S: DecStr;
````     ````I:integer;
````     ````theLength: byte;

````     ````begin
````     ````for I := 1 to TabDelimitedEndingColumn do
````          ````begin
````          ````S := Field^^[I];

````          ````If ItsAllBlanks(S) then
````               ````S:= '';

````          ````theLength:= byte(S);
````          ````theTargetFile.WriteByte(theLength);

````          ````if theLength > 0 then
````               ````theTargetFile.Write(S);
````          ````end;
````     ````end;

Procedure DataStorageForSpeedFormatFile.InitializeDataStorageForSpeedFormatFile(theBufferedFile: cBufferedFile);

Var
````     ````thePtr: Ptr;

````     ````begin
````     ````NextFreeByte:= 1;
````     ````NextDataStorageForSpeedFormatFile:= nil;

````     ````thePtr:= NewPtrClear(SizeOfDataStorageForSpeedFormatFileBlock);
````     ````FailNIL(thePtr);

````     ````itsBufferedFile:= theBufferedFile;

````     ````itsDataStorageForSpeedFormatFile:= thePtr;
````     ````end;

Var
````     ````LengthOfTheString: LongInt;
````     ````AvailableSpace: LongInt;
````     ````theBufferedFile: cBufferedFile;
````     ````thePtr: Ptr;
````     ````theDataStorageForSpeedFormatFile: DataStorageForSpeedFormatFile;

````     ````begin
````     ````theDataStorageForSpeedFormatFile:= self;

````     ``LengthOfTheString:= Length(S) + 1; ``{+1 for the length byte}````

````     ````AvailableSpace:= SizeOfDataStorageForSpeedFormatFileBlock - NextFreeByte + 1;

````     ````if AvailableSpace < LengthOfTheString then
````          ````begin
````          ````New(theDataStorageForSpeedFormatFile);
````          ````FailNIL(theDataStorageForSpeedFormatFile);

````          ````theBufferedFile:= itsBufferedFile;
````          ````theDataStorageForSpeedFormatFile.InitializeDataStorageForSpeedFormatFile(theBufferedFile);
````          ````itsBufferedFile.CurrentBlockOfDataStorage:= theDataStorageForSpeedFormatFile;
````          ````end;

````          ````thePtr:= theDataStorageForSpeedFormatFile.itsDataStorageForSpeedFormatFile;
````          ````thePtr:= Ptr(LongInt(thePtr) + theDataStorageForSpeedFormatFile.NextFreeByte - 1);
````          ````BlockMove(@S, thePtr, LengthOfTheString);

````          ````theDataStorageForSpeedFormatFile.NextFreeByte:= theDataStorageForSpeedFormatFile.NextFreeByte + LengthOfTheString;

````          ````AddStringToStorage:= thePtr;
````          ````end;

Function DataStorageForSpeedFormatFile.Free;

Var
````     ````thePtr: Ptr;

````     ````begin
````     ````thePtr:= itsDataStorageForSpeedFormatFile;
````     ````itsDataStorageForSpeedFormatFile:= nil;

````     ````ForgetPtr(thePtr);

````     ````inherited Free;
````     ``end;````

```Click here for the full Archived Thread...`````` ```