| C语言学习 | 您所在的位置：网站首页 › c语言中进制转换程序 › C语言学习 |
|
目录 一、自由抒发 二、余除法 1、思路 （1）正数转换 （2）负数转换 2、函数 （1）参数介绍 （2）源码 三、按位与法 1、思路 2、函数 （1）参数介绍 （2）源码 （3）宏 四、测试 1、Demo 2、编译 3、测试环境 4、功能验证 5、性能验证 （1）Decimal2Binary （2）Arbitrary2Binary 6、结果 五、qsort函数 1、使用与介绍 2、源码 （1）qsort （2）__qsort_r 一、自由抒发这段时间在摸索进程间通信时，发现权限的表示是用二进制位进行展现，所以想着实现一个将十进制转二进制字符串表示出来更直观。其实也是想换换脑子，稍稍放松一下，最后加油、加油、再加油。最后的最后再说一句，能想到并实现第二种方法，很有成就感，灵感来源于标准库函数qsort的源码实现（后面会贴出来供大家参考），不得不说大佬值得我们学习，多的不说了开始吧。 二、余除法 1、思路因为正数和负数的二进制转换不一样，所以分开讨论。 （1）正数转换以数字9为例，一直除以2，余数为二进制位，算出的第一个余数为最低位，以升序排列。 9 / 2 = 4 ... 1 -- 低位 4 / 2 = 2 ... 0 | 2 / 2 = 1 ... 0 | 1 / 2 = 0 ... 1 -- 高位int占四个字节，每个字节8位，最后表示出来的结果如下 00000000000000000000000000001001 （2）负数转换在计算机中，负数以其正值的补码形式表达，补码是正数二进制取反加一。我们就用上面计算好的9的二进制来进行讲解。 首先取反，也就是0变1，1变0的过程。 11111111111111111111111111110110末尾加一，逢二进一，就是最终结果啦。 11111111111111111111111111110111 2、函数 （1）参数介绍 序号函数名描述1DecimalVal需要转换成二进制的十进制数。2RetBinary返回的二进制字符数组。3BinaryLen二进制字符数组的长度。 （2）源码 Status Decimal2Binary(int DecimalVal, MyStrType RetBinary, size_t BinaryLen) { JudgeAllNullPointer(RetBinary); size_t BinaryUseLen = sizeof(int) * ONE_BYTE_TO_BIT; //二进制数据的长度计算方法为：int类型占用的字节数 * 一个字节的占用位数。 if (BinaryLen < BinaryUseLen + 1) { LogFormat(Error,"Decimal2Binary : Fail, RetBinary Len Need %ld.\n",BinaryUseLen + 1); return FAIL_FLAG; } RetBinary[BinaryUseLen] = STR_END_CHAR; BinaryUseLen--; int Quotient = DecimalVal; //商 int Remainder; //余数 if (DecimalVal >= 0)//正数 { do { Remainder = Quotient % 2; Quotient = Quotient / 2; switch (Remainder) { case 0: RetBinary[BinaryUseLen] = '0'; break; case 1: RetBinary[BinaryUseLen] = '1'; break; default: LogFormat(Error,"Decimal2Binary : Fail, DecimalVal :%d, Remainder : %d.\n",DecimalVal,Remainder); return FAIL_FLAG; } BinaryUseLen--; } while (Quotient != 0); for (; BinaryUseLen > 0; BinaryUseLen--)//补齐其他空余位数。 { RetBinary[BinaryUseLen] = '0'; } RetBinary[BinaryUseLen] = '0'; } else//在计算机中，负数以其正值的补码形式表达。负数二进制 = 正数二进制取反 + 1。 { //直接取反，避免二次遍历数组。 do { Remainder = Quotient % 2; Quotient = Quotient / 2; switch (Remainder) { case 0: RetBinary[BinaryUseLen] = '1'; break; case -1: RetBinary[BinaryUseLen] = '0'; break; default: LogFormat(Error,"Decimal2Binary : Fail, DecimalVal :%d, Remainder : %d.\n",DecimalVal,Remainder); return FAIL_FLAG; } BinaryUseLen--; } while (Quotient != 0); for (; BinaryUseLen > 0; BinaryUseLen--)//补齐其他空余位数。 { RetBinary[BinaryUseLen] = '1'; } RetBinary[BinaryUseLen] = '1'; //反码加一 for (BinaryUseLen = sizeof(int) * ONE_BYTE_TO_BIT - 1; BinaryUseLen > 0; BinaryUseLen--) { if (RetBinary[BinaryUseLen] == '0') { RetBinary[BinaryUseLen] = '1'; break; } RetBinary[BinaryUseLen] = '0'; } if (BinaryUseLen == 0) { RetBinary[BinaryUseLen] = '0'; } } LogFormat(Debug,"Decimal2Binary : OK, RetBinary : %s, DecimalVal :%d.\n",RetBinary,DecimalVal); return SUCCESS_FLAG; } 三、按位与法 1、思路位操作与，有一个假为假，两个都是真为真。0为假，1为真。 01000101还是以int 9为例子，int类型进行四个字节，不过我按照每8位一分割，是不是有些感觉了，继续往后说。 00000000 00000000 00000000 00001001每个字节占8位是固定的，如果我想取最右边第一个是不是可以与二进制一进行与呢。二进制一如下 00000001与后的结果，还是为1，结果为真 00000001后续的7位我们就进行这种操作。 00001001 & 00000001 = 00000001 00001001 & 00000010 = 00000000 00001001 & 00000100 = 00000000 00001001 & 00001000 = 00001000 00001001 & 00010000 = 00000000 00001001 & 00100000 = 00000000 00001001 & 01000000 = 00000000 00001001 & 10000000 = 00000000每一位如果为真就是1，假就是0。 一个字节是八位，每个数据类型都是以字节为基本单位，char占用一个字节，所以可以把所有数据类型转换成char*，进行一一计算。 2、函数 （1）参数介绍 序号函数名描述1TransformData需要转换的数据。2TransformDataSize需要转换的数据字节数。3RetBinary返回的二进制字符串。输出参数。4BinaryLen二进制字符串的最大长度。输入参数。 （2）源码 Status Arbitrary2Binary(void* TransformData, size_t TransformDataSize, MyStrType RetBinary, size_t BinaryLen) { JudgeAllNullPointer(RetBinary); size_t BinaryUseLen = TransformDataSize * ONE_BYTE_TO_BIT; //二进制数据的长度计算方法为：int类型占用的字节数 * 一个字节的占用位数。 if (BinaryLen < BinaryUseLen + 1) { LogFormat(Error,"Arbitrary2Binary : Fail, RetBinary Len Need %ld.\n",BinaryUseLen + 1); return FAIL_FLAG; } RetBinary[BinaryUseLen] = STR_END_CHAR; BinaryUseLen--; char* TmpData = TransformData; size_t TmpDataIdx = 0; for (; TmpDataIdx < TransformDataSize; TmpDataIdx++,BinaryUseLen--) { RetBinary[BinaryUseLen] = (TmpData[TmpDataIdx] & CHAR_TYPE_SET_ONE_INDEX_1) ? '1' : '0'; BinaryUseLen--; RetBinary[BinaryUseLen] = (TmpData[TmpDataIdx] & CHAR_TYPE_SET_ONE_INDEX_2) ? '1' : '0'; BinaryUseLen--; RetBinary[BinaryUseLen] = (TmpData[TmpDataIdx] & CHAR_TYPE_SET_ONE_INDEX_3) ? '1' : '0'; BinaryUseLen--; RetBinary[BinaryUseLen] = (TmpData[TmpDataIdx] & CHAR_TYPE_SET_ONE_INDEX_4) ? '1' : '0'; BinaryUseLen--; RetBinary[BinaryUseLen] = (TmpData[TmpDataIdx] & CHAR_TYPE_SET_ONE_INDEX_5) ? '1' : '0'; BinaryUseLen--; RetBinary[BinaryUseLen] = (TmpData[TmpDataIdx] & CHAR_TYPE_SET_ONE_INDEX_6) ? '1' : '0'; BinaryUseLen--; RetBinary[BinaryUseLen] = (TmpData[TmpDataIdx] & CHAR_TYPE_SET_ONE_INDEX_7) ? '1' : '0'; BinaryUseLen--; RetBinary[BinaryUseLen] = (TmpData[TmpDataIdx] & CHAR_TYPE_SET_ONE_INDEX_8) ? '1' : '0'; } LogFormat(Debug,"Arbitrary2Binary : OK, RetBinary : %s.\n",RetBinary); return SUCCESS_FLAG; } （3）宏 #define CHAR_TYPE_SET_ONE_INDEX_1 0B00000001 #define CHAR_TYPE_SET_ONE_INDEX_2 0B00000010 #define CHAR_TYPE_SET_ONE_INDEX_3 0B00000100 #define CHAR_TYPE_SET_ONE_INDEX_4 0B00001000 #define CHAR_TYPE_SET_ONE_INDEX_5 0B00010000 #define CHAR_TYPE_SET_ONE_INDEX_6 0B00100000 #define CHAR_TYPE_SET_ONE_INDEX_7 0B01000000 #define CHAR_TYPE_SET_ONE_INDEX_8 0B10000000 四、测试 1、Demo #include "DataConvertion.h" #define TEST_ARRAY_LEN 65 Status main() { char RetBinary[TEST_ARRAY_LEN]; int TestData; long long TestLL; for ( TestData = -9,TestLL = -9; TestData < 10; TestData++,TestLL++) { Decimal2Binary(TestData, RetBinary, TEST_ARRAY_LEN); Arbitrary2Binary(&TestData, sizeof(TestData), RetBinary, TEST_ARRAY_LEN); Arbitrary2Binary(&TestLL, sizeof(TestLL), RetBinary, TEST_ARRAY_LEN); } return SUCCESS_FLAG; } 2、编译 [gbase@czg2 DataConvertion]$ make clean rm -rf Test [gbase@czg2 DataConvertion]$ make gcc -Wall -Wextra -O3 -std=gnu11 Test.c -o Test -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/ -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/Log/ -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/DataConvertion/ -L /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Make/Libs/ -L /usr/lib64/ -l PublicFunction -l Log -l DataConvertion我把函数以动态库的形式编译到Demo中了，大家可以直接编译到一起，其实是一样的。 3、测试环境 名称值CPUIntel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz操作系统CentOS Linux release 7.9.2009 (Core)内存3G逻辑核数2 4、功能验证 [gbase@czg2 DataConvertion]$ ./Test 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 11111111111111111111111111110111, DecimalVal :-9. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 11111111111111111111111111110111. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 1111111111111111111111111111111111111111111111111111111111110111. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 11111111111111111111111111111000, DecimalVal :-8. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 11111111111111111111111111111000. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 1111111111111111111111111111111111111111111111111111111111111000. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 11111111111111111111111111111001, DecimalVal :-7. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 11111111111111111111111111111001. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 1111111111111111111111111111111111111111111111111111111111111001. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 11111111111111111111111111111010, DecimalVal :-6. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 11111111111111111111111111111010. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 1111111111111111111111111111111111111111111111111111111111111010. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 11111111111111111111111111111011, DecimalVal :-5. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 11111111111111111111111111111011. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 1111111111111111111111111111111111111111111111111111111111111011. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 11111111111111111111111111111100, DecimalVal :-4. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 11111111111111111111111111111100. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 1111111111111111111111111111111111111111111111111111111111111100. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 11111111111111111111111111111101, DecimalVal :-3. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 11111111111111111111111111111101. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 1111111111111111111111111111111111111111111111111111111111111101. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 11111111111111111111111111111110, DecimalVal :-2. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 11111111111111111111111111111110. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 1111111111111111111111111111111111111111111111111111111111111110. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 11111111111111111111111111111111, DecimalVal :-1. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 11111111111111111111111111111111. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 1111111111111111111111111111111111111111111111111111111111111111. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 00000000000000000000000000000000, DecimalVal :0. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 00000000000000000000000000000000. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 0000000000000000000000000000000000000000000000000000000000000000. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 00000000000000000000000000000001, DecimalVal :1. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 00000000000000000000000000000001. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 0000000000000000000000000000000000000000000000000000000000000001. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 00000000000000000000000000000010, DecimalVal :2. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 00000000000000000000000000000010. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 0000000000000000000000000000000000000000000000000000000000000010. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 00000000000000000000000000000011, DecimalVal :3. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 00000000000000000000000000000011. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 0000000000000000000000000000000000000000000000000000000000000011. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 00000000000000000000000000000100, DecimalVal :4. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 00000000000000000000000000000100. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 0000000000000000000000000000000000000000000000000000000000000100. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 00000000000000000000000000000101, DecimalVal :5. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 00000000000000000000000000000101. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 0000000000000000000000000000000000000000000000000000000000000101. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 00000000000000000000000000000110, DecimalVal :6. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 00000000000000000000000000000110. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 0000000000000000000000000000000000000000000000000000000000000110. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 00000000000000000000000000000111, DecimalVal :7. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 00000000000000000000000000000111. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 0000000000000000000000000000000000000000000000000000000000000111. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 00000000000000000000000000001000, DecimalVal :8. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 00000000000000000000000000001000. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 0000000000000000000000000000000000000000000000000000000000001000. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Decimal2Binary : OK, RetBinary : 00000000000000000000000000001001, DecimalVal :9. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 00000000000000000000000000001001. 2024-03-12 11:06:24-P[130212]-T[0]-[Debug]-Arbitrary2Binary : OK, RetBinary : 0000000000000000000000000000000000000000000000000000000000001001. 5、性能验证基于上面的Demo，我们只测试单个函数，其他函数测试前，请注释掉，再编译。Debug级别日志会关闭，影响性能，测试2亿多条数据。 （1）Decimal2Binary #include "DataConvertion.h" #define TEST_ARRAY_LEN 65 Status main() { char RetBinary[TEST_ARRAY_LEN]; int TestData; long long TestLL; for ( TestData = -9,TestLL = -9; TestData < 200000000; TestData++,TestLL++) { Decimal2Binary(TestData, RetBinary, TEST_ARRAY_LEN); //Arbitrary2Binary(&TestData, sizeof(TestData), RetBinary, TEST_ARRAY_LEN); //Arbitrary2Binary(&TestLL, sizeof(TestLL), RetBinary, TEST_ARRAY_LEN); } return SUCCESS_FLAG; } [gbase@czg2 DataConvertion]$ time ./Test real 0m5.808s user 0m5.799s sys 0m0.004s [gbase@czg2 DataConvertion]$ time ./Test real 0m6.221s user 0m6.027s sys 0m0.014s [gbase@czg2 DataConvertion]$ time ./Test real 0m5.904s user 0m5.893s sys 0m0.009s [gbase@czg2 DataConvertion]$ perf stat -e page-faults ./Test Performance counter stats for './Test': 118 page-faults:u 5.595555016 seconds time elapsed 5.590535000 seconds user 0.001002000 seconds sys （2）Arbitrary2Binary #include "DataConvertion.h" #define TEST_ARRAY_LEN 65 Status main() { char RetBinary[TEST_ARRAY_LEN]; int TestData; long long TestLL; for ( TestData = -9,TestLL = -9; TestData < 200000000; TestData++,TestLL++) { //Decimal2Binary(TestData, RetBinary, TEST_ARRAY_LEN); Arbitrary2Binary(&TestData, sizeof(TestData), RetBinary, TEST_ARRAY_LEN); //Arbitrary2Binary(&TestLL, sizeof(TestLL), RetBinary, TEST_ARRAY_LEN); } return SUCCESS_FLAG; } [gbase@czg2 DataConvertion]$ time ./Test real 0m3.610s user 0m3.599s sys 0m0.007s [gbase@czg2 DataConvertion]$ time ./Test real 0m3.643s user 0m3.638s sys 0m0.002s [gbase@czg2 DataConvertion]$ time ./Test real 0m3.979s user 0m3.969s sys 0m0.004s [gbase@czg2 DataConvertion]$ perf stat -e page-faults ./Test Performance counter stats for './Test': 118 page-faults:u 3.610504632 seconds time elapsed 3.602109000 seconds user 0.004011000 seconds sys 6、结果按位与法相较于余除法在效率上有一定的提升，在后续的编程中，我们也可以多利用位操作。 五、qsort函数 1、使用与介绍大家可以参考之前的博客《C语言学习-15_qsort_bsearch函数》 2、源码 （1）qsort void qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) { return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL); } （2）__qsort_r void __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg) { size_t size = n * s; char *tmp = NULL; struct msort_param p; /* For large object sizes use indirect sorting. */ if (s > 32) size = 2 * n * sizeof (void *) + s; if (size < 1024) /* The temporary array is small, so put it on the stack. */ p.t = __alloca (size); else { /* We should avoid allocating too much memory since this might have to be backed up by swap space. */ static long int phys_pages; static int pagesize; if (pagesize == 0) { phys_pages = __sysconf (_SC_PHYS_PAGES); if (phys_pages == -1) /* Error while determining the memory size. So let's assume there is enough memory. Otherwise the implementer should provide a complete implementation of the `sysconf' function. */ phys_pages = (long int) (~0ul >> 1); /* The following determines that we will never use more than a quarter of the physical memory. */ phys_pages /= 4; /* Make sure phys_pages is written to memory. */ atomic_write_barrier (); pagesize = __sysconf (_SC_PAGESIZE); } /* Just a comment here. We cannot compute phys_pages * pagesize and compare the needed amount of memory against this value. The problem is that some systems might have more physical memory then can be represented with a `size_t' value (when measured in bytes. */ /* If the memory requirements are too high don't allocate memory. */ if (size / pagesize > (size_t) phys_pages) { _quicksort (b, n, s, cmp, arg); return; } /* It's somewhat large, so malloc it. */ int save = errno; tmp = malloc (size); __set_errno (save); if (tmp == NULL) { /* Couldn't get space, so use the slower algorithm that doesn't need a temporary array. */ _quicksort (b, n, s, cmp, arg); return; } p.t = tmp; } p.s = s; p.var = 4; p.cmp = cmp; p.arg = arg; if (s > 32) { /* Indirect sorting. */ char *ip = (char *) b; void **tp = (void **) (p.t + n * sizeof (void *)); void **t = tp; void *tmp_storage = (void *) (tp + n); while ((void *) t < tmp_storage) { *t++ = ip; ip += s; } p.s = sizeof (void *); p.var = 3; msort_with_tmp (&p, p.t + n * sizeof (void *), n); /* tp[0] .. tp[n - 1] is now sorted, copy around entries of the original array. Knuth vol. 3 (2nd ed.) exercise 5.2-10. */ char *kp; size_t i; for (i = 0, ip = (char *) b; i < n; i++, ip += s) if ((kp = tp[i]) != ip) { size_t j = i; char *jp = ip; memcpy (tmp_storage, ip, s); do { size_t k = (kp - (char *) b) / s; tp[j] = jp; memcpy (jp, kp, s); j = k; jp = kp; kp = tp[k]; } while (kp != ip); tp[j] = jp; memcpy (jp, tmp_storage, s); } } else { if ((s & (sizeof (uint32_t) - 1)) == 0 && ((uintptr_t) b) % __alignof__ (uint32_t) == 0) { if (s == sizeof (uint32_t)) p.var = 0; else if (s == sizeof (uint64_t) && ((uintptr_t) b) % __alignof__ (uint64_t) == 0) p.var = 1; else if ((s & (sizeof (unsigned long) - 1)) == 0 && ((uintptr_t) b) % __alignof__ (unsigned long) == 0) p.var = 2; } msort_with_tmp (&p, b, n); } free (tmp); } |
| CopyRight 2018-2019 实验室设备网 版权所有 |