技术文章记录


  • 首页

  • 前端

  • 归档

JavaScript的正则表达式

发表于 2018-01-25

JavaScript 中的正则表达式

1、 正则表达式概述

ECMAScript 3 开始支持正则表达式,其语法和 Perl 语法很类似,一个完整的正则表达式结构如下:

var expression = / pattern / flags ;

其中,模式(pattern)部分可以是任何简单或复杂的正则表达式,可以包含字符类、限定符、分组、向前查找以及反向引用。
每个正则表达式都可带有一或多个标志(flags),用以标明正则表达式的行为,正则表达式支持下列 3 个标志:

g: 表示全局(global)模式,即模式将被应用于所有字符串,而非在发现第一个匹配项时立即停止;
i : 表示不区分大小写(case-insensitive)模式,即在确定匹配项时忽略模式与字符串的大小写;
m:表示多行(multiline)模式,即在到达一行文本末尾时还会继续查找下一行中是否存在与模式匹配的项。
如果多个标志同时使用时,则写成:gmi 。

正则表达式的创建有两种方式: new RegExp(expression) 和 直接字面量。

//使用直接字面量创建

var exp1 = /(^\s+)|(\s+$)/g;

//使用RegExp对象创建

var exp2 = new RegExp(“(^\s+)|(\s+$)”,”g”);

exp1 和 exp2 是两个完全等价的正则表达式,需要注意的是,传递给 RegExp 构造函数的两个参数都是字符串,不能把正则表达式字面量传递给 RegExp 构造函数。

与其他语言中的正则表达式类似,模式中使用的所有元字符都必须转义。正则表达式中的元字符包括:

( [ { \ ^ $ | ) ? * + .] }
这些元字符在正则表达式中都有一或多种特殊用途,因此如果想要匹配字符串中包含的这些字符,就必须对它们进行转义。

//匹配 .docx

var exp = /.docx/gi ;

由于 RegExp 构造函数的模式参数是字符串,所以在某些情况下要对字符进行双重转义。所有元字符都必须双重转义,那些已经转义过的字符也是如此。

// 对 . 再次转义
var exp = new RegExp(“\.docx”,”gi”);

//匹配 \n

var exp1 = /\n/g; //对\n中的\转义

var exp2 = new RegExp(“\\n”,”g”); // 对 \n 再次转义

2、() [] {} 的区别

() 的作用是提取匹配的字符串。表达式中有几个()就会得到几个相应的匹配字符串。比如 (\s+) 表示连续空格的字符串。

[] 是定义匹配的字符范围。比如 [a-zA-Z0-9] 表示字符文本要匹配英文字符和数字。

{} 一般用来表示匹配的长度,比如 \d{3} 表示匹配三个数字,\d{1,3} 表示匹配1~3个数字,\d{3,} 表示匹配3个以上数字。

3、^ 与$

^ 匹配一个字符串的开头,比如 (^a) 就是匹配以字母a开头的字符串

$ 匹配一个字符串的结尾,比如 (b$) 就是匹配以字母b结尾的字符串

^ 还有另个一个作用就是取反,比如[^xyz] 表示匹配的字符串不包含xyz

注意问题:

  • 如果 ^ 出现在[ ] 中一般表示取反,而出现在其他地方则是匹配字符串的开头。
  • ^ 和 $ 配合可以有效匹配完整字符串: /d+/.test(‘4xpt’) -> true,而 /^\d+$/.test(‘4xpt’)->false

4、\d \s \w .

\d 匹配一个非负整数, 等价于 [0-9]

\s 匹配一个空白字符

\w 匹配一个英文字母或数字,等价于[0-9a-zA-Z]

. 匹配除换行符以外的任意字符,等价于[^\n]

5、* + ?

  • 表示匹配前面元素0次或多次,比如 (\s*) 就是匹配0个或多个空格
  • 表示匹配前面元素1次或多次,比如 (\d+) 就是匹配由至少1个整数组成的字符串

? 表示匹配前面元素0次或1次,相当于{0,1} ,比如(\w?) 就是匹配最多由1个字母或数字组成的字符串

6、$1 与 \1

$1-$9 存放着正则表达式中最近的9个正则表达式的提取的结果,这些结果按照子匹配的出现顺序依次排列。基本语法是:RegExp.$n ,这些属性是静态的,除了replace中的第二个参数可以省略 RegExp 之外,其他地方使用都要加上 RegExp 。

//使用RegExp访问

/(\d+)-(\d+)-(\d+)/.test(“2016-03-26”)

RegExp.$1 // 2016

RegExp.$2 // 03

RegExp.$3 // 26

//在replace中使用

“2016-03-26”.replace(/(\d+)-(\d+)-(\d+)/,”$1年$2月$3日”)

// 2016年03月26日
\1 表示后向引用,是指在正则表达式中,从左往右数,第1个()中的内容,以此类推,\2表示第2个(),\0表示整个表达式。

//匹配日期格式,表达式中的\1代表重复(-|\/|.)

var rgx = /\d{4}(-|\/|.)\d{1,2}\1\d{1,2}”/

rgx.test(“2016-03-26”) //true

rgx.test(“2016-03.26”) //false

两者的区别是:\n只能用在表达式中,而$n只能用在表达式之外的地方。

7、test 与 match

前面的大都是JS正则表达式的语法,而test则是用来检测字符串是否匹配某一个正则表达式,如果匹配就会返回true,反之则返回false

/\d+/.test(“123”) ; //true

/\d+/.test(“abc”) ; //false

match是获取正则匹配到的结果,以数组的形式返回

“186a619b28”.match(/\d+/g); // [“186”,”619”,”28”]

8、replace

replace 本身是JavaScript字符串对象的一个方法,它允许接收两个参数:

replace([RegExp|String],[String|Function])

第1个参数可以是一个普通的字符串或是一个正则表达式

第2个参数可以是一个普通的字符串或是一个回调函数

如果第1个参数是 RegExp,JS会先提取RegExp匹配出的结果,然后用第2个参数逐一替换匹配出的结果

如果第2个参数是回调函数,每匹配到一个结果就回调一次,每次回调都会传递以下参数:

result: 本次匹配到的结果

$1,…$9: 正则表达式中有几个(),就会传递几个参数,$1~$9分别代表本次匹配中每个()提取的结果,最多9个

offset:记录本次匹配的开始位置

source:接受匹配的原始字符串

9、经典案例

【1】实现字符串的 trim 函数,去除字符串两边的空格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
String.prototype.trim = function(){

//方式一:将匹配到的每一个结果都用""替换

return this.replace(/(^\s+)|(\s+$)/g,function(){

return "";

});

//方式二:和方式一的原理相同

return this.replace(/(^\s+)|(\s+$)/g,'');
};

^\s+ 表示以空格开头的连续空白字符,\s+$ 表示以空格结尾的连续空白字符,加上() 就是将匹配到的结果提取出来,由于是 | 的关系,因此这个表达式最多会match到两个结果集,然后执行两次替换:

1
2
3
4
5
6
7
8
9
10
11
12
13
String.prototype.trim = function(){
/**
* @param rs:匹配结果
* @param $1:第1个()提取结果
* @param $2:第2个()提取结果
* @param offset:匹配开始位置
* @param source:原始字符串
*/
this.replace(/(^\s+)|(\s+$)/g,function(rs,$1,$2,offset,source){
//arguments中的每个元素对应一个参数
console.log(arguments);
});
};

“ abcd “.trim();

输出结果:

[“ “, “ “, undefined, 0, “ abcd “] //第1次匹配结果
[“ “, undefined, “ “, 5, “ abcd “] //第2次匹配结果

【2】提取浏览器 url 中的参数名和参数值,生成一个key/value 的对象。

1
2
3
4
5
6
7
8
9
10
11
function getUrlParamObj(){
var obj = {};
//获取url的参数部分
var params = window.location.search.substr(1);
//[^&=]+ 表示不含&或=的连续字符,加上()就是提取对应字符串
params.replace(/([^&=]+)=([^&=]*)/gi,function(rs,$1,$2){
obj[$1] = decodeURIComponent($2);
});

return obj;
}

/([^&=]+)=([^&=]*)/gi 每次匹配到的都是一个完整key/value,形如 xxxx=xxx, 每当匹配到一个这样的结果时就执行回调,并传递匹配到的 key 和 value,对应到$1和$2 。

【3】扩展 typeof,包含引用类型的具体类型。

1
2
3
4
5
function getDataType(obj){
let rst = Object.prototype.toString.call(obj);
rst = rst.replace(/\[object\s(\w+)\]/,'$1'); //[object Xxx]
return rst.toLowerCase()
}

getDataType(1); //number

getDataType(‘a’); //string

getDataType(null); //null

getDataType([]); //array

$1 是正则表达式中第一个() 中匹配的内容。需要注意的是,replace的第二个参数只能是字符串或函数,因此,这里的 $1 需要放在引号中。

【4】在字符串指定位置插入新字符串。

1
2
3
4
5
6
7
8
String.prototype.insetAt = function(str,offset){

offset = offset + 1;
//使用RegExp()构造函数创建正则表达式
var regx = new RegExp("(^.{"+offset+"})");

return this.replace(regx,"$1"+str);
};

“abcd”.insetAt(‘xyz’,2); //在c字符后插入xyz

>>“abcxyzd”

当offset=2时,正则表达式为:(^.{3}) .表示除\n之外的任意字符,{3} 表示匹配前三个连续字符,加()就会将匹配到的结果提取出来,然后通过replace将匹配到的结果替换为新的字符串,形如:结果=结果+str

【5】将手机号12988886666转化成129**6666 。

1
2
3
4
5
6
7
8
9
10
11
12
13

function telFormat(tel){

tel = String(tel);

//方式一
return tel.replace(/(\d{3})(\d{4})(\d{4})/,function (rs,$1,$2,$3){
return $1+"****"+$3
});

//方式二
return tel.replace(/(\d{3})(\d{4})(\d{4})/,"$1****$3");
}

(\d{3}\d{4}\d{4}) 可以匹配完整的手机号,并分别提取前 3 位、4-7 位和 8-11位,”$1$3” 是将第 2 个匹配结果用代替并组成新的字符串,然后替换完整的手机号。

【6】实现HTML编码,将< / > “ & ` 等字符进行转义,避免XSS攻击 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function htmlEncode(str) {
//匹配< / > " & `
return str.replace(/[<>"&\/`]/g, function(rs) {
switch (rs) {
case "<":
return "<";
case ">":
return ">";
case "&":
return "&";
case "\"":
return """;
case "/":
return "/"
case "`":
return "'"
}
});
}

字节对齐

发表于 2017-11-25

引言

   考虑下面的结构体定义:

1
2
3
4
5
6
typedef struct{
char c1;
short s;
char c2;
int i;
}T_FOO;

  假设这个结构体的成员在内存中是紧凑排列的,且c1的起始地址是0,则s的地址就是1,c2的地址是3,i的地址是4。

  现在,我们编写一个简单的程序:

1
2
3
4
5
6
7
8
9
int main(void){  
T_FOO a;
printf("c1 -> %d, s -> %d, c2 -> %d, i -> %d\n",
(unsigned int)(void*)&a.c1 - (unsigned int)(void*)&a,
(unsigned int)(void*)&a.s - (unsigned int)(void*)&a,
(unsigned int)(void*)&a.c2 - (unsigned int)(void*)&a,
(unsigned int)(void*)&a.i - (unsigned int)(void*)&a);
return 0;
}

     运行后输出:

1
c1 -> 0, s -> 2, c2 -> 4, i -> 8

  为什么会这样?这就是字节对齐导致的问题。

  本文在参考诸多资料的基础上,详细介绍常见的字节对齐问题。因成文较早,资料来源大多已不可考,敬请谅解。

一 什么是字节对齐

   现代计算机中,内存空间按照字节划分,理论上可以从任何起始地址访问任意类型的变量。但实际中在访问特定类型变量时经常在特定的内存地址访问,这就需要各种类型数据按照一定的规则在空间上排列,而不是顺序一个接一个地存放,这就是对齐。

二 对齐的原因和作用

  不同硬件平台对存储空间的处理上存在很大的不同。某些平台对特定类型的数据只能从特定地址开始存取,而不允许其在内存中任意存放。例如Motorola 68000 处理器不允许16位的字存放在奇地址,否则会触发异常,因此在这种架构下编程必须保证字节对齐。

   但最常见的情况是,如果不按照平台要求对数据存放进行对齐,会带来存取效率上的损失。比如32位的Intel处理器通过总线访问(包括读和写)内存数据。每个总线周期从偶地址开始访问32位内存数据,内存数据以字节为单位存放。如果一个32位的数据没有存放在4字节整除的内存地址处,那么处理器就需要2个总线周期对其进行访问,显然访问效率下降很多。

   因此,通过合理的内存对齐可以提高访问效率。为使CPU能够对数据进行快速访问,数据的起始地址应具有“对齐”特性。比如4字节数据的起始地址应位于4字节边界上,即起始地址能够被4整除。

  此外,合理利用字节对齐还可以有效地节省存储空间。但要注意,在32位机中使用1字节或2字节对齐,反而会降低变量访问速度。因此需要考虑处理器类型。还应考虑编译器的类型。在VC/C++和GNU GCC中都是默认是4字节对齐。

三 对齐的分类和准则

   主要基于Intel X86架构介绍结构体对齐和栈内存对齐,位域本质上为结构体类型。

   对于Intel X86平台,每次分配内存应该是从4的整数倍地址开始分配,无论是对结构体变量还是简单类型的变量。

3.1 结构体对齐

  在C语言中,结构体是种复合数据类型,其构成元素既可以是基本数据类型(如int、long、float等)的变量,也可以是一些复合数据类型(如数组、结构体、联合等)的数据单元。编译器为结构体的每个成员按照其自然边界(alignment)分配空间。各成员按照它们被声明的顺序在内存中顺序存储,第一个成员的地址和整个结构的地址相同。

  字节对齐的问题主要就是针对结构体。

3.1.1 简单示例

  先看个简单的例子(32位,X86处理器,GCC编译器):

  【例1】设结构体如下定义:

1
2
3
4
5
6
7
8
9
10
struct A{
int a;
char b;
short c;
};
struct B{
char b;
int a;
short c;
};

   已知32位机器上各数据类型的长度为:char为1字节、short为2字节、int为4字节、long为4字节、float为4字节、double为8字节。那么上面两个结构体大小如何呢?

  结果是:sizeof(strcut A)值为8;sizeof(struct B)的值却是12。

  结构体A中包含一个4字节的int数据,一个1字节char数据和一个2字节short数据;B也一样。按理说A和B大小应该都是7字节。之所以出现上述结果,就是因为编译器要对数据成员在空间上进行对齐。

3.1.2 对齐准则

  先来看四个重要的基本概念:

  1) 数据类型自身的对齐值:char型数据自身对齐值为1字节,short型数据为2字节,int/float型为4字节,double型为8字节。

  2) 结构体或类的自身对齐值:其成员中自身对齐值最大的那个值。

  3) 指定对齐值:#pragma pack (value)时的指定对齐值value。

  4) 数据成员、结构体和类的有效对齐值:自身对齐值和指定对齐值中较小者,即有效对齐值=min{自身对齐值,当前指定的pack值}。

  基于上面这些值,就可以方便地讨论具体数据结构的成员和其自身的对齐方式。

  其中,有效对齐值N是最终用来决定数据存放地址方式的值。有效对齐N表示“对齐在N上”,即该数据的“存放起始地址%N=0”。而数据结构中的数据变量都是按定义的先后顺序存放。第一个数据变量的起始地址就是数据结构的起始地址。结构体的成员变量要对齐存放,结构体本身也要根据自身的有效对齐值圆整(即结构体成员变量占用总长度为结构体有效对齐值的整数倍)。

  以此分析3.1.1节中的结构体B:

  假设B从地址空间0x0000开始存放,且指定对齐值默认为4(4字节对齐)。成员变量b的自身对齐值是1,比默认指定对齐值4小,所以其有效对齐值为1,其存放地址0x0000符合0x0000%1=0。成员变量a自身对齐值为4,所以有效对齐值也为4,只能存放在起始地址为0x0004~0x0007四个连续的字节空间中,符合0x0004%4=0且紧靠第一个变量。变量c自身对齐值为 2,所以有效对齐值也是2,可存放在0x0008~0x0009两个字节空间中,符合0x0008%2=0。所以从0x0000~0x0009存放的都是B内容。

  再看数据结构B的自身对齐值为其变量中最大对齐值(这里是b)所以就是4,所以结构体的有效对齐值也是4。根据结构体圆整的要求, 0x0000~0x0009=10字节,(10+2)%4=0。所以0x0000A~0x000B也为结构体B所占用。故B从0x0000到0x000B 共有12个字节,sizeof(struct B)=12。

  之所以编译器在后面补充2个字节,是为了实现结构数组的存取效率。试想如果定义一个结构B的数组,那么第一个结构起始地址是0没有问题,但是第二个结构呢?按照数组的定义,数组中所有元素都紧挨着。如果我们不把结构体大小补充为4的整数倍,那么下一个结构的起始地址将是0x0000A,这显然不能满足结构的地址对齐。因此要把结构体补充成有效对齐大小的整数倍。其实对于char/short/int/float/double等已有类型的自身对齐值也是基于数组考虑的,只是因为这些类型的长度已知,所以他们的自身对齐值也就已知。

  上面的概念非常便于理解,不过个人还是更喜欢下面的对齐准则。

  结构体字节对齐的细节和具体编译器实现相关,但一般而言满足三个准则:

  1) 结构体变量的首地址能够被其最宽基本类型成员的大小所整除;

  2) 结构体每个成员相对结构体首地址的偏移量(offset)都是成员大小的整数倍,如有需要编译器会在成员之间加上填充字节(internal adding);

  3) 结构体的总大小为结构体最宽基本类型成员大小的整数倍,如有需要编译器会在最末一个成员之后加上填充字节{trailing padding}。

  对于以上规则的说明如下:

  第一条:编译器在给结构体开辟空间时,首先找到结构体中最宽的基本数据类型,然后寻找内存地址能被该基本数据类型所整除的位置,作为结构体的首地址。将这个最宽的基本数据类型的大小作为上面介绍的对齐模数。

  第二条:为结构体的一个成员开辟空间之前,编译器首先检查预开辟空间的首地址相对于结构体首地址的偏移是否是本成员大小的整数倍,若是,则存放本成员,反之,则在本成员和上一个成员之间填充一定的字节,以达到整数倍的要求,也就是将预开辟空间的首地址后移几个字节。

  第三条:结构体总大小是包括填充字节,最后一个成员满足上面两条以外,还必须满足第三条,否则就必须在最后填充几个字节以达到本条要求。

  【例2】假设4字节对齐,以下程序的输出结果是多少?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* OFFSET宏定义可取得指定结构体某成员在结构体内部的偏移 */
#define OFFSET(st, field) (size_t)&(((st*)0)->field)
typedef struct{
char a;
short b;
char c;
int d;
char e[3];
}T_Test;

int main(void){
printf("Size = %d\n a-%d, b-%d, c-%d, d-%d\n e[0]-%d, e[1]-%d, e[2]-%d\n",
sizeof(T_Test), OFFSET(T_Test, a), OFFSET(T_Test, b),
OFFSET(T_Test, c), OFFSET(T_Test, d), OFFSET(T_Test, e[0]),
OFFSET(T_Test, e[1]),OFFSET(T_Test, e[2]));
return 0;
}

   执行后输出如下:

1
2
3
Size = 16
a-0, b-2, c-4, d-8
e[0]-12, e[1]-13, e[2]-14

  下面来具体分析:

  首先char a占用1个字节,没问题。

  short b本身占用2个字节,根据上面准则2,需要在b和a之间填充1个字节。

  char c占用1个字节,没问题。

  int d本身占用4个字节,根据准则2,需要在d和c之间填充3个字节。

  char e[3];本身占用3个字节,根据原则3,需要在其后补充1个字节。

  因此,sizeof(T_Test) = 1 + 1 + 2 + 1 + 3 + 4 + 3 + 1 = 16字节。

3.1.3 对齐的隐患

3.1.3.1 数据类型转换

  代码中关于对齐的隐患,很多是隐式的。例如,在强制类型转换的时候:

1
2
3
4
5
6
7
8
9
10
int main(void){  
unsigned int i = 0x12345678;

unsigned char *p = (unsigned char *)&i;
*p = 0x00;
unsigned short *p1 = (unsigned short *)(p+1);
*p1 = 0x0000;

return 0;
}

  最后两句代码,从奇数边界去访问unsigned short型变量,显然不符合对齐的规定。在X86上,类似的操作只会影响效率;但在MIPS或者SPARC上可能导致error,因为它们要求必须字节对齐。

  又如对于3.1.1节的结构体struct B,定义如下函数:

1
2
3
void Func(struct B *p){
//Code
}

  在函数体内如果直接访问p->a,则很可能会异常。因为MIPS认为a是int,其地址应该是4的倍数,但p->a的地址很可能不是4的倍数。

  如果p的地址不在对齐边界上就可能出问题,比如p来自一个跨CPU的数据包(多种数据类型的数据被按顺序放置在一个数据包中传输),或p是经过指针移位算出来的。因此要特别注意跨CPU数据的接口函数对接口输入数据的处理,以及指针移位再强制转换为结构指针进行访问时的安全性。

  解决方式如下:
  1) 定义一个此结构的局部变量,用memmove方式将数据拷贝进来。

1
2
3
4
5
void Func(struct B *p){
struct B tData;
memmove(&tData, p, sizeof(struct B));
//此后可安全访问tData.a,因为编译器已将tData分配在正确的起始地址上
}

  注意:如果能确定p的起始地址没问题,则不需要这么处理;如果不能确定(比如跨CPU输入数据、或指针移位运算出来的数据要特别小心),则需要这样处理。

  2) 用#pragma pack (1)将STRUCT_T定义为1字节对齐方式。

3.1.3.2 处理器间数据通信

  处理器间通过消息(对于C/C++而言就是结构体)进行通信时,需要注意字节对齐以及字节序的问题。

  大多数编译器提供内存对其的选项供用户使用。这样用户可以根据处理器的情况选择不同的字节对齐方式。例如C/C++编译器提供的#pragma pack(n) n=1,2,4等,让编译器在生成目标文件时,使内存数据按照指定的方式排布在1,2,4等字节整除的内存地址处。

  然而在不同编译平台或处理器上,字节对齐会造成消息结构长度的变化。编译器为了使字节对齐可能会对消息结构体进行填充,不同编译平台可能填充为不同的形式,大大增加处理器间数据通信的风险。

  下面以32位处理器为例,提出一种内存对齐方法以解决上述问题。

  对于本地使用的数据结构,为提高内存访问效率,采用四字节对齐方式;同时为了减少内存的开销,合理安排结构体成员的位置,减少四字节对齐导致的成员之间的空隙,降低内存开销。

  对于处理器之间的数据结构,需要保证消息长度不会因不同编译平台或处理器而导致消息结构体长度发生变化,使用一字节对齐方式对消息结构进行紧缩;为保证处理器之间的消息数据结构的内存访问效率,采用字节填充的方式自己对消息中成员进行四字节对齐。

  数据结构的成员位置要兼顾成员之间的关系、数据访问效率和空间利用率。顺序安排原则是:四字节的放在最前面,两字节的紧接最后一个四字节成员,一字节紧接最后一个两字节成员,填充字节放在最后。

  举例如下:

1
2
3
4
5
6
7
typedef struct tag_T_MSG{
long ParaA;
long ParaB;
short ParaC;
char ParaD;
char Pad; //填充字节
}T_MSG;

3.1.3.3 排查对齐问题

  如果出现对齐或者赋值问题可查看:

  1) 编译器的字节序大小端设置;

  2) 处理器架构本身是否支持非对齐访问;

  3) 如果支持看设置对齐与否,如果没有则看访问时需要加某些特殊的修饰来标志其特殊访问操作。

3.1.4 更改对齐方式

  主要是更改C编译器的缺省字节对齐方式。

   在缺省情况下,C编译器为每一个变量或是数据单元按其自然对界条件分配空间。一般地,可以通过下面的方法来改变缺省的对界条件:

  使用伪指令#pragma pack(n):C编译器将按照n个字节对齐;
  使用伪指令#pragma pack(): 取消自定义字节对齐方式。
  另外,还有如下的一种方式(GCC特有语法):

  •   __attribute((aligned (n))): 让所作用的结构成员对齐在n字节自然边界上。如果结构体中有成员的长度大于n,则按照最大成员的长度来对齐。
  •   attribute ((packed)): 取消结构在编译过程中的优化对齐,按照实际占用字节数进行对齐。

  【注】attribute机制是GCC的一大特色,可以设置函数属性(Function Attribute)、变量属性(Variable Attribute)和类型属性(Type Attribute)。详细介绍请参考:

  http://www.unixwiz.net/techtips/gnu-c-attributes.html

  下面具体针对MS VC/C++ 6.0编译器介绍下如何修改编译器默认对齐值。

  1) VC/C++ IDE环境中,可在[Project]|[Settings],C/C++选项卡Category的Code Generation选项的Struct Member Alignment中修改,默认是8字节。

    

  VC/C++中的编译选项有/Zp[1|2|4|8|16],/Zpn表示以n字节边界对齐。n字节边界对齐是指一个成员的地址必须安排在成员的尺寸的整数倍地址上或者是n的整数倍地址上,取它们中的最小值。亦即:min(sizeof(member), n)。

  实际上,1字节边界对齐也就表示结构成员之间没有空洞。

  /Zpn选项应用于整个工程,影响所有参与编译的结构体。在Struct member alignment中可选择不同的对齐值来改变编译选项。

  2) 在编码时,可用#pragma pack动态修改对齐值。具体语法说明见附录5.3节。

  自定义对齐值后要用#pragma pack()来还原,否则会对后面的结构造成影响。

  【例3】分析如下结构体C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 #pragma pack(2)  //指定按2字节对齐
struct C{
char b;
int a;
short c;
};
#pragma pack() //取消指定对齐,恢复缺省对齐
```


&emsp;&emsp;变量b自身对齐值为1,指定对齐值为2,所以有效对齐值为1,假设C从0x0000开始,则b存放在0x0000,符合0x0000%1= 0;变量a自身对齐值为4,指定对齐值为2,所以有效对齐值为2,顺序存放在0x0002~0x0005四个连续字节中,符合0x0002%2=0。变量c的自身对齐值为2,所以有效对齐值为2,顺序存放在0x0006~0x0007中,符合 0x0006%2=0。所以从0x0000到0x00007共八字节存放的是C的变量。C的自身对齐值为4,所以其有效对齐值为2。又8%2=0,C只占用0x0000~0x0007的八个字节。所以sizeof(struct C) = 8。

&emsp;&emsp;注意,结构体对齐到的字节数并非完全取决于当前指定的pack值,如下:

```c
#pragma pack(8)
struct D{
char b;
short a;
char c;
};
#pragma pack()

  此时sizeof(struct C)的值为7。

3.2 栈内存对齐

  在VC/C++中,栈的对齐方式不受结构体成员对齐选项的影响。总是保持对齐且对齐在4字节边界上。

  【例4】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#pragma pack(push, 1)  //后面可改为1, 2, 4, 8
struct StrtE{
char m1;
long m2;
};
#pragma pack(pop)

int main(void){
char a;
short b;
int c;
double d[2];
struct StrtE s;

printf("a address: %p\n", &a);
printf("b address: %p\n", &b);
printf("c address: %p\n", &c);
printf("d[0] address: %p\n", &(d[0]));
printf("d[1] address: %p\n", &(d[1]));
printf("s address: %p\n", &s);
printf("s.m2 address: %p\n", &(s.m2));
return 0;
}

  结果如下:

1
2
3
4
5
6
7
a    address:   0xbfc4cfff
b address: 0xbfc4cffc
c address: 0xbfc4cff8
d[0] address: 0xbfc4cfe8
d[1] address: 0xbfc4cff0
s address: 0xbfc4cfe3
s.m2 address: 0xbfc4cfe4

  可以看出都是对齐到4字节。并且前面的char和short并没有被凑在一起(成4字节),这和结构体内的处理是不同的。

  至于为什么输出的地址值是变小的,这是因为该平台下的栈是倒着“生长”的。

3.3 位域对齐

3.3.1 位域定义

  有些信息在存储时,并不需要占用一个完整的字节,而只需占几个或一个二进制位。例如在存放一个开关量时,只有0和1两种状态,用一位二进位即可。为了节省存储空间和处理简便,C语言提供了一种数据结构,称为“位域”或“位段”。

  位域是一种特殊的结构成员或联合成员(即只能用在结构或联合中),用于指定该成员在内存存储时所占用的位数,从而在机器内更紧凑地表示数据。每个位域有一个域名,允许在程序中按域名操作对应的位。这样就可用一个字节的二进制位域来表示几个不同的对象。

  位域定义与结构定义类似,其形式为:

struct 位域结构名

{ 位域列表 };

  其中位域列表的形式为:

类型说明符位域名:位域长度

  位域的使用和结构成员的使用相同,其一般形式为:

位域变量名.位域名

  位域允许用各种格式输出。

  位域在本质上就是一种结构类型,不过其成员是按二进位分配的。位域变量的说明与结构变量说明的方式相同,可先定义后说明、同时定义说明或直接说明。

  位域的使用主要为下面两种情况:

  1) 当机器可用内存空间较少而使用位域可大量节省内存时。如把结构作为大数组的元素时。

  2) 当需要把一结构体或联合映射成某预定的组织结构时。如需要访问字节内的特定位时。

3.3.2 对齐准则

  位域成员不能单独被取sizeof值。下面主要讨论含有位域的结构体的sizeof。

  C99规定int、unsigned int和bool可以作为位域类型,但编译器几乎都对此作了扩展,允许其它类型的存在。位域作为嵌入式系统中非常常见的一种编程工具,优点在于压缩程序的存储空间。

  其对齐规则大致为:

  1) 如果相邻位域字段的类型相同,且其位宽之和小于类型的sizeof大小,则后面的字段将紧邻前一个字段存储,直到不能容纳为止;

  2) 如果相邻位域字段的类型相同,但其位宽之和大于类型的sizeof大小,则后面的字段将从新的存储单元开始,其偏移量为其类型大小的整数倍;

  3) 如果相邻的位域字段的类型不同,则各编译器的具体实现有差异,VC6采取不压缩方式,Dev-C++和GCC采取压缩方式;

  4) 如果位域字段之间穿插着非位域字段,则不进行压缩;

  5) 整个结构体的总大小为最宽基本类型成员大小的整数倍,而位域则按照其最宽类型字节数对齐。

  【例5】

1
2
3
4
5
 struct BitField{
char element1 : 1;
char element2 : 4;
char element3 : 5;
};

  【例6】

1
2
3
4
5
 struct BitField1{
char element1 : 1;
short element2 : 5;
char element3 : 7;
};

  由于相邻位域类型不同,在VC6中其sizeof为6,在Dev-C++中为2。

  【例7】

1
2
3
4
5
  struct BitField2{
char element1 : 3;
char element2 ;
char element3 : 5;
};

  非位域字段穿插在其中,不会产生压缩,在VC6和Dev-C++中得到的大小均为3。

  【例8】

1
2
3
4
5
6
7
8
struct StructBitField{
int element1 : 1;
int element2 : 5;
int element3 : 29;
int element4 : 6;
char element5 :2;
char stelement; //在含位域的结构或联合中也可同时说明普通成员
};

  位域中最宽类型int的字节数为4,因此结构体按4字节对齐,在VC6中其sizeof为16。

3.3.3 注意事项

  关于位域操作有几点需要注意:

   1) 位域的地址不能访问,因此不允许将&运算符用于位域。不能使用指向位域的指针也不能使用位域的数组(数组是种特殊指针)。

   例如,scanf函数无法直接向位域中存储数据:

1
2
3
4
5
int main(void){  
struct BitField1 tBit;
scanf("%d", &tBit.element2); //error: cannot take address of bit-field 'element2'
return 0;
}

  可用scanf函数将输入读入到一个普通的整型变量中,然后再赋值给tBit.element2。

  2) 位域不能作为函数返回的结果。

  3) 位域以定义的类型为单位,且位域的长度不能够超过所定义类型的长度。例如定义int a:33是不允许的。

  4) 位域可以不指定位域名,但不能访问无名的位域。

  位域可以无位域名,只用作填充或调整位置,占位大小取决于该类型。例如,char :0表示整个位域向后推一个字节,即该无名位域后的下一个位域从下一个字节开始存放,同理short :0和int :0分别表示整个位域向后推两个和四个字节。

  当空位域的长度为具体数值N时(如int :2),该变量仅用来占位N位。

  【例9】

1
2
3
4
5
struct BitField3{
char element1 : 3;
char :6;
char element3 : 5;
};

   结构体大小为3。因为element1占3位,后面要保留6位而char为8位,所以保留的6位只能放到第2个字节。同样element3只能放到第3字节。

1
2
3
4
5
struct BitField4{
char element1 : 3;
char :0;
char element3 : 5;
};

  长度为0的位域告诉编译器将下一个位域放在一个存储单元的起始位置。如上,编译器会给成员element1分配3位,接着跳过余下的4位到下一个存储单元,然后给成员element3分配5位。故上面的结构体大小为2。

  5) 位域的表示范围。

  •   位域的赋值不能超过其可以表示的范围;
  •   位域的类型决定该编码能表示的值的结果。

  对于第二点,若位域为unsigned类型,则直接转化为正数;若非unsigned类型,则先判断最高位是否为1,若为1表示补码,则对其除符号位外的所有位取反再加一得到最后的结果数据(原码)。如:

1
2
unsigned int p:3 = 111;   //p表示7
int p:3 = 111; //p 表示-1,对除符号位之外的所有位取反再加一

  6) 带位域的结构在内存中各个位域的存储方式取决于编译器,既可从左到右也可从右到左存储。

  【例10】在VC6下执行下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  int main(void){  
union{
int i;
struct{
char a : 1;
char b : 1;
char c : 2;
}bits;
}num;

printf("Input an integer for i(0~15): ");
scanf("%d", &num.i);
printf("i = %d, cba = %d %d %d\n", num.i, num.bits.c, num.bits.b, num.bits.a);
return 0;
}

  输入i值为11,则输出为i = 11, cba = -2 -1 -1。

  Intel x86处理器按小字节序存储数据,所以bits中的位域在内存中放置顺序为ccba。当num.i置为11时,bits的最低有效位(即位域a)的值为1,a、b、c按低地址到高地址分别存储为10、1、1(二进制)。

  但为什么最后的打印结果是a=-1而不是1?

  因为位域a定义的类型signed char是有符号数,所以尽管a只有1位,仍要进行符号扩展。1做为补码存在,对应原码-1。

  如果将a、b、c的类型定义为unsigned char,即可得到cba = 2 1 1。1011即为11的二进制数。

  注:C语言中,不同的成员使用共同的存储区域的数据构造类型称为联合(或共用体)。联合占用空间的大小取决于类型长度最大的成员。联合在定义、说明和使用形式上与结构体相似。

  7) 位域的实现会因编译器的不同而不同,使用位域会影响程序可移植性。因此除非必要否则最好不要使用位域。

  8) 尽管使用位域可以节省内存空间,但却增加了处理时间。当访问各个位域成员时,需要把位域从它所在的字中分解出来或反过来把一值压缩存到位域所在的字位中。

四 总结

  让我们回到引言部分的问题。

  缺省情况下,C/C++编译器默认将结构、栈中的成员数据进行内存对齐。因此,引言程序输出就变成”c1 -> 0, s -> 2, c2 -> 4, i -> 8”。

  编译器将未对齐的成员向后移,将每一个都成员对齐到自然边界上,从而也导致整个结构的尺寸变大。尽管会牺牲一点空间(成员之间有空洞),但提高了性能。

  也正是这个原因,引言例子中sizeof(T_ FOO)为12,而不是8。

  总结说来,就是

  在结构体中,综合考虑变量本身和指定的对齐值;

  在栈上,不考虑变量本身的大小,统一对齐到4字节。

五 附录

5.1 字节序与网络序

5.1.1 字节序

  字节序,顾名思义就是字节的高低位存放顺序。

  对于单字节,大部分处理器以相同的顺序处理比特位,因此单字节的存放和传输方式一般相同。

  对于多字节数据,如整型(32位机中一般占4字节),在不同的处理器的存放方式主要有两种(以内存中0x0A0B0C0D的存放方式为例)。

  1) 大字节序(Big-Endian,又称大端序或大尾序)

   在计算机中,存储介质以下面方式存储整数0x0A0B0C0D则称为大字节序:

数据以8bit为单位
低地址方向 0x0A 0x0B 0x0C 0x0D 高地址方向
数据以16bit为单位
低地址方向 0x0A0B 0x0C0D 高地址方向

   其中,最高有效位(MSB,Most Significant Byte)0x0A存储在最低的内存地址处。下个字节0x0B存在后面的地址处。同时,最高的16bit单元0x0A0B存储在低位。

  简而言之,大字节序就是“高字节存入低地址,低字节存入高地址”。

   这里讲个词源典故:“endian”一词来源于乔纳森·斯威夫特的小说《格列佛游记》。小说中,小人国为水煮蛋该从大的一端(Big-End)剥开还是小的一端(Little-End)剥开而争论,争论的双方分别被称为Big-endians和Little-endians。

   1980年,Danny Cohen在其著名的论文”On Holy Wars and a Plea for Peace”中为平息一场关于字节该以什么样的顺序传送的争论而引用了该词。

   借用上面的典故,想象一下要把熟鸡蛋旋转着稳立起来,大头(高字节)肯定在下面(低地址)

  2) 小字节序(Little-Endian,又称小端序或小尾序)

  在计算机中,存储介质以下面方式存储整数0x0A0B0C0D则称为小字节序:

数据以8bit为单位
高地址方向 0x0A 0x0B 0x0C 0x0D 低地址方向
数据以16bit为单位
高地址方向 0x0A0B 0x0C0D 低地址方向

  其中,最低有效位(LSB,Least Significant Byte)0x0D存储在最低的内存地址处。后面字节依次存在后面的地址处。同时,最低的16bit单元0x0A0B存储在低位。

  可见,小字节序就是“高字节存入高地址,低字节存入低地址”。

  C语言中的位域结构也要遵循比特序(类似字节序)。例如:

1
2
3
4
struct bitfield{
unsigned char a: 2;
unsigned char b: 6;
}

  该位域结构占1个字节,假设赋值a = 0x01和b=0x02,则大字节机器上该字节为(01)(000010),小字节机器上该字节为(000010)(01)。因此在编写可移植代码时,需要加条件编译。

  注意,在包含位域的C结构中,若位域A在位域B之前定义,则位域A所占用的内存空间地址低于位域B所占用的内存空间。

  对上述问题,详细的讲解可参考http://www.linuxjournal.com/article/6788。

  另见以下联合体,在小字节机器上若low=0x01,high=0x02,则hex=0x21:

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(void){
union{
unsigned char hex;
struct{
unsigned char low : 4;
unsigned char high : 4;
};
}convert;
convert.low = 0x01;
convert.high = 0x02;
printf("hex = 0x%0x\n", convert.hex);
return 0;
}

5.1.2 网络序

  网络传输一般采用大字节序,也称为网络字节序或网络序。IP协议中定义大字节序为网络字节序。

  对于可移植的代码来说,将接收的网络数据转换成主机的字节序是必须的,一般会有成对的函数用于把网络数据转换成相应的主机字节序或反之(若主机字节序与网络字节序相同,通常将函数定义为空宏)。

  伯克利socket API定义了一组转换函数,用于16和32位整数在网络序和主机字节序之间的转换。Htonl、htons用于主机序转换到网络序;ntohl、ntohs用于网络序转换到本机序。

  注意:在大小字节序转换时,必须考虑待转换数据的长度(如5.1.1节的数据单元)。另外对于单字符或小于单字符的几个bit数据,是不必转换的,因为在机器存储和网络发送的一个字符内的bit位存储顺序是一致的。

5.1.3 位序

  用于描述串行设备的传输顺序。一般硬件传输采用小字节序(先传低位),但I2C协议采用大字节序。网络协议中只有数据链路层的底端会涉及到。

5.1.4 处理器字节序

  不同处理器体系的字节序如下所示:

  •   X86、MOS Technology 6502、Z80、VAX、PDP-11等处理器为Little endian;
  •   Motorola 6800、Motorola 68000、PowerPC 970、System/370、SPARC(除V9外)等处理器为Big endian;
  •   ARM、PowerPC (除PowerPC 970外)、DEC Alpha,SPARC V9,MIPS,PA-RISC and IA64等的字节序是可配置的。

5.1.5 字节序编程

  请看下面的语句:

1
printf("%c\n", *((short*)"AB") >> 8);

  在大字节序下输出为’A’,小字节序下输出为’B’。

  下面的代码可用来判断本地机器字节序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
复制代码
//字节序枚举类型
typedef enum{
ENDIAN_LITTLE = (INT8U)0X00,
ENDIAN_BIG = (INT8U)0X01
}E_ENDIAN_TYPE;

E_ENDIAN_TYPE GetEndianType(VOID)
{
INT32U dwData = 0x12345678;

if(0x78 == *((INT8U*)&dwData))
return ENDIAN_LITTLE;
else
return ENDIAN_BIG;
}

//Start of GetEndianTypeTest//
#include <endian.h>
VOID GetEndianTypeTest(VOID)
{
#if _BYTE_ORDER == _LITTLE_ENDIAN
printf("[%s]<Test Case> Result: %s, EndianType = %s!\n", __FUNCTION__,
(ENDIAN_LITTLE != GetEndianType()) ? "ERROR" : "OK", "Little");
#elif _BYTE_ORDER == _BIG_ENDIAN
printf("[%s]<Test Case> Result: %s, EndianType = %s!\n", __FUNCTION__,
(ENDIAN_BIG != GetEndianType()) ? "ERROR" : "OK", "Big");
#endif
}
//End of GetEndianTypeTest//

Java中抽象类和接口的用法和区别

发表于 2017-10-14

一、抽象类

1、抽象类

包含一个抽象方法的类就是抽象类

2、抽象方法

声明而未被实现的方法,抽象方法必须使用abstract关键词字声明

1
2
3
4
5
6
7
 
public abstract class People { //关键词abstract,声明该类为抽象类
public int age;
public void Num() {
}
public abstract Name(); //声明该方法为抽象方法
}

3、抽象类被子类继承,子类(如果不是抽象类)必须重写抽象类中的所有抽象方法

4、抽象类不能被直接实例化,要通过其子类进行实例化

5、只要包含一个抽象方法的抽象类,该方法必须要定义成抽象类,不管是否还包含有其他方法。

6、子类中的抽象方法不能与父类的抽象方法同名。

7、abstract不能与final并列修饰同一个类。

8、abstract 不能与private、static、final或native并列修饰同一个方法。

美丽长滩岛

发表于 2017-08-11

长滩岛(Boracay)是菲律宾中部的一座岛屿,面积10.32平方公里,人口12,003人(2000年)。属于热带海洋气候,行政区划属西米沙鄢大区的阿克兰省,位于班乃岛西北2公里,是菲律宾的旅游胜地之一。

坐着萌萌的嘟嘟车转圈

中午的太阳还是有点大的

顺便理个发,入乡随俗了…

路过海边

海边小村庄里,孩子们在玩耍呢…

最爽的莫过于出海浮潜 船开到大海中就停了 导游便开始往海里扔面包屑 大家都开始蠢蠢欲动 会游泳的小伙伴们早就蓄势待发了 我虽然装备都带好…

然后发现人家还有长滩的玩耍。选择了一个笑脸伞,虽然坐飞机过去了,但是还是想坐坐笑…

挂在螃蟹船的脚上看夕阳,真是美不胜收。可惜当地的管理不规范,螃蟹船的船主说好看30分钟,不到15分钟就上岸让我们下去又接上新的一波游客。夕阳…

必须推荐,非常刺激!是非常!耍完整个手臂都痛。长滩风浪大,很适合玩这个!被甩进海里整个人都是懵的。我们六个人,5个人都被扔进海里了!最安全…

日落风帆是长滩特有的特色,而且很好玩,尤其是黄昏日落的时候,很惬意~情侣的话推荐包船

美丽的黄昏就是好基友,也能看到完美的背影…

夜晚,本地的酒头晕了….

山顶的泳池

回酒店睡个懒觉

突然想起白天可爱的小车

和路过的风景

二叉树

发表于 2017-08-03

二叉树的使用场景

  • AVL树:最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树
    红黑树:平衡二叉树,广泛用在C++的STL中。map和set都是用红黑树实现的。我们熟悉的STL的map容器底层是RBtree,当然指的不是unordered_map,后者是hash。
    B/B+树用在磁盘文件组织 数据索引和数据库索引
    Trie树 字典树,用在统计和排序大量字符串

  • epoll在内核中的实现,用红黑树管理事件块
    nginx中,用红黑树管理timer等
    Java的TreeMap实现
    著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块
    B和B+主要用在文件系统以及数据库中做索引等,比如Mysql:B-Tree Index in MySql
    trie 树的一个典型应用是前缀匹配,比如下面这个很常见的场景,在我们输入时,搜索引擎会给予提示
    还有比如IP选路,也是前缀匹配,一定程度会用到trie

  • 跳表:Redis中就使用跳表,而不是红黑树来存储管理其中的元素(应该说的是一级元素-直接的Key,里面的value应该是有不同的数据结构)。

12
hellen

hellen

7 日志
© 2018 hellen
由 Hexo 强力驱动
|
主题 — NexT.Gemini v5.1.4