[C programming] Structure

Created by Tran Anh Tai

We cover below parts.

- Basics of structures
- Structures and functions
- Arrays of structures
- Pointers to structures
- Self-referential structures
- Table lookup
- Typedef
- Unions
- Bit-fields

1. Basics of structures 
Define structure assignment - structures may be copied and assigned to, passed to functions, and returned by functions.

A struct declaration defines a type. The right brace that terminates the list of members may be followed by a list of variables, just as for any basic type. That is,
struct { ... } x, y, z;
is syntactically analogous to

int x, y, z;

Structures can be nested.

?

1 2 3 4 5 6 7 8 9

struct point {  int x;  int y; }; struct rect {  struct point pt1;  struct point pt2; };

The rect structure contains two point structures. If we declare screen as
struct rect screen;
then
screen.pt1.x
refers to the x coordinate of the pt1 member of screen.
2. Structures and functions

The only legal operations on a structure are copying it or assigning to it as a unit, taking its address with &, and accessing its members.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

/* makepoint: make a point from x and y components */ struct point makepoint(int x, int y) {  struct point temp;     temp.x = x;     temp.y = y;     return temp; } struct rect screen; struct point middle; struct point makepoint(int, int); screen.pt1 = makepoint(0,0); screen.pt2 = makepoint(XMAX, YMAX); middle = makepoint((screen.pt1.x + screen.pt2.x)/2, (screen.pt1.y + screen.pt2.y)/2);

If a large structure is to be passed to a function, it is generally more efficient to pass a pointer than to copy the whole structure.

?

1 2 3 4 5

struct point *pp; struct point origin, *pp; pp = &origin; printf("origin is (%d,%d)\n", (*pp).x, (*pp).y);

If using *pp.x means *(pp.x), which is illegal here because x is not a pointer.

Pointers to structures are so frequently used that an alternative notation is provided as a shorthand. If p is a pointer to a structure, then

?

1	p->member-of-structure

refers to the particular member. So we could write instead

?

1	printf("origin is (%d,%d)\n", pp->x, pp->y);

Both . and -> associate from left to right, so if we have

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

struct rect r, *rp = &r; then these four expressions are equivalent: r.pt1.x rp->pt1.x (r.pt1).x (rp->pt1).x Given the declaration struct {      int len;      char *str; } *p; then ++p->len

increments len, not p, because the implied parenthesization is ++(p->len). Parentheses can be used to alter binding: (++p)->len increments p before accessing len, and (p++)->len increments p afterward. (This last set of parentheses is unnecessary.)

In the same way, *p->str fetches whatever str points to; *p->str++ increments str after accessing whatever it points to (just like *s++); (*p->str)++ increments whatever str points to; and *p++->str increments p after accessing whatever str points to.

3. Arrays of structure 
Consider writing a program to count the occurrences of each C keyword. We need an array of character strings to hold the names, and an array of integers for the counts. One possibility is to use two parallel arrays, keyword and keycount, as in

?

1 2	char *keyword[NKEYS]; int keycount[NKEYS];

But the very fact that the arrays are parallel suggests a different organization, an array of structures. Each keyword is a pair:

?

1 2	char *word; int cout;

and there is an array of pairs. The structure declaration

?

1 2 3 4

struct key {       char *word;       int count; } keytab[NKEYS];

declares a structure type key, defines an array keytab of structures of this type, and sets aside storage for them. Each element of the array is a structure. This could also be written

?

1 2 3 4 5

struct key {      char *word;      int count; }; struct key keytab[NKEYS];

Check how to implement this example. 

?

1. #define MAXWORD 100  
2.    
3. /* All keywords, see A2.4, p192 of the book. */  
4.    
5. struct key {  
6.  char *word;  
7.  int count;  
8. } keytab[] = {  
9.  "auto", 0,  
10.  "break", 0,  
11.  "case", 0,  
12.  "char", 0,   
13.  "const", 0,  
14.  "continue", 0,  
15.  "default", 0,  
16.  "do", 0,  
17.  "double", 0,  
18.  "else", 0,  
19.  "enum", 0,  
20.  "extern", 0,  
21.  "float", 0,  
22.  "for", 0,  
23.  "goto", 0,  
24.  "if", 0,  
25.  "int", 0,  
26.  "long", 0,  
27.  "register", 0,  
28.  "return", 0,   
29.  "short", 0,  
30.  "signed", 0,  
31.  "sizeof", 0,   
32.  "static", 0,   
33.  "struct", 0,  
34.  "switch", 0,  
35.  "typedef", 0,   
36.  "union", 0,   
37.  "unsigned", 0,   
38.  "void", 0,   
39.  "volatile", 0,   
40.  "while", 0,  
41. };  
42.    
43. #define NKEYS (sizeof keytab / sizeof keytab[0])  
44.    
45. int binsearch (char *word, struct key tab[], int n);  
46. int  getword (char *word, int lim);  
47.    
48. int main ()  
49. {  
50.  int n;  
51.  char word[MAXWORD];  
52.    
53.  while (getword(word, MAXWORD) != EOF)  
54.  {  
55.   printf("GET:%s\n", word);  
56.   if ((n = binsearch(word, keytab, NKEYS)) >= 0)  
57.    keytab[n].count++;  
58.     }  
59.  for (n = 0; n < NKEYS; n++)  
60.   if (keytab[n].count > 0)  
61.    printf("%4d %s\n", keytab[n].count, keytab[n].word);  
62.      
63.  return 0;  
64. }  
65.    
66. int binsearch (char *word, struct key tab[], int n)  
67. {  
68.  int cond;  
69.  int low, high, mid;  
70.    
71.  low = 0;  
72.  high = n - 1;  
73.  while (low <= high) {  
74.   mid = (low + high) / 2;  
75.   if ((cond = strcmp(word, tab[mid].word)) < 0)  
76.    high = mid - 1;  
77.   else if (cond > 0)  
78.    low = mid + 1;  
79.   else  
80.    return mid;  
81.  }  
82.    
83.  return -1;  
84. }  
85.    
86. int  getch (void);  
87. void ungetch (int c);  
88.    
89. /* getword() now only returns words starting with a letter and followed by  
90.  * letters, digits, or underscores.  Everything else is skipped and ignored.   
91.  * It returns EOF if an error is detected or if the end of file is reached.  
92.  */  
93.    
94. int getword (char *word, int lim)  
95. {  
96.  int c, d;  
97.  char *w = word;  
98.    
99.     while (isspace(c = getch()))  
100.  ;  
101.     
102.  if (c != EOF)  
103.   *w++ = c;  
104.   if (!isalpha(c)) {  
105.   *w = '\0';  
106.   return c;  
107.  }  
108.     
109.  for ( ; --lim > 0; w++)  
110.  if (!isalnum(*w = getch())) {  
111.  ungetch(*w);  
112.  break;  
113.  }  
114.  *w = '\0';  
115.  return word[0];   
116. }  
117.    
118. #define BUFSIZE 100  
119. char    buf[BUFSIZE];  
120. int     bufp = 0;  
121.    
122. int getch (void)  
123. {  
124.         return bufp > 0 ? buf[--bufp] : getchar();  
125. }  
126.    
127. void ungetch (int c)  
128. {  
129.         if (bufp >= BUFSIZE)  
130.             printf("Error: Too many characters!\n");  
131.         else  
132.             buf[bufp++] = c;  
133. }  

4. Pointers to structures
To illustrate some of the considerations involved with pointers to and arrays of structures, let us write the keyword-counting program again, this time using pointers instead of array indices.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

struct key *binsearch(char *, struct key *, int); /* count C keywords; pointer version */ main() {  char word[MAXWORD];  struct key *p;  while (getword(word, MAXWORD) != EOF)   if (isalpha(word[0]))   if ((p=binsearch(word, keytab, NKEYS)) != NULL)   p->count++;  for (p = keytab; p < keytab + NKEYS; p++)  if (p->count > 0)  printf("%4d %s\n", p->count, p->word);  return 0; } /* binsearch: find word in tab[0]...tab[n-1] */ struct key *binsearch(char *word, struct key *tab, int n) {  int cond;  struct key *low = &tab[0];  struct key *high = &tab[n];  struct key *mid;     while (low < high) {  mid = low + (high-low) / 2;   if ((cond = strcmp(word, mid->word)) < 0)    high = mid;    else if (cond > 0)    low = mid + 1;    else    return mid;  }  return NULL; }

the elements of keytab are now accessed by pointers.

The initializers for low and high are now pointers to the beginning and just past the end of the table.
The computation of the middle element can no longer be simply
mid = (low+high) / 2 /* WRONG */
because the addition of pointers is illegal. Subtraction is legal, however, so high-low is the number of elements, and thus
mid = low + (high-low) / 2
sets mid to the element halfway between low and high.
The most important change is to adjust the algorithm to make sure that it does not generate an illegal pointer or attempt to access an element outside the array. The problem is that &tab[-1] and &tab[n] are both outside the limits of the array tab. The former is strictly illegal, and it is illegal to dereference the latter. The language definition does guarantee, however, that pointer arithmetic that involves the first element beyond the end of an array (that is, &tab[n]) will work correctly.

Don't assume, however, that the size of a structure is the sum of the sizes of its members. Because of alignment requirements for different objects, there may be unnamed ``holes'' in a structure. Thus, for instance, if a char is one byte and an int four bytes, the structure
struct {
     char c;
     int i;
};
might well require eight bytes, not five.

5. Self-referential structures
It is illegal for a structure to contain an instance of itself, but is possible to make a pointer to the structure.
Below example uses a data structure called binary tree to count the occurrences of all the words in some input. Since the list of words isn't known in advance, we can't conveniently sort it and use a binary search.

1. #define MAXWORD   100  
2.    
3. // binary tree   
4. struct tnode {    
5.  char *word; // point to text  
6.  int count; // number of occurences  
7.  struct tnode *left; // left child  
8.  struct tnode *right; // right child  
9. };  
10.    
11. struct tnode *addtree (struct tnode *p, char *w);  
12. void  treeprint (struct tnode *p);  
13. int   getword (char *word, int lim);  
14.    
15. int main (int argc, char *argv[])  
16.    
17. {  
18.  struct tnode *root;  
19.  char  word[MAXWORD];  
20.    
21.  /* Keywords are not inserted in the binary tree. */  
22.    
23.  root = NULL;  
24.  while (getword(word, MAXWORD) != EOF)  
25.   if (isalpha(word[0]))  
26.   root = addtree(root, word);  
27.    
28.  treeprint(root);  
29.    
30.  return 0;  
31. }  
32.    
33. struct tnode *talloc (void);  
34. char  *_strdup (char *s);  
35.    
36. struct tnode *addtree (struct tnode *p, char *w)  
37. {  
38.  int cond;  
39.    
40.  if (p == NULL) {  
41.    
42.   p = talloc();  
43.   p->word = _strdup(w);  
44.   p->count = 1;  
45.   p->left = p->right = NULL;  
46.    
47.  } else if ((cond = strcmp(w, p->word)) == 0)  
48.   p->count++; // repeated word  
49.  else if (cond <0 p-="">left = addtree(p->left, w);  
50.  else  
51.   p->right = addtree(p->right, w);  
52.    
53.  return p;  
54. }  
55.    
56. struct tnode *talloc (void)  
57. {  
58.  return (struct tnode *) malloc(sizeof(struct tnode));  
59. }  
60.    
61. char *_strdup (char *s)  
62. {  
63.  char *p;  
64.    
65.  if ((p = (char *) malloc(strlen(s) + 1)) != NULL)  
66.   strcpy(p, s);  
67.    
68.  return p;  
69. }  
70.    
71. void treeprint (struct tnode *p)  
72. {  
73.  if (p != NULL) {  
74.   treeprint(p->left);  
75.   printf("%d %s\n",p->count, p->word);  
76.   treeprint(p->right);  
77.  }  
78. }  
79.    
80. int getch (void);  
81. void ungetch (int c);  
82.    
83. /* See exercise 6-1 for a description of the updated getword() function. */  
84.    
85. int getword (char *word, int lim)  
86. {  
87.     int c, d;  
88.  char *w = word;  
89.    
90.     while (isspace(c = getch()))  
91.  ;  
92.     
93.  if (c != EOF)  
94.   *w++ = c;  
95.   if (!isalpha(c)) {  
96.   *w = '\0';  
97.   return c;  
98.  }  
99.     
100.  for ( ; --lim > 0; w++)  
101.  if (!isalnum(*w = getch())) {  
102.  ungetch(*w);  
103.  break;  
104.  }  
105.  *w = '\0';  
106.     
107.  return word[0];   
108. }  
109.    
110. #define BUFSIZE 100  
111.    
112. char    buf[BUFSIZE];  
113. int     bufp = 0;  
114.    
115. int getch (void)  
116. {  
117.     return bufp > 0 ? buf[--bufp] : getchar();  
118. }  
119.    
120. void ungetch (int c)  
121. {  
122.     if (bufp >= BUFSIZE)  
123.   printf("Error: Too many characters!\n");  
124.  else  
125.   buf[bufp++] = c;  
126. }  

6. Table lookup 

7. Typedef

8. Unions
9. Bit-fields
Consider bitmask below.

?

1. unsigned char flags;  
2.    
3. // initialising the flags  
4. // note that assignming a value will clobber any other flags, so you  
5. // should generally only use the = operator when initialising vars.  
6. flags = LOG_ERRORS;  
7. // sets to 1 i.e. bit 0  
8.    
9. //initialising to multiple values with OR (|)  
10. flags = LOG_ERRORS | LOG_WARNINGS | LOG_INCOMING;  
11. // sets to 1 + 2 + 8 i.e. bits 0, 1 and 3  
12.    
13. // setting one flag on, leaving the rest untouched  
14. // OR bitmask with the current value  
15. flags |= LOG_INCOMING;  
16.    
17. // testing for a flag  
18. // AND with the bitmask before testing with ==  
19. if ((flags & LOG_WARNINGS) == LOG_WARNINGS)  
20.    ...  
21.    
22. // testing for multiple flags  
23. // as above, OR the bitmasks  
24. if ((flags & (LOG_INCOMING | LOG_OUTGOING))  
25.          == (LOG_INCOMING | LOG_OUTGOING))  
26.    ...  
27.    
28. // removing a flag, leaving the rest untouched  
29. // AND with the inverse (NOT) of the bitmask  
30. flags &= ~LOG_OUTGOING;  
31.    
32. // toggling a flag, leaving the rest untouched  
33. flags ^= LOG_LOOPBACK;  

Use bit-field for alternative solution 

?

1. /* bit-field */  
2.    
3. struct {  
4. unsigned int is_keyword : 1;  
5. unsigned int is_extern : 1;  
6. unsigned int is_static : 1;  
7. } flags;  
8.    
9. // to turn the bits on;  
10. flags.is_extern = flags.is_static = 1;  
11.    
12. // to turn them off;  
13. flags.is_extern = flags.is_static = 0;  
14.    
15. // to test them  
16. if (flags.is_extern == 0 && flags.is_static == 0)