目录

一、自由抒发

二、余除法

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为真。

01
000
101

还是以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);
}

# 学习 # c语言 # unix # 开发语言 # visual studio code
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

cover

赛项征集 | 第二届开放原子开源大赛——汽车软件开源赛火热进行中

avatar 开放原子开发者工作坊

开放原子校源行启动优质开源课程征集，助力高校开源人才培养

校源行启动优质开源课程征集，助力高校开源人才培养

avatar 开放原子开发者工作坊
cover

第二届Open Source Congress在北京成功举办

avatar 开放原子开发者工作坊