数据结构之顺序表已毕

前言

做iOS开发的仇人们都了解,方今风尚的Xcode7,新建项目默许就打开了bitcode设置.而且大部分开发者都被这么些出人意料的bitcode功效给坑过造成品种编译失利,而那一个因为bitcode而编译失利的的类型都有一个共同点,就是链接了第三方二进制的库或者框架,而这么些框架或者库恰好没有包蕴bitcode的东西(暂且称为东西),从而致使项目编译不成功.所以每当遇上那几个场地时候一大半人都是直接设置Xcode关闭bitcode功用,全部不生成bitcode.也不去探讨这一开关背后暗藏的原理.中枪的请点个赞.

LLVM是当下苹果应用的编译器工具链,Bitcode是LLVM编译器的中间代码的一种编码,LLVM的前端可以明白为C/C++/OC/斯威·夫特(S·wift)等编程语言,LLVM的后端可以领悟为种种芯片平台上的汇编指令或者可进行机器指令数据,那么,BitCode就是位于那两边直接的中游码.
LLVM的编译工作规律是前者负责把项目程序源代码翻译成Bitcode中间码,然后再根据差异对象机器芯片平台转换为相应的汇编指令以及翻译为机械码.那样设计就可以让LLVM成为了一个编译器架构,可以简单的在LLVM架构之上发明新的语言(前端),以及在LLVM架构下边襄助新的CPU(后端)指令输出,即使Bitcode仅仅只是一个中间码不可以在其他平台上运行,可是它可以转账为任何被援助的CPU架构,包括现在还没被发明的CPU架构,也就是说现在打开Bitcode成效交由一个App到应用商店,将来只要苹果新出了一款手机并CPU也是崭新设计的,在苹果后台服务器一样可以从这几个App的Bitcode初叶编译转化为新CPU上的可执行程序,可供新手机用户下载运行这一个App.

逐一表简介

顺序表就是以数组的款型来存储和治本工作节点。具体的数据结构如下图:

图片 1

由上图能够,seqlist结构体就是实际的顺序表数据结构,length变量表示存储的作业节点的个数,capacity变量表示pnode指向的堆区空间容量。该堆区是一个指针数组,每一个数组元素存储一个事务节点的地方,来针对种种业务节点,因而,管理那几个指针数组的是一个二级指针pnode;

正史回看

在中兴出来以前,苹果紧要的编译器技术是用经过多少立异的GCC工具链来把Objective-C语言编写的代码编译出所指定的机器处理器上原生的可举行程序.编译器爆发的可执行程序叫做”Fat
Binaries”–类似于Windows下PE格式的exe和Linux下的ELF格式的二进制,不一致的是,一个”Fat
Binary”能够包含同一个顺序的不少版本,所以同一个可执行文件可以在不一样的统计机上运行.首要就是以此技能让苹果的硬件很不难的从PowerPC迁移到PowerPC64的微机,以及后来再迁移到速龙和AMD64处理器.那个方案带来的负面影响就是同一个文件中存了多份可实施代码,除了当前机械可进行的那一份之外其余都是没用的,白占空间.
那一个在商海上被叫做”Universal
Binary”,在苹果从PowerPC迁移到速龙处理器的事务起首存在的(一个二进制文件既包括一份PowerPC版本和一份速龙版本).逐步的新兴又援助同时富含英特尔32bit和英特尔 64bit. 在一个Fat
binary中,又操作系统运行时依据处理器类型动态拔取正确的二进制版本来运行,不过应用程序要协理不一致平台的处理器的话,应用程序本身要多占用部分空间.当然也有部分瘦身的工具,比如lipo,可以用来移除fat
binary中这一个当前机械中不被接济的依然多余的可实施代码达到瘦身目标,lipo不会改变程序执行逻辑,仅仅只是文件的大小瘦身.

头文件表明

//seqlist.h
#ifndef _SEQLIST_H_
#define _SEQLIST_H_

typedef void SeqList;
typedef void SeqListNode;

typedef struct tag_SeqList{
    int length;
    int capacity;
    unsigned int **pnode;
}TSeqList;

//创建并且返回一个空的线性表
SeqList *SeqList_Create(int capacity);

//销毁一个线性表
void SeqList_Destroy(SeqList* plist);

//将一个线性表list中的所有元素清空,线性表回到创建时的状态
void SeqList_Clear(SeqList* plist);

//返回一个线性表list中的所有元素个数
int SeqList_Length(SeqList* plist);

//向一个线性表list的pos位置处插入新元素node节点
int SeqList_Insert(SeqList* plist, SeqListNode* pnode, int pos);

//获取一个线性表list的pos位置处的元素
SeqListNode* SeqList_Get(SeqList* plist, int pos);

//删除一个线性表list的pos位的node节点元素,返回值为被删除的元素,NULL表示删除失败
SeqListNode* SeqList_Delete(SeqList* plist, int pos);

//遍历顺序表
#define SeqList_Traverse(plist,node_type,number) \
({ \
    int i;\
    for(i=0; i < plist->length; i++) { \
        printf("number: %d\n",((typeof(node_type)*)(plist->pnode[i]))->number);\
    }  })
#endif //seqlist.h

seqlist.h头文件是对顺序表数据结构和成效接口的架空。在那里面,主要注意一下几点:

  • SeqList和SeqListNode的数据类型:
    是将void数据类型的卷入。原因之一是增高代码的可读性,其二,将void封装,是为着同盟越来越多种类型的业务节点。
  • 以宏函数情势遍历顺序表:首先,我想说名的少数是,遍历的功效实在在我们规划数据结构的操作函数时是没必要设计的。大家统筹的是对事情节点的管理,是“增删改查”,“查”本就可以取得想要的业务节点,但当自家设计是,我们常常会涉嫌遍历的成效,可在自身安顿时意识,数组指针中数组元素指向的事体节点的数据类型不确定,所以无法用printf函数直接打印想要的节点数据。想尝尝的缓解这几个题材,于是自己才设计了这几个宏函数。不用定义的函数的艺术去贯彻遍历功用,是因为不可以在形参中直接得到工作节点的数据类型,只可以通过宏的款型取得工作节点的数据类型。测试代码如下:

#include <stdio.h>
#include <stdlib.h>

typedef struct a{
    char ch;
    int num;
}A; 
int main ()
{
    A a;
    void *ptype = NULL;
    ptype = (void *)&a;
    printf("%lu\n",sizeof(typeof(ptype)));
    return 0;
}

运行的结果是:4,而不是8。获得的是ptype指针的数据类型,而不是struct
a那种数据类型。假若大家用定义函数的不二法门而不是概念宏函数的不二法门去落到实处遍历时,那么,大家接受工作节点的形参只好是“void
*”类型,但大家不能在函数内部接纳typeof关键子获取到形参指向的数量的数据类型,而宏函数能形成。

编译器现状

趁着移动装备移动互联网的长远发展,现在活动设备中的程序大小变得更为主要了,紧假诺因为运动装备中不会有电脑上那么大的一个硬盘驱动器.还有就是苹果已经从原本的ARM处理器迁移到自己设计的A4,A5,A5X,A6,A7,A8,A8X,A9,A9X以及继续的A10处理器,他们的指令集已经发生了改动和原始ARM设计的有所不相同,所有的那几个变迁都被iOS操作系统底层以及Xcode/LLVM编译工具向上层程序员一定程度的晶莹了,编译出来的次序会包蕴众多举行代码版本.当面对这么些题目后,苹果投入大批量资金迁移到LLVM编译器架构并利用bitcode的要求性进一步大.从最早先的把OPENGL编译为一定的GPU指令到把Clang编译器(LLCM的C/OC编译前端)扶助Objective-C的改革并视作Xcode的默认编译器.

LLVM提供了一个虚构指令集机制,它可以翻译出指定的所支撑的计算机架构的进行代码(机器码).那么些就使得为iOS应用程序的编译开发一个截然基于LLVM架构的工具链成为可能.而LLVM的那些编造的通用的指令集可以用很多种代表格式:

  • 号称IR的公文表示的汇编格式(像汇编语言);
  • 转换为二进制数据表示的格式(像目的代码),那些二进制格式就是大家所说的bitcode.

Bitcode和观念的可进行命令集差别,他维护的是函数功用的类型和署名,比如,传统可实施命令集中,一连串(<=8)的布尔值可以减小存储到单个字节中,不过在bitcode中他们是个别独立表示的.其余,逻辑运算操作(比如寄存器清零操作)也由他们相应的逻辑表示方法($R=0);当这几个BitCode要更换为一定机器平台的一声令下集时,他可以用经过针对一定机器平台优化过的汇编指令来顶替:xor eax, eax.(这些汇编指令同样是寄存器<eax>清零操作).

可是bitcode他也不是一点一滴独立于电脑平台和调用约定的.寄存器的高低在命令集中是一个一定关键的表征,众所周知,64bit寄存器可以比32bit寄存器存储越来越多的数据,生成64bit平台的bitcode和32bit平台的bitcode是扎眼例外的,还有,调用约定能够根据函数定义或者函数调用来定义,那么些足以确定函数的参数传递是传寄存器值吗依旧压栈.
一些编程语言还有局地像sizeof(long)那样的预处理指令,那几个将在bitcode生成此前前被翻译.一般情形下,对于支撑fastcc(fast
calling convention)调用的64bit平台会转移与其同一的bitcode代码.

效益函数已毕

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "seqlist.h"

//创建并且返回一个空的线性表
SeqList *SeqList_Create(int capacity)
{
    TSeqList *plist = NULL;

    plist = (TSeqList*)malloc(sizeof(TSeqList));
    memset(plist, 0, sizeof(TSeqList));
    if(NULL == plist)
    {
        perror("SeqList_Create TSeqList");
        return NULL;
    }
    plist->pnode = (unsigned int**)malloc(sizeof(unsigned int)*capacity);
    memset(plist->pnode, 0, sizeof(unsigned int)*capacity);
    if(NULL == plist->pnode)
    {
        perror("SeqList_Create pnode");
        return NULL;
    }
    //plist->length = 0;
    plist->capacity = capacity;

    return plist;
}

//销毁一个线性表
void SeqList_Destroy(SeqList* plist)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Destroy)!\n ");
        return ;
    }

    if(ptlist->pnode != NULL)
    {
        free(ptlist->pnode);
    }
    free(plist);
    return ;
}

//将一个线性表list中的所有元素清空,线性表回到创建时的状态
void SeqList_Clear(SeqList* plist)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Clear)!\n ");
        return ;
    }
    ptlist->length = 0;
    return ;
}

//返回一个线性表list中的所有元素个数
int SeqList_Length(SeqList* plist)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Length)!\n ");
        return -1;
    }

    return ptlist->length;
}

//向一个线性表list的pos位置处插入新元素node节点
int SeqList_Insert(SeqList* plist, SeqListNode* pnode, int pos)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist || NULL == pnode )
    {
        printf("SeqList is empty(SeqList_Insert)!\n ");
        return -1;
    }

    if( pos<-1 || pos >= ptlist->capacity )
    {
        printf("pos is unvalid(SeqList_Insert)!\n");
        return -2;
    }       

    int i;
    for(i=ptlist->length; i>pos; i--)
        ptlist->pnode[i] = ptlist->pnode[i-1];

    ptlist->pnode[pos] = (unsigned int*)pnode;
    ptlist->length ++;

    return 0;
}

//获取一个线性表list的pos位置处的元素
SeqListNode* SeqList_Get(SeqList* plist, int pos)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Get)!\n ");
        return NULL;
    }

    if( pos<-1 || pos > ptlist->capacity )
    {
        printf("pos is unvalid(SeqList_Insert)!\n");
        return NULL;
    }       
    return ptlist->pnode[pos];
}

//删除一个线性表list的pos位的node节点元素,返回值为被删除的元素,NULL表示删除失败
SeqListNode* SeqList_Delete(SeqList* plist, int pos)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty!(SeqList_Delete)\n ");
        return NULL;
    }

    if( pos<-1 || pos > ptlist->capacity )
    {
        printf("pos is unvalid!(SeqList_Delete)\n");
        return NULL;
    }       

    SeqListNode *pnode = NULL;
    pnode = (SeqListNode*)ptlist->pnode[pos];

    int i;
    for(i=pos; i < ptlist->length; i++)
        ptlist->pnode[i] = ptlist->pnode[i+1];
    ptlist->length --;

    return pnode;
}

苹果的要求

到此,让我们思考一下,为何苹果默许须要watchOS和tvOS的App要上传bitcode?
因为把bitcode上传到他自己的焦点服务器后,他可以为对象安装App的装备开展优化二进制,减小安装包的下载大小,当然iOS开发者也可以上传三个版本而不是包裹到单个包里,但是这么会占据越来越多的囤积空间.
最主要的是允许苹果能够在后台服务器对应用程序进行签约,而不用导出任何密钥到巅峰开发者那.

上传到服务器的bitcode给苹果带来更便宜是:
未来新陈设了新指令集的新CPU,可以继续从那份bitcode起始编译出新CPU上进行的可执行文件,以供用户下载安装.
然则bitcode给开发者带来的劳苦之处就是:
没用bitcode从前,当应用程序奔溃后,开发者可以依照取得的的奔溃日志再配上上传到苹果服务器的二进制文件的调节符号表音讯可以回复程序运行进程到奔溃时后调用栈音信,对问题举办固化排查.然而用了bitcode之后,用户安装的二进制不是开发者那边转移的,而是苹果服务器经过优化后变卦的,其相应的调剂符号音信丢失了,也就不可以展开前边说的东山再起奔溃现场找原因了.

眼前,watchOS和tvOS应用宣布必须上传带bitcode版本的包.iOS应用宣布对bitcode的需求是可选的,用户可以在Xcode的类型设置中关闭.
相当于在编译的时候加一个标记:embed-bitcode-marker(调试构建)
embed-bitcode(打包/真机构建).那一个在clang编译器的参数是-fembed-bitcode,swift编译器的参数是-embed-bitcode.

效益测试代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "seqlist.h"

typedef struct student{
    char name[20];
    int age;
}student;

int main(int argc, char *argv[])
{
    student stu1,stu2,stu3,stu4,stu5;

    stu1.age = 20;
    stu2.age = 21;
    stu3.age = 22;
    stu4.age = 23;
    stu5.age = 24;

   TSeqList *pslist = (TSeqList*)SeqList_Create(5);

    SeqList_Insert(pslist, (SeqListNode*)&stu1, 0);
    SeqList_Insert(pslist, (SeqListNode*)&stu2, 1);
    SeqList_Insert(pslist, (SeqListNode*)&stu3, 2);
    SeqList_Insert(pslist, (SeqListNode*)&stu4, 3);
    SeqList_Insert(pslist, (SeqListNode*)&stu5, 4);
    printf("length: %d\n",SeqList_Length(pslist));
    SeqList_Traverse(pslist,student,age);

    SeqList_Delete(pslist,2);
    printf("length: %d\n",SeqList_Length(pslist));
    int i;
    student *ptmp = NULL;
    for(i=0; i < SeqList_Length(pslist); i++)
    {   
        ptmp = SeqList_Get(pslist,i);   
        printf("age: %d\n",ptmp->age);
    }
    SeqList_Clear(pslist);
    SeqList_Destroy(pslist);
    return 0;
}

实践出真知

我们依然应当实际弄八个测试代码举行实施和查验一下比较好.做一回测试,第四次准备四个C语言源代码继续测试;第二次把里面一个转移为汇编语言源代码后再一个C代码和一个汇编代码一起重复之前的测试步骤举办比较校验差距.

  • 1 . 如下四个总体是Objective-C代码:

test.m :

#import <Foundation/Foundation.h>
void greeting(void)
{
    NSLog(@"hello world!");
}

demo.m :

#import <Foundation/Foundation.h>
void demo(void)
{
    NSLog(@"demo func");
}

用Clang编译成 ARM64 格式且带bitcode的靶子文件test.o demo.o:

wuqiong:~ apple$ xcrun -sdk iphoneos clang -arch arm64 -fembed-bitcode -c test.m demo.m

下一场把七个目标文件打包为一个静态库文件:

wuqiong:~ apple$ xcrun -sdk iphoneos ar  -r libTest.a test.o demo.o
ar: creating archive libTest.a

用Shell命令otool查看目的文件中是还是不是包罗bitcode段:

wuqiong:~ apple$ otool -l test.o |grep bitcode
  sectname __bitcode
  sectname __bitcode

比方看到输出了2行sectname __bitcode,就是认证那静态库中的三个目标文件包括了bitcode.

  • 2.底下把里面一个demo.m换成汇编语言再参与编译:

用下边的吩咐把demo.m的C代码转换为ARM64汇编语言格式demo.s:

wuqiong:~ apple$ xcrun -sdk iphoneos clang -arch arm64 -S demo.m
wuqiong:~ apple$ cat demo.s
    .section    __TEXT,__text,regular,pure_instructions
    .ios_version_min 9, 2
    .globl  _demo
    .align  2
_demo:                                  ; @demo
    .cfi_startproc
; BB#0:
    stp x29, x30, [sp, #-16]!
    mov  x29, sp
Ltmp0:
    .cfi_def_cfa w29, 16
Ltmp1:
    .cfi_offset w30, -8
Ltmp2:
    .cfi_offset w29, -16
    adrp    x0, L__unnamed_cfstring_@PAGE
    add x0, x0, L__unnamed_cfstring_@PAGEOFF
    bl  _NSLog
    ldp x29, x30, [sp], #16
    ret
    .cfi_endproc

    .section    __TEXT,__cstring,cstring_literals
L_.str:                                 ; @.str
    .asciz  "demo func"

    .section    __DATA,__cfstring
    .align  4                       ; @_unnamed_cfstring_
L__unnamed_cfstring_:
    .quad   ___CFConstantStringClassReference
    .long   1992                    ; 0x7c8
    .space  4
    .quad   L_.str
    .quad   9                       ; 0x9

    .section    __DATA,__objc_imageinfo,regular,no_dead_strip
L_OBJC_IMAGE_INFO:
    .long   0
    .long   0


.subsections_via_symbol

然后删除demo.m这个C源代码,仅留下test.mdemo.s:

wuqiong:~ apple$ rm demo.m

如今,大家来把test.m其一C源代码和dmeo.s以此汇编源代码来一头带着-fembed-bitcode参数来生成靶子代码并打包为一个静态库:

wuqiong:~ apple$ xcrun -sdk iphoneos clang -arch arm64 -fembed-bitcode -c test.m demo.s
wuqiong:~ apple$ xcrun -sdk iphoneos ar -r libTest.a test.o demo.o

然后大家再运行otool工具来检查这些新的静态库中隐含的2个目的文件是不是都带有bitcode段:

wuqiong:~ apple$ ar -t libTest.a
__.SYMDEF SORTED
test.o
demo.o
wuqiong:~ apple$ otool -l libTest.a | grep bitcode
  sectname __bitcode

很意外,这一遍,只有一行sectname __bitcode输出,那就认证这七个目标文件,有一个不带有bitcode段,哪怕大家在编译的时候指定了参数-fembed-bitcode也没有用.至于具体是哪一个不带bitcode段,大家自然知道就是极度从ARM64汇编语言编译过来的靶子文件不带.

那就是说就得出一个定论,bitcode的变更,是由汇编语言以上的上层语言编译而来,和最前方所说的那么,他是上层语言与汇编语言(机器语言)之间的一个中级码.

眼前大家一般的iOS应用开发中,一般不会需求用到汇编层面去优化的代码.所以我们重点关怀第三方(开源)C代码,越发是音视频编码解码这几个计算密集型项目代码,关键总括的代码针对特定平台都有对应平台的汇编版本达成,当然也有C的落到实处,然则默许编译一般都是用的汇编版本,那样就会导致大家在编译这一个开源代码的时候就是你带了-fembed-bitcode参数也仅仅只是让项目中的部分C代码的对象文件带了bitcode段,而那小数的汇编代码的目的文件一律不带bitcode段,那样编译出这些库交给上层开发者使用的时候,就会并发在包装上传或者真机调试的时候因为Xcode默许开了bitcode功用而链接退步,导致无法真机调试或者不可能上传应用到AppStore.

总结

学数据结构大家要做的不仅是上学数据结构的算法实现,更关键的是能写出一种具有普适性的工具,站在一个更高的布署性策略的角度去设计代码,那一点对于学习数据结构来说很重大,没有这一点做支撑,学到的数据结构就只是一个空壳子,不能灵活的拔取。

此文之初衷

近期在指引自己戴维(戴维)营战友们做手机音视频直播的App,调试的时候手机采集音视频,摄像用h264编码,音频采纳aac编码,通过RTMP磋商往斗鱼直播频道发表媒体流,项目要求用FFMPEGlibx264五个开源项目,在编译为iOS框架库提须求学员用的时候,他们碰着了bitcode的题材,就算可以利用直接关闭bitcode来防止不当,不过战友的求知欲必须满意,格物致知,必须让其知其究竟.

libx264是VideoLan基金会保管的一个录像编解码的开源项目,其大气用到了一一平台的多媒体汇编指令举行了优化,在编译为不带bitcode的库的时候,完全按官方autotools编译方法是从未此外问题的;编译全带bitcode的库的时候我们只能关门汇编优化,在执行./configure等级可以增加--disable-asm参数来禁用汇编.可是,那些选项在configure本子中的完结机制有题目.导致其依然调用了汇编的函数,可是汇编的代码却绝非编译进去,从而会导致项目为真机构建和打包的链接阶段会揭示找不到符号的荒谬,那样就不可能不辱职分一矢双穿.出于轻微程度的性变态影响,故把前面的FFMPEGlibx264类型的编译脚本举行了更正和打补丁.近期早已可以做到一键编译出带全体bitcode的FFMPEG和libx264的框架了.

FFmpeg需求依靠libx264.

机动编译脚本项目地点位于github:
https://github.com/Diveinedu-CN/FFmpeg-iOS-build-script.git

出于时日和字数原因,关于其余越多详细的音信就不苗条道来了.

大卫(戴维)营教育Slogan: Dive in education!

越来越多iOS开发精品文章:大卫(David)营技术博客

Post Author: admin

发表评论

电子邮件地址不会被公开。 必填项已用*标注