The main use of structures is to lump together collections of disparate variable types, so they can conveniently be treated as a unit. For example, if we were writing a compiler or assembler, we might need for each identifier information like its name (a character array), its source line number (an integer), some type information (a character, perhaps), and probably a usage count (another integer).
char id[10];
int line;
char type;
int usage;
We can make a structure out of this quite easily. We first tell C what the structure will look like, that is, what kinds of things it contains; after that we can actually reserve storage for it, either in the same statement or separately. The simplest thing is to define it and allocate storage all at once:
struct {
char id[10];
int line;
char type;
int usage;
} sym;
This defines sym to be a structure with the specified shape; id, line, type and usage are members of the structure. The way we refer to any particular member of the structure is
structure-name . member
as in
sym.type = 077;
if( sym.usage == 0 ) ...
while( sym.id[j++] ) ...
etc.
Although the names of structure members never stand alone, they still have to be unique; there can't be another id or usage in some other structure.
So far we haven't gained much. The advantages of structures start to come when we have arrays of structures, or when we want to pass complicated data layouts between functions. Suppose we wanted to make a symbol table for up to 100 identifiers. We could extend our definitions like
char id[100][10];
int line[100];
char type[100];
int usage[100];
but a structure lets us rearrange this spread-out information so all the data about a single identifer is collected into one lump:
struct {
char id[10];
int line;
char type;
int usage;
} sym[100];
This makes sym an array of structures; each array element has the specified shape. Now we can refer to members as
sym[i].usage++; /* increment usage of i-th identifier */
for( j=0; sym[i].id[j++] != '\0'; ) ...
etc.
Thus to print a list of all identifiers that haven't been used, together with their line number,
for( i=0; i
if( sym[i].usage == 0 )
printf("%d\t%s\n", sym[i].line, sym[i].id);
Suppose we now want to write a function lookup(name) which will tell us if name already exists in sym, by giving its index, or that it doesn't, by returning a -1. We can't pass a structure to a function directly; we have to either define it externally, or pass a pointer to it. Let's try the first way first.
int nsym 0; /* current length of symbol table */
struct {
char id[10];
int line;
char type;
int usage;
} sym[100]; /* symbol table */
main( ) {
...
if( (index = lookup(newname)) >= 0 )
sym[index].usage++; /* already there ... */
else
install(newname, newline, newtype);
...
}
lookup(s)
char *s; {
int i;
extern struct {
char id[10];
int line;
char type;
int usage;
} sym[ ];
for( i=0; i
if( compar(s, sym[i].id) > 0 )
return(i);
return(-1);
}
compar(s1,s2) /* return 1 if s1==s2, 0 otherwise */
char *s1, *s2; {
while( *s1++ == *s2 )
if( *s2++ == '\0' )
return(1);
return(0);
}
The declaration of the structure in lookup isn't needed if the external definition precedes its use in the same source file, as we shall see in a moment.
Now what if we want to use pointers?
struct symtag {
char id[10];
int line;
char type;
int usage;
} sym[100], *psym;
psym = &sym[0]; /* or p = sym; */
This makes psym a pointer to our kind of structure (the symbol table), then initializes it to point to the first element of sym.
Notice that we added something after the word struct: a ``tag'' called symtag. This puts a name on our structure definition so we can refer to it later without repeating the definition. It's not necessary but useful. In fact we could have said
struct symtag {
... structure definition
};
which wouldn't have assigned any storage at all, and then said
struct symtag sym[100];
struct symtag *psym;
which would define the array and the pointer. This could be condensed further, to
struct symtag sym[100], *psym;
The way we actually refer to an member of a structure by a pointer is like this:
ptr -> structure-member
The symbol `->' means we're pointing at a member of a structure; `->' is only used in that context. ptr is a pointer to the (base of) a structure that contains the structure member. The expression ptr->structure-member refers to the indicated member of the pointed-to structure. Thus we have constructions like:
psym->type = 1;
psym->id[0] = 'a';
and so on.
For more complicated pointer expressions, it's wise to use parentheses to make it clear who goes with what. For example,
struct { int x, *y; } *p;
p->x++ increments x
++p->x so does this!
(++p)->x increments p before getting x
*p->y++ uses y as a pointer, then increments it
*(p->y)++ so does this
*(p++)->y uses y as a pointer, then increments p
The way to remember these is that ->, . (dot), ( ) and [ ] bind very tightly. An expression involving one of these is treated as a unit. p->x, a[i], y.x and f(b) are names exactly as abc is.
If p is a pointer to a structure, any arithmetic on p takes into account the actual size of the structure. For instance, p++ increments p by the correct amount to get the next element of the array of structures. But don't assume that the size of a structure is the sum of the sizes of its members -- because of alignments of different sized objects, there may be ``holes'' in a structure.
Enough theory. Here is the lookup example, this time with pointers.
struct symtag {
char id[10];
int line;
char type;
int usage;
} sym[100];
main( ) {
struct symtag *lookup( );
struct symtag *psym;
...
if( (psym = lookup(newname)) ) /* non-zero pointer */
psym -> usage++; /* means already
there */
else
install(newname, newline, newtype);
...
}
struct symtag *lookup(s)
char *s; {
struct symtag *p;
for( p=sym; p < &sym[nsym]; p++ )
if( compar(s, p->id) > 0)
return(p);
return(0);
}
The function compar doesn't change: `p->id' refers to a string.
In main we test the pointer returned by lookup against zero, relying on the fact that a pointer is by definition never zero when it really points at something. The other pointer manipulations are trivial.
The only complexity is the set of lines like
struct symtag *lookup( );
This brings us to an area that we will treat only hurriedly; the question of function types. So far, all of our functions have returned integers (or characters, which are much the same). What do we do when the function returns something else, like a pointer to a structure? The rule is that any function that doesn't return an int has to say explicitly what it does return. The type information goes before the function name (which can make the name hard to see).
Examples:
char f(a)
int a; {
...
}
int *g( ) { ... }
struct symtag *lookup(s) char *s; { ... }
The function f returns a character, g returns a pointer to an integer, and lookup returns a pointer to a structure that looks like symtag. And if we're going to use one of these functions, we have to make a declaration where we use it, as we did in main above.
Notice the parallelism between the declarations
struct symtag *lookup( );
struct symtag *psym;
In effect, this says that lookup( ) and psym are both used the same way - as a pointer to a structure -- even though one is a variable and the other is a function.
