10.1.1 Function Declarations

For functions , the declaration looks like bodyless definition, ended by a semicolon. Listing 10-3 shows an example.

Listing 10-3. fun_decl_def.c

/* This is declaration */
void f( int x );

/* This is definition */
void f( int x )    {
    puts( "Hello!" );
}

Such declarations are sometimes called function prototypes. Every time you are using a function whose body is not yet defined OR is defined in another file, you should write its prototype first.

In function prototype the argument names can be omitted, as shown in Listing 10-4.

Listing 10-4. fun_proto_omit_arguments.c

int square( int x );
/* same as */
int square( int );

To sum up, two scenarios are considered correct for functions.

1. Function is defined first, then called (see Listing 10-5).

   Listing 10-5. fun_sc_1.c

   int square( int x ) { return x * x; }
   
   ...
   int z = square(5);

2. Prototype first, then call, then the function is defined (see Listing 10-6).

   Listing 10-6. fun_sc_2.c

   int square( int x );
   
   ...
   int z = square(5);
   
   ...
   
   int square( int x ) { return x * x; }

Listing 10-7 shows a typical error situation, where the function body is declared after the call, but no declaration precedes the call.

Listing 10-7. fun_sc_3.c

int z = square( 5 );
...

int square( int x ) { return x * x; }

10.1.2 Structure Declarations

It is quite common to define a recursive data structure such as linked list . Each element stores a value and a link to the next element. The last element stores NULL instead of a valid pointer to mark the end of list. Listing 10-8 shows the linked list definition.

Listing 10-8. list_definition.c

struct list {
    int value;
    struct list* next;
};

However, in case of two mutually recursive structures, you have to add a forward declaration for at least one of them. Listing 10-9 shows an example.

Listing 10-9. mutually_recursive_structures.c

struct b; /* forward declaration */
struct a {
    int value;
    struct b* next;
};

/* no need to forward declare struct a because it is already defined */
struct b {
    struct a* other;
};

If there is no definition of a tagged type but only a declaration, it is called an incomplete type. In this case we can work freely with pointers to it, but we can never create a variable of such type, dereference it, or work with arrays of such type. The functions must not return an instance of such type, but, similarly, they can return a pointer. Listing 10-10 shows an example.

Listing 10-10. incomplete_type_example.c

struct llist_t;

struct llist_t* f() { ... }   /* ok  */
struct llist_t g();           /* ok  */
struct llist_t g()  { ... }   /* bad */

These types have a very specific use case which we will elaborate in Chapter 13.

10.2.1 Functions from Other Files

It is, of course, possible to call functions or reference global variables from other files. To perform a call, you have to add the called function’s prototype to the current file. For example, you have two files: square.c, which contains a function square, and main_square.c, which contains the main function. Listing 10-11 and Listing 10-12 show these files.

Listing 10-11. square.c

int square( int x ) { return x * x; }

Listing 10-12. main_square.c

#include <stdio.h>
int square( int x );

int main(void) {
    printf( "%d\n", square( 5 ) );
    return 0;
}

Each code file is a separate module and thus is compiled independently, just as in assembly. A .c file is translated into an object file. As for our educational purposes we stick with ELF (Executable and Linkable Format) files; let’s crack the resulting object files open and see what’s inside. Refer to Listing 10-13 to see the symbol table inside the main_square.o object file, and to Listing 10-14 for the file square.o. Refer to section 5.3.2 for the symbol table format explanation.

Listing 10-13. main_square

> gcc -c -std=c89 -pedantic -Wall main_square.c
> objdump -t main_square.o

main.o:     file format elf64-x86-64

SYMBOL TABLE:
0000000000000000 l    df *ABS*  0000000000000000 main.c
0000000000000000 l    d  .text  0000000000000000 .text
0000000000000000 l    d  .data  0000000000000000 .data
0000000000000000 l    d  .bss   0000000000000000 .bss
0000000000000000 l    d  .note.GNU-stack
0000000000000000 .note.GNU-stack
0000000000000000 l    d  .eh_frame
0000000000000000 .eh_frame
0000000000000000 l    d  .comment
0000000000000000 .comment
0000000000000000 g     F .text  000000000000001c main
0000000000000000         *UND*  0000000000000000 square

Listing 10-14. square

> gcc  -c -std=c89 -pedantic -Wall square.c
> objdump -t square.o
square.o:     file format elf64-x86-64

SYMBOL TABLE:
0000000000000000 l    df *ABS*  0000000000000000 square.c
0000000000000000 l    d  .text  0000000000000000 .text
0000000000000000 l    d  .data  0000000000000000 .data
0000000000000000 l    d  .bss   0000000000000000 .bss
0000000000000000 l    d  .note.GNU-stack
0000000000000000 .note.GNU-stack
0000000000000000 l    d  .eh_frame
0000000000000000 .eh_frame
0000000000000000 l    d  .comment
0000000000000000 .comment
0000000000000000 g     F .text  0000000000000010 square

As you see, all functions (namely, square and main) have become global symbols, as the letter g in the second column suggests, despite not being marked in some special way. It means that all functions are like labels marked with global keyword in assembly—in other words, visible to other modules.

The function prototype for square, located in main_square.c, is attributed to an undefined section.

0000000000000000    *UND*    0000000000000000   square

GCC is providing you an access to the whole compiler toolchain, which means that it is not only translating files but calling linker with appropriate arguments. It also links files against standard C library.

After linking, the symbol table becomes more populated due to standard library and utility symbols, such as .gnu.version.

10.2.2 Data in Other Files

If there is a global variable defined in other .c file that we want to address, it should be declared, preferably, but not necessarily, with extern keyword. You should not initialize extern variables; otherwise, compiler issues a warning.

Listing 10-15 and Listing 10-16 show the first example of a global variable usage from another file.

Listing 10-15. square_ext.c

extern int z;
int square( int x ) { return x * x + z; }

Listing 10-16. main_ext.c

int z = 0;
int square( int x );

int main(void) {
    printf( "%d\n", square( 5 ) );
    return 0;
}

The C standard marks the keyword extern as optional. We recommend that you never omit extern keyword so that you might easily distinguish in which file exactly you want to create a variable.

However, in case you do omit extern keyword, how does the compiler distinguish between variable definition and declaration, when no initializing is provided? It is especially interesting given that the files are compiled separately.

In order to study this question, we are going to take a look at the symbol tables for object files using the nm utility.

We write down files main.c and other.c, and then we compile them into .o files by using -c flag and then link them. Listing 10-17 shows the command sequence.

Listing 10-17. glob_build

> gcc -c -std=c89 -pedantic -Wall -o main.o main.c
> gcc -c -std=c89 -pedantic -Wall -o other.o other.c
> gcc -o main main.o other.o

There is one global variable called x. It is not assigned with a value in main.c, but it is initialized in other.c.

Using nm we can quickly view the symbol table, as shown in Listing 10-18. We have shortened the table for the main executable file on purpose to avoid cluttering the listing with service symbols.

Listing 10-18. glob_nm

> nm main.o
0000000000000000 T main
                 U printf
0000000000000004 C x

> nm other.o
0000000000000000 D x

> nm main
0000000000400526 T main
                 U printf@@GLIBC_2.2.5
0000000000601038 D x

As we see, in main.o the symbol x, corresponding to the variable int x, is marked with the flag C (global common), while in the other object file main.o it is marked D (global data). There can be as many similar global common symbols as you like, and in the resulting executable file they will all be squashed into one.

However, you cannot have multiple declarations of the same symbol in the same source file; you are limited to a maximum of one declaration and one definition.

10.2.3 Header Files

So, we know how to split the code into multiple files now. Every file that uses an external definition should have its declaration written before the actual usage. However, when the amount of files grows, maintaining consistency becomes hard. A common practice is to use header files in order to ease maintenance.

Let’s say there are two files: main_printer.c and printer.c. Listings 10-19 and 10-20 show them.

Listing 10-19. main_printer.c

void print_one(void);
void print_two(void);
int main(void) {
    print_one();

    print_two();
    return 0;
}

Listing 10-20. printer.c

#include <stdio.h>

void print_one(void) {
    puts( "One" );
}
void print_two(void) {
    puts( "Two" );
}

Here is the real-world scenario. In order to use a function from the file printer.c in some file other.c, you have to write down prototypes of the functions defined in printer.c somewhere in the beginning of other.c. To use them in the third file, you will have to write their prototypes in the third file too. So, why do it by hand when we can create a separate file that will only contain functions and global variables declarations, but not definitions, and then include it with the help of a preprocessor?

We are going to modify this example by introducing a new header file printer.h, containing all declarations from printer.c. Listing 10-21 shows the header file.

Listing 10-21. printer.h

void print_one( void );
void print_two( void );

Now, every time you want to use functions defined in printer.c you just have to put the following line in the beginning of current code file:

#include "printer.h"

The preprocessor will replace this line with the contents of printer.h. Listing 10-22 shows the new main file.

Listing 10-22. main_printer_new.c

#include "printer.h"

int main(void) {
    print_one();
    print_two();
    return 0;
}

This mechanism, which looks similar to the modules or libraries importing from such languages as Java or C#, is by its nature very different. So, telling that the line #include "some.h" means “importing a library called some” is very wrong. Including a text file is not importing a library! Static libraries, as we know, are essentially the same object files as the ones produced by compiling .c files. So, the picture for an exemplary file f.c looks as follows:

• Compilation of f.c starts.

• The preprocessor encounters the #include directives and includes corresponding .h files “as is.”

• Each .h file contains function prototypes, which will become entries in the symbol table after the code translation.

• For each such import-like entry, the linker will search through all object files in its input for a defined symbol (in section .data , .bss , or .text ). In one place, it will find such a symbol and link the import-like entry with it.

This symbol might be found in the C standard library.

But wait, are we giving to the linker the standard library as input? We are going to discuss it in the next section.

10.4.1 Include Guard

One file can contain a maximum of one declaration and one definition for any given symbol . While you will not write duplicate declarations, you will most probably use header files, which might include other header files, and so on. Knowing which declarations will be present in the current file is not easy: you have to navigate through each header file, and each header file that they include, and so on.

For example, there are three files: a.h, b.h, and main.c, shown in Listing 10-30.

Listing 10-30. inc_guard_motivation.c

/* a.h */
void a(void);

/* b.h */
#include "a.h"
void b(void);

/* main.c */
#include "a.h"
#include "b.h"

What will the preprocessed main.c file look like? We are going to launch gcc -E main.c. Listing 10-31 shows the result.

Listing 10-31. multiple_inner_includes.c

# 1 "main.c"
# 1 "<built-in>"
# 1 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 1 "<command-line>" 2
# 1 "main.c"
# 1 "a.h" 1
void a(void);
# 2 "main.c" 2
# 1 "b.h" 1
# 1 "a.h" 1
void a(void);
# 2 "b.h" 2

void b(void);
# 2 "main.c" 2

Now main.c contains a duplicate function declaration void a(void), which results in a compilation error. The first declaration comes from the a.h file directly; the second one comes from file b.h which includes a.h on its own.

There are two common techniques to prevent that.

• Using a directive #pragma once in the header start. This is a non-standard way of forbidding the multiple inclusion of a header file. Many compilers support it, but because it is not a part of the C standard, its usage is discouraged.

• Using so-called Include guards .

Listing 10-32 shows an include guard for some file file.h.

Listing 10-32. file.h

#ifndef _FILE_H_
#define _FILE_H_

void a(void);

#endif

The text between directives #ifndef _FILE_H_ and #endif will only be included if the symbol X is not defined. As we see, the very first line in this text is: #define _FILE_H_. It means that the next time all this text will be included as a result of #include directive execution; the same #ifndef _FILE_H_ directive will prevent the file contents from being included for the second time.

Usually, people name such preprocessor symbols based on the file name, one such convention was shown and consists of

• Capitalizing file name.

• Replacing dots with underscores.

• Prepending and appending one or more underscores.

We crafted a typical include file for you to observe its structure. Listing 10-33 shows this example.

Listing 10-33. pair.h

#ifndef _PAIR_H_
#define _PAIR_H_

#include <stdio.h>

struct pair {
    int x;
    int y;
};

void pair_apply( struct pair* pair, void (*f)(struct pair) );
void pair_tofile( struct pair* pair, FILE* file );

#endif

The include guard is the first thing we observe in this file. Then come other includes. Why do you need to include files in header files? Sometimes, your functions or structures rely on external types, defined elsewhere. In this example , the function pair_tofile accepts an argument of type FILE*, which is defined in the stdio.h standard header file (or in one of the headers it includes on its own). The type definition comes after that, and then the function prototypes.

10.4.2 Why Is Preprocessor Evil?

Extensive preprocessor usage is considered bad for a number of reasons:

• It often makes code smaller, but also much less readable.

• It introduces unnecessary abstractions.

• In most cases it makes debugging harder.

• Macros often confuse IDEs (integrated development environments) and their autocompletion engines, as well as different static analyzers. Do not be snobbish about these because in larger projects they are of a great help.

The preprocessor knows nothing about language structure, so every preprocessor structure in isolation can be an invalid language statement. For example, a macro #define OR else { can become a part of a valid statement after all substitutions, but it is not a valid statement alone. When macros mix and the statement limits are not well defined, understanding such code is hard.

Some tasks can be close to impossible to solve because of the preprocessor. It limits the amount of intelligence that can be put into the programming environment or static analysis tools. Let’s explore several pitfalls :

1. How clever should the static code analyzer be to understand what foo returns (see Listing 10-34)?

   Listing 10-34. ifdef_pitfall_sig.c

   #ifdef SOMEFLAG
   int foo() {
   #else
       void  foo()  {
   #endif
   /* ... */
   }

2. You have to find all occurrences of the min macro, which is defined as

   #define min(x,y) ((x) < (y) ? (x) : (y)).

   As you have seen in the previous example, to parse the program you have to first perform preprocessing passes, otherwise the tool might not even understand the functions boundaries. Once you perform preprocessing, all min macros are substituted and thus become untraceable and indistinguishable from such lines as

   int z = ((10) < (y) ? (5) : (3)).

3. Static analysis (and even your own program understanding) will suffer because of macro usage. Syntactically, macro instantiations with parameters are indistinguishable from function calls. However, while function arguments are evaluated before a function call is performed, macro arguments are substituted and then the resulting lines of code are executed.

For example, take the same macro #define min(x,y) ((x) < (y) ? (x) : (y)). The instantiation with arguments a and b-- will look like: ((a) < (b--) ? (a) : (b--)). As you see, if a >= b, then the variable b will be decremented twice. If min was a function, b-- would have been executed only once.

10.5.1 Sneak Peek into Dynamic Memory Allocation

In order to complete the next assignment, you have to learn to use the malloc and free functions . We will discuss them in greater detail later, but for now, we will do a quick introduction.

The local variables as well as the global ones allow you to allocate a fixed amount of bytes. However, when the allocated memory size depends on input, you can either allocate as much memory as you think will suffice in all cases or use malloc function, which allocates as much memory as you ask it to.

void* malloc(size_t sz) returns the start of an allocated memory buffer of size sz (in bytes) or NULL in case of failure. This buffer holds random values on start. As it returns void*, this pointer can be assigned to a pointer of any other type.

All these allocated regions of memory should be freed when they are no longer used by calling free on them.

In order to use these two functions , you have to include malloc.h. Listing 10-35 shows a minimal example of malloc and free usage.

Listing 10-35. simple_malloc.c

#include <malloc.h>

int main( void ) {
    int* array;

    /* malloc returns the allocated memory starting address
     * Notice that its argument is the byte size, elements count multiplied
     * by element size */
array = malloc( 10 * sizeof( int ));

    /* actions on array are performed here */

    free( array ); /* now the related memory region is deallocated */
    return 0;
}

10.5.2 Example

Listing 10-36 shows the example. It contains three functions of interest:

• array_read to read an array from stdin. The memory allocation happens here.

  Notice the usage of scanf function to read from stdin. Do not forget that it accepts not the variable values but their addresses, so it could perform an actual writing into them.

• array_print to print a given array to stdout.

• array_sum to sum all elements in an array.

Notice that the array allocated somewhere using malloc persists until the moment free is called on its starting address. Freeing an already freed array is an error.

Listing 10-36. sum_malloc.c

#include <stdio.h>

#include <malloc.h>

int* array_read( size_t* out_count ) {
    int* array;
    size_t i;
    size_t cnt;
    scanf( "%zu", &cnt );
    array = malloc( cnt * sizeof( int ) );

    for( i = 0; i < cnt; i++ )
        scanf( "%d", & array[i] );

    *out_count = cnt;
    return array;
}

void array_print( int const* array, size_t count ) {
    size_t i;

    for( i = 0; i < count; i++ )
        printf( "%d  ", array[i] );
    puts("");
}

int array_sum( int const* array, size_t count ) {
    size_t i;
    int sum = 0;
    for( i = 0; i < count; i++ )
        sum = sum + array[i];
    return sum;
}

int main( void ) {
    int* array;
    size_t count;

    array = array_read( &count );
    array_print( array, count );
    printf( "Sum is: %d\n", array_sum( array, count ) );
    free( array );
    return 0;
}                                                                                    

10.6.1 Assignment

The program accepts an arbitrary number of integers through stdin. What you have to do is

1. Save them all in a linked list in reverse order.

2. Write a function to compute the sum of elements in a linked list.

3. Use this function to compute the sum of elements in the saved list.

4. Write a function to output the n-th element of the list. If the list is too short, signal about it.

5. Free the memory allocated for the linked list.

You need to learn to use

• Structural types to encode the linked list itself.

• The EOF constant. Read the section “Return value” of the man scanf.

You can be sure that

• The input does not contain anything but integers separated by whitespaces.

• All input numbers can be contained into int variables.

Following is the recommended list of functions to implement:

• list_create – accepts a number, returns a pointer to the new linked list node.

• list_add_front – accepts a number and a pointer to a pointer to the linked list. Prepends the new node with a number to the list.

For example: a list (1,2,3), a number 5, and the new list is (5,1,2,3).

• list_add_back, adds an element to the end of the list. The signature is the same as list_add_front.

• list_get gets an element by index, or returns 0 if the index is outside the list bounds.

• list_free frees the memory allocated to all elements of list.

• list_length accepts a list and computes its length.

  • list_node_at accepts a list and an index, returns a pointer to struct list, corresponding to the node at this index. If the index is too big, returns NULL.

  • list_sum accepts a list , returns the sum of elements.

These are some additional requirements:

• All pieces of logic that are used more than once (or those which can be conceptually isolated) should be abstracted into functions and reused.

• The exception to the previous requirement is when the performance drop is becoming crucial because code reusage is changing the algorithm in a radically ineffective way. For example, you can use the function list_at to get the n-th element of a list in a loop to calculate the sum of all elements. However, the former needs to pass through the whole list to get to the element. As you increase n, you will pass the same elements again and again.

In fact, for a list of length N, we can calculate the number of times elements will be addressed to compute a sum.

We start with a sum equal to 0. Then we add the first element, for that we need to address it alone (1). Then we add the second element, addressing the first and the second (2). Then we add the third element, addressing the first, the second, and the third as we look through the list from its beginning. In the end what we get is something like O(N ²) for those familiar with the O-notation. Essentially it means that by increasing the list size by 1, the time to sum such a list will have N added to it.

In such case it is indeed wiser to just pass through the list, adding a current element to the accumulator.

• Writing small functions is very good most of the time.

• Consider writing separate functions to: add an element to the front, add to the back, create a new linked list node.

• Do not forget to extensively use const, especially in functions accepting pointers as arguments!