home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / c / 12495 < prev    next >
Encoding:
Text File  |  1992-08-18  |  2.7 KB  |  65 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!think.com!spdcc!dirtydog.ima.isc.com!karl
  3. From: karl@ima.isc.com (Karl Heuer)
  4. Subject: Re: Sorting (continued)
  5. Message-ID: <1992Aug18.175649.19458@ima.isc.com>
  6. Sender: usenet@ima.isc.com (news)
  7. Organization: Interactive Systems, Cambridge, MA 02138-5302
  8. References: <1992Aug15.135836.23357@midway.uchicago.edu> <1992Aug18.175114.19201@ima.isc.com>
  9. Date: Tue, 18 Aug 1992 17:56:49 GMT
  10. Lines: 53
  11.  
  12. In article <1992Aug15.135836.23357@midway.uchicago.edu>
  13. pynq@midway.uchicago.edu asks how to handle a sorting problem.
  14.  
  15. I've already discussed the suggested algorithms; in this article I'd like to
  16. outline a possible sort engine which doesn't depend on the array model of
  17. qsort().  Given such an engine in our software toolchest, pynq's problem
  18. would be trivial.
  19.  
  20. I think it should be possible to design something along the following lines:
  21.  
  22.     #include <sort.h>
  23.     sort_t *mksort(int (*cmpf)(void const *, void const *),
  24.         size_t eltsize, unsigned int flags, ...);
  25.     int putsort(sort_t *, void const *);
  26.     void *getsort(sort_t *);
  27.     void rmsort(sort_t *);
  28.  
  29.     /* sample program */
  30.     int mycompare(void const *x, void const *y) {
  31.         return (strcmp(*(char * const *)x, *(char * const *)y));
  32.     }
  33.     main() {
  34.         char *buf;
  35.         sort_t *sp;
  36.         void *p;
  37.         if ((sp = mksort(mycompare, sizeof(char *), 0)) == NULL) die();
  38.         while ((buf = fgetline(stdin)) != NULL) {
  39.         if (putsort(sp, &buf) != 0) die();
  40.         }
  41.         while ((p = getsort(sp)) != NULL) puts(*(char **)p);
  42.         return (0);
  43.     }
  44.  
  45. Here's the basic idea.  |mksort()| creates an opaque object that will somehow
  46. hold all the state information.  |putsort()| adds an element to the set; it
  47. returns |int| rather than |void| only because it might have to signal an error
  48. from an internal |malloc()|.  |getsort()| returns a null pointer if the set is
  49. empty, otherwise it returns the "smallest" element, and deletes it from the
  50. set.  |rmsort()| does any final cleanup.
  51.  
  52. Although the usual sequence of calls would be as shown in the example, it's
  53. also possible to terminate the |getsort()| loop before exhausting the set.
  54. Also, if it can be done without compromising the speed, it would be nice if
  55. the package would allow additional calls to |putsort()| even after the user
  56. has started to retrieve them with |getsort()|.
  57.  
  58. This package could be implemented using any of the algorithms listed in the
  59. original article, or any other method.  Although the details are not visible
  60. to the user, hints on the anticipated usage can be provided through the
  61. |flags| argument (and perhaps additional arguments), in case no single
  62. algorithm has acceptable behavior for all cases.
  63.  
  64. Karl W. Z. Heuer (karl@ima.isc.com or uunet!ima!karl), The Walking Lint
  65.