快速排序法

太过爱你忘了你带给我的痛 2022-08-06 03:13 297阅读 0赞

// vos\_test.cpp : Defines the entry point for the console application.  
//

\#include "stdafx.h"  
\#include "vos.h"

\#define TABLE\_MID\_MACHINE\_NAME     "midmachine"  
\#define TABLE\_MIDMACH\_COLNAME\_ID   "id"  
\#define TABLE\_MIDMACH\_COLNAME\_IP   "ip"  
\#define TABLE\_MIDMACH\_ACTIVE\_FLAG  "activeflag"  
\#define TABLE\_MIDMACH\_COLNAME\_MACH "name"

\#define APP\_NULL VOS\_NULL  
\#define app\_u32 vos\_u32  
\#define app\_void vos\_void

typedef struct  
\{  
 app\_u32 ulcommandid;  //命令字ID  
 app\_u32 ulseq;        //序号，规则每个命令字都对应一批序号，从0开始，即对每个命令下到对应pid进行时序控制  
 app\_u32 uldstpid;     //目标PID  
\} st\_oamreg\_map;

STATIC st\_oamreg\_map\* g\_stoamregmap = APP\_NULL;  
STATIC app\_u32 g\_maxoamregnum = 100;

\#define MAKE\_CMDSEQ(STOBJ) ((STOBJ.ulcommandid << 8) | STOBJ.ulseq)

//快速排序法  
void Qsort(st\_oamreg\_map a\[\], int low, int high)  
\{  
 if (low >= high)  
 \{  
  return;  
 \}

int first = low;  
 int last = high;  
 int keyvalue = 0;  
 int lastvalue = 0;  
 int firstvalue = 0;

st\_oamreg\_map key;  
 memset(&key, 0, sizeof(st\_oamreg\_map));  
 memcpy(&key, &a\[first\], sizeof(st\_oamreg\_map));  
 keyvalue = MAKE\_CMDSEQ(key);

while (first < last)  
 \{  
  while ((first < last) && ((lastvalue = MAKE\_CMDSEQ(a\[last\])) >= keyvalue)) --last;

memcpy(&a\[first\], &a\[last\], sizeof(st\_oamreg\_map));

while ((first < last) && ((firstvalue = MAKE\_CMDSEQ(a\[first\])) <= keyvalue)) ++first;

memcpy(&a\[last\], &a\[first\], sizeof(st\_oamreg\_map));  
 \}

memcpy(&a\[first\], &key, sizeof(st\_oamreg\_map));

Qsort(a, low, first-1);  
 Qsort(a, first+1, high);  
\}  
static app\_void app\_oam\_initoamregmap()  
\{  
 app\_u32 ullen = 0;  
 app\_u32 ulrunrslt = VOS\_OK;

ullen = sizeof(st\_oamreg\_map) \* g\_maxoamregnum;  
 g\_stoamregmap = (st\_oamreg\_map \*)malloc(ullen);  
 memset(g\_stoamregmap, 0, ullen);  
 return;  
\}  
STATIC app\_u32 app\_oam\_register(st\_oamreg\_map stcmdmap)  
\{  
 app\_u32 ulindex = 0;

for (ulindex = 0; ulindex < g\_maxoamregnum; ulindex++)  
 \{  
  if (((stcmdmap.ulcommandid == g\_stoamregmap\[ulindex\].ulcommandid)  
   && (stcmdmap.uldstpid == g\_stoamregmap\[ulindex\].uldstpid))  
   || ((stcmdmap.ulcommandid == g\_stoamregmap\[ulindex\].ulcommandid)  
   && (stcmdmap.ulseq == g\_stoamregmap\[ulindex\].ulseq)))  
  \{  
   vos\_syslog(-1, vos\_log\_type\_running,  
    "\[Error\] ulcommandid(0x%x) ulseq(%d) uldstpid(0x%x) repeat %s(%d)\\r\\n",  
    stcmdmap.ulcommandid, (int)stcmdmap.ulseq, stcmdmap.uldstpid,  
    vos\_filterpathforfile((vos\_u8\*)\_\_FILE\_\_), \_\_LINE\_\_);  
   return -1;  
  \}

if ((0 == g\_stoamregmap\[ulindex\].ulcommandid)  
   && (0 == g\_stoamregmap\[ulindex\].uldstpid)  
   && (0 == g\_stoamregmap\[ulindex\].ulseq))  
  \{  
   g\_stoamregmap\[ulindex\].ulcommandid = stcmdmap.ulcommandid;  
   g\_stoamregmap\[ulindex\].ulseq = stcmdmap.ulseq;  
   g\_stoamregmap\[ulindex\].uldstpid = stcmdmap.uldstpid;  
   return VOS\_OK;  
  \}  
 \}

return -1;  
\}

STATIC app\_u32 app\_oam\_multi\_register(st\_oamreg\_map \*pstcmdmap, app\_u32 ulnum)  
\{  
 app\_u32 ulresult = VOS\_OK;  
 app\_u32 ulindex = 0;

for (ulindex = 0; ulindex < ulnum; ulindex++)  
 \{  
  ulresult = app\_oam\_register(pstcmdmap\[ulindex\]);  
  if (VOS\_OK != ulresult)  
  \{  
   return ulresult;  
  \}  
 \}

//!!!这里可以进行2级排序操作，但本注册功能只在本模块使用，因此简单处理，不进行排序操作了  
 //!!!维护该模块的同事需要特别注意，注册时务必保证排序正确  
 //!!!先按照命令排序，然后序号排序(要求从小到大)   
 Qsort(g\_stoamregmap, 0, ulnum-1);  
   
 return ulresult;  
\}

int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{  
 app\_u32 ulrunrslt = VOS\_OK;  
 vos\_u32 ulindex = 0;

//初始化oam注册映射  
 app\_oam\_initoamregmap();

//!!!注意以下数组注册必须保证顺序，否则执行中时序将会出错!!!  
 //!!!顺序为: 先按命令字，再按序号(从0开始，必须从小到大)!!!  
 static const st\_oamreg\_map s\_oamreg\[\] =  
 \{  
  //暂停  
  \{0x8011, 23, 333\},  
  \{0x8011, 0, 111\},  
  \{0x8003, 0, 777\},

//恢复  
  \{0x8001, 0, 444\},  
  \{0x8001, 1, 555\},  
  \{0x8003, 2, 999\},  
  \{0x8001, 2, 666\},

//停止    
  \{0x8003, 1, 888\},    
  \{0x8003, 3, 1000\},  
  \{0x8003, 4, 2000\},  
  \{0x8003, 5, 3000\},  
  \{0x8011, 1, 222\},  
 \};

ulrunrslt = app\_oam\_multi\_register((st\_oamreg\_map\*)s\_oamreg, sizeof(s\_oamreg)/sizeof(s\_oamreg\[0\]));  
 if (VOS\_OK != ulrunrslt)  
 \{  
  return ulrunrslt;  
 \}

for (ulindex = 0; ulindex < g\_maxoamregnum; ulindex++)  
 \{  
  printf("0x%x 0x%x %d \\n", g\_stoamregmap\[ulindex\].ulcommandid,  
   g\_stoamregmap\[ulindex\].ulseq, g\_stoamregmap\[ulindex\].uldstpid);  
 \}

return VOS\_OK;