14.2.2 Type Specific Wrapper Functions
The generic interface described above is su cient 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 check-ing 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 di erent 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 di erent 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 in Section 14.1.3.
1 #include "vector_int.h"
2 #include <assert.h>
3
4 Vector *vector create int(size t capacity)
5 {
6return 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 }
14.2.3 Case Study: qsort()
The standard library function qsort() is declared in header stdlib.h and provides a generic algo-rithm 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 {
15struct Database *d1 = (struct Database *)a;
16struct Database *d2 = (struct Database *)b;
17
18if (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 di erent 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 e ciency due to function-call overhead. The function qsort() incurs function-call overhead for each comparison, and so tends to be less e cient 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 e cient as custom-built code.
No comments:
Post a Comment