[mascara-docs.git] / lang / C / the.ansi.c.programming.language / c.programming.notes.int / sx10b.html
| blob | c22008e189bb9025c9ba1b0e3748b89a64fcd49d |
2 <!-- This collection of hypertext pages is Copyright 1995-7 by Steve Summit. -->
3 <!-- This material may be freely redistributed and used -->
4 <!-- but may not be republished or sold without permission. -->
5 <html>
6 <head>
13 </head>
14 <body>
17 <p>In this section we'll list several situations
18 where function pointers can be useful.
20 that is,
21 rearranging a set of items into a desired sequence.
22 It's especially common for the
23 set of items
24 to be contained in an array.
25 Suppose you were writing a function to sort an array of strings.
26 Roughly speaking,
27 the algorithm for sorting the elements of an array looks like this:
28 <blockquote><I><pre>
29 for all pairs of elements in the array
30 if the pair is out of order
31 swap them
32 </pre>
33 </I></blockquote>In C,
34 the outline of the function might therefore look like this:
35 <pre>
36 stringsort(char *strings[], int nstrings)
37 {
39 {
41 {
42 char *tmp = strings[i];
43 strings[i] = strings[j];
44 strings[j] = tmp;
45 }
46 }
47 }
48 </pre>
49 Remember,
51 and returns either a negative number, zero, or a positive number
52 depending on whether the first string was ``less than,''
53 the same as, or ``greater than'' the second string.
54 If you haven't seen it before,
55 the series of three assignments
57 is a standard idiom for swapping two items.
58 (The more obvious pair of assignments
59 <pre>
60 strings[i] = strings[j];
61 strings[j] = strings[i];
62 </pre>
63 would just about as obviously not work,
66 </p><p>Naturally,
67 a real sort function implementing a real sorting algorithm
68 will be a bit more elaborate;
69 in particular, the details of how we choose
70 which pairs of elements to compare
71 (and in what order)
72 can make a huge difference in how efficiently
73 the function completes its job.
74 We'll show a complete example in a minute,
75 but for now,
76 our more important focus is on the comparison step.
77 The final ordering of the strings
79 of what it means for one string to be
80 ``less than'' or ``greater than'' another.
83 (as we saw in chapter
85 8)
86 is to look at them a character at a time,
87 based on their values in the machine's character set
88 (which is how C always treats characters).
89 In ASCII, the character set that most computers use,
90 the codes representing the letters are in order,
92 pretty close to alphabetical order,
93 with the significant difference that all the upper-case letters
94 come before the lower-case letters.
96 would sort the words
97 ``Zeppelin,''
98 ``able,''
99 ``baker,''
100 and
101 ``Charlie''
102 into the order
103 <blockquote><pre>
104 Charlie
105 Zeppelin
106 able
107 baker
108 </pre>
110 which consist entirely of digits,
111 because it goes from left to right,
112 stopping when it finds the first difference,
113 without regard to whether it was comparing
114 the ten's digit of one number to the hundred's of another.
116 would sort the strings
123 and
125 into the order
126 <pre>
127 1
128 12
129 2
130 234
131 24
132 3
133 4
134 </pre>
135 </p><p>Depending on circumstances,
136 we might want our string sorting function to sort
138 or into ``dictionary''
140 order
141 (that is, with all the a's together, both upper-case and lower-case),
142 or into numeric order.
144 telling it which comparison strategy to use,
145 although that would mean that whenever we invented
146 a new comparison strategy,
147 we would have to define a new code or flag value
149 But, if we observe that the final ordering
150 depends entirely on the behavior of the comparison function,
152 to accept a pointer to the function which we want it to use
153 to compare each pair of strings.
154 It will go through its usual routine of comparing and exchanging,
155 but whenever it makes the comparisons,
156 the actual function it calls will be
157 the function pointed to by the function pointer we hand it.
158 Making it sort in a different order,
159 according to a different comparison strategy,
161 but instead
162 will just involve
163 passing it a pointer to a different comparison function
164 (after perhaps writing that function).
166 which also accepts a pointer to the string comparison function:
167 <pre>
168 void stringsort(char *strings[], int nstrings, int (*cmpfunc)())
169 {
170 int i, j;
171 int didswap;
173 do {
174 didswap = 0;
176 {
177 j = i + 1;
179 {
180 char *tmp = strings[i];
181 strings[i] = strings[j];
182 strings[j] = tmp;
183 didswap = 1;
184 }
185 }
186 } while(didswap);
187 }
188 </pre>
189 (This code uses a fairly simpleminded sorting algorithm.
190 It repeatedly compares adjacent pairs of elements,
191 keeping track of whether it had to exchange any.
192 If it makes it all the way through the array
193 without exchanging any, it's done;
194 otherwise, it has at least made progress,
195 and it goes back for another pass.
196 This is not the world's best algorithm;
197 in fact it's not far from
198 the infamous ``bubble sort.''
199 Although our focus here is on function pointers,
200 not sorting,
201 in a minute we'll take time out
202 and look at a simple improvement to this algorithm
204 </p><p>Now, if we have an array of strings
205 <pre>
207 </pre>
209 <pre>
210 stringsort(array1, 4, strcmp);
211 </pre>
212 Notice
213 that
216 and passing that pointer as the third argument
218 </p><p>If we wanted to sort these words in ``dictionary'' order,
221 when comparing letters:
222 <pre>
225 int dictstrcmp(char *str1, char *str2)
226 {
227 while(1)
228 {
229 char c1 = *str1++;
230 char c2 = *str2++;
232 if(isupper(c1))
233 c1 = tolower(c1);
235 if(isupper(c2))
236 c2 = tolower(c2);
238 if(c1 != c2)
239 return c1 - c2;
240 if(c1 == '\0')
241 return 0;
242 }
243 }
244 </pre>
246 are both from the standard library
249 if its argument is an upper-case letter,
252 we can sort our array a different way:
253 <pre>
254 stringsort(array1, 4, dictstrcmp);
255 </pre>
260 although neither of them is standard.)
261 </p><p>We can also write another string-comparison function
262 which treats the strings as numbers,
263 and compares them numerically:
264 <pre>
265 int numstrcmp(char *str1, char *str2)
266 {
267 int n1 = atoi(str1);
268 int n2 = atoi(str2);
270 else if(n1 == n2) return 0;
271 else return 1;
272 }
273 </pre>
274 </p><p>Then, we can sort an array of numeric strings correctly:
275 <pre>
277 stringsort(array2, 7, numstrcmp);
278 </pre>
279 </p><p>(As an aside,
280 you will occasionaly see code
281 which is supposed to compare two integers
282 and return a negative, zero, or positive result--i.e. just
284 which does so by the seemingly simpler technique of just saying
285 <pre>
286 return n1 - n2;
287 </pre>
288 It turns out that this trick has a serious drawback.
292 and will overflow on some machines,
293 producing an incorrect result.
294 So the explicit comparison code
296 is considerably safer.)
297 </p><p>Finally, since we've started looking at sorting functions,
298 let's look at a simple improvement to the string sorting function
299 we've just been using.
300 It has been plodding along comparing
301 adjacent elements,
302 so
303 when an element is far out of place,
304 it takes many passes to percolate it to the correct position
305 (one cell at a time).
306 The
308 improvement,
309 based on the work of Donald L. Shell,
310 is to compare pairs of more widely-separated elements at first,
311 then proceed to compare more and more closely-situated elements,
312 until on the last pass
313 (or passes)
314 we compare adjacent elements, as before.
315 Since the earlier passes will have done more of the work
316 (and more quickly),
317 the later passes will just have to do the ``final cleanup.''
318 Here is the improvement:
319 <pre>
320 void stringsort(char *strings[], int nstrings, int (*cmpfunc)())
321 {
322 int i, j, gap;
323 int didswap;
326 {
327 do {
328 didswap = 0;
330 {
331 j = i + gap;
333 {
334 char *tmp = strings[i];
335 strings[i] = strings[j];
336 strings[j] = tmp;
337 didswap = 1;
338 }
339 }
340 } while(didswap);
341 }
342 }
343 </pre>
344 The inner loops are the same as before,
345 except that where we had before always been computing
347 now we compute
350 (controlled by a third, outer loop)
351 which starts out large
353 and then diminishes until it's 1.
354 Although this code contains three nested loops instead of two,
355 it will end up making far fewer trips through the inner loop,
356 and so will execute faster.
357 </p><p>The Standard C library contains a general-purpose sort function,
359 which can sort any type of data (not just strings).
360 It's a bit trickier to use (due to this generality),
361 and you almost always have to write an auxiliary comparison function.
362 For example,
365 even when you're sorting strings
367 Here is an auxiliary comparison function
369 which would behave like our earlier call to
371 </TT>:
373 <pre>
374 /* compare strings via pointers */
375 int pstrcmp(const void *p1, const void *p2)
376 {
377 return strcmp(*(char * const *)p1, *(char * const *)p2);
378 }
380 ...
382 qsort(array1, 4, sizeof(char *), pstrcmp);
383 </pre>
385 it calls your comparison function
386 with pointers to the elements of your array.
388 the comparison function ends up receiving pointers to pointers.
390 it's written so that it can sort arrays of anything.
393 is the size of the array element.)
395 what the type of the elements being sorted is,
397 to those elements
398 when it calls the comparison function.
400 where the situation is similar:
402 because it doesn't know what type we'll use the pointers to point to.)
404 we use
405 the explicit cast
406 <TT>(char * const *)
410 to find out what they point to,
414 to do most of the work,
415 but we have to do a bit of work first to recover the correct pointers.
417 in the cast
418 <TT>(char * const *)
419 </TT>keeps the compiler from complaining,
420 since the pointers being passed in to the comparison function
422 meaning that although it may not be clear what they point to,
423 it's guaranteed that
424 we won't be using them
425 to modify whatever it is they point to.
427 so that the compiler doesn't worry
428 that we're going to accidentally use the converted pointers
429 to modify what we shouldn't.)
430 <br>
431 <br>
432 </p><p>That was a rather elaborate first example
433 of what function pointers can be used for!
434 Let's move on to some others.
435 </p><p>Suppose you wanted a program to plot equations.
440 How would you tell it what function to plot?
441 By a function pointer, of course!
443 over the range you specified,
444 calling the function pointed to by your pointer
446 You might call
447 <pre>
449 </pre>
450 to plot a sine wave,
451 and
452 <pre>
454 </pre>
455 to plot the square root function.
457 your first question would be
458 how to draw lines or otherwise do graphics in C at all,
459 and unfortunately this is one of the questions
460 which the C language doesn't answer.
461 There are potentially different ways of doing graphics,
462 with different system functions to call,
463 for every different kind of computer,
464 operating system,
465 and graphics device.)
466 </p><p>One of the simplest
467 (and allegedly least user-friendly)
468 styles of user interfaces
470 or CLI.
471 The user types a command, hits the RETURN key,
472 and the system interprets the command.
473 Often, the first ``word'' on the line is the command name,
474 and any remaining words are
475 ``arguments'' or ``option flags.''
476 The various shells under Unix,
477 COMMAND.COM under MS-DOS,
478 and the adventure game we've been writing
479 are all examples of CLI's.
480 If you sit down to write some code implementing a CLI,
481 it's simple enough to read a line of text typed by the user,
482 and simple enough to break it up into words.
483 But how do you map the first word on the line
484 to the code which implements that command?
485 A straightforward, rather simpleminded way
487 <pre>
494 ...
495 else fprintf(stderr, "command not found\n");
496 </pre>
497 </p><p>This works, but can become unwieldy.
498 Another technique is to write several separate functions,
499 each implementing one command,
500 and then to build a table
501 (typically an array of structures)
502 associating the command name as typed by the user
503 with the function implementing that command.
504 In the table,
505 the command name is a string
506 and the function is represented by a function pointer.
507 With this table in hand,
508 processing the user's command becomes a relatively simple matter
509 of searching the table for the matching command string
510 and then calling the corresponding pointed-to function.
512 (We'll see an example
513 of this technique
514 in this week's assignment.)
515 </p><p>Our last example concerns larger, more elaborate systems
516 which manipulate many types of data.
517 (Here, by ``types of data,''
518 I am referring to data structures used by the program,
520 but in any case
521 more elaborate than C's basic data types.)
522 It is often the case that similar operations
523 must be performed on dissimilar data types.
524 The conventional way of implementing such operations
525 is to have the code for each operation
526 look at the data type it's operating on
527 and adjust its behavior accordingly;
528 in the worst case,
529 each piece of code
530 (for each operation)
535 If a new data type is ever added,
536 new cases must be added to all
537 segments
538 of the code
539 implementing all of the operations.
540 </p><p>Another way of organizing such code
541 is to place one or more function pointers
542 right there
544 in the data structures describing each data type.
545 These pointers point to functions
546 which are streamlined and optimized
547 for performing the operations on just one data type.
548 (Each piece of data would obviously have its pointer(s) set
549 to point to the function(s) for its own data type.)
550 This idea is one of the cornerstones of
552 We could use a version of it in our adventure game, too:
553 rather than writing new, global pieces of code
554 implementing each new command verb we want to let the user type,
555 and then making each of those pieces of code
556 check all sorts of attributes
557 to ensure that the command can't be used on inappropriate objects
558 (``break water with cup'',
559 ``light candle with bucket,'' etc.)
560 we could attach special-purpose pieces of code
561 to the individual objects themselves
562 (via function pointers, of course)
563 and arrange that the code would only fire up
564 if the player were trying to use the relevant object.
565 </p><hr>
566 <p>
567 Read sequentially:
572 </p>
573 <p>
577 </p>
578 </body>
579 </html>