yc_algorithm.c

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
 * The young Library
 * Copyright (c) 2006 by Yang Huan(杨桓)

 * Permission to use, copy, modify, distribute and sell this software for any
 * purpose is hereby granted without fee, provided that the above copyright
 * notice appear in all copies and that both that copyright notice and this
 * permission notice appear in supporting documentation.
 * The author make no representations about the suitability of this software
 * for any purpose. It is provided "as is" without express or implied warranty.
 */

/******************************************************************************/
/******************************************************************************/
#include "yc_algorithm.h"

#ifdef __cplusplus
    namespace youngc {  extern "C" {
#endif
/******************************************************************************/
/******************************************************************************/

enum YOUNG_LIBRARY_ALGORITHM_CONSTANT
{
    SORT_THRESHOLD = 16,
    SORT_STACK_SIZE = sizeof(ylib_word_t) * 4
};

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

static void simple_sort( ylib_byte_t* front,
                         ylib_byte_t* back,
                         size_t element_size,
                         ylib_fp_cmp_t compare,
                         void (*swap)(void*, void*) )
{
    ylib_byte_t* max;
    ylib_byte_t* current;

    /* while 循环每运行一次就将 [front, back] 最大的元素同 back 交换位置，
     * 同时 back 递减一个元素，缩小未排序的空间 */
    while( back > front )
    {
        max = front;

        /* 找到 [front, back] 最大元素的所在位置 */
        for( current = front; current <= back; current += element_size )
        {
            if( compare( max, current ) < 0 )
                max = current;
        }

        swap( max, back );
        back -= element_size;
    }
}

void quicksort( void* first, size_t count, size_t element_size,
                ylib_fp_cmp_t compare, void (*swap)(void*, void*) )
{
    int stk;
    size_t len;
    ylib_byte_t *front, *back, *middle, *ftgap, *bkgap;
    ylib_byte_t* ftstk[SORT_STACK_SIZE];
    ylib_byte_t* bkstk[SORT_STACK_SIZE];

    if( count < 2 || element_size < 1 )
        return;

    stk = 0;
    front = (ylib_byte_t*)first;
    back = front + (count - 1) * element_size;

recursion:
    len = ( back - front ) / element_size + 1;

    if( len <= SORT_THRESHOLD )
        simple_sort( front, back, element_size, compare, swap );
    else
    {
        middle = front + (len / 2) * element_size;  /* 中点 */

        /* front <= middle <= back */
        if( compare( middle, front ) < 0 )
            swap( front, middle );
        if( compare( back, front ) < 0 )
            swap( front, back );
        if( compare( back, middle ) < 0 )
            swap( back, middle );

        ftgap = front;
        bkgap = back;

        /* 下面的无限循环将整个排序区间划分为三个子区间，
         * 第一个子区间内的元素值 <= 分割元素值
         * 第二个子区间内的元素值 = 分割元素值
         * 第三个子区间内的元素值 > 分割元素值 */
        for(;;)
        {
            /* front <= ftgap < back
             * front < bkgap <= back
             * array[i] <= array[middle] ( front <= i <= ftgap )
             * array[i] >  array[middle] ( bkgap <= i < back )
             * array[back] >= array[middle] */


            /* 在前半区间内递增寻找大于 middle 的值 */
            if( middle > ftgap )
            {
                do
                {
                    ftgap += element_size;
                } while( ftgap < middle && compare( ftgap, middle ) <= 0 );
            }
            /* 如果过了中点还没有退出循环，表示后半区间还有不大于 middle 的值，
             * 这时调整 ftgap 的查找范围为整个区间 */
            if( middle <= ftgap )
            {
                do
                {
                    ftgap += element_size;
                } while( ftgap <= back && compare( ftgap, middle ) <= 0 );
            }
            /* 查找完成后，有:
             * front < ftgap <= back + 1
             * array[i] <= array[middle] ( front <= i < ftgap )
             * 未找到则 ftgap > back ；否则 array[ftgap] > array[middle] */


            /* 在后半区间内递减寻找不大于middle的值 */
            do
            {
                bkgap -= element_size;
            } while( bkgap > middle && compare( middle, bkgap ) < 0 );
            /* 查找完成后，有：
             * front <= bkgap < back
             * array[i] > array[middle] ( bkgap < i < back )
             * 未找到则 bkgap = middle, 否则 array[bkgap] <= array[middle] */


            if( bkgap < ftgap )
                break;
            /* ftgap > back 或者 bkgap == front 时退出循环，此时有：
             * array[ftgap] > array[middle]
             * array[bkgap] <= array[middle]
             * ftgap <= back
             * bkgap > front */


            /* 将找到的大于middle和小于middle的值交换 */
            swap( ftgap, bkgap );

            if( bkgap == middle )
                middle = ftgap;
        }  /* end for */

        /* 退出循环后，有：
         * array[i] <= array[middle] ( front <= i < ftgap )
         * array[i] >  array[middle] ( bkgap < i < back )
         * array[back] >= array[middle]
         * bkgap < ftgap
         * 实际上也就意味着有以下关系:
         * bkgap == ftgap-1 或者 bkgap == back - 1, ftgap == back + 1,
         * array[back] == array[middle] */

        bkgap += element_size;
        if( middle < bkgap )
        {
            /* 寻找在[middle, bkgap)内与middle不相等的值 */
            do
            {
                bkgap -= element_size;
            } while( bkgap > middle && compare( bkgap, middle ) == 0 );
        }
        if( middle >= bkgap )
        {
            /* 寻找在[front, bkgap)内与middle不相等的值 */
            do
            {
                bkgap -= element_size;
            } while( bkgap > front && compare( bkgap, middle ) == 0 );
        }

        /* 分割完成后，有：
         * bkgap < ftgap
         * front <= bkgap <= back
         * array[i] <= array[middle] ( front <= i <= bkgap )
         * array[i] == array[middle] ( bkgap < i < ftgap )
         * array[i] >  array[middle] ( ftgap <= i < back )
         * array[back] >= array[middle]
         * 对 [front, ftgap] 和 [bkgap, back] 排序 */
        if( bkgap - front >= back - ftgap )  /* 前半部分元素更多 */
        {
            if( front < bkgap )  /* 将元素多的前半部分的参数入栈 */
            {
                ftstk[stk] = front;
                bkstk[stk] = bkgap;
                ++stk;
            }
            if( ftgap < back )  /* 先对元素少的后半部分进行递归排序 */
            {
                front = ftgap;
                goto recursion;
            }
        }
        else  /* 后半部分元素更多 */
        {
            if( ftgap < back )  /* 将元素多的后半部分的参数入栈 */
            {
                ftstk[stk] = ftgap;
                bkstk[stk] = back;
                ++stk;
            }
            if( front < bkgap )  /* 先对元素少的前半部分进行递归排序 */
            {
                back = bkgap;
                goto recursion;
            }
        }
    }  /* end else */

    /* 将入栈的参数弹出 */
    --stk;
    if( stk >= 0 )
    {
        front = ftstk[stk];
        back = bkstk[stk];
        goto recursion;
    }
}

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

const void* find( const void* first, size_t count, size_t element_size,
                  const void* value, ylib_fp_cmp_t compare )
{
    const ylib_byte_t* curr = (const ylib_byte_t*)first;

    for( ; count > 0; --count, curr += element_size )
    {
        if( compare( curr, value ) == 0 )
            return curr;
    }

    return NULL;
}

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

const void* search( const void* master_first, size_t master_count,
                    const void* sub_first, size_t sub_count,
                    size_t element_size, ylib_fp_cmp_t compare )
{
    const ylib_byte_t* curr1 = (const ylib_byte_t*)master_first;
    const ylib_byte_t* curr2 = (const ylib_byte_t*)sub_first;
    const ylib_byte_t* sub_last = curr2 + sub_count * element_size;

    if( master_count < sub_count )
        return NULL;

    while( curr2 != sub_last )
    {
        if( compare(curr1, curr2) == 0 )
        {
            curr1 += element_size;
            curr2 += element_size;
        }
        else  /* 遇到不相等时的处理 */
        {
            if( master_count == sub_count )
                return NULL;
            else  /* master_first前进一个位置，重新开始匹配 */
            {
                master_first = (const ylib_byte_t*)master_first + element_size;
                curr1 = (const ylib_byte_t*)master_first;
                curr2 = (const ylib_byte_t*)sub_first;
                --master_count;
            }
        }
    }

    return master_first;
}

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

bool matching( const void* first1, size_t count1,
               const void* first2, size_t count2,
               size_t element_size, ylib_fp_cmp_t compare )
{
    if( count1 != count2 )
        return false;

    if( first1 == first2 && count1 == count2 )
        return true;

    for( ; count1 > 0; --count1 )
    {
        if( compare( first1, first2 ) != 0 )
            return false;

        first1 = (const ylib_byte_t*)first1 + element_size;
        first2 = (const ylib_byte_t*)first2 + element_size;
    }

    return true;
}

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

const void* lower_bound( const void* first, size_t count, size_t element_size,
                         const void* value, ylib_fp_cmp_t compare )
{
    size_t half;
    const ylib_byte_t* middle;

    while( count > 0 )
    {
        half = count / 2;
        middle = (const ylib_byte_t*)first + half * element_size;

        if( compare( middle, value ) < 0 ) /* 要查找的值在后半部分 */
        {
            first = middle + element_size;
            count -= ( half + 1 );
        }
        else /* 要查找的值在前半部分 */
            count = half;
    }

    return first;
}

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

const void* upper_bound( const void* first, size_t count, size_t element_size,
                         const void* value, ylib_fp_cmp_t compare )
{
    size_t half;
    const ylib_byte_t* middle;

    while( count > 0 )
    {
        half = count / 2;
        middle = (const ylib_byte_t*)first + half * element_size;

        if( compare( middle, value ) > 0 ) /* 要查找的值在前半部分 */
            count = half;
        else /* 要查找的值在后半部分 */
        {
            first = middle + element_size;
            count -= ( half + 1 );
        }
    }

    return first;
}

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

pair_pointer equal_range( const void* first, size_t count, size_t element_size,
                          const void* value, ylib_fp_cmp_t compare )
{
    size_t half;
    const ylib_byte_t* middle;
    pair_pointer result;
    result.first = NULL;
    result.second = NULL;

    while( count > 0 )
    {
        half = count / 2;
        middle = (const ylib_byte_t*)first + half * element_size;

        if( compare( value, middle ) < 0 ) /* 在前半部分 */
            count = half;
        else if( compare( middle, value ) < 0 ) /* 在后半部分 */
        {
            first = middle + element_size;
            count -= ( half + 1 );
        }
        else /* middle == value */
        {
            size_t len = ( middle - (const ylib_byte_t*)first ) / element_size;
            result.first = lower_bound( first, len,
                                        element_size, value, compare );
            result.second = upper_bound( middle + element_size, count,
                                         element_size, value, compare );
            return result;
        }
    }

    return result;
}

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

size_t count( const void* first, size_t count, size_t element_size,
              const void* value, ylib_fp_cmp_t compare )
{
    size_t result = 0;
    const ylib_byte_t* begin = (const ylib_byte_t*)first;

    for( ; count > 0; --count, begin += element_size )
    {
        if( compare( begin, value ) == 0 )
            ++result;
    }

    return result;
}

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

const void* min_element( const void* first, size_t count,
                         size_t element_size, ylib_fp_cmp_t compare )
{
    const void* result = first;
    const ylib_byte_t* begin = (const ylib_byte_t*)first;

    for( ; count > 0; --count, begin += element_size )
    {
        if( compare( begin, result ) < 0 )
            result = begin;
    }

    return result;
}

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

const void* max_element( const void* first, size_t count,
                         size_t element_size, ylib_fp_cmp_t compare )
{
    const void* result = first;
    const ylib_byte_t* begin = (const ylib_byte_t*)first;

    for( ; count > 0; --count, begin += element_size )
    {
        if( compare( begin, result ) > 0 )
            result = begin;
    }

    return result;
}

/******************************************************************************/
/******************************************************************************/
#ifdef __cplusplus
    }  }
#endif
/******************************************************************************/
/******************************************************************************/