Tutorial : C - Generic Programming

Generic Programming

Writing generic and reusable software is one of the pinnacles of software design. It permits the creation of a toolbox of generally useful code modules or libraries that may be used time and again. The antithesis of generic design is a set of functions that possess virtually identical code, but differ in terms of the types they operate on. The basic purpose of generic programming is to avoid such code repetition; to define an algorithm or data-structure and that works with a variety of different types. Coding for the general case tends to reduce the overall coding effort, reduce the likelihood of errors, and increase code modularity and reuse.

Some of the topics presented below have been covered in previous chapters. This chapter brings them together under the guise of writing generic programs. The most powerful feature in the C language for generic programming is the ability to cast between different types, particularly pointer types, and, most significantly, the generic pointer type void*. This chapter examines the use of void* in generic software design in terms of two examples: an expandable array and the standard library function qsort(). The discussion of qsort() also shows how function pointers can be used to enhance the flexibility of a generic design.

 

 

Basic Generic Design: Typedefs, Macros, and Unions
 
Typedefs, macros, and unions facilitate limited forms of generality, with each permitting increased flexibility in a specific area of code design. Typedefs provide type-name synonyms, macros circumvent C type-checking, and unions define variant types.

 

 

Typedefs

The keyword typedef permits the creation of new type names for existing types. These type synonyms permit an algorithm to be written such that it can work with different types by simply changing the appropriate typedefs. For example, by defining the name

typedef char Item;

an algorithm defined in terms of Item can be changed to work with doubles by simply changing the typedef to

typedef double Item;

This technique is demonstrated in the expandable vector example in Section 11.7, where the variable type contained by the vector is specified by a typedef. The limitation of typedef is that its type is fixed at compile time, and an algorithm cannot be used with different types in a single program.

 

 

Macros

Macros can be used with different types in a given program because they avoid the type-constraints of the C compiler. The C preprocessor expands macro text inline, so that macros essentially automate code duplication. For example, given the macro

#define MAX(x,y) ((x)<(y) ? (y) : (x))

and a set of variables

int x = 1, y = 2, z;
double a = 3.2, b = -9.1, c;

then the following code

z = MAX(x,y);
c = MAX(a / 2.7,b + 1);

expands to

z = ((x)<(y) ? (y) : (x));
c = ((a / 2.7)<(b + 1) ? (b + 1) : (a / 2.7));

As another example, the macro below returns the number of elements in an array x.

#define NELEMS(x) (sizeof(x)/sizeof(x[0]))

This macro works for arrays of any type including arrays of doubles, pointers, structures, and so forth.

Using macros for anything but the most trivial of operations is not advised. To compose any significant algorithm as a macro is both notationally inconvenient and error prone. Macros do not obey the type and scope rules imposed by the C language, and can introduce cryptic syntactical errors if not used with caution.

 

 

Unions

Unions permit the definition of variant types—types that may represent one of several different types. This facility is useful if one wishes to pass various types at different times through the same function interface. It is also used to create a collection of different types (i.e., to create a heterogeneous array).

An example of a heterogeneous array is given in Section 11.8, where we noted that unions are usually wrapped in a structure, which defines the type of the value currently stored by the union. The following example shows a similar design for passing variant types to a function.

1 enum VariantType { INT, FLOAT, STRING };
2
3 typedef struct {
4 	enum VariantType type;
5 		union {
6 			int i;
7 			float f;
8 			char *s;
9 		} value;
10 	} Variant;
11
12 	void interpret command(Variant command)
13 	{
14 		switch (command.type)
15 		{
16 			case INT: printf("Got integer %d\n", command.value.i); break;
17 			case FLOAT: printf("Got float %f\n", command.value.f); break;
18 			case STRING: printf("Got string %s\n", command.value.s); break;
19 			default: printf("Unknown type %d\n", command.type); break;
20 		}
21 	}

The function interpret_command() might be passed information as follows.

Variant v, w;
v.type = INT; v.value.i = -5;
w.type = STRING; w.value.s = "COMMAND";
interpret_command(v);
interpret_command(w);

Aside: Notice that the definition of the structure Variant (lines 3 to 10) contains an unnamed union type with a single variable value. Structures and unions do not have to be named if they define a set of variables and are never referred to again.

 

 

Advanced Generic Design: 

The void* pointer type, in conjunction with the ability to cast between pointer types, permits a very powerful and flexible form of generic programming. With these facilities we can implement algorithms and data-structures that operate on any number of different types. In addition, we show how function pointers can be used to specialise certain parts of an algorithm at run-time.

This discussion is presented in terms of two examples. The first is the expandable array Vector that has been developed. The second is the standard library function qsort(), which is used to sort the elements of an array.

 

 

Case Study: Expandable Array

The following implementation of the expandable array overcomes the limitations of the previous versions. It permits any number of Vector objects to be defined, and each of these may contain elements of a different type. There is no longer the constraint of one item-type per program that was imposed by typedef. This increase in flexibility comes at the price of a slight decrease in efficiency and a significant loss of compile-time type-safety. However, the issue of type-safety can be redeemed somewhat by using wrapper functions, as we shall see.

The first thing to notice when reading this source code is how similar it is to the original implementation, which permitted just one vector and could only contain integers (see Section 9.5). A fully generic implementation is thus possible without any great increase in code complexity.

The code below shows the contents of the public interface declared in vector.h. The header exports all the declarations that should be visible to the client in order to use this module. Notice that the definition of struct Vector is not exported. All operations on Vector are performed by its associated functions, and the client only ever uses a pointer as a handle to a Vector object. Particularly, the client never has access to the structure members. Therefore, only the structure declaration, which is called an “incomplete type” or “opaque type”,1 needs to be visible to the client.

1 #ifndef GENERIC EXPANDABLE VECTOR H
2 #define GENERIC EXPANDABLE VECTOR H
3
4 #include <stddef.h> /* for size t */
5 typedef struct Vector Vector;
6
7 /* Vector creation and destruction. */
8 Vector *vector create(size t capacity, size t itemsize);
9 void vector destroy(Vector *v);
10
11 /* Vector access operations. */
12 int vector push back(Vector *v, const void *item);
13 void vector pop back(Vector *v, void *item);
14 void* vector get element(Vector *v, size t index);
15 void* vector get begin(Vector *v);
16 void* vector get end(Vector *v);
17
18 /* Size operations. */
19 size t vector get item size(const Vector *v);
20 size t vector get size(const Vector *v);
21 size t vector get capacity(const Vector *v);
22 int vector set size(Vector *v, size t size);
23 int vector set capacity(Vector *v, size t size);
24
25 #endif

The next section of code is from the top of the source file vector.c. Lines 6 to 14 comprise the private interface, which contains implementation details that are internal to the Vector functionality and are hidden from the client.

1 #include <stdlib.h>
2 #include <string.h>
3 #include <assert.h>
4 #include "vector.h"
5
6 static const size t StartSize = 5; /* initial vector capacity */
7 static const float GrowthRate = 1.6f; /* geometric growth of vector capacity */
8
9 typedef struct Vector {
10 void *data; /* pointer to vector elements */
11 size t capacity; /* current reserved memory for vector */
12 size t size; /* current size of vector (number of stored items) */
13 size t itemsize; /* size of each item */
14 } Vector;

An important advantage of hiding the members of struct Vector in the private interface is that it permits different implementations to be used without having any effect on client code. For example, the structure might one day be changed to

typedef struct Vector {
	void *begin; /* pointer to beginning of allocated memory */
	void *end; /* pointer to one-past-end of allocated memory */
	void *last; /* pointer to one-past-end of last vector item */
	size_t itemsize; /* size of each item */
} Vector;

This structure definition would permit alternative implementations of the functions described below that might be slightly more efficient. The key point is that these changes would be contained within the module and would not be visible to clients.

The next two functions create and destroy a Vector, respectively. Their implementation is trivial. The function vector_create() is passed two variables. The first is an initial capacity—the number of elements for which to allocate space. The second is the size of each element which, because the function is generic, is not known to the compiler and must be stated explicitly. For example, to create a Vector of integers with initial space for five values, we write

Vector v;
v = vector_create(5, sizeof(int));
15 Vector *vector create(size t capacity, size t itemsize)
16 /* Initialise a vector with the specified capacity for items of size itemsize. */
17 {
18 Vector *v = (Vector *)malloc(sizeof (Vector));
19 if (v) {
20 v−>data = malloc(capacity*itemsize);
21 v−>capacity = (v−>data == NULL)?0: capacity;
22 v−>size = 0;
23 v−>itemsize = itemsize;
24 }
25 return v;
26 }
27
28 void vector destroy(Vector *v)
29 /* Release memory owned by vector. */
30 {
31 free(v−>data);
32 free(v);
33 }

The functions below provide access to the elements of Vector. Of these, the implementation of vector_push_back() is the most complex, but it is described thoroughly. The only new features are the conversions between void* and char* pointer types, and the use of the standard library function memcpy().

34 int vector push back(Vector *v, const void *item)
35 /* Add element to back of vector. Return index of new element if successful, and -1 if fails. */
36 {
37 /* If out-of-space, allocate more. */
38 if (v−>size == v−>capacity) {
39 size t newsize = (v−>capacity == 0) ? StartSize : (size t)(v−>capacity*GrowthRate + 1.0);
40 void *p = realloc(v−>data, newsize*v−>itemsize);
41 if (p == NULL)
42 return −1;
43
44 v−>capacity = newsize; /* allocate succeeds, update data-structure */
45 v−>data = p;
46 }
47
48 /* We have enough room. */
49 memcpy((char*)v−>data + v−>size * v−>itemsize, item, v−>itemsize);
50 return v−>size++;
51 }
52
53 void vector pop back(Vector *v, void *item)
54 /* Return element from back of vector, and remove it from the vector. */
55 {
56 assert(v−>size > 0);
57 −−v−>size;
58 memcpy(item, (char*)v−>data + v−>size * v−>itemsize, v−>itemsize);
59 }
60
61 void* vector get element(Vector *v, size t index)
62 /* Return pointer to the element at the specified index. */
63 {
64 assert(index >= 0 && index < v−>size);
65 return (char*)v−>data + index * v−>itemsize;
66 }
67
68 /* Return pointer to beginning of array (ie, to first element of array). */
69 void* vector get begin(Vector *v) { return v−>data; }
70
71 /* Return pointer to one-past-end of array. */
72 void* vector get end(Vector *v) { return (char*)v−>data + v−>size*v−>itemsize; }

The conversion to a char* pointer is necessary because it is not possible to perform pointer arithmetic with a void* pointer. That is, a void* pointer is simply a variable large enough to hold any pointer type; it does not specify any particular pointed-to type and does not inform the compiler as to the size of the pointed-to type. Thus, an expression such as ptr + index has no meaning for a void* pointer as the compiler cannot compute the pointer offset. Furthermore, it is not possible to dereference a void* pointer.

By converting a void* pointer to char*, we are able to perform pointer arithmetic over each byte of the pointed-to data. This gives us full control over the array of elements in Vector. For example, consider the statement on line 65, which returns a pointer to the element specified by index.

return (char *)data + index * itemsize;

This statement might equivalently have been written

char *tmp = (char *)data;
return &tmp[index * itemsize];

Notice that, since we are operating on bytes, the required pointer offset must be computed explicity: index * itemsize. However, if the type of the array elements were known, the array pointer could be cast to this type and the compiler would compute the offset automatically. For example, if the array was known to be of type double, the above statement could be rewritten as

double *tmp = (double *)data;
return &tmp[index];

but, as we don’t know the type at compile time, we must compute the offset ourselves. To copy bytes of data from one place to another, we use the standard function memcpy(), which has the following interface.

void *memcpy(void *dest, const void *src, size_t size);

This function copies size bytes from the region of memory pointed to by src to the region of memory pointed to by dest. The functions vector_get_begin() and vector_get_end() return pointers to the first element in the array and to the one-past-the-end of the array, respectively. The use of one-past-the-end pointers is uncommon in C but ubiquitous in C++. It permits the implementation of the following idiom to iterate over an array.

float *begin, *end, *pf;
begin = (float *)vector_get_begin(v);
end = (float *)vector_get_end(v);
for (pf = begin; pf != end; ++pf)
printf("%f ", *pf);

The final set of functions shown below are provided for completeness. Their implementations present no new details not described previously.

73 /* Inquire after size of vector item. */
74 size t vector get item size(const Vector *v) { return v−>itemsize; }
75
76 /* Inquire after vector size and capacity */
77 size t vector get size(const Vector *v) { return v−>size; }
78 size t vector get capacity(const Vector *v) { return v−>capacity; }
79
80 int vector set size(Vector *v, size t size)
81 /* Set vector size. Return 0 if successful, -1 if fails. */
82 {
83 if (size > v−>capacity) {
84 void *p = realloc(v−>data, size*v−>itemsize);
85 if (p == NULL)
86 return −1;
87
88 v−>capacity = size; /* allocate succeeds, update data-structure */
89 v−>data = p;
90 }
91
92 v−>size = size;
93 return 0;
94 }
95
96 int vector set capacity(Vector *v, size t size)
97 /* Shrink or grow allocated memory reserve for array.
98 * A size of 0 deletes the array. Return 0 if successful, -1 if fails. */
99 {
100 if (size != v−>capacity) {
101 void *p = realloc(v−>data, size*v−>itemsize);
102 if (p == NULL && size > 0)
103 return −1;
104
105 v−>capacity = size;
106 v−>data = p;
107 }
108
109 if (size < v−>size)
110 v−>size = size;
111 return 0;
112 }

 

 

Type Specific Wrapper Functions

The generic interface described above is sufficient for use in client applications, but is subject to a number of disadvantages. The most important is loss of type-safety. For example, having created a Vector of ints, the compiler will not prevent you from pushing doubles onto it, or attempting to pop char pointers. A related problem is that the compiler will not perform the usual type conversions when passing variables to these functions, such as converting a float to double for a Vector of doubles. And finally, this interface does not allow constants or expressions to be passed to a Vector, as in the following examples.

vector_push_back(v, &50); /* Invalid, cannot take address of a constant. */
vector_push_back(v, &(i + j)); /* Invalid, cannot take address of an expression. */

A good technique to improve type-safety, and also address the other problems mentioned above, is to wrap the generic interface in type-specific “wrapper functions”. These functions use the generic implementations to perform the bulk of the algorithm but provide interfaces that permit type checking and type conversion by the compiler. Consider the following set of wrapper functions for Vectors of type int. The header file vector_int.h contains the public interface.

1 #ifndef INT EXPANDABLE VECTOR H
2 #define INT EXPANDABLE VECTOR H
3
4 #include "vector.h"
5
6 /* Vector creation. */
7 Vector *vector create int(size t capacity);
8
9 /* Vector access operations. */
10 int vector push back int(Vector *v, int item);
11 int vector pop back int(Vector *v);
12
13 #endif

There are several points to note from this header file. The first is operations such as pushing an integer onto the array may be performed with expressions or constants.

vector_push_back_int(v, 50);
vector_push_back_int(v, i + j);

The second is that items of the wrong type are automatically converted to ints by the usual type conversion rules.

char val = 32;
vector_push_back_int(v, val); /* val automatically converted to int. */

Finally, notice that wrappers are not provided for most of the generic public interface. This is because most operations do not require a type-specific wrapper, and the generic interface can be used directly without issue. For example, vector_destroy(), vector_get_element(), vector_set_size(), etc, do not rely on type information.

Style Note: It is good practice to avoid including header files in other header files where possible. This is in order to minimise dependencies between different modules. In the case of vector_int.h, the inclusion of vector.h could be avoided, and replaced with

typedef struct Vector Vector;

as the declarations in vector_int.h make no reference to any other part of the Vector public interface. Rather, vector.h would be included in the source file vector_int.c, and the dependence between the two headers is reduced to a single declaration.

We have chosen to include vector.h in vector_int.h on this occasion because the two modules are inherently coupled. We never call vector_create_int() without calling the generic function vector_destroy(). Thus, there is no need to minimise their dependence.

The next set of functions are the contents of the source file vector_int.c. These functions call the generic functions to perform the actual operations, but also incorporate some type-checking code. In the following implementations, checking is very primitive—simply that the passed vector contains items of the appropriate size, which protects against memory errors. They do not check whether the actual element types are correct, and different types of compatible size will not be caught. It is possible to strengthen this type-checking by including a type-field in the Vector structure similar to that used for unions.

1 #include "vector_int.h"
2 #include <assert.h>
3
4 Vector *vector create int(size t capacity)
5 {
6 return vector create(capacity, sizeof (int));
7 }
8
9 int vector push back int(Vector *v, int item)
10 {
11 assert(vector get item size(v) == sizeof (int));
12 return vector push back(v, &item);
13 }
14
15 int vector pop back int(Vector *v)
16 {
17 int i;
18 assert(vector get item size(v) == sizeof (int));
19 vector pop back(v, &i);
20 return i;
21 }

 

 

Case Study: qsort()

The standard library function qsort() is declared in header stdlib.h and provides a generic algorithm for sorting arrays. The function is called qsort() because it is typically implemented using the algorithm known as “quick-sort”. Quick-sort is the algorithm of choice for most sorting tasks, as it is on average the fastest general-purpose method available. The details and pitfalls of quick-sort are beyond the scope of this text but are discussed thoroughly in any good algorithms textbook.

The qsort() function is interesting, not simply because it can be used with arrays of any type, but because it uses function pointers to allow the client to customise part of the sorting algorithm. The ability to create specialised sub-algorithms via function pointers greatly enhances the power of generic code. In the case of qsort(), the custom sub-algorithm is a comparison function that compares two elements in an array so that they might be placed in sorted order.

The general interface of qsort() is

void qsort(void *array, size_t nobj, size_t size,
	int (*cmp)(const void *, const void *));

where the first three arguments are a pointer to the beginning of an array, the number of elements in the array, and the size of each element, respectively. The last argument is a pointer to a comparison function, which takes two (generic) arguments and returns an integer. This function is used internally by qsort(), which passes it pairs of array elements. The function returns a negative value if the first element is less than the second, a positive value if the second is less than the first, and zero if they are equal.

The following example uses qsort() to sort an array of structures of type struct Database. This structure contains two values—a key and another item—and the array elements are to be sorted so that the keys are in ascending order. The function comp_dbase(), in lines 12 to 23, specifies this ordering given any two Database variables, and is the custom comparison function for qsort(). Notice that the comparison statements on lines 18 to 22 may have been written more succinctly as

return d1->key - d2->key;

but we refrain from this approach as the result might overflow if one key is very negative and the other very positive.

In main() we first create an array of Database elements, and give each element a random key value (lines 30 to 33). We then sort the array and print the result with the keys now in ascending order.

1 #include <stdlib.h>
2 #include <string.h>
3 #include <stdio.h>
4
5 #define NELEMS(x) (sizeof (x)/sizeof (x[0]))
6
7 struct Database {
8 int key;
9 float item;
10 };
11
12 int comp dbase(const void *a, const void *b)
13 /* Returns -ve if a<b, 0 if a==b, +ve if a>b */
14 {
15 struct Database *d1 = (struct Database *)a;
16 struct Database *d2 = (struct Database *)b;
17
18 if (d1−>key < d2−>key)
19 return −1;
20 if (d1−>key > d2−>key)
21 return 1;
22 return 0;
23 }
24
25 int main(void)
26 {
27 int i;
28 struct Database db[10];
29
30 for (i = 0; i < NELEMS(db); ++i) {
31 db[i].key = rand();
32 db[i].item = (float)i;
33 }
34
35 qsort(db, NELEMS(db), sizeof db[0], comp dbase);
36
37 for (i = 0; i < NELEMS(db); ++i)
38 printf("%5d %.1f\n", db[i].key, db[i].item);
39 }

The power of qsort() is that it may be used with arrays of any arbitrary data-type such as,

struct Dictionary {
	char *word;
	char *defn;
};

and each different data type may be compared via its own particular comparison function, as in the following example.

int comp_dict(const void *a, const void *b)
{
	struct Dictionary *d1 = (struct Dictionary *)a;
	struct Dictionary *d2 = (struct Dictionary *)b;
	return strcmp(d1->word, d2->word);
}

Thus, if we were to create an array dt[100] of type struct Dictionary, we could sort it as follows.

qsort(dt, NELEMS(dt), sizeof(dt[0]), comp_dict);

Generic code that relies on function pointers typically comes at the price of reduced efficiency due to function-call overhead. The function qsort() incurs function-call overhead for each comparison, and so tends to be less efficient than a custom-built quick-sort algorithm. In C++ the facilities of templates and inlined functions avoid these runtime penalties and permit the construction of generic code that is as efficient as custom-built code.