"Fossies" - the Fresh Open Source Software Archive

Member "tin-2.4.1/src/heapsort.c" (12 Oct 2016, 6253 Bytes) of archive /linux/misc/tin-2.4.1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "heapsort.c" see the Fossies "Dox" file reference documentation.

    1 /*-
    2  * Copyright (c) 1991, 1993
    3  *  The Regents of the University of California.  All rights reserved.
    4  *
    5  * This code is derived from software contributed to Berkeley by
    6  * Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias.
    7  *
    8  * Redistribution and use in source and binary forms, with or without
    9  * modification, are permitted provided that the following conditions
   10  * are met:
   11  * 1. Redistributions of source code must retain the above copyright
   12  *    notice, this list of conditions and the following disclaimer.
   13  * 2. Redistributions in binary form must reproduce the above copyright
   14  *    notice, this list of conditions and the following disclaimer in the
   15  *    documentation and/or other materials provided with the distribution.
   16  * 4. Neither the name of the University nor the names of its contributors
   17  *    may be used to endorse or promote products derived from this software
   18  *    without specific prior written permission.
   19  *
   20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   30  * SUCH DAMAGE.
   31  */
   32 
   33 #if 0
   34 #   include <sys/cdefs.h>
   35 #   include <errno.h>
   36 #   include <stddef.h>
   37 #   include <stdlib.h>
   38 #else
   39 #   ifndef TIN_H
   40 #       include "tin.h"
   41 #   endif /* !TIN_H */
   42 #endif /* 0 */
   43 
   44 #if defined(USE_HEAPSORT) && !defined(HAVE_HEAPSORT)
   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, count, size, tmp) { \
   53     count = size; \
   54     do { \
   55         tmp = *a; \
   56         *a++ = *b; \
   57         *b++ = tmp; \
   58     } while (--count); \
   59 }
   60 
   61 /* Copy one block of size size to another. */
   62 #define COPY(a, b, count, size, tmp1, tmp2) { \
   63     count = size; \
   64     tmp1 = a; \
   65     tmp2 = b; \
   66     do { \
   67         *tmp1++ = *tmp2++; \
   68     } while (--count); \
   69 }
   70 
   71 /*
   72  * Build the list into a heap, where a heap is defined such that for
   73  * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N.
   74  *
   75  * There two cases.  If j == nmemb, select largest of Ki and Kj.  If
   76  * j < nmemb, select largest of Ki, Kj and Kj+1.
   77  */
   78 #define CREATE(initval, nmemb, par_i, child_i, par, child, size, count, tmp) { \
   79     for (par_i = initval; (child_i = par_i * 2) <= nmemb; \
   80         par_i = child_i) { \
   81         child = abase + child_i * size; \
   82         if (child_i < nmemb && compar(child, child + size) < 0) { \
   83             child += size; \
   84             ++child_i; \
   85         } \
   86         par = abase + par_i * size; \
   87         if (compar(child, par) <= 0) \
   88             break; \
   89         SWAP(par, child, count, size, tmp); \
   90     } \
   91 }
   92 
   93 /*
   94  * Select the top of the heap and 'heapify'.  Since by far the most expensive
   95  * action is the call to the compar function, a considerable optimization
   96  * in the average case can be achieved due to the fact that k, the displaced
   97  * elememt, is usually quite small, so it would be preferable to first
   98  * heapify, always maintaining the invariant that the larger child is copied
   99  * over its parent's record.
  100  *
  101  * Then, starting from the *bottom* of the heap, finding k's correct place,
  102  * again maintianing the invariant.  As a result of the invariant no element
  103  * is 'lost' when k is assigned its correct place in the heap.
  104  *
  105  * The time savings from this optimization are on the order of 15-20% for the
  106  * average case. See Knuth, Vol. 3, page 158, problem 18.
  107  *
  108  * XXX Don't break the #define SELECT line, below.  Reiser cpp gets upset.
  109  */
  110 #define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) { \
  111     for (par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i) { \
  112         child = abase + child_i * size; \
  113         if (child_i < nmemb && compar(child, child + size) < 0) { \
  114             child += size; \
  115             ++child_i; \
  116         } \
  117         par = abase + par_i * size; \
  118         COPY(par, child, count, size, tmp1, tmp2); \
  119     } \
  120     for (;;) { \
  121         child_i = par_i; \
  122         par_i = child_i / 2; \
  123         child = abase + child_i * size; \
  124         par = abase + par_i * size; \
  125         if (child_i == 1 || compar(k, par) < 0) { \
  126             COPY(child, k, count, size, tmp1, tmp2); \
  127             break; \
  128         } \
  129         COPY(child, par, count, size, tmp1, tmp2); \
  130     } \
  131 }
  132 
  133 /*
  134  * Heapsort -- Knuth, Vol. 3, page 145.  Runs in O (N lg N), both average
  135  * and worst.  While heapsort is faster than the worst case of quicksort,
  136  * the BSD quicksort does median selection so that the chance of finding
  137  * a data set that will trigger the worst case is nonexistent.  Heapsort's
  138  * only advantage over quicksort is that it requires little additional memory.
  139  */
  140 int
  141 heapsort(
  142     void *vbase,
  143     size_t nmemb,
  144     size_t size,
  145     t_compfunc compar)
  146 {
  147     char tmp, *tmp1, *tmp2, *abase, *k, *p, *t;
  148     size_t cnt, i, j, l;
  149 
  150     if (nmemb <= 1)
  151         return (0);
  152 
  153     if (!size) {
  154         errno = EINVAL;
  155         return (-1);
  156     }
  157 
  158 #if !defined(TIN_H)
  159     if ((k = malloc(size)) == NULL)
  160         return (-1);
  161 #else
  162     k = my_malloc(size);
  163 #endif /* !TIN_H */
  164 
  165     /*
  166      * Items are numbered from 1 to nmemb, so offset from size bytes
  167      * below the starting address.
  168      */
  169     abase = (char *)vbase - size;
  170 
  171     for (l = nmemb / 2 + 1; --l;)
  172         CREATE(l, nmemb, i, j, t, p, size, cnt, tmp);
  173 
  174     /*
  175      * For each element of the heap, save the largest element into its
  176      * final slot, save the displaced element (k), then recreate the
  177      * heap.
  178      */
  179     while (nmemb > 1) {
  180         COPY(k, abase + nmemb * size, cnt, size, tmp1, tmp2);
  181         COPY(abase + nmemb * size, abase + size, cnt, size, tmp1, tmp2);
  182         --nmemb;
  183         SELECT(i, j, nmemb, t, p, size, k, cnt, tmp1, tmp2);
  184     }
  185     free(k);
  186     return (0);
  187 }
  188 #endif /* USE_HEAPSORT && !HAVE_HEAPSORT */