目录

一、MySQL复制技术

1. 主从复制       

2. 组复制

二、组复制使用场景

三、组复制相关服务

1. 故障检测

2. 组成员服务

3. 容错

四、组复制技术细节

1. 组复制插件体系结构

2. 复制组

3. 数据操作语言（Data Manipulation Language，DML）

4. 数据定义语句（Data Definition Language，DDL ）

5. 分布式恢复

        MySQL Group Replication（MGR）是MySQL 5.7.17版本引入的一个服务器插件，可用于创建高可用、可扩展、容错的复制拓扑结构。组复制可以在单主模式下操作，其中只有一个服务器接受更新，这个单主是系统自动选举出来的。对于高级用户，也可以部署为多主模式，其中所有服务器都可以接受更新。内置的组成员服务可以在任何给定的时间点保持组的视图一致并可供所有服务器使用。当服务器加入或离开组时，视图也会相应更新。当服务器宕机，故障检测机制会检测到此情况并通知组其视图已更改。这些都是自动进行的。

        创建容错系统最常见的方法是组件冗余。换句话说，一个组件被移除时，系统应该继续按预期运行。这产生了一系列挑战，将这种系统的复杂性提高到了一个完全不同的水平。数据复制必须维护和管理多个服务器，还必须处理若干其它经典的分布式系统问题，如网络分区或脑裂。对MySQL而言，最终的挑战是将数据复制逻辑与协调多个服务器的逻辑相融合。这可以概括为让每个服务器的状态在数据变化时达成一致，即便它们都作为单个数据库系统运行，但最终都收敛到相同的状态。

        MGR对属于同一组的服务器自动进行协调。对于要提交的事务，组成员必须就全局事务序列中给定事务的顺序达成一致。提交或回滚事务由每个服务器单独完成，但所有服务器都必须做出相同的决定。如果存在网络分区，导致成员无法达成事先定义的分割策略，则在解决此问题之前系统不会继续进行，这是一种内置的自动裂脑保护机制。MGR由组通信系统（Group Communication System，GCS）协议支持。该系统提供故障检测机制、组成员服务以及安全且有序的消息传递。所有这些属性都是创建系统的关键，可确保在服务器组中一致地复制数据。该技术的核心是Paxos算法的实现，它充当组通信引擎。

一、MySQL复制技术

        在深入了解MySQL组复制的细节之前，先介绍一些其产生的背景以及工作原理，以帮助理解组复制，以及传统异步复制、半同步复制和组复制之间的区别。

1. 主从复制

       

        传统的MySQL复制提供了一种简单的主从复制方法。有一个主库，一个或多个从库。主库执行并提交事务，然后通过二进制日志将事务相关的事件异步发送到从库，以便重放。这是一个无共享系统，默认情况下所有服务器都拥有完整的数据副本。




        半同步复制为异步复制协议添加了一个同步步骤。这意味着主库在提交时等待至少一个从库确认它已收到该事务，才会继续提交操作。




        图1图2分别表示MySQL异步复制协议以及它的半同步变体。对角箭头表示服务器之间交换的消息或服务器与客户端应用程序之间交换的消息。

2. 组复制

        组由多个服务器构成，通过传递消息进行交互，通信层保证原子消息传递。MGR构建于此通信层抽象之上，并实现了多主更新复制协议。组中的每个服务器独立地执行事务，但是所有读写事务只有在得到组的批准后才会提交。只读事务在组内不需要协调，因此立即提交。对于任何读写事务，当事务准备好在始发服务器处提交时，服务器以原子方式广播写入值（更改的行）和对应的写入集（更新的行的唯一标识符），然后将该事务加入全局事务列表。最终所有服务器都以相同的顺序接收并应用相同的事务集，所以它们在组内保持一致。

        不同服务器上并发执行的事务之间可能存在冲突。MGR在certify过程中检查并发事务的写集来检测这种冲突。如果在不同服务器上执行的两个并发事务更新同一行，则存在冲突。解决方案是先到事务提交，后到事务回滚，即按顺序第一个事务在所有服务器提交，而第二个事务在在原始服务器上回滚并在组中的其它服务器中删除。这实际上体现的是多主分布式事务的首个提交获胜原则。




        图3描述了MGR协议。组复制同样是一种无共享复制方案，其中每个服务器都有自己的整个数据副本。

二、组复制使用场景

        组复制可用来创建具有冗余的容错系统。即使某些服务器发生故障，只要它不是全部或大多数，系统仍然可用。根据失败的服务器数量，可能会降低性能或可伸缩性，但它仍然可用。组成员服务跟踪服务器故障，该服务依赖于分布式故障检测器，能够在任何服务器脱离组时发出信号，无论是意外停止还是主动停止。分布式恢复过程确保当服务器加入组时能自动更新。单个服务器发生故障时不会停止服务，也无需服务器故障转移。总之，MGR保证数据库服务持续可用。

        需要注意，尽管数据库服务可用，但在服务器崩溃的情况下，必须将连接到它的客户端重定向或转移到其它服务器。组复制不解决数据库连接重定向的问题，连接器、负载平衡器、路由器或某种形式的中间件更适合处理此问题，例如MySQL Router。

        以下是组复制的典型使用场景。

弹性复制：服务器的数量能够动态增加或减少，并且尽可能减小副作用，例如云数据库服务。
	
高可用分片：分片是实现写扩展的流行方法。使用MGR实现高可用分片，其中每个分片映射到复制组。
	
主从复制的替代方案：在某些情况下，使用单个主服务器会使其成为热点，写入整个组会更具可扩展性。
三、组复制相关服务

1. 故障检测

        组复制包括一种故障检测机制，该机制能够查找并报告哪些服务器已经宕机。当服务器A在给定时间内没有从服务器B接收到消息时，发生超时并引发怀疑。然后如果组同意怀疑是真的，那么该组决定给定服务器确实宕机了。这意味着该组中的其余成员将采取协调决策以排除给定成员。

        如果一个服务器与组的其余部分隔离，它会怀疑所有其它服务器都已失败，但由于无法与该组达成协议（因为无法确保法定票数），其怀疑并没有结果。当服务器以这种方式与组隔离时，它无法执行任何本地事务。

2. 组成员服务

        MGR依赖于组成员服务，该服务内置于插件中。它定义了哪些服务器在线并参与该组。在线服务器列表通常称为视图。因此，组中的每个服务器都具有一致的视图，其中是在给定时刻主动参与该组的成员。

        服务器不仅必须同意事务提交，还​​要同意当前视图。因此，如果服务器同意新服务器成为组的一部分，则组本身将重新配置为将该服务器集成在其中，从而触发视图更改。相反的情况也会发生，如果服务器离开组，则组会动态更新配置并触发视图更改。

        组成员离开组分主动与被动。主动离开会启动组的动态重新配置，这会触发所有其它成员必须在没有该服务器的情况下就新视图达成一致。被动离开（如已意外停止或断网）时，故障检测机制会建议重新配置组，这需要组中大多数服务器的同意。如果该组无法达成协议，为阻止脑裂，系统无法动态更改配置，这意味着管理员需要介入解决此问题。

3. 容错

        MGR构建于Paxos分布式算法的实现之上，需要多数服务器处于活动状态才能达到法定票数，从而做出决定。这直接影响系统可以容忍的故障机数量，但不会影响组复制自身及其整体功能。容忍 f 个故障机所需的服务器数量 n 为：n = 2 * f + 1。

        实践中为了容忍一个故障机，该组必须具有三个服务器，因为此时如果一个服务器发生故障，仍然有两个服务器构成多数，并允许系统继续自动做出决策并继续提供服务。但如果第二个服务器继续失败，那么该组（剩下一个服务器）会阻塞，因为没有多数票可以做出决定。

四、组复制技术细节

1. 组复制插件体系结构

        MGR是一个MySQL插件，它以现有的MySQL复制架构为基础，利用二进制日志、基于行的日志记录和全局事务标识符（GTID）等功能。图4显示了MGR插件架构。




        MGR插件包含一组捕获、应用和生命周期API，用于控制插件与MySQL服务器的交互方式。这些接口将MySQL服务器核心与MGR插件隔离。服务器向插件通知启动、恢复、准备接收连接、即将提交事务等消息。插件指示服务器执行诸如提交事务、中止正在进行的事务、事务在中继日志中排队等动作。

        组复制插件体系结构的下一层是一组组件。捕获组件负责跟踪与正在执行的事务相关的上下文。应用组件负责在数据库上执行远程事务。恢复组件管理分布式恢复，负责选择捐赠者，对故障做出反应，执行追赶程序，使加入该组的服务器获得更新。

        堆栈下一层的复制协议模块包含复制协议的特定逻辑。它处理冲突检测，接收事务并将其传播到组。

        组复制插件体系结构的最后两层是组通信系统（GCS）API，以及基于Paxos的组通信引擎（XCom）的实现。GCS API将消息传递层的实现与插件上层分离，组通信引擎处理与复制组成员的通信。

2. 复制组

        MGR中的一组服务器构成一个复制组，组名形式为UUID。组是动态的，服务器可以离开（主动或被动）并随时加入组。服务器加入或离开时，组会自行调整。如果服务器加入组，组会通过从现有服务器获取状态自动更新新加入的服务器。状态通过MySQL异步复制进行传输。如果服务器离开该组，其余服务器会知道它已离开并自动重新配置该组。

3. 数据操作语言（Data Manipulation Language，DML）

        组中的每个服务器都被允许随时执行读写事务。任何服务器都可以在没有任何事先协调的情况下执行事务。但在提交时，它与组中的其余服务器协调，以便就该事务的操作做出决定。这种协调有两个目的：一是检查事务是否可以提交；二是传播更新，以便其它服务器也可以应用该事务。

        当事务通过原子广播发送时，组中的所有服务器都接收该事务，或者都不接收该事务。它们会以与之前发送的其它事务相同的顺序收到它，并通过检查和比较写入事务集来执行冲突检测。冲突解决遵循首个提交者获胜规则。例如，事务t1和t2在不同的站点同时执行，t2排在t1之前，并且两者都改变​​了同一行，那么t2赢得冲突被执行，t1被中止。如果两个事务经常发生冲突，最好在同一台服务器上启动它们，这样它们有机会在本地锁管理机制下并行执行，而不是稍后在复制协议中中止。

4. 数据定义语句（Data Definition Language，DDL ）

        在组复制拓扑中，执行数据定义语句时需要小心。MySQL 8.0 引入了对原子数据定义语言的支持，其中完整的DDL语句作为单个原子事务提交或回滚。但是，原子或其它DDL语句隐式结束当前会话中处于活动状态的任何事务，就好像在执行语句之前已完成COMMIT一样。这意味着DDL语句自成事务，不能在另一个事务中，或在START TRANSACTION ... COMMIT等事务控制语句中，或者与同一事务中的其它语句结合使用。

        组复制基于乐观复制，其中语句被乐观执行（执行时不事先锁定对象）并在稍后必要时回滚。每个服务器首先执行和提交而不保护组协议。因此，在多主模式下复制DDL语句时需要更加小心。如果对同一对象进行结构更改（使用DDL）并更改对象包含的数据（使用DML），则需要通过同一服务器处理更改。如果不这样做，可能会因操作中断或部分完成，导致数据不一致。如果组以单主模式部署，则不会发生此问题，因为所有更改都是通过同一服务器（主服务器）执行的。

5. 分布式恢复

（1）分布式恢复基础

        组复制分布式恢复可以概括为服务器从组中获得丢失事务的过程，以便它可以加入具有已处理相同事务集成员的组。在分布式恢复期间，加入组的服务器会缓冲其正在接收的，组中所需的事务和成员事件。一旦加入该组的服务器收到了该组的所有事务，它就会应用在恢复过程中缓冲的事务。此过程结束时，服务器随之作为在线成员加入组。

        分布式恢复分为两个阶段。第一阶段，加入该组的服务器选择该组上的一个在线服务器作为其缺失状态的捐赠者。捐赠者负责为新服务器提供加入该组的所有数据，直到它加入该组为止。这是通过在捐赠者和加入该组的服务器之间建立的标准异步复制通道来实现的。复制通道是MySQL 5.7 中提出的概念。简单讲一个复制通道表示从主库到从库的一条复制路径，在多源复制中主到从可以存在多条复制通道。通过此复制通道复制捐赠者的二进制日志，直到加入该组的服务器成为该组的一部分，并发生视图更改时。加入该组的服务器在收到捐赠者的二进制日志时应用它们。

        复制二进制日志时，加入该组的服务器还会缓存在组内交换的每个事务。也就是说，它监听在加入该组之后发生的事务，同时应用来自捐赠者的数据。当第一阶段结束并且关闭捐赠者的复制通道时，加入该组的服务器开始第二阶段：追赶。在此阶段，加入组的服务器继续执行高速缓存的事务。排队等待执行的事务数最终达到零时，该成员将在线声明。

        当加入组的服务器从捐赠者获取二进制日志时，恢复过程可以承受捐赠者故障。在这种情况下，捐赠者在第一阶段期间失败时，加入该组的服务器将故障转移到新的捐赠者并从新捐赠者恢复。加入该组的服务器将关闭与失败的捐赠者的连接，并打开与新捐赠者的连接，这些都是自动进行的。

（2）基于时间点的恢复

        为了使加入组的服务器与捐赠者同步到特定时间点，加入组和捐赠者的服务器利用MySQL全局事务标识符（GTID）机制。但GTID仅提供了一种方法来发现加入该组的服务器缺少哪些事务，不会传达认证信息。这是二进制日志视图标记的工作，它标记二进制日志流中的视图更改，还包含其它元数据信息，如认证相关数据。

        视图对应于主动参与当前配置的一组成员，在特定时间点，这些组成员在系统中是正确的和在线的。视图更改发生在组配置修改（例如成员加入或离开）时。任何组成员身份更改都会导致在同一逻辑时间点向所有成员传达视图更改。视图标识符唯一标识视图。只要视图发生更改，就会生成一个视图标识符。

        在通信层，视图更改及其关联的视图ID是成员加入之前和之后数据变化的边界。此概念通过新的二进制日志事件实现：“视图更改日志事件”。因此视图ID也成为在组成员资格发生变化之前和之后传输的事务的标记。视图标识符本身由两部分构成：随机部分和单调递增整数部分。第一部分在创建组时生成，并且在组中至少有一个成员时保持不变。每次视图更改发生时，第二部分都会递增。随机部分识别组的开始，增量部分标识组的改变。

（3）视图更改

        视图更改时，执行以下步骤将标识符合并到二进制日志事件：

        1. 开始：稳定组

        如图5所示，所有服务器都在线并处理来自组的传入事务。一些服务器复制的事务可能稍微落后，但最终它们会相同。此时该组充当一个分布式数据库副本。




 

        2. 视图更改：加入一个组成员

        每当新成员加入组并因此执行视图更改时，每个联机服务器都会把视图更改日志事件排入队列以备执行。在视图更改之前，服务器上可能有一些属于旧视图的事务排队进行应用，将视图更改事件排在它们之后可确保正确标记何时发生了视图更改。

        同时，加入该组的服务器通过视图的在线服务器列表中选择捐赠者。如图6所示，成员加入时生成视图4，在线成员将此视图更改事件写入二进制日志。




 

        3. 状态转移：追赶

        一旦加入该组的服务器选择该组中的某服务器作为捐赠者，则在两者之间建立新的异步复制连接并且开始状态转移（第一阶段）。这种与捐赠者的交互一直持续到服务器加入组的应用程序线程，该线程处理服务器进入组时所触发的视图更改日志事件。加入该组的服务器从捐赠者复制，直到它到达与视图改变相匹配的视图标识符，如图7所示。




 

        加入该组的服务器知道它应该在哪个视图标识符停止复制。由于视图标识符在相同的逻辑时间被发送到组中的所有成员，避免了复杂的GTID集合计算，因为视图ID清楚地标记了属于每个组视图的数据。

        加入该组的服务器正在从捐赠者复制时，它也会缓存来自该组的传入事务。最后它停止从捐赠者复制并切换到应用缓存的那些事务，如图8所示。




 

        4. 完成：赶上

        当加入组的服务器识别出具有预期视图标识符的视图更改日志事件时，终止与捐赠者的连接并开始应用缓存的事务。视图更改日志事件除了在二进制日志中充当分隔标记，还扮演另一个角色。当新服务器进入组时，它传达所有服务器感知的认证信息，即最后的视图改变。如果没有视图更改事件，加入该组的服务器将没有必要的信息对后续事务进行冲突检测。

        追赶的持续时间（第二阶段）是不确定的，它取决于负载和进入组的事务的多少。此过程完全联机，加入组的服务器在追赶时不会阻止组中的任何其它服务器。当进行到第二阶段时，加入该组的服务器的事务可能落后，落后的多少取决于负载。

        当加入组的服务器达到零排队事务并且其存储的数据等于其它成员时，其公共状态将更改为联机，如图9所示。




 

（4）分布式恢复的使用建议和限制

        分布式恢复基于传统的异步复制，如果加入组的服务器没有数据或者只有非常旧的备份数据，恢复过程可能很慢。这意味着要在第一阶段传输大量数据，新增服务器可能需要很长时间才能恢复。因此建议在将服务器添加到组之前，应该为其配置已经在组中的服务器的相当近的快照。这最小化了第一阶段的所需时间并减少了对捐赠服务器的影响，因为它只需保传输较少的二进制日志。

刷题目再次遇到了声明这种最基本形式的考题，以此记录，共勉。

关于多维数组声明的形式你知道哪几种呢？
首先先上一个错误的例子：


这里arr9 - arr11在等式右边都错误的在中括号中加了数组大小，导致报错；

而arr11、arr12则是等式右边二维数组初始化时没有赋予初始大小导致报错。
正确的声明形式如下：



本质上arr0、arr4和arr3、arr8是一样的；
而arr1-2和arr5-6则是以一种俏皮的方式进行了声明，虽然也是可以通过编译运行的，但是我的IDE上的阿里代码规约还是建议使用arr0、arr4 或者 arr3、arr8这种形式。



大家只要知道可以这样子声明即可，实际工作中为了方便他人查看代码，还是遵守一些规约吧！

这里献上代码以供大家到IDE中测试：
    int[][] arr0 = new int[2][2];
    int arr1[][] = new int[2][2];
    int []arr2[] = new int[2][2];
    int [][]arr3 = new int[2][2];

    int[][][] arr4 = new int[2][2][2];
    int arr5[][][] = new int[2][2][2];
    int []arr6[][] = new int[2][2][2];
    int [][]arr7[] = new int[2][2][2];
    int [][][]arr8 = new int[2][2][2];


最近在找实习，压力有点大，写点博客减减压。

CSDN
  
GitHub
C语言0长度数组(可变数组/柔性数组)详解
  
AderXCoding/language/c/zero_length_array

 

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可, 转载请注明出处, 谢谢合作 



1  零长度数组概念

众所周知, GNU/GCC 在标准的 C/C++ 基础上做了有实用性的扩展, 零长度数组（Arrays of Length Zero） 就是其中一个知名的扩展.

多数情况下,  其应用在变长数组中, 其定义如下



struct Packet
{
    int state;
    int len;
    char cData[0]; //这里的0长结构体就为变长结构体提供了非常好的支持
};

首先对 0长度数组, 也叫柔性数组 做一个解释 ：

用途 : 长度为0的数组的主要用途是为了满足需要变长度的结构体
用法 : 在一个结构体的最后, 申明一个长度为0的数组, 就可以使得这个结构体是可变长的. 对于编译器来说, 此时长度为0的数组并不占用空间, 因为数组名本身不占空间, 它只是一个偏移量,  数组名这个符号本身代表了一个不可修改的地址常量 

  
(注意 : 数组名永远都不会是指针!), 但对于这个数组的大小, 我们可以进行动态分配
  
  
注意 ：如果结构体是通过calloc、malloc或 者new等动态分配方式生成，在不需要时要释放相应的空间。
  
  
优点 ：比起在结构体中声明一个指针变量、再进行动态分 配的办法，这种方法效率要高。因为在访问数组内容时，不需要间接访问，避免了两次访存。
  
  
缺点 ：在结构体中，数组为0的数组必须在最后声明，使 用上有一定限制。


对于编译器而言, 数组名仅仅是一个符号, 它不会占用任何空间, 它在结构体中, 只是代表了一个偏移量, 代表一个不可修改的地址常量!



2  0长度数组的用途

我们设想这样一个场景, 我们在网络通信过程中使用的数据缓冲区, 缓冲区包括一个len字段和data字段, 分别标识数据的长度和传输的数据, 我们常见的有几种设计思路

定长数据缓冲区, 设置一个足够大小 MAX_LENGTH 的数据缓冲区
设置一个指向实际数据的指针, 每次使用时, 按照数据的长度动态的开辟数据缓冲区的空间.
我们从实际场景中应用的设计来考虑他们的优劣. 主要考虑的有, 缓冲区空间的开辟, 释放和访问.



2.1  定长包(开辟空间, 释放, 访问)

比如我要发送 1024 字节的数据, 如果用定长包, 假设定长包的长度 MAX_LENGTH 为 2048, 就会浪费 1024 个字节的空间, 也会造成不必要的流量浪费.

数据结构定义
//  定长缓冲区
struct max_buffer
{
    int     len;
    char    data[MAX_LENGTH];
};

数据结构大小
考虑对齐, 那么数据结构的大小 >= sizeof(int) + sizeof(char) * MAX_LENGTH

由于考虑到数据的溢出, 变长数据包中的 data  数组长度一般会设置得足够长足以容纳最大的数据, 因此 max_buffer 中的 data 数组很多情况下都没有填满数据, 因此造成了浪费

数据包的构造
假如我们要发送 CURR_LENGTH = 1024 个字节, 我们如何构造这个数据包呢:

一般来说, 我们会返回一个指向缓冲区数据结构 max_buffer 的指针.



    ///  开辟
    if ((mbuffer = (struct max_buffer *)malloc(sizeof(struct max_buffer))) != NULL)
    {
        mbuffer->len = CURR_LENGTH;
        memcpy(mbuffer->data, "Hello World", CURR_LENGTH);


        printf("%d, %s\n", mbuffer->len, mbuffer->data);
    }

访问
这段内存要分两部分使用

前部分 4 个字节 p->len, 作为包头(就是多出来的那部分)，这个包头是用来描述紧接着包头后面的数据部分的长度，这里是 1024, 所以前四个字节赋值为 1024 (既然我们要构造不定长数据包，那么这个包到底有多长呢，因此，我们就必须通过一个变量来表明这个数据包的长度，这就是len的作用)，

而紧接其后的内存是真正的数据部分, 通过 p->data, 最后, 进行一个 memcpy() 内存拷贝, 把要发送的数据填入到这段内存当中

释放
那么当使用完毕释放数据的空间的时候, 直接释放就可以了



    /// 销毁
    free(mbuffer);
    mbuffer = NULL;

小结

使用定长数组, 作为数据缓冲区, 为了避免造成缓冲区溢出, 数组的大小一般设为足够的空间 MAX_LENGTH, 而实际使用过程中, 达到 MAX_LENGTH 长度的数据很少, 那么多数情况下, 缓冲区的大部分空间都是浪费掉的.
但是使用过程很简单, 数据空间的开辟和释放简单, 无需程序员考虑额外的操作
2.2  指针数据包(开辟空间, 释放, 访问)

如果你将上面的长度为 MAX_LENGTH 的定长数组换为指针, 每次使用时动态的开辟 CURR_LENGTH 大小的空间, 那么就避免造成 MAX_LENGTH - CURR_LENGTH  空间的浪费, 只浪费了一个指针域的空间.

数据包定义
struct point_buffer
{
    int     len;
    char    *data;
};

数据结构大小
考虑对齐, 那么数据结构的大小 >= sizeof(int) + sizeof(char *)

空间分配
但是也造成了使用在分配内存时，需采用两步



    // =====================
    // 指针数组  占用-开辟-销毁
    // =====================
    ///  占用
    printf("the length of struct test3:%d\n",sizeof(struct point_buffer));
    ///  开辟
    if ((pbuffer = (struct point_buffer *)malloc(sizeof(struct point_buffer))) != NULL)
    {
        pbuffer->len = CURR_LENGTH;
        if ((pbuffer->data = (char *)malloc(sizeof(char) * CURR_LENGTH)) != NULL)
        {
            memcpy(pbuffer->data, "Hello World", CURR_LENGTH);


            printf("%d, %s\n", pbuffer->len, pbuffer->data);
        }
    }

首先, 需为结构体分配一块内存空间;
其次再为结构体中的成员变量分配内存空间.
这样两次分配的内存是不连续的, 需要分别对其进行管理. 当使用长度为的数组时, 则是采用一次分配的原则, 一次性将所需的内存全部分配给它.

释放
相反, 释放时也是一样的.



    /// 销毁
    free(pbuffer->data);
    free(pbuffer);
    pbuffer = NULL;

小结

使用指针结果作为缓冲区, 只多使用了一个指针大小的空间, 无需使用 MAX_LENGTH 长度的数组, 不会造成空间的大量浪费.
但那是开辟空间时, 需要额外开辟数据域的空间, 施放时候也需要显示释放数据域的空间, 但是实际使用过程中, 往往在函数中开辟空间, 然后返回给使用者指向 struct point_buffer 的指针, 这时候我们并不能假定使用者了解我们开辟的细节, 并按照约定的操作释放空间, 因此使用起来多有不便, 甚至造成内存泄漏
2.3  变长数据缓冲区(开辟空间, 释放, 访问)

定长数组使用方便, 但是却浪费空间, 指针形式只多使用了一个指针的空间, 不会造成大量空间分浪费, 但是使用起来需要多次分配, 多次释放, 那么有没有一种实现方式能够既不浪费空间, 又使用方便的呢?

GNU C 的0长度数组, 也叫变长数组, 柔性数组就是这样一个扩展. 对于0长数组的这个特点，很容易构造出变成结构体，如缓冲区，数据包等等：

数据结构定义
//  0长度数组
struct zero_buffer
{
    int     len;
    char    data[0];
};

数据结构大小
这样的变长数组常用于网络通信中构造不定长数据包, 不会浪费空间浪费网络流量, 因为char    data[0]; 只是个数组名, 是不占用存储空间的,

即 sizeof(struct zero_buffer) = sizeof(int)

开辟空间
那么我们使用的时候, 只需要开辟一次空间即可



    ///  开辟
    if ((zbuffer = (struct zero_buffer *)malloc(sizeof(struct zero_buffer) + sizeof(char) * CURR_LENGTH)) != NULL)
    {
        zbuffer->len = CURR_LENGTH;
        memcpy(zbuffer->data, "Hello World", CURR_LENGTH);


        printf("%d, %s\n", zbuffer->len, zbuffer->data);
    }

释放空间
释放空间也是一样的, 一次释放即可



    ///  销毁
    free(zbuffer);
    zbuffer = NULL;



2.4 总结



// zero_length_array.c
#include <stdio.h>
#include <stdlib.h>


#define MAX_LENGTH      1024
#define CURR_LENGTH      512

//  0长度数组
struct zero_buffer
{
    int     len;
    char    data[0];
}__attribute((packed));


//  定长数组
struct max_buffer
{
    int     len;
    char    data[MAX_LENGTH];
}__attribute((packed));


//  指针数组
struct point_buffer
{
    int     len;
    char    *data;
}__attribute((packed));

int main(void)
{
    struct zero_buffer  *zbuffer = NULL;
    struct max_buffer   *mbuffer = NULL;
    struct point_buffer *pbuffer = NULL;


    // =====================
    // 0长度数组  占用-开辟-销毁
    // =====================
    ///  占用
    printf("the length of struct test1:%d\n",sizeof(struct zero_buffer));
    ///  开辟
    if ((zbuffer = (struct zero_buffer *)malloc(sizeof(struct zero_buffer) + sizeof(char) * CURR_LENGTH)) != NULL)
    {
        zbuffer->len = CURR_LENGTH;
        memcpy(zbuffer->data, "Hello World", CURR_LENGTH);


        printf("%d, %s\n", zbuffer->len, zbuffer->data);
    }
    ///  销毁
    free(zbuffer);
    zbuffer = NULL;


    // =====================
    // 定长数组  占用-开辟-销毁
    // =====================
    ///  占用
    printf("the length of struct test2:%d\n",sizeof(struct max_buffer));
    ///  开辟
    if ((mbuffer = (struct max_buffer *)malloc(sizeof(struct max_buffer))) != NULL)
    {
        mbuffer->len = CURR_LENGTH;
        memcpy(mbuffer->data, "Hello World", CURR_LENGTH);


        printf("%d, %s\n", mbuffer->len, mbuffer->data);
    }
    /// 销毁
    free(mbuffer);
    mbuffer = NULL;

    // =====================
    // 指针数组  占用-开辟-销毁
    // =====================
    ///  占用
    printf("the length of struct test3:%d\n",sizeof(struct point_buffer));
    ///  开辟
    if ((pbuffer = (struct point_buffer *)malloc(sizeof(struct point_buffer))) != NULL)
    {
        pbuffer->len = CURR_LENGTH;
        if ((pbuffer->data = (char *)malloc(sizeof(char) * CURR_LENGTH)) != NULL)
        {
            memcpy(pbuffer->data, "Hello World", CURR_LENGTH);


            printf("%d, %s\n", pbuffer->len, pbuffer->data);
        }
    }
    /// 销毁
    free(pbuffer->data);
    free(pbuffer);
    pbuffer = NULL;


    return EXIT_SUCCESS;
}



长度为0的数组并不占有内存空间, 而指针方式需要占用内存空间.
对于长度为0数组, 在申请内存空间时, 采用一次性分配的原则进行; 对于包含指针的结构体, 才申请空间时需分别进行, 释放时也需分别释放.
对于长度为的数组的访问可采用数组方式进行
3  GNU Document中 变长数组的支持


  
参见
  
  
6.17 Arrays of Length Zero
  
  
C Struct Hack – Structure with variable length array


在 C90 之前, 并不支持0长度的数组, 0长度数组是 GNU C 的一个扩展, 因此早期的编译器中是无法通过编译的

对于 GNU C 增加的扩展, GCC 提供了编译选项来明确的标识出他们

1、-pedantic 选项，那么使用了扩展语法的地方将产生相应的警告信息

2、-Wall 使用它能够使GCC产生尽可能多的警告信息

3、-Werror, 它要求GCC将所有的警告当成错误进行处理



// 1.c
#include <stdio.h>
#include <stdlib.h>


int main(void)
{
    char a[0];
    printf("%ld", sizeof(a));
    return EXIT_SUCCESS;
}

我们来编译



gcc 1.c -Wall   # 显示所有警告
#none warning and error

gcc 1.c -Wall -pedantic  # 对GNU C的扩展显示警告
1.c: In function ‘main’:
1.c:7: warning: ISO C forbids zero-size array ‘a’


gcc 1.c -Werror -Wall -pedantic # 显示所有警告同时GNU C的扩展显示警告, 将警告用error显示
cc1: warnings being treated as errors
1.c: In function ‘main’:
1.c:7: error: ISO C forbids zero-size array ‘a’



0长度数组其实就是灵活的运用的数组指向的是其后面的连续的内存空间



struct buffer
{
    int     len;
    char    data[0];
};

在早期没引入0长度数组的时候, 大家是通过定长数组和指针的方式来解决的, 但是

定长数组定义了一个足够大的缓冲区, 这样使用方便, 但是每次都造成空间的浪费
指针的方式, 要求程序员在释放空间是必须进行多次的free操作, 而我们在使用的过程中往往在函数中返回了指向缓冲区的指针, 我们并不能保证每个人都理解并遵从我们的释放方式
所以 GNU 就对其进行了0长度数组的扩展. 当使用data[0]的时候, 也就是0长度数组的时候，0长度数组作为数组名, 并不占用存储空间.

在C99之后，也加了类似的扩展，只不过用的是 char payload[]这种形式（所以如果你在编译的时候确实需要用到-pedantic参数，那么你可以将char payload[0]类型改成char payload[], 这样就可以编译通过了，当然你的编译器必须支持C99标准的，如果太古老的编译器，那可能不支持了)



// 2.c payload
#include <stdio.h>
#include <stdlib.h>

struct payload
{
    int   len;
    char  data[];
};

int main(void)
{
    struct payload pay;
    printf("%ld", sizeof(pay));
    return EXIT_SUCCESS;
}

使用 -pedantic 编译后, 不出现警告, 说明这种语法是 C 标准的



gcc 2.c -pedantic -std=c99



所以结构体的末尾, 就是指向了其后面的内存数据。因此我们可以很好的将该类型的结构体作为数据报文的头格式，并且最后一个成员变量，也就刚好是数据内容了.

GNU手册还提供了另外两个结构体来说明，更容易看懂意思：



struct f1 {
    int x;
    int y[];
} f1 = { 1, { 2, 3, 4 } };

struct f2 {
    struct f1 f1;
    int data[3];
} f2 = { { 1 }, { 5, 6, 7 } };

我把f2里面的2,3,4改成了5,6,7以示区分。如果你把数据打出来。即如下的信息：



f1.x = 1
f1.y[0] = 2
f1.y[1] = 3
f1.y[2] = 4

也就是f1.y指向的是{2,3,4}这块内存中的数据。所以我们就可以轻易的得到，f2.f1.y指向的数据也就是正好f2.data的内容了。打印出来的数据：



f2.f1.x = 1
f2.f1.y[0] = 5
f2.f1.y[1] = 6
f2.f1.y[2] = 7

如果你不是很确认其是否占用空间. 你可以用sizeof来计算一下。就可以知道sizeof(struct f1)=4,也就是int y[]其实是不占用空间的。但是这个0长度的数组，必须放在结构体的末尾。如果你没有把它放在末尾的话。编译的时候，会有如下的错误：



main.c:37:9: error: flexible array member not at end of struct
     int y[];
         ^

到这边，你可能会有疑问，如果将struct f1中的int y[]替换成int *y，又会是如何？这就涉及到数组和指针的问题了. 有时候吧，这两个是一样的，有时候又有区别。

首先要说明的是，支持0长度数组的扩展，重点在数组，也就是不能用int *y指针来替换。sizeof的长度就不一样了。把struct f1改成这样：



struct f3 {
    int x;
    int *y;
};

在32/64位下, int均是4个字节, sizeof(struct f1)=4，而sizeof(struct f3)=16

因为 int *y 是指针, 指针在64位下, 是64位的， sizeof(struct f3) = 16, 如果在32位环境的话, sizeof(struct f3) 则是 8 了, sizeof(struct f1) 不变. 所以 int *y 是不能替代 int y[] 的.

代码如下



// 3.c
#include <stdio.h>
#include <stdlib.h>


struct f1 {
    int x;
    int y[];
} f1 = { 1, { 2, 3, 4 } };

struct f2 {
    struct f1 f1;
    int data[3];
} f2 = { { 1 }, { 5, 6, 7 } };


struct f3
{
    int x;
    int *y;
};

int main(void)
{
    printf("sizeof(f1) = %d\n", sizeof(struct f1));
    printf("sizeof(f2) = %d\n", sizeof(struct f2));
    printf("szieof(f3) = %d\n\n", sizeof(struct f3));

    printf("f1.x = %d\n", f1.x);
    printf("f1.y[0] = %d\n", f1.y[0]);
    printf("f1.y[1] = %d\n", f1.y[1]);
    printf("f1.y[2] = %d\n", f1.y[2]);


    printf("f2.f1.x = %d\n", f1.x);
    printf("f2.f1.y[0] = %d\n", f2.f1.y[0]);
    printf("f2.f1.y[1] = %d\n", f2.f1.y[1]);
    printf("f2.f1.y[2] = %d\n", f2.f1.y[2]);

    return EXIT_SUCCESS;
}





4  0长度数组的其他特征

4.1   为什么0长度数组不占用存储空间


  
参见
  
  
结构体中的指针与零长度数组
  
  
GNU C中的零长度数组


0长度数组与指针实现有什么区别呢, 为什么0长度数组不占用存储空间呢?

其实本质上涉及到的是一个C语言里面的数组和指针的区别问题. char a[1]里面的a和char *b的b相同吗？

《 Programming Abstractions in C》（Roberts, E. S.，机械工业出版社，2004.6）82页里面说


  
“arr is defined to be identical to &arr[0]”.


也就是说，char a[1]里面的a实际是一个常量，等于&a[0]。而char *b是有一个实实在在的指针变量b存在。 所以，a=b是不允许的，而b=a是允许的。 两种变量都支持下标式的访问，那么对于a[0]和b[0]本质上是否有区别？我们可以通过一个例子来说明。

参见如下两个程序 gdb_zero_length_array.c 和 gdb_zero_length_array.c



//  gdb_zero_length_array.c
#include <stdio.h>
#include <stdlib.h>

struct str
{
    int len;
    char s[0];
};

struct foo
{
    struct str *a;
};

int main(void)
{
    struct foo f = { NULL };

    printf("sizeof(struct str) = %d\n", sizeof(struct str));

    printf("before f.a->s.\n");
    if(f.a->s)
    {
        printf("before printf f.a->s.\n");
        printf(f.a->s);
        printf("before printf f.a->s.\n");
    }

    return EXIT_SUCCESS;
}





//  gdb_pzero_length_array.c
#include <stdio.h>
#include <stdlib.h>

struct str
{
    int len;
    char *s;
};

struct foo
{
    struct str *a;
};

int main(void)
{
    struct foo f = { NULL };

    printf("sizeof(struct str) = %d\n", sizeof(struct str));

    printf("before f.a->s.\n");

    if (f.a->s)
    {
        printf("before printf f.a->s.\n");
        printf(f.a->s);
        printf("before printf f.a->s.\n");
    }

    return EXIT_SUCCESS;
}



可以看到这两个程序虽然都存在访问异常, 但是段错误的位置却不同

我们将两个程序编译成汇编, 然户 diff 查看他们的汇编代码有何不同



gcc -S gdb_zero_length_array.c -o gdb_test.s
gcc -S gdb_pzero_length_array.c -o gdb_ptest
diff gdb_test.s gdb_ptest.s

1c1
<   .file   "gdb_zero_length_array.c"
---
>   .file   "gdb_pzero_length_array.c"
23c23
<   movl    $4, %esi
---
>   movl    $16, %esi
30c30
<   addq    $4, %rax
---
>   movq    8(%rax), %rax
36c36
<   addq    $4, %rax
---
>   movq    8(%rax), %rax



#    printf("sizeof(struct str) = %d\n", sizeof(struct str));
23c23
<   movl    $4, %esi    #printf("sizeof(struct str) = %d\n", sizeof(struct str));
---
>   movl    $16, %esi  #printf("sizeof(struct str) = %d\n", sizeof(struct str));

从64位系统中, 汇编我们看出, 变长数组结构的大小为4, 而指针形式的结构大小为16



f.a->s
30c30/36c36
<   addq    $4, %rax
---
>   movq    8(%rax), %rax

可以看到有

对于 char s[0] 来说, 汇编代码用了 addq 指令, addq $4, %rax
对于 char*s 来说，汇编代码用了 movq 指令, movq 8(%rax), %rax
addq 对 %rax + sizeof(struct str), 即str结构的末尾即是char s[0]的地址, 这一步只是拿到了其地址, 而 movq 则是把地址里的内容放进去, 因此有时也被翻译为leap指令, 参见下一列子

从这里可以看到, 访问成员数组名其实得到的是数组的相对地址, 而访问成员指针其实是相对地址里的内容(这和访问其它非指针或数组的变量是一样的)

访问相对地址，程序不会crash，但是，访问一个非法的地址中的内容，程序就会crash。
有时候



// 4-1.c
#include <stdio.h>
#include <stdlib.h>

int main(void)
{

    char *a;
    printf("%p\n", a);

    return EXIT_SUCCESS;
}



4-2.c
#include <stdio.h>
#include <stdlib.h>

int main(void)
{

    char a[0];
    printf("%p\n", a);

    return EXIT_SUCCESS;
}



$ diff 4-1.s 4-2.s
1c1
<       .file   "4-1.c"
---
>       .file   "4-2.c"
13c13
<       subl    $16, %esp
---
>       subl    $32, %esp
15c15
<       leal    16(%esp), %eax
---
>       movl    28(%esp), %eax

对于 char a[0] 来说, 汇编代码用了 leal 指令, leal    16(%esp), %eax
对于 char *a 来说，汇编代码用了 movl 指令, movl    28(%esp), %eax
4.2   地址优化

// 5-1.c
#include <stdio.h>
#include <stdlib.h>

int main(void)
{

    char a[0];
    printf("%p\n", a);

    char b[0];
    printf("%p\n", b);

    return EXIT_SUCCESS;
}



由于0长度数组是 GNU C 的扩展, 不被标准库任可, 那么一些巧妙编写的诡异代码, 其执行结果就是依赖于编译器和优化策略的实现的.

比如上面的代码, a和b的地址就会被编译器优化到一处, 因为a[0] 和 b[0] 对于程序来说是无法使用的, 这让我们想到了什么?

编译器对于相同字符串常量, 往往地址也是优化到一处, 减少空间占用



//  5-2.c
#include <stdio.h>
#include <stdlib.h>

int main(void)
{

    const char *a = "Hello";
    printf("%p\n", a);

    const char *b = "Hello";
    printf("%p\n", b);

    const char c[] = "Hello";
    printf("%p\n", c);

    return EXIT_SUCCESS;
}





参考

结构体中的指针与零长度数组

零长度数组的妙用

C语言中长度为0的数组

C/C++ 中的0长数组（柔性数组）

GNU C中的零长度数组

C语言变长数组data[0]【总结】

长度为0的数组——C语言的非标准用法之一

长度为0的数组的size为什么不一定是0？

有关C语言占位符

C语言技巧之长度为0的数组

零长度数组使用 

使用零长度数组

零长度数组

C/C++ 中长度为0的数组

GCC 中零长数组与变长数组

零长度数组的妙用

Multiple 0-length arrays have the same address?



本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可, 转载请注明出处, 谢谢合作.

NOIP 2015 普及组 初赛
疑难点 学习 感悟。
本份试卷本人得分93，两处错误，一错在二、1.题，眼花了，多数了个数据3241；二错在四、2.题(5)空，该空写成rbound=mid-1，这个错误在考试中是改正不了的，这是由本人解题方法决定的。也就是说该份试卷本人的极限是98。







一、
1.
C.1000*1000字节 是硬件商，软件商的做法。
D.1024*1024字节 来自教科书，也就是来源于计算机的二进制表达。
权衡之下选D
7.

示例如下（来自自个的理解）：

101.101 十进制 转十进制1*10^2+0*10^1+1*10^0+1*10^-1+0*10^-2+1*10^-3
101.101 二进制 转十进制1*2^2+0*2^1+1*2^0+1*2^-1+0*2^-2+1*2^-3
101.101 八进制 转十进制1*8^2+0*8^1+1*8^0+1*8^-1+0*8^-2+1*8^-3
101.101 十六进制 转十进制1*16^2+0*16^1+1*16^0+1*16^-1+0*16^-2+1*16^-3
以十进制为中介
0.1=1*2^-1=0.5
x*16^-1=0.5 => x=8
故答案为A
12.
n个顶点的树，边数为n-1
故答案为6-1=5，选B
13.
一直对D答案比较困惑，实际跨越的空间肯定不与个数成正比，不过，实际占有的空间与个数成正比，最终确定不选D，因A明显错误，只有数组才能做到随机访问。故选A
16.

(来自《算法竞赛入门经典》P155)

用递归定义 二叉树T 的先序遍历、中序遍历、后序遍历：
先序遍历 PreOrder(T)=T的根节点+PreOrder(T的左子树)+PreOrder(T的右子树)
中序遍历 InOrder(T)=InOrder(T的左子树)+T的根节点+InOrder(T的右子树)
后序遍历 PostOrder(T)=PostOrder(T的左子树)+PostOrder(T的右子树)+T的根节点



通过举例：一个根节点与一个只有一个节点的左子树；一个根节点与一个只有一个节点的右子树。本题很快就能做完。
17.

(来自《啊哈！算法》P184)
满二叉树的严格定义是一棵深度为h且有2^h-1个结点的二叉树。如下图所示：




完全二叉树严格定义：若设二叉树的高度为h，除第h层外，其他各层(1-h-1)的结点数都达到最大个数，
第h层从右向左连续缺若干节点，则这个二叉树就是完全二叉树。
如下图所示：




2^n-1=63
n=6
故为B
19.

T(n)=T(n-1)+n
推导：

T(n)=T(n-2)+n-1+n
T(n)=T(n-3)+n-2+n-1+n
T(n)=T(n-4)+n-3+n-2+n-1+n
......
T(n)=T(1)+2+......+n-3+n-2+n-1+n
T(n)=T(0)+1+2+......+n-3+n-2+n-1+n


T(n)=1+1+2+......+n-3+n-2+n-1+n
T(n)=1+(1+n)*n/2
T(n)=(n^2+n+2)/2
故T(n)=O(n^2)
故选D


二、
1.
枚举24种组合，选出符合条件的有9种，如下：
2143
2341
2413
3142
3412
3421
4123
4312
4321


2.
猜测应该是完全二叉树，满二叉树到完全二叉树，每少两个叶节点就多出一个叶结点。

(来自《啊哈！算法》P184)
满二叉树的严格定义是一棵深度为h且有2^h-1个结点的二叉树。如下图所示：




完全二叉树严格定义：若设二叉树的高度为h，除第h层外，其他各层(1-h-1)的结点数都达到最大个数，
第h层从右向左连续缺若干节点，则这个二叉树就是完全二叉树。
如下图所示：




满二叉树：
2^11-1=2047
叶节点个数2^10=1024
完全二叉数：
2047-2015=32，少了32个叶节点，应多出16个叶节点
故叶节点数：
1024-32+16=1008
三、
3.
统计小写字母个数。
4.

(来自《算法竞赛入门经典》P66)
函数的形参和在函数内声明的变量都是该函数的局部变量。无法访问其他函数的局部变量。
局部变量的存储空间是临时分配的，函数执行完毕时，局部变量的空间将被释放，其中的值无法保留到下次使用。
题中a的变化没有影响到p1，原因如上所示，故c1值不变。
题中*a影响的是p2指向的内存块，即c2里的值，故(*a)++对应的c2值要改变。
四、
1.
a.很快识别出dayNum数组中的数据是12个月的天数。
b.将2015年1月的数据代入该程序，进行模拟，第一步写出(3)空，第二步写出(4)空，第三步写出(1)空，第四步写出(5)空，最难写的是(2)空，写该空时尝试了2015年2月的数据。
2.
a.程序未完全看懂，代入数据0 3 9进行程序模拟。
b.第一步完成(1)，完全能猜出，第二步完成(5)空，采用对称性rbound=mid-1，虽然是错的，此空的错误，本人无法在考试时纠正(正确答案rbound=mid)，但不影响其它空的填写。
c.第三步完成(4)空，第四步完成(2)空，因count需要初始化，所以(2)空还是简单。
d.第五步完成(3)空，一开始猜反了，但在模拟数据过程中，很快纠正。