With C in TPF - Discontiguous Array Objects
by Dan Evans

Arrays are one of the simplest and most versatile data structures in a programmer's toolkit. In most systems, the contiguous storage needed for an array of any desired size is immediately available. However, in TPF, contiguous storage is limited to a maximum of 4K bytes. Newcomers to TPF are amazed at this apparently primitive approach to storage allocation, but experienced TPF programmers know that the underlying reason is efficiency. List allocation of fixed sized storage blocks has the lowest overhead of any dynamic allocation technique. A block of storage can be allocated from a list with one COMPARE AND SWAP instruction, which is not only efficient, but also needs no locking in a multi-processor configuration because CS performs serialization. We can appreciate TPF's efficiency, but that doesn't make the implementation of large arrays any easier. Like the Marines, what we need are a few good C functions.

Since large arrays can't be contiguous in TPF, we have to build them in pieces and save the storage location of each piece. We can do that with a new data structure which we'll call a "linked array."

#define LARRSZ 32
#define ChainEnd (LinkedArray *)0
typedef struct linkedArray
{
unsigned larbase;
struct linkedArray *larnxt;
Element larval[LARRSZ];
} LinkedArray;

The C type definition for LinkedArray defines each piece of a linked array. A complete linked array is a chain of zero or more of these pieces anchored by a pointer to the first piece. The symbolic definition LARRSZ provides the number of array members in each linked array piece. The definition of ChainEnd is a simple mnemonic for a null pointer which has meaning in this context. The type Element is the type of each array member. Its actual definition is up to the programmer creating the array. In order to show a non-trivial example of linked array use, we will use a type definition for Element which declares a structure containing some elementary fields and a union.

typedef struct
{short tag;
unsigned short mask;
union
{int count;
char *base;
} u;
} Element;

C type definitions introduce a single word as the synonym for a potentially complicated data structure. They are a convenient abstraction and make a program easier to read. They can also be misused when the names have little relevance to their actual use. Type definitions are identifiers, just like variable names, so in order to distinguish type names from variables, programming groups often adopt lexical conventions for type definitions. One common convention capitalizes the first letter of a type name, which is what we will do. This is only a convention, not a C language requirement.

The size of a LinkedArray piece is subject to the TPF 4K constraint. The symbolic constant LARRSZ can be varied so that this constraint is satisfied. The sample program below uses a much smaller LARRSZ than necessary in order to force a large number of links in the array. The C sizeof operator returns the number of bytes required for a particular type. In our case, sizeof(LinkedArray) is equal to:

sizeof(unsigned) + sizeof(struct linkedArray *) + LARRSZ * sizeof(Element)

A linked array is managed by two functions: lar_set() stores any member of a linked array, and lar_get() returns any member. As currently implemented, member subscripts go from 0 to the largest unsigned integer. Negative subscripts could also be supported with minor changes. Each LinkedArray piece of a linked array stores the subscript of the lowest numbered member in the piece, a pointer to the next piece, and LARRSZ members of type Element. Only pieces which have at least one member are allocated. Members are initialized to the value Default_Element when a LinkedArray piece is allocated. A default element for our example could look like:

#define Default_Element(a) Element a = {0, 0, 0}

The actual definition of Default_Element is up to the programmer.

The function lar_get() is the simpler of the two functions, so we'll look at it first. The prototype declaration for lar_get() shows that it is passed a LinkedArray pointer and the subscript of the member requested. It returns the value of that member. The passed pointer should be the anchor for a linked array chain.

static Element lar_get(LinkedArray *lar, unsigned ix)
{static Default_Element(dflt);
while (lar != ChainEnd && ix >= lar->larbase + LARRSZ)
lar = lar->larnxt;
if (lar == ChainEnd || ix < lar->larbase)
return dflt;
return lar->larval[ix - lar->larbase];
}

The while loop sequentially moves the pointer lar to the first LinkedArray piece whose upper bound is greater than the desired subscript, or until it is equal to ChainEnd, a 0. Note the use of a parameter as a local variable. Since parameters are passed by value in C, this can be done without affecting values in the calling program. This is a common C technique, and saves stack storage. The controlling expression for the while loop relies on the logical and operator &&, which guarantees that the left operand will be evaluated first and the right operand will be evaluated only when the left operand is true. When lar is equal to ChainEnd, the left operand is false, so the right operand is not evaluated; lar is not used to address storage if it is 0. When the loop ends, a check determines which condition ended it. If the end of the chain was reached or the requested subscript was below the lower bound of the current LinkedArray piece, the requested member is not in an allocated piece, so the default element value is returned. Otherwise, the base subscript of the piece is subtracted from the requested subscript to get the location of the requested member in the current piece. The value of that member is returned. The evaluation order of the && operator is again used in the if expression to guarantee that lar is not used if it is 0. The Default_Element macro is used to define a variable dflt with the default value of an array member. The ability to return a structured value is new with ANSI C, and may not be found in all C compilers.

Setting a value in a linked array requires a bit more work, and relies on a pointer to a pointer. The prototype for lar_set() shows that it is passed a parameter lrp which is declared as a pointer to a LinkedArray pointer. It is also passed a subscript and an Element value. The function will store the Element value at the subscript in the linked array anchored by the pointer pointed to by the parameter lrp. When you read it in English, you can appreciate the simplicity of C's syntax for the declaration. The pointer to pointer scheme is necessary because we may need to allocate a new LinkedArray piece and chain it in front of all existing pieces. In this case, the anchor must be updated. To do that, we need to know its location, so we need a pointer to the anchor pointer. In fact, any newly allocated piece must be added to the chain and an existing pointer in the chain must be updated with the address of the new piece.

static int lar_set(LinkedArray **lrp, unsigned ix, Element val)
{
int i;
LinkedArray *lar;
Element *ep;
static Default_Element(dflt);
while (*lrp != ChainEnd && ix >= (*lrp)->larbase + LARRSZ)
lrp = &(*lrp)->larnxt;
lar = *lrp;
if (lar == ChainEnd || lar->larbase > ix)
{
if ((lar = (LinkedArray *)malloc(sizeof(LinkedArray)))
return 0;
lar->larbase = (ix / LARRSZ) * LARRSZ;
for (i = 0, ep = lar->larval; i < LARRSZ; ++i, ++ep)
*ep = dflt;
lar->larnxt = *lar;
*lar = lar;
}
lar->larval[ix - lar->larbase] = val;
return 1;
}

The first while loop in lar_set() is identical to the one in lar_get() except that lar has been replaced by *lrp. Since lrp is a pointer to a LinkedArray pointer, it must be de-referenced to get the value of the LinkedArray pointer. The expression lrp = &(*lrp)->larnxt; sequentially moves lrp through the chain, but instead of pointing to each LinkedArray piece, it points in succession to each pointer which points to a LinkedArray piece. The loop stops when the chain ends or when the upper bound of the next piece is greater than the requested subscript.

The next assignment removes the indirectness of lrp for efficiency. If the subscript is now less than the lower bound of the next piece or we went off the end of the chain, there is no LinkedArray piece containing the desired subscript. We must allocate a new piece and initialize it with default members. Note the use of an Element pointer to sequentially move through the piece instead of coding a subscript calculation each time through the loop. The final two statements within the allocation block link the new piece into the chain at the proper point. The new piece is set to point to the piece containing the first larger base subscript or to 0 if the new piece is being added at the end of the chain, and then linked into the chain.

When control reaches the last statement in lar_set(), the variable lar points to the desired piece, whether newly allocated or previously existing. Then, the Element parameter is stored at the proper place in the array.

The data structure LinkedArray and the two functions which manipulate it together form an object. The object stores and retrieves Element values by subscript. A user of the LinkedArray object is hidden from the implementation details, and is only concerned with the capabilities provided by the object. The user should not be affected by internal changes to the object. For example, if we are using Prisym/C in TPF, the memory allocation function malloc() could be replaced by a getcc() call for direct access to TPF's storage allocation macro. In order to improve performance, the LinkedArray could be changed to additionally store the upper bound of a piece, so that the upper bound calculation can be eliminated from both routines. Instead of a sequential chain, the LinkedArray could be implemented with a Skip List to improve performance/size trade-offs. A user would still see the essential functions lar_get() and lar_set().

It is also possible to add new functions to an object. lar_read() and lar_write() might save and retrieve LinkedArray data on disk. Since storage blocks and disk blocks come in the same size in TPF, these would be almost trivial additions. The only interesting issues concern storage addresses which are no longer valid once a data structure is written to disk, and how to reconstitute the object's data structure when it is read back in.

The real conceptual power of an object is inheritance. New objects can be built from existing ones. One restriction of the LinkedArray object is the requirement for fixed length Element's. If we needed to store dynamic strings, it would be possible to use the LinkedArray object to define a StringArray object. The functions str_get() and str_set() could use a LinkedArray object to manage string pointers and lengths, and use new functions to manage string storage. However, with dynamic strings, the issue of external storage will be more difficult to solve. If a String object had already been defined, the job might be easier.

The linked array functions smooth a rough spot in TPF. They could be written in other languages, but their expression in C is clear and concise. The power of C and the performance of TPF should be an unbeatable combination. The following test program will let you test linked arrays on any platform which has a C compiler, including TPF with Prisym/C. The include file larray.h should contain the above functions and definitions.

#include "larray.h"
main(int argc, char **argv)
{unsigned i, ct, ix, x, evnhi, oddhi;
Element e;
LinkedArray *lp = 0;
ct = 0; e.tag = 1; e.mask = 0;
for (i = 2 * (LARRSZ - 1); i < 32767; i += 2 * (LARRSZ - 1), ++ct)
{
e.u.count = i;
if (lar_set(&lp, i, e) == 0)
printf("Unable to store element %u, storage exceeded\n", i), break;
}
evnhi = i; e.tag = 2;
for (i = (LARRSZ - 1); i < 32767; i += 2 * (LARRSZ - 1), ++ct)
{
e.u.count = -i;
if (lar_set(&lp, i, e) == 0)
printf("Unable to store element %u, storage exceeded\n", i), break;
}
oddhi = i; ix = 0;
for (i = (LARRSZ - 1); i < evnhi || i < oddhi; i += (LARRSZ - 1))
{
if (i & 1)
{
if (i >= oddhi) continue;
}
else
{
if (i >= evnhi) continue;
}
++ix;
e = lar_get(lp, i);
x = (e.tag == 2) ? -e.u.count : e.u.count;
if (x != i)
printf("Mismatch at element %u\n", i);
}
printf("%d elements stored and %d retrieved\n", ct, ix);
return 0;
}