qsort.c

DVB软件,基于CT216软件的开发源程序.

/**************************************************************************

        (C)Copyright Cheertek Inc. 2002-2004,
           D700, all right reserved.

        Product : STB Firmware

****************************************************************************/
/***
*qsort.c - quicksort algorithm; qsort() library function for sorting arrays
*
*       Copyright (c) 1985-1997, Microsoft Corporation. All rights reserved.
*
*Purpose:
*       To implement the qsort() routine for sorting arrays.
*
*******************************************************************************/

//#include <cruntime.h>
// #include <stdlib.h> daphne
#include <string.h>
//#include <search.h>
#include "dvb_msg.h"
#include "db_defs.h"
#include "ap_defs.h"
/*******************************************************************************************/
#if 1
#define QSORT_MSG(p)
#else
#define QSORT_MSG(p)			printf p
#endif

#if 1
#define QSORT_DBG(p)
#else
#define QSORT_DBG(p) 		printf p
#endif

/*******************************************************************************************/          



/* prototypes for local routines */
static void  shortsort(char *lo, char *hi, unsigned width,
                int (*comp)(unsigned, unsigned));
static void  _ext_swap(char *p, char *q, unsigned int width);

/* this parameter defines the cutoff between using quick sort and
   insertion sort for arrays; arrays with lengths shorter or equal to the
   below value use insertion sort */

#define CUTOFF 8            /* testing shows that this is good value */

// Matt Add
extern void DVB_ServiceSwap( EN_SERVICE_TYPE , u16 , u16 );
static bool8 b8QSortEX=FALSE;
static unsigned trace_idx;
static EN_SERVICE_TYPE db_type;
static void *array_base_address;
static void *array_base_address_tmp;

/***
*qsort(base, num, wid, comp) - quicksort function for sorting arrays
*
*Purpose:
*       quicksort the array of elements
*       side effects:  sorts in place
*
*Entry:
*       char *base = pointer to base of array
*       unsigned num  = number of elements in the array
*       unsigned width = width in bytes of each array element
*       int (*comp)() = pointer to function returning analog of strcmp for
*               strings, but supplied by user for comparing the array elements.
*               it accepts 2 pointers to elements and returns neg if 1<2, 0 if
*               1=2, pos if 1>2.
*
*Exit:
*       returns void
*
*Exceptions:
*
*******************************************************************************/

/* sort the array between lo and hi (inclusive) */

void  _ext_qsort (
    void *base,
    unsigned num,
    unsigned width,
    int (*comp)(unsigned, unsigned)
    )
{
    char *lo, *hi;              /* ends of sub-array currently sorting */
    char *mid;                  /* points to middle of subarray */
    char *loguy, *higuy;        /* traveling pointers for partition step */
    unsigned size;              /* size of the sub-array */
    char *lostk[16], *histk[16];
    int stkptr;                 /* stack for saving sub-array to be processed */

    /* Note: the number of stack entries required is no more than
       1 + log2(size), so 30 is sufficient for any array */

    if (num < 2 || width == 0)
        return;                 /* nothing to do */

    stkptr = 0;                 /* initialize stack */

    array_base_address = base;
    lo = base;
    hi = (char *)base + width * (num-1);        /* initialize limits */

    /* this entry point is for pseudo-recursion calling: setting
       lo and hi and jumping to here is like recursion, but stkptr is
       prserved, locals aren't, so we preserve stuff on the stack */
recurse:

    size = (hi - lo) / width + 1;        /* number of el's to sort */

    /* below a certain size, it is faster to use a O(n^2) sorting method */
    if (size <= CUTOFF) {
         shortsort(lo, hi, width, comp);
    }
    else {
        /* First we pick a partititioning element.  The efficiency of the
           algorithm demands that we find one that is approximately the
           median of the values, but also that we select one fast.  Using
           the first one produces bad performace if the array is already
           sorted, so we use the middle one, which would require a very
           wierdly arranged array for worst case performance.  Testing shows
           that a median-of-three algorithm does not, in general, increase
           performance. */

        mid = lo + (size / 2) * width;      /* find middle element */
        _ext_swap(mid, lo, width);               /* swap it to beginning of array */

        /* We now wish to partition the array into three pieces, one
           consisiting of elements <= partition element, one of elements
           equal to the parition element, and one of element >= to it.  This
           is done below; comments indicate conditions established at every
           step. */

        loguy = lo;
        higuy = hi + width;

        /* Note that higuy decreases and loguy increases on every iteration,
           so loop must terminate. */
        for (;;) {
            /* lo <= loguy < hi, lo < higuy <= hi + 1,
               A[i] <= A[lo] for lo <= i <= loguy,
               A[i] >= A[lo] for higuy <= i <= hi */

            do  {
                loguy += width;
            } while (loguy <= hi && comp((unsigned)loguy, (unsigned)lo) <= 0);

            /* lo < loguy <= hi+1, A[i] <= A[lo] for lo <= i < loguy,
               either loguy > hi or A[loguy] > A[lo] */

            do  {
                higuy -= width;
            } while (higuy > lo && comp((unsigned)higuy, (unsigned)lo) >= 0);

            /* lo-1 <= higuy <= hi, A[i] >= A[lo] for higuy < i <= hi,
               either higuy <= lo or A[higuy] < A[lo] */

            if (higuy < loguy)
                break;

            /* if loguy > hi or higuy <= lo, then we would have exited, so
               A[loguy] > A[lo], A[higuy] < A[lo],
               loguy < hi, highy > lo */

            _ext_swap(loguy, higuy, width);

            /* A[loguy] < A[lo], A[higuy] > A[lo]; so condition at top
               of loop is re-established */
        }

        /*     A[i] >= A[lo] for higuy < i <= hi,
               A[i] <= A[lo] for lo <= i < loguy,
               higuy < loguy, lo <= higuy <= hi
           implying:
               A[i] >= A[lo] for loguy <= i <= hi,
               A[i] <= A[lo] for lo <= i <= higuy,
               A[i] = A[lo] for higuy < i < loguy */

        _ext_swap(lo, higuy, width);     /* put partition element in place */

        /* OK, now we have the following:
              A[i] >= A[higuy] for loguy <= i <= hi,
              A[i] <= A[higuy] for lo <= i < higuy
              A[i] = A[lo] for higuy <= i < loguy    */

        /* We've finished the partition, now we want to sort the subarrays
           [lo, higuy-1] and [loguy, hi].
           We do the smaller one first to minimize stack usage.
           We only sort arrays of length 2 or more.*/

        if ( higuy - 1 - lo >= hi - loguy ) {
            if (lo + width < higuy) {
                lostk[stkptr] = lo;
                histk[stkptr] = higuy - width;
                ++stkptr;
            }                           /* save big recursion for later */

            if (loguy < hi) {
                lo = loguy;
                goto recurse;           /* do small recursion */
            }
        }
        else {
            if (loguy < hi) {
                lostk[stkptr] = loguy;
                histk[stkptr] = hi;
                ++stkptr;               /* save big recursion for later */
            }

            if (lo + width < higuy) {
                hi = higuy - width;
                goto recurse;           /* do small recursion */
            }
        }
    }

    /* We have sorted the array, except for any pending sorts on the stack.
       Check if there are any, and do them. */

    --stkptr;
    if (stkptr >= 0) {
        lo = lostk[stkptr];
        hi = histk[stkptr];
        goto recurse;           /* pop subarray from stack */
    }
    else
        return;                 /* all subarrays done */
}


/***
*shortsort(hi, lo, width, comp) - insertion sort for sorting short arrays
*
*Purpose:
*       sorts the sub-array of elements between lo and hi (inclusive)
*       side effects:  sorts in place
*       assumes that lo < hi
*
*Entry:
*       char *lo = pointer to low element to sort
*       char *hi = pointer to high element to sort
*       unsigned width = width in bytes of each array element
*       int (*comp)() = pointer to function returning analog of strcmp for
*               strings, but supplied by user for comparing the array elements.
*               it accepts 2 pointers to elements and returns neg if 1<2, 0 if
*               1=2, pos if 1>2.
*
*Exit:
*       returns void
*
*Exceptions:
*
*******************************************************************************/

static void  shortsort (
    char *lo,
    char *hi,
    unsigned width,
    int (*comp)(unsigned, unsigned)
    )
{
    char *p, *max;
//    bool8 found_max;
    int comp_result;

    /* Note: in assertions below, i and j are alway inside original bound of
       array to sort. */

    while (hi > lo) {
        /* A[i] <= A[j] for i <= j, j > hi */
        max = lo;
//        found_max = FALSE;
        for (p = lo+width; p <= hi; p += width) {
            /* A[i] <= A[max] for lo <= i < p */
            
            comp_result = comp((unsigned)p, (unsigned)max);
//            if( comp_result!=0 ) {
//                found_max = TRUE;

                //if ( comp_result>0) {	//wilson 20070323 for consider 2 value are equal
                if ( comp_result>=0) {
                    max = p;
                }

//            }
            /* A[i] <= A[max] for lo <= i <= p */
        }

        /* A[i] <= A[max] for lo <= i <= hi */
//        if( found_max==TRUE )
//		  {
//            QSORT_DBG(("shortsort: "));
//		  }
            _ext_swap(max, hi, width);

        /* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */

        hi -= width;

        /* A[i] <= A[j] for i <= j, j > hi, loop top condition established */
    }
    /* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,
       so array is sorted */
}


/***
*swap(a, b, width) - swap two elements
*
*Purpose:
*       swaps the two array elements of size width
*
*Entry:
*       char *a, *b = pointer to two elements to swap
*       unsigned width = width in bytes of each array element
*
*Exit:
*       returns void
*
*Exceptions:
*
*******************************************************************************/

static void  _ext_swap (
    char *a,
    char *b,
    unsigned width
    )
{
    char tmp;
    u16 pu16SrvIndex, pu16SrvIndex2;
    //int idx_a, idx_b;

    if ( a != b )
    {
		if(b8QSortEX==TRUE)
		{
#if 0
			//QSORT_DBG(("\n%x, %x, %x, %x\n", (unsigned)a, (unsigned)b, (unsigned)base_address, (unsigned)width));
		    if(PU8TOU16(a)==trace_idx)
		    {
		    	trace_idx = PU8TOU16(b);
		    	//QSORT_DBG(("trace = %x\n", trace_idx));
		    }
		    else if(PU8TOU16(b)==trace_idx)
		    {
		    	trace_idx = PU8TOU16(a);
		    	//QSORT_DBG(("trace = %x\n", trace_idx));
		    }
#endif		    
			pu16SrvIndex = ((u16 *)array_base_address_tmp)[(a-(char *)array_base_address)/sizeof(u16)];
			pu16SrvIndex2 = ((u16 *)array_base_address_tmp)[(b-(char *)array_base_address)/sizeof(u16)];
		    DVB_ServiceSwap( db_type, pu16SrvIndex, pu16SrvIndex2);
		}

		/* Do the swap one character at a time to avoid potential alignment
	           problems. */
        while ( width-- ) {
            tmp = *a;
            *a++ = *b;
            *b++ = tmp;
        }
    }
}


int  qsort_ex ( void *base, void *baseTmp, unsigned num, unsigned width, int (*comp)(unsigned, unsigned), unsigned org_idx, EN_SERVICE_TYPE enSrvType )
{
    u16 i;
    
    array_base_address_tmp = baseTmp;

	b8QSortEX = TRUE;	// sorting on dram
    
    db_type = enSrvType;
    //QSORT_DBG(("trace = %x\n", trace_idx));
	_ext_qsort( base, num, width, comp );

    b8QSortEX = FALSE;

    trace_idx = 0;
    for(i=0; i<num; i++)
    {
        if( PU8TOU16((u8*)base+(i*width))==org_idx)
        {
            trace_idx = i;
            break;
        }
    }

    //QSORT_DBG(("trace = %d\n", trace_idx));
    return trace_idx;
}