我的git代码仓库: [https://code.aliyun.com/whjwnavy] or [https://github.com/WHJWNAVY]

内存排序算法

设计语言 WHJWNAVY 285℃ 0评论

/******************************************************************************
 
                  版权所有 (C), 2017, WHJWNAVY
 
 ******************************************************************************
  
     : mac_qsort.c
       : 初稿
         : wnavy
  生成日期   : 星期五,20170303
  最近修改   :
  功能描述   : 内存排序函数使用示例
  函数列表   :
              hwApiMacAddrGet
              macaddr_comp_t
              main
              qsort_comp
              qsort_t
              sys_util_mac2Str
              sys_util_mactbl_print
  
使用说明   :比如有一个存放FDB表的结构体数组,结构体里包含MAC地址,如果我们想要
              对这个结构体数组排序,要求是按照MAC地址从小到达的顺序排列,该怎么做?
              本文就是为了解决类似这样的问题:按照指定条件对一断内存进行排序。
******************************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef unsigned int size_t;
#ifndef assert
#define assert(expr) do{}while (0)
#endif
 

#define ETHERADDR_LEN        6/*以太网地址长度*/
typedef unsigned char        mac_addr_t;
 

/* 定义L2 MAC地址基本类型 */
typedef enum hwMacType_e 
{
    HW_MAC_TYPE_LEARN,              /* 
学习MAC类型 */
    HW_MAC_TYPE_NORMAL,             /* 正常转发状态的MAC类型 */
    HW_MAC_TYPE_SRC_DROP,           /* 源丢弃MAC类型 */
    HW_MAC_TYPE_DST_DROP,           /* 目的丢弃MAC类型 */
    HW_MAC_TYPE_BLACKHOLE,          /* 黑洞MAC类型,报文源或者目的MAC匹配该表项会被丢弃 */
    HW_MAC_TYPE_MIRROR_TO_CPU,      /*MACCPU并转发类型,目的MAC报文上CPU并转发  */  
    HW_MAC_TYPE_FORWARD_TO_CPU,     /*MACCPU类型,目的MAC报文上CPU*/      
    HW_MAC_TYPE_END
}hwMacType_t;
 

typedef struct hwMacAddr_s 
{
    hwMacType_t     MacType;                    /* MAC
地址表项种类 */
    mac_addr_t      MacAddr[ETHERADDR_LEN];     /* MAC地址 */
    int             VlanId;                     /* VLAN */
    int             AgUnit;                     /* AG
端口号 */
    int             hwIndex;                    /* 对应的硬件表项索引 */
}hwMacAddr_t;
 

#define MAC_ADDR_LEN        (ETHERADDR_LEN*(sizeof(mac_addr_t)))
#define MAC_ADDR_TBL_LEN    30
#define GET_MAC_ADDR(p)     (((hwMacAddr_t *)(p))->MacAddr)
 

/*****************************************************************************
 
    : qsort_t
 功能描述  : 内存排序函数(实际上就是qsort函数,取自于uboot源码)
 输入参数  : void  *base               :待排序数组首地址
             size_t nel                :数组中待排序元素数量
             size_t width              :各元素的占用空间大小
             int (*comp)(const void *  
             const void *)             :
指向函数的指针,用于确定排序的顺序
 输出参数  : void  *base               :待排序数组首地址
     : void
*****************************************************************************/
void qsort_t(void  *base, size_t nel, size_t width, int (*comp)(const void *, const void *))
{
    size_t wgap, i, j, k;
    char tmp;
    if ((nel > 1) && (width > 0))
    {
        assert(nel <= ((size_t)(-1)) / width); /* check for overflow */
        wgap = 0;
        do
        {
            wgap = 3 * wgap + 1;
        }
        while (wgap < (nel - 1) / 3);
        /* From the above, we know that either wgap == 1 < nel or */
        /* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap <  nel. */
        wgap *= width;          /* So this can not overflow if wnel doesn't. */
        nel *= width;           /* Convert nel to 'wnel' */
        do
        {
            i = wgap;
            do
            {
                j = i;
                do
                {
                    register char *a;
                    register char *b;
                    j -= wgap;
                    a = j + ((char *)base);
                    b = a + wgap;
                    if ((*comp)(a, b) <= 0)
                    {
                        break;
                    }
                    k = width;
                    do
                    {
                        tmp = *a;
                        *a++ = *b;
                        *b++ = tmp;
                    }
                    while (--k);
                }
                while (j >= wgap);
                i += width;
            }
            while (i < nel);
            wgap = (wgap - width) / 3;
        }
        while (wgap);
    }
}
 

/*****************************************************************************
 
    : qsort_comp_t
 功能描述  : MAC地址比较函数
 输入参数  :  
 输出参数  : 
     : 
*****************************************************************************/
int macaddr_comp_t(mac_addr_t* cst, mac_addr_t* ctt, size_t cntt)
{
    int res = 0;
    mac_addr_t* cs = cst;
    mac_addr_t* ct = ctt;
    size_t cnt = cntt;
 

    while (cnt)
    {
        if ((res = ((mac_addr_t)(*cs) - (mac_addr_t)(*ct))) != 0)
        {
            break;
        }
        cs++;
        ct++;
        cnt--;
    }
    return res;
}
 

/*****************************************************************************
 
    : qsort_comp
 功能描述  : 内存比较函数,需要根据自己的需要编写
 输入参数  : const void *p1  
             const void *p2  
 
输出参数  : 
     : p1==p2,则返回零;
             p1<p2,则返回负数;
             p1>p2,则返回正数。
*****************************************************************************/
int qsort_comp(const void *p1, const void *p2)
{
    return macaddr_comp_t((mac_addr_t *)GET_MAC_ADDR(p1), (mac_addr_t *)GET_MAC_ADDR(p2), MAC_ADDR_LEN);
}
 

/*****************************************************************************
 
    : hwApiMacAddrGet
 功能描述  : 模拟从硬件中获取FDB
 输入参数  : 
 输出参数  : 
     : 
*****************************************************************************/
void hwApiMacAddrGet(hwMacAddr_t* tbl, size_t len)
{
    size_t i = 0, j=0;
    mac_addr_t t = 255;
    //mac_addr_t* addrt;
    
    for(i=0; i<len; i++)
    {
        tbl[i].MacType = HW_MAC_TYPE_LEARN;
        tbl[i].VlanId = 1;
        tbl[i].AgUnit = 10;
        tbl[i].hwIndex = i;
        //addrt = tbl[i].MacAddr;
        for(j=0; j<MAC_ADDR_LEN; j++)
        {
            tbl[i].MacAddr[j] = t--;
            //printf("tbl[%d].MacAddr[%d]=[%d]\r\n", i, j, tbl[i].MacAddr[j]);
            if(t<0) t=255;//
从大到小

        }
    }
}
 
/*****************************************************************************
 
    : sys_util_mac2Str
 功能描述  : MAC地址转换成字符串
 输入参数  : 
 输出参数  : 
     : 
*****************************************************************************/
int sys_util_mac2Str(mac_addr_t *pMac, char *pStr)
{
    /* parameter check */
    if((NULL == pMac)|| (NULL == pStr))
    {
        return -1;
    }
    
    sprintf(pStr, "%02X:%02X:%02X:%02X:%02X:%02X",
    pMac[0], pMac[1], pMac[2], pMac[3], pMac[4], pMac[5]);
    return 0;
}
 

/*****************************************************************************
 
    : sys_util_mactbl_print
 功能描述  : 格式化输出FDB
 输入参数  : 
 输出参数  : 
     : 
*****************************************************************************/
void sys_util_mactbl_print(hwMacAddr_t* macaddr_tbl)
{
    size_t i = 0;
    char macaddr_str[24] = {0};
 

    for(i=0; i<MAC_ADDR_TBL_LEN; i++)
    {
        memset(macaddr_str, 0sizeof(macaddr_str));
        sys_util_mac2Str(macaddr_tbl[i].MacAddr, macaddr_str);
        printf("MacType[%03d], VlanId[%03d], AgUnit[%02d], hwIndex[%03d], MacAddr[%s]\r\n",
               macaddr_tbl[i].MacType, macaddr_tbl[i].VlanId, macaddr_tbl[i].AgUnit, 
               macaddr_tbl[i].hwIndex, macaddr_str);
    }
}
 

void main(void)
{
    hwMacAddr_t* macaddr_tbl = malloc(sizeof(hwMacAddr_t)*MAC_ADDR_TBL_LEN);
    hwApiMacAddrGet(macaddr_tbl, MAC_ADDR_TBL_LEN);
    printf("No Sorted Hardware Table:\r\n");//
从大到小

    sys_util_mactbl_print(macaddr_tbl);
    qsort_t(macaddr_tbl, MAC_ADDR_TBL_LEN, sizeof(hwMacAddr_t), qsort_comp);
    printf("Sorted Hardware Table:\r\n");//
从小到大

    sys_util_mactbl_print(macaddr_tbl);
}


转载请注明:胡椒小兄弟 » 内存排序算法

喜欢 (1)or分享 (0)
发表我的评论
取消评论
表情 签到