home *** CD-ROM | disk | FTP | other *** search
/ Fish 'n' More 1 / FishNMoreVol1.bin / more / programming / arpprog / olddocs / qsort < prev    next >
Encoding:
Text File  |  1988-02-22  |  2.3 KB  |  133 lines
  1.  
  2.  
  3.  
  4.      QSort(31.0)      ARP Programmers Manual       QSort(31.0)
  5.  
  6.  
  7.  
  8.      FUNCTION
  9.       QSort    - Quickly sort whatever    you want.
  10.  
  11.      SYNOPSIS
  12.       stkerr = QSort( ptr, region_size, byte_size, user_func)
  13.         d0          a0          d0      d1         a1
  14.  
  15.      FUNCTION
  16.       QSort    is an implementation of    Hoares sorting algorithm.  It
  17.       uses a constant amount of stack no matter what the size of
  18.       the file.
  19.  
  20.      INPUTS
  21.       baseptr   - pointer to the start of a    memory region to be
  22.           sorted
  23.  
  24.       region_size -    size of    region to be sorted, in    number of
  25.           elements (not    bytes!)
  26.  
  27.       byte_size - size of a    single element,    in bytes.
  28.  
  29.       user_function    - function to be provided by caller, which
  30.           compares two elements    from the set to    be sorted.
  31.           QSort    will call the user function like so:
  32.           return = user_function(el1, el2)
  33.            d0           a0     a1
  34.  
  35.           Your function    must return the    following in D0:
  36.  
  37.           if (el1 < el2) return    < 0
  38.           if (el1 > el2) return    > 0
  39.           if (el1 == el2) return = 0
  40.  
  41.           You must save    all registers except a0, a1, d0, d1.
  42.           (See below for an example of a C calling sequence)
  43.  
  44.           QSort    will also pass A5 to you unchanged.  You can use
  45.           this register    to point to pass information to    your
  46.           comparison routine.
  47.  
  48.      RETURNS
  49.       stkerr - -1 if everything is cool, 0 if there    was an
  50.           internal recursion stack overflow (not too likely).
  51.  
  52.      EXAMPLE:
  53.       Here is an example of    a calling sequence from    C, which is to
  54.       sort an array    of pointers to strings:
  55.       char **names;
  56.       long numEls;
  57.       extern    Cmp();
  58.  
  59.       if (QSort(names, numELs, 4L, Cmp))
  60.  
  61.  
  62.  
  63.      Page 1                         (printed 2/22/88)
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.      QSort(31.0)      ARP Programmers Manual       QSort(31.0)
  71.  
  72.  
  73.  
  74.            do whatever
  75.            else
  76.            STACK_ERROR()
  77.  
  78.       the Cmp function would look like this:
  79.  
  80.       Cmp()
  81.       {
  82.       {
  83.       #asm
  84.           public     _geta4
  85.           movem.l d2-d3/a4/a6,-(sp)    ; save important registers
  86.           movem.l a0/a1,-(sp)    ; push args
  87.           bsr     _geta4
  88.           bsr     _cmp       ; call real compare function
  89.           addq.l  #8,sp       ; clean up args
  90.           movem.l (sp)+,d2-d3/a4/a6    ; restore registers
  91.       #endasm
  92.       }
  93.       }
  94.  
  95.       The cmp function called by the above is a normal C
  96.       function, it can be whatever you like.  Here is a sample
  97.       one:
  98.  
  99.       cmp(s1,s2)
  100.       char **s1, **s2;
  101.       {
  102.            return strcmp(*a, *b);
  103.       }
  104.  
  105.      BUGS
  106.       None known.
  107.  
  108.      AUTHOR
  109.       SDB
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.      Page 2                         (printed 2/22/88)
  130.  
  131.  
  132.  
  133.