![cover](https://img-blog.csdnimg.cn/img_convert/52357f4fa522497e902fdb606b4e5790.png)
C语言学习-23-十进制转二进制(多种方法实现)
本文介绍如果通过多种方法实现十进制到二进制的转换,包括思路、源码、测试等。
目录
一、自由抒发
这段时间在摸索进程间通信时,发现权限的表示是用二进制位进行展现,所以想着实现一个将十进制转二进制字符串表示出来更直观。其实也是想换换脑子,稍稍放松一下,最后加油、加油、再加油。最后的最后再说一句,能想到并实现第二种方法,很有成就感,灵感来源于标准库函数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)参数介绍
序号 | 函数名 | 描述 |
1 | DecimalVal | 需要转换成二进制的十进制数。 |
2 | RetBinary | 返回的二进制字符数组。 |
3 | BinaryLen | 二进制字符数组的长度。 |
(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为真。
0 | 1 | |
0 | 0 | 0 |
1 | 0 | 1 |
还是以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)参数介绍
序号 | 函数名 | 描述 |
1 | TransformData | 需要转换的数据。 |
2 | TransformDataSize | 需要转换的数据字节数。 |
3 | RetBinary | 返回的二进制字符串。输出参数。 |
4 | BinaryLen | 二进制字符串的最大长度。输入参数。 |
(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、测试环境
名称 | 值 |
CPU | Intel(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);
}
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)