Data Structures and Algorithms: Functions as Data Types

Data Structures and Algorithms

Functions as Data Types

2.7.1 C functions

C allows a function to be used as a data item. This makes it possible to pass functions as arguments to other functions. This capability, although not often used, is extremely useful when it is appropriate. For example, as we initially defined the collections, even though we were careful to design our collection so that it would handle any type of data, we limited ourselves to collections of only one type of data in any one program. This is caused by the need to define an external function for comparing items. Ideally, we would like to specify a general comparison function function for the objects in the collection when we constructed the collection. In C, this is easy (although the syntax is definitely non-intuitive!). We want to have a general comparison function which tells us what order objects to be stored in our collection should be ranked in, ie we need a function:

int ItemCmp( void *a, void *b );

which returns -1, 0 or +1 depending on whether a is less than, equal to or greater than b. (Note that we're allowing a very general notion of 'less than': the ItemCmp can order items according to any rule which might be appropriate to these items.)

So we add to our collection structure, a comparison function:


struct t_collection {
    int item_cnt;
    int (*ItemCmp)( void *, void * );
    ....
    };

ItemCmp is a pointer to a function which has the prototype:


    int ItemCmp( void *, void * );

The parentheses are necessary to distinguish this declaration from the function prototype and an invocation of the function! The ConsCollection function now becomes:


    collection ConsCollection( int max_items, 
                       int (*ItemCmp)( void *, void * ) );

A use of the collection now looks like:


#include "widget.h"     /* import the ADT for widgets */
    int WidgetComp( widget, widget );
    collection LotsOfWidgets;

    LotsOfWidgets = ConsCollection( large_no, WidgetComp );

In the body of the ADT, the ItemCmp function is used by de-referencing the pointer to the function and using it normally: in FindInCollection, we might have:


int FindInCollection( collection c, void *a )
    {
    .....
    if ( (*(c->ItemCmp))( c->items[i], a ) == 0 )
        {
        /* Found match ... */
    ....
    }

In the example above, an excessive number of parentheses has been used, because I simply don't want to bother to look up the precedence rules: why risk making a silly mistake, when a few extra parentheses will ensure that the compiler treats the code as you intended?

However, C permits a 'shortcut' - which doesn't require de-referencing the pointer to the function: in the source code examples, an ItemCmp function has been added to a tree collection.

New collection specification

New tree implementation

Key terms