目录

一、自由抒发

二、余除法

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、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

“源”聚天大，码动未来|开放原子校源行（天津大学站）即将启幕！

11月22日，开放原子校源行（天津大学站）将在天津大学北洋园校区隆重举办。

avatar 开放原子开发者工作坊

openEuler系累计装机量突破1000万，树立操作系统产业新里程碑

11月15日，以“以智能，致世界”为主题的操作系统大会2024在北京中关村国际创新中心召开。

avatar 开放原子开发者工作坊

多模态大模型&科学计算双管齐下，百度飞桨两大赛项报名倒计时！

第二届开放原子大赛是由开放原子开源基金会组织举办的开源技术领域专业赛事，聚焦解决真问题，重点覆盖基础软件、工业软件、人工智能大模型等领域

avatar 开放原子开发者工作坊