home *** CD-ROM | disk | FTP | other *** search
/ Aminet 18 / aminetcdnumber181997.iso / Aminet / dev / gcc / ixemulsrc.lha / ixemul / stdlib / heapsort.c < prev    next >
C/C++ Source or Header  |  1996-12-11  |  4KB  |  129 lines
  1. /*-
  2.  * Copyright (c) 1991 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #if defined(LIBC_SCCS) && !defined(lint)
  35. static char sccsid[] = "@(#)heapsort.c    5.1 (Berkeley) 6/4/91";
  36. #endif /* LIBC_SCCS and not lint */
  37.  
  38. #define _KERNEL
  39. #include "ixemul.h"
  40. #include "kprintf.h"
  41.  
  42. #include <sys/cdefs.h>
  43. #include <stdlib.h>
  44.  
  45. /*
  46.  * Swap two areas of size number of bytes.  Although qsort(3) permits random
  47.  * blocks of memory to be sorted, sorting pointers is almost certainly the
  48.  * common case (and, were it not, could easily be made so).  Regardless, it
  49.  * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer
  50.  * arithmetic gets lost in the time required for comparison function calls.
  51.  */
  52. #define    SWAP(a, b) { \
  53.     cnt = size; \
  54.     do { \
  55.         ch = *a; \
  56.         *a++ = *b; \
  57.         *b++ = ch; \
  58.     } while (--cnt); \
  59. }
  60.  
  61. /*
  62.  * Build the list into a heap, where a heap is defined such that for
  63.  * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N.
  64.  *
  65.  * There two cases.  If j == nmemb, select largest of Ki and Kj.  If
  66.  * j < nmemb, select largest of Ki, Kj and Kj+1.
  67.  *
  68.  * The initial value depends on if we're building the initial heap or
  69.  * reconstructing it after saving a value.
  70.  */
  71. #define    HEAP(initval) { \
  72.     for (i = initval; (j = i * 2) <= nmemb; i = j) { \
  73.         p = (char *)bot + j * size; \
  74.         if (j < nmemb && compar(p, p + size) < 0) { \
  75.             p += size; \
  76.             ++j; \
  77.         } \
  78.         t = (char *)bot + i * size; \
  79.         if (compar(p, t) <= 0) \
  80.             break; \
  81.         SWAP(t, p); \
  82.     } \
  83. }
  84.  
  85. /*
  86.  * Heapsort -- Knuth, Vol. 3, page 145.  Runs in O (N lg N), both average
  87.  * and worst.  While heapsort is faster than the worst case of quicksort,
  88.  * the BSD quicksort does median selection so that the chance of finding
  89.  * a data set that will trigger the worst case is nonexistent.  Heapsort's
  90.  * only advantage over quicksort is that it requires no additional memory.
  91.  */
  92. int heapsort(bot, nmemb, size, compar)
  93.     register void *bot;
  94.     register size_t nmemb, size;
  95.     int (*compar) __P((const void *, const void *));
  96. {
  97.     register char *p, *t, ch;
  98.     register int cnt, i, j, l;
  99.  
  100.     if (nmemb <= 1)
  101.         return (0);
  102.     if (!size) {
  103.         errno = EINVAL;
  104.         KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  105.         return (-1);
  106.     }
  107.     /*
  108.      * Items are numbered from 1 to nmemb, so offset from size bytes
  109.      * below the starting address.
  110.      */
  111.     bot -= size;
  112.  
  113.     for (l = nmemb / 2 + 1; --l;)
  114.         HEAP(l);
  115.  
  116.     /*
  117.      * For each element of the heap, save the largest element into its
  118.      * final slot, then recreate the heap.
  119.      */
  120.     while (nmemb > 1) {
  121.         p = (char *)bot + size;
  122.         t = (char *)bot + nmemb * size;
  123.         SWAP(p, t);
  124.         --nmemb;
  125.         HEAP(1);
  126.     }
  127.     return (0);
  128. }
  129.