Click Here!
home account info subscribe login search FAQ/help site map contact us


 
Brief Full
 Advanced
      Search
 Search Tips
[an error occurred while processing this directive]
Previous Table of Contents Next


The asterisk in parentheses is the nucleus of a function pointer. Two additional components are required—the return type, which is void in this example, and a parameter list enclosed in parentheses on the right. In this case, the parameter list is empty. Please note that you did not define a pointer in the declaration void (*) (), only a type of a pointer. A pointer variable, of course, has to have a name. Here is an example of a pointer variable with the same signature:

void (*p) ();  //p is a pointer to a function that does not
	        //return a value and takes no arguments

The name of a pointer variable appears on the right of the asterisk, within the parentheses. After a pointer variable is declared, a value can be assigned to it. A value is simply the name of a function that has an identical signature, for instance:

void func() {}
p = func;

A different value can be assigned to p as long as the value assigned to it is an address of a function with an identical signature. Please note that the name of a function is not a part of its type.

Let’s get back to qsort. The fourth argument of qsort is a pointer to a function of the type:

int (*) (const void *, const void *)

Now you can parse this expression. The leftmost token is the return value, int in this case. The asterisk enclosed in two parentheses denotes a function pointer. The parameter list appears next. It declares the type of the function’s arguments—a void pointer to a const object and another void pointer to a const object. Thus, any function that takes two void pointers to const objects (no additional arguments are allowed) and returns an int is suitable for qsort.qsort is responsible for invoking this callback function through its address. That is, the callback function “registers” itself in qsort, and lets qsort call it as needed.

What is the role of qsort’s callback function? A sorting operation consists of two independent stages. First, the elements have to be compared to one another. In the second stage, the result of the comparison is used to relocate elements to their relative positions in the array. As you can see, the first stage is type dependent; in order to compare two elements, their types and values are needed. However, the second phase, that is, the elements’ relocation process, is type independent. All it needs is the size of an element, its address, and the total number of elements in order to reposition them in memory. This information is contained in the first three arguments of qsort. The fourth argument is a pointer to the callback function. The callback function compares the elements and therefore, it has to know their type.

To summarize, the sorting algorithms can be divided into two tasks: one responsible for memory relocations, and a second task, which is responsible for performing comparisons. The memory relocation task is implemented in a generic function; the comparison task is implemented in a callback function.

Let’s look at MAIN.CPP again to see the invocation of qsort.

qsort( iarr,          /* address of array’s beginning */
       10,            /* number of elements in array */
       sizeof (int),  /* sizeof each element */
       compare);      /* pointer to user-defined comparison function */

The address of compare, the callback function, is passed in the fourth argument. compare itself is declared in COMPARE.H like this:

int __cdecl compare (const void* pfirst, const void  * psecond);

As you can see, compare has a signature that complies with the signature expected by qsort.compare returns an int and takes two void pointers that point to const data. (The __cdecl specifier is a Microsoft-specific flag that instructs the compiler to use the C calling convention.) The return value has to be in one of three ranges: 0 indicates the arguments are equivalent. A negative value indicates the first argument is smaller than the second one, and a positive value indicates the first argument is greater than the second one.

Now that you know what compare basically does, let’s look at COMPARE.CPP to see how it does it.

compare takes two arguments, pfirst and psecond. As you already know, the comparison is aware of the type of the array elements. Therefore, compare first casts pfirst and psecond into pointers to const int, and dereferences the resulting pointers. Two local const ints, first and second, hold the values recovered from the dereferenced pointers.

int __cdecl compare (const void* pfirst, const void  * psecond)
{
  const int first = * ( (const int *)  pfirst);  /* dereference first arg */
  const int second = *( (const int*) psecond);  /* dereference second arg */

The rest is simple. Subtract second from first and return the result:

return (first - second);

compare is invoked by qsort, which in turn examines the value returned from compare to relocate the elements of the array in an ascending order.

Comments

qsort, as noted earlier, is a generic function. To see how it sorts an array of C strings, use a revised version of the preceding example.

Steps

1.  Erase the contents of the COMPARE.CPP file entirely and type the following code into it:
#include <string.h>

int __cdecl compare (const void * pfirst, const void  * psecond)
{
  return strcmp(*(const char**) pfirst, *(const char **) psecond);
}
2.  Save COMPARE.CPP. Erase the contents of the MAIN.CPP entirely and then type the following code into it:
#include <stdlib.h>
#include <stdio.h>
#include “compare.h”

void main()
{
  /* define an array of pointers to char and initialize */
  /* its elements */
  char * sarr[] = {“Stroustrup”, “Koenig”, “Ritchie”,
  ⇒“Kernighan”};
  int j = 0; /* loop counter */

  for(; j < 4; j++) /* display array before sorting */
    printf (“element %d of sarr is: %s\n”, j, sarr[j]);
     /* sort sarr using qsort function */
  qsort( sarr,          /* address of array’s beginning */
	 4,               /* number of elements in array */
	 sizeof (char *), /* sizeof each element */
	 compare);        /* pointer to user-defined */
			     /* comparison function */

  printf (“sorted\n\n”);
  j = 0;  /* reset loop counter */

  for(; j < 4; j++) /* display sorted array */
    printf (“element %d of carr is: %s\n”, j, sarr[j]);
}


Previous Table of Contents Next


Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home

Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.