Variable-length array in a structure

[Hated Moron]

Suppose you're using a structure to represent an object, and a collection of those structures (perhaps a linked-list or a structure array) to represent a set of those objects. Further suppose that the objects themselves each contain a collection of things, which you want to represent as an array inside the structure.

All perfectly straightforward, because structures can contain arrays as members. But what if the collections within those objects are not all the same size, and indeed the size of the array is not known at the start? Now you're in trouble because an array structure-member has to be declared when the structure is created, so each of the objects ends up with the same size array:

Code: Select all

DIM object{array(SIZE), other, structure, members}
DIM set_of_objects{(HOWMANY)} = object{}

The only obvious way to deal with this is to make the array the maximum size it can ever be, and to store the actual number of elements as another structure member:

Code: Select all

DIM object{array(MAX_SIZE), actual_size%, other, structure, members}
DIM set_of_objects{(HOWMANY)} = object{}

But this is potentially very wasteful. If most of the objects contain only small collections (or perhaps no collection at all) and only a few contain large collections, you may have to allocate hugely more memory for the arrays than you really need to.

For a long time I couldn't think of an elegant solution to this, but there is one: rather than storing the array itself in the structure store a pointer to the array instead:

Code: Select all

DIM object{array%%, other, structure, members}
DIM set_of_objects{(HOWMANY)} = object{}

With the aid of some helper routines you can now create and access different-sized arrays in each structure:

Code: Select all

DEF PROC_create_array(object{}, size%)
PRIVATE temp()
PTR(temp()) = object.array%%
DIM temp(size%)
object.array%% = PTR(temp())
ENDPROC

Code: Select all

DEF PROC_write_to_array(obkect{}, index%, number)
PRIVATE temp()
PTR(temp()) = object.array%%
temp(index%) = number
ENDPROC

Code: Select all

DEF FN_read_from_array(object{}, index%)
PRIVATE temp()
PTR(temp()) = object.array%%
= temp(index%)

Using PRIVATE rather than LOCAL avoids any issues that might arise from BASIC expecting the 'temporary' array to be stored on the stack.

A potentially valuable side-effect is that the 'temporary' array, being a conventional array, can have functions like SUM() and MOD() applied which an array within a structure can't:

Code: Select all

DEF FN_sum_array(object{})
PRIVATE temp()
PTR(temp()) = object.array%%
= SUM(temp())

[hellomike]

Smart stuff Richard.
Why does there also be the need for

Code: Select all

PTR(temp()) = object.array%%

in the PROC_create_array() definition? I would assume object.array%% is still NULL.

The code seems two have 2 (syntax) errors: object_array%% and a closing bracket in the PROC_write_to_array definition.

Regards,

Mike

[Hated Moron]

Why does there also be the need for

Code: Select all

PTR(temp()) = object.array%%

in the PROC_create_array() definition? I would assume object.array%% is still NULL.

You're right that it will usually be NULL, so one could write PTR(temp()) = FALSE instead and it would work - so long as PROC_create_array() is called only once for each structure.

But by setting it to object.array%% instead of FALSE it ensures that the usual behaviour of DIM - i.e. that the array can be re-DIMensioned without complaint so long as the dimensions are identical to the original ones - is retained.

If you set it to FALSE the effect of calling PROC_create_array (which perhaps should have been called PROC_DIM_array to emphasise this usage) twice would be to discard the old array and create a new one, causing a memory leak.

So since you have to set PTR(temp()) to something - you can't omit that statement altogether - it's nicer to set it to object.array%% than to FALSE. It also means that all the routines have the same preamble.

The code seems two have 2 (syntax) errors: object_array%% and a closing bracket in the PROC_write_to_array definition.

Fixed, thanks.