6
6
2014
0

B树

1.B数B-树。(B数即B-树)

B数的数据可能很庞大,不能将所有数据都读入内存,故内存缓存B树的一部分数据。我们要尽量保证每次读入尽可能多的信息。正由于这个原因,一个结点的大小通常相当于一个完整的磁盘页。因此,一个B树结点可以拥有的子女数就由磁盘页的大小决定。

也可以说B树的设计目的:减少磁盘的读、写操作

 

(1)B数每个叶子节点具有相同的深度

(2)每个结点能包含的关键字数有一个上界和下界。这些节用B数的最小度数的固定整数t>=2来表示

  (2.1)非根结点必须至少有t-1个关键字,即每个非根结点至少有t个子女。

  (2.2)如果树非空,则根节点至少包含一个关键字。

  (2.3)每个结点可以包含至多2t-1个关键字。故一个节点内至多有2t个子女,若一个结点是满的,则它有2t-1个关键字

(3)每个结点x有以下域:

   (3.1)n[x]该结点的关键字书

   (3.2)n[x]个关键字。这n[x]个关键字以非降序排列。key1[x]<=key2[x]...

   (3.3)leaf[x],x为叶子,则为true.若为内部结点,则为false

4.每个内结点包含n[x]+1个指向子女的指针。c1[x],c2[x],...

5.关键字keyi[x]对存储在各个子树中的关键字加以分隔:若ki为存储在ci[x]为根子树的关键字中,则

k1<=key1[x]<=k2<=key2[x]......

 

B树中并非只有叶子节点才存数据,中间节点也存数据

 

2.B+树

B+数和B数的差异:

1.有n颗子树的结点中含有n个关键字。

2.所有的叶子节点中包含了全部关键字的信息,即指向含有这些关键字记录的指针。

3.所有的非终端结点看成索引部分,结点中仅含有其子树根节点的最大(或者最小)关键字。而B数非终端结点页包含了的有效信息。

why??B+数比B树更适合文件索引和数据库索引。

首先B+ B树对比二叉树:B+ B具有多个分支,相比二叉树来说深度降低,一个结点对应着一次io操作,所以深度降低,则查找一个元素降低了访盘的次数!

然后比较B+ 与 B树,由于B+树的非叶子节点只存储索引信息,而B树还存储需要查找的有信息,所以B+树一个结点的索引信息更多。如果把所有同一内部结点的关键字放在同一盘中,那么关键字数量就越多。相对IO次数就降低了。

而且,只有非终结点并没有指向文件内容,所以死任何关键字的查找都要走一条从根到叶子节点的路径,长度相同,所以效率相当。

 

3 B*-Tree

B*树是在B+树上的改进:

B+树分裂:当一个结点满时,则分配一个新的结点,将原来结点1/2的数据复制到新节点,最后在父节点中增加新节点的指针。故B+树的分裂影响原结点和父节点。

B*树的分裂:当一个结点满时,如果它下一个兄弟结点未满,那么将一部分数据移到兄弟节点中,再在原结点中插入关键字,最后修改兄弟结点的关键字(因为兄弟节点关键字范围变了)。如果兄弟也满了,则在原结点与兄弟结点之间加入新节点,原结点和兄弟结点各复制1/3的数据到新节点,最后在父节点中增加新节点的指针。

所以说B*树是一颗丰满的树。B*树保证了非叶子节点的块利用率 >= 2/3 。所以相对B+树空间利用率更高

 

 

推荐参考:

http://www.360doc.com/content/11/1103/13/6938655_161335261.shtml

Category: 算法、数据结构 | Tags:
6
5
2014
0

红黑树

参考

http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#.E6.8F.92.E5.85.A5

1.有二叉平衡树,why红黑树。

 二叉平衡树的缺点,在删除时,需要调整整棵树,费时间。红黑树只需要调整局部

2.红黑树性质:

1).所有节点非红即黑

2).根是黑的

3).所有叶子是黑的。(叶子指不存数据的NULL结点)

4).红结点的儿子一定是黑的

5).从任意结点出发,到其所有叶子节点的路径上黑色节点数相同。(同一结点到不同叶子结点路径上)

3.红黑树的插入

新插入的结点默认为红色,这样可以保证性质5),若性质4)收到威胁,再采取措施

先分析:我们可以得到

性质1)3)可以始终保持,

性质4)在增加红色结点、重绘黑色结点为红色、做旋转时受到威胁

性质5)在增加黑色结点、重绘红色结点为黑色、做旋转时受到威胁

在如下描述中,新插入的标记为N,N的父亲标记为P,N的祖父标记为G,N的叔父标记为U.先分析插入的情况

(3.1)N为根节点。直接重绘为黑色

(3.2)P为黑色。直接插入

一下情况P为红色,由1)得知,N一定有叔父结点。ps 不存数据的NULL叶子节点也可以使叔父结点。

(3.3)P和U都是红色,N为P的左儿子或右儿子。则把PU重绘黑,G重绘红。在把G当做N进行从(3.1)开始的各种情况的检查。

(3.4)P红色,而U为黑色(包括U为存数据的黑色以及叶子节点的黑色),N是P的右儿子,P是G的左儿子。则进行左旋,接着按(3.5)做处理

(3.5)P红色,而U为黑色(包括U为存数据的黑色以及叶子节点的黑色),N是P的左儿子,P是G的左儿子。对G进行右旋

插入实际上是原地算法,上述都采用了尾部递归。

 

4.红黑树的删除

首先把删除两个具有两个儿子节点(非叶子儿子)的问题转化为删除另一个只有一个儿子节点的问题(非叶子儿子)。先找到左子树中最大元素或者右子树中最小元素来顶替节点,即把找到的结点先转移到要删除的结点中,接着再删除我们从中复制出的那个结点。

若选择复制左子树的最大节点,复制出的那个结点有下图三种情况(最大节点,故要删除的结点没有右儿子)。

(1)红色结点,左右儿子为不存数据的NULL。则直接删除,结束。不破坏性质

(2)黑色结点,左右儿子为不存数据的NULL。这个情况删除略微麻烦,见下面详细讨论

(3)黑色结点,左儿子为红色,右儿子为NULL。这种情况,删掉黑色后,原本指向黑色结点的指针指向黑色结点的左儿子,并把左儿子重绘为黑色,结束。

 

其他情况若有左儿子,则不满足性质(4),即红色结点左儿子为红色。或者性质(5),黑色结点左儿子为黑色。

下面都来讨论删除该复制出的那个结点,要删除的结点是N。删除上面第(2)中情况

(4.1)N是新根,直接删除

(4.2)S红色(推出P为黑)。则在P上左旋转,然后对调N的P和G的颜色。此时N的新S为黑,P为红,以左边框内作为单位,转到(4.4)(4.5)(4.6)来处理

(4.3)N的P、S以及S的SL、SR都是黑色。把S重绘为红色。则该小单元在删除N后黑色个数相同,则把框内看成整体,从(4.1)开始调整。即从(4.1)开始,在P上做重新平衡处理

(4.4)N的P为红色,S以及SL、SR都是黑色。则把P和S的颜色交换,就完成了

(4.5)S黑色,SL红色,SR黑色。将S做右旋,再交换SL和S的颜色,再由(4.6)处理

(4.6)S黑色,SR红色。在P点做左旋;交换P,S的颜色;把SR重绘为黑色。这样通过N的路径上多了一个黑色,N可以删除了

 

Category: 算法、数据结构 | Tags:
6
2
2014
0

c++容器之迭代器

本文参考一下的博客:

http://blog.csdn.net/yxysdcl/article/details/5567460

 

迭代器实现了容器中对象的访问方法。迭代器就如同一个指针,其实指针也就是特殊的迭代器。下面看两个小例子帮助理解:

1.简单变量类型迭代器

一下是vector类型的简单实现

template <class T>
class vector {
private:
	T* pbegin;
	int n; //当前大小
public:
	vector() {
		pbegin = new T[100]; //暂时先固定大小
		n = 0;
	}
	
	T* begin() {
		return pbegin;
	}
	void insert(T d){
		pbegin[n++] = d;
	}
	typedef T* iterator; //vector的迭代器就是基础指针类型
};

vector是数组的实现,故由首地址可以知道后面元素的位置,故访问vector迭代器,其实就是基础指针,可以通过++,--操作

下面为测试操作

//测试vector
	vector<int> a;
	a.insert(1);
	a.insert(2);
	vector<int>::iterator itra;
	itra = a.begin();
	printf("%d/n", *itra); 
	itra++;
	printf("%d/n", *itra);
	itra--; //基础指针类型都支持++,--,+,-等操作符
	printf("%d/n", *itra);

2.链表类型的迭代器。

链表每个元素在不同位置,那怎么设计迭代器,使得它也可以通过++/--等操作实现定位呢?一下为例子

template <class T>
class List{
private:
	struct Node{ //链表的节点
		T data;
		Node* next;
	};
	Node* pbegin; //表头
	class List_iterator{ //链表的迭代器
		Node* cur; //当前指向
	public:
		void operator = (Node* ptr) {
			cur = ptr;
		}
		void operator ++ () {
			cur = cur->next;
		}
		// ...还可以重载-- + -等操作符
		T operator * (){
			return cur->data;
		}
	};
public :
	List() {
		pbegin=NULL;
	}
	Node* begin() {
		return pbegin;
	}
	void insert(T d) {
		Node* p=pbegin;
		while(p && p->next) p=p->next;
		Node* t = new Node;
		t->data = d;
		t->next = NULL;
		if(pbegin==NULL)
			pbegin = t;
		else
			p->next = t;
	}
	typedef List_iterator iterator; //List的迭代器是一个类
};

如上面代码,即对++操作进行了重载。测试代码如下

/测试List
	List<int> b;
	b.insert(1);
	b.insert(2);
	List<int>::iterator itrb;
	itrb = b.begin();
	printf("%d/n", *itrb);
	itrb++; // 该迭代器只支持++
	printf("%d/n", *itrb);

由此我们可以看出迭代器的目的,即通过迭代器,更方便的便利访问容器里的元素。这样在STL设计算法时,可以脱离容器设计更加通用的算法。如,容器中查找一个元素一般是遍历整个集合,如果没有迭代器,需要为vector和list设计两个查找算法。

总结;

模板:将算法和特定的数据类型分离

迭代器:将算法和特定的容器分离

Category: 面向对象 | Tags:
6
2
2014
0

关于模板解读

本文借鉴参考:

http://www.cnblogs.com/gaojun/archive/2010/09/10/1823354.html

1.概念

模板的好处:实现代码的重用。

如何实现?:把类型定义为参数。

下面举例说明好处。若返回a,b之间较大的数,由于a,b类型不确定,故可能要定义多个函数。如:

//函数1.

int max(int x,int y);
{return(x>y)?x:y ;}

//函数2.
float max( float x,float y){
return (x>y)? x:y ;}

//函数3.
double max(double x,double y)
{return (c>y)? x:y ;}

如果主函数调用max(a,b).而a、b是char类型的,则程序会出错。因为定义的三个类型中没有char的比较。于是就能用模板来解决这个问题

2.函数的模板

函数模板形式

Template<class T或者typename T>

返回值类型 函数名 (形参表)

{ //函数定义}

以下程序

#include <iostream>

using std::cout;

using std::endl;

//声明一个函数模版,用来比较输入的两个相同数据类型的参数的大小,class也可以被typename代替,

//T可以被任何字母或者数字代替。

template <class T>

T min(T x,T y)

{ return(x<y)?x:y;}

void main( )

{

     int n1=2,n2=10;

     double d1=1.5,d2=5.6;

     cout<< "较小整数:"<<min(n1,n2)<<endl;

     cout<< "较小实数:"<<min(d1,d2)<<endl;

     system("PAUSE");

}

这样就可以通过模板将函数定义一次。

3.类模板

定义一个类模板:

Template(class T或者typename T)

class 类名{

//类定义};

看如下例子

// ClassTemplate.h
#ifndef ClassTemplate_HH

#define ClassTemplate_HH

template<typename T1,typename T2>

class myClass{

private:

     T1 I;

     T2 J;

public:

     myClass(T1 a, T2 b);//Constructor

     void show();

};

//这是构造函数

//注意这些格式

template <typename T1,typename T2>

myClass<T1,T2>::myClass(T1 a,T2 b):I(a),J(b){}

//这是void show();

template <typename T1,typename T2>

void myClass<T1,T2>::show()

{

     cout<<"I="<<I<<", J="<<J<<endl;

}

#endif

// Test.cpp

#include <iostream>

#include "ClassTemplate.h"

using std::cout;

using std::endl;

void main()

{

     myClass<int,int> class1(3,5);

     class1.show();

     myClass<int,char> class2(3,'a');

     class2.show();

     myClass<double,int> class3(2.9,10);

     class3.show();

     system("PAUSE");

}

 

Category: 面向对象 | Tags:
5
27
2014
0

list_entry函数

在文件系统内核代码中有list_entry函数,详细解说见:

http://blog.csdn.net/chuchuanchuan/article/details/8138009

http://blog.csdn.net/sh_sige/article/details/9814673

list_entry的宏定义如下:

#define list_entry(ptr,type,member) container_of(ptr,type,member),由于containner_of宏中包含offsetof宏,故如下分析这两个宏

1.#define offsetof(TYPE,MEMBER) ((size_t)&((TYPE *)0)->MEMBER)

宏功能:获得一个结构体变量在该结构体中的偏移量。

#include <stdio.h>
#define offsetof(TYPE, MEMBER) ((int)(&((TYPE *)0)->MEMBER))
struct _test_{
    int  x;
    int  y;
    float z;
};

int main(void)
{
 int temp = -1;
 temp = offsetof(struct _test_, z);
 printf("temp = %d\n", temp);
 return 0;
}

 运行结果:temp=8

即求出结构体成员变量z在结构体中的偏移为8

 

2 #define container_of(ptr,type,member)({const typeof(((type *)0)->member) *_mptr=(ptr); (type *)((char *)_mptr-offsetof(type,member));})

宏功能:由结构体(type)某成员变量(member)指针(ptr),求出该结构体(type)的首指针。ps 该首指针是包含该成员变量实例的首指针。

#include <stdio.h>
#define offsetof(TYPE, MEMBER) ((int)(&((TYPE *)0)->MEMBER))

#define container_of(ptr, type, member) ({   \
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \
        (type *)( (char *)__mptr - offsetof(type,member) );})

struct _test_
{
 int  x;
 int  y;
 int  z;
};

void Assignment(struct _test_ *t)
{
 t->x = 1;
 t->y = 2;
 t->z = 3;
}

void GetheadPoint(int *tz)//传入成员变量的指针tz,即可以得到该成员变量首指针temp
{
 struct _test_ *p;
 int temp = -1;
 p = container_of(tz,struct _test_, z);   //根据成员变量的地址获得该结构体的首地址
 temp = p->y;                            //根据首地址获得其中另外一个成员变量的值
 printf("line31 = %d\n", temp);
}

int main(void)
{
 int temp = -1;
 struct _test_ tmp;                       //定义一个结构体变量

 Assignment(&tmp);                        //给这个变量赋值
 GetheadPoint(&tmp.z);                    //只传给这个函数一个结构体成员变量的地址

 printf("line43 tmp - >x = %d\n", tmp.x); 
 return 0;
}

运行结果:由getheadpoint函数得知,由穿入成员变量指针,可以得到该struct实例的首指针

Category: 文件系统 | Tags:
5
26
2014
0

硬链接&软链接

硬链接是一个指针,指向文件的索引结点。不为其分配新的inode。

软连接要分配新的inode,完成dentry->inode->block的分配(dentry中的name就是创建软连接文件的文件名)。block指向另一个dentry文件。

 

先看硬链接、软连接的构造方法。

删除一个文件或者目录。实际上是把inode的链接数减1,链接数是统计的硬链接,不影响其他指向此inode的链接。而会对指向该文件和目录的软链接有影响。

所以说硬链接是直接指向文件的inode,而软连接是指向目录的。

在截图中我们可以看出,ls -F 指令,软连接用@标识

上图中第一列是inode号,第三列是硬链接数,可以看到a.txt和b.txt是共享一个inode号的,且文件属性相同。由于共享了inode号,故不同的文件系统中是不能建立硬链接的。

而软链接c.txt与a.txt,b.txt的inode号以及文件属性都不同。即软连接有自己的inode号。

此时a.txt和b.txt的硬链接数都是2

以下两点软硬链接用法区别

1.硬链接不许对目录创建,而软链接而对目录创建

原因,有两点:

1.防止遍历时出现死循环。软连接之所以不会出现死循环是因为系统可以在遍历目录时,可以判断出这是一个符号链接,若连续出现符号链接超过某个此处,则终端循环。

2.dentry(目录和文件都有自己的dentry)中有一个指向父目录的指针。若父目录中有两个dentry地址,则该目录项中的每个dentry的parent向不知道指向哪个了。

 

2.硬链接不能跨文件系统,软链接可以跨文件系统

 

硬链接实现的是多个文件名指向同一个inode,即多个dentry对应一个inode。也就是每个硬链接对应一个目录项

这部分没有完全描述清楚,之后又了解再及时补充

 

下面插入一幅图:

 

通过上图我们可以上到软连接的数据区实际上指向的是源文件的dentry,所以说:

对于软连接:创建一个软链接,inode的引用计数不会增加,删除被链接的源文件,则相关软连接变成了死链接。

对于硬链接:创建硬链接,inode的引用计数会加1.

这部分有参考:

http://www.cnblogs.com/stli/archive/2010/11/10/1873212.html

http://blog.csdn.net/kension/article/details/3796603

Category: 文件系统 | Tags:
5
26
2014
0

dentry与inode

首先看dentry数据结构。位于include/linux/dcache.h中 struct dentry

ps:dentry虽然是目录的意思,但是在vfs中,目录和文件都有自己的dentry。(dentry中存了文件名,同一文件存在别名就是这个结构实现的)

struct dentry {
atomic_td_count;目录项对象使用计数器
unsignedintd_flags;目录项标志
structinode*d_inode;与文件名关联的索引节点
structdentry*d_parent;父目录的目录项对象
structlist_headd_hash;散列表表项的指针
structlist_headd_lru;未使用链表的指针
structlist_headd_child;父目录中目录项对象的链表的指针
structlist_headd_subdirs;对目录而言,表示子目录目录项对象的链表
structlist_headd_alias;相关索引节点(别名)的链表
intd_mounted;对于安装点而言,表示被安装文件系统根项
structqstrd_name;文件名
unsignedlongd_time;/*usedbyd_revalidate*/
structdentry_operations*d_op;目录项方法
structsuper_block*d_sb;文件的超级块对象
vunsignedlongd_vfs_flags;
void*d_fsdata;与文件系统相关的数据
unsignedchard_iname[DNAME_INLINE_LEN];存放短文件名
};

再看inode数据结构。include/linux/fs.h

struct inode {/*vfs中数据结构 数据结构中各项的含义见 Linux 内核 465页*/
	struct hlist_node	i_hash;
	struct list_head	i_list;		/* backing dev IO list */
	struct list_head	i_sb_list;
	struct list_head	i_dentry; /*引用该索引节点的目录项对象链表表头*/
	unsigned long		i_ino;/*索引节点号*/
	atomic_t		i_count;
	unsigned int		i_nlink;
	uid_t			i_uid;
	gid_t			i_gid;
	dev_t			i_rdev;
	unsigned int		i_blkbits;
	u64			i_version;
	loff_t			i_size;
#ifdef __NEED_I_SIZE_ORDERED
	seqcount_t		i_size_seqcount;
#endif
	struct timespec		i_atime;
	struct timespec		i_mtime;
	struct timespec		i_ctime;
	blkcnt_t		i_blocks;
	unsigned short          i_bytes;
	umode_t			i_mode;
	spinlock_t		i_lock;	/* i_blocks, i_bytes, maybe i_size */
	struct mutex		i_mutex;
	struct rw_semaphore	i_alloc_sem;
	const struct inode_operations	*i_op;/*与索引结点有关的操作*/
	const struct file_operations	*i_fop;	/* former ->i_op->default_file_ops */
	struct super_block	*i_sb;
	struct file_lock	*i_flock;
	struct address_space	*i_mapping;
	struct address_space	i_data;
#ifdef CONFIG_QUOTA
	struct dquot		*i_dquot[MAXQUOTAS];
#endif
	struct list_head	i_devices;
	union {
		struct pipe_inode_info	*i_pipe;
		struct block_device	*i_bdev;
		struct cdev		*i_cdev;
	};

	__u32			i_generation;

#ifdef CONFIG_FSNOTIFY
	__u32			i_fsnotify_mask; /* all events this inode cares about */
	struct hlist_head	i_fsnotify_mark_entries; /* fsnotify mark entries */
#endif

#ifdef CONFIG_INOTIFY
	struct list_head	inotify_watches; /* watches on this inode */
	struct mutex		inotify_mutex;	/* protects the watches list */
#endif

	unsigned long		i_state;
	unsigned long		dirtied_when;	/* jiffies of first dirtying */

	unsigned int		i_flags;

	atomic_t		i_writecount;
#ifdef CONFIG_SECURITY
	void			*i_security;
#endif
#ifdef CONFIG_FS_POSIX_ACL
	struct posix_acl	*i_acl;
	struct posix_acl	*i_default_acl;
#endif
	void			*i_private; /* fs or device private pointer */
}

"文件"即按一定形式存储在介质上的信息,该信息包含两方面,其一是存储的数据本身,其二是概述的索引。在内存中,每个文件都有一个inode和dentry结构。dentry记录文件名,上级目录,子目录等信息,正是我们看到的树状结构;inode记录着文件在存储介质上的位置和分布,dentry->d_inode指向对应的inode结构。inode代表物理意义上的文件,通过inode可以得到一个数组,这个数组记录文件内容的位置,若数组为(4,5,9),则对应数据位于硬盘的4,5,9块。其索引节点号为inode->ino,根据ino就可以计算出对应硬盘中inode的具体位置。


dentry所描述的是逻辑意义上的文件,所描述的是文件逻辑上的属性,所以dentry在磁盘上没有对应的影像;而inode结构代表的是物理意义上的文件,故磁盘上也有inode结构

inode结构中有一个队列i_dentry,凡是代表同一个文件的所有目录项都通过d_alias域挂入响应的inode结构中的i_dentry队列。


进程打开一个文件,就会有一个file结构与之对应,同一个进程可以多次打开同一个文件而得到多个不同的file结构,file结构描述了被打开文件的属性,读写偏移指针等

两个不同的file可以对应同一个dentry结构,进程多次打开一个文件,对应只有一个dentry结构,dentry存的是目录项和对应文件的inode的信息。

在介质中,每个文件对应一个inode结点,每个文件可有多个文件名,即可以通过不同的文件名访问同一个文件,多个文件名对应一个文件的关系就是数据结构中dentry和inode多对一的关系。inode中不存储文件名字,只有节点号,通过节点号(ino),可以找到数据在介质中的具体位置,即通过内存inode结构中的ino可以定位到磁盘上的inode结构;而dentry则保存文件名和对应的节点号(inode号),这样就可以实现不同文件名访问一个inode。不同的dentry是通过ln指令实现的。


dentry树描绘了文件系统目录结构,但整个目录结构不能长驻内存,因为非常大。内存装不下。

初始状态下,系统只有代表根目录的dentry和所指向的inode(在根文件系统中挂载生成)。此时要打开一个文件,文件路径对应的结点不存在,根目录的dentry无法找到需要的子节点。这时需要通过inode->i_op中lookup方法找到inode的子节点,找到后,再创建一个dentry与之关联。

由这个过程可以看出。现有inode再有dentry。

当生成的dentry无人使用时被释放,d_count字段记录了dentry的引用计数,引用为0时,dentry被释放。这里的释放不是直接销毁,而是将dentry放入一个“最近最少使用”队列。当队列过大,内存紧缺时,dentry才被释放。这个LRU队列就像是一个缓存池, 加速了对重复的路径的访问. 而当dentry被真正释放时, 它所对应的inode将被减引用. 如果引用为0, inode也被释放.

故需找一个文件路径是有三种情况:

1.dentry引用大于0,直接在dentry树种找

2.dentry不在树种,在lru队列中找,LRU队列中的dentry被散列到一个散列表中,便于查找,若找到,则重新添加到dentry树种。

3.若2也未找到,则区找inode,找到后,再创建对应的dentry

这里补充每个目录项对象可以出于以下四种状态之一:

1:空闲状态  即该目录项不包含有效的信息,且没被VFS使用。

2.未使用状态  该对象的d_count计数为0,但d_inode指向关联的索引节点

3.正在使用状态  该对象的d_count计数不为0,但d_inode指向关联的索引节点

4.负状态   与目录项关联的索引结点不存在了


mount过程:

linux首先找到磁盘分区的super block,然后通过解析磁盘的inode table与file data。构建出自己的dentry列表和inode列表。VFS是按照Ext的方法进行构建的,两者非常相似。如inode结点。ext_inode结点中的一些成员变量其实是没有用的,如引用计数等,保留目的是为了和vfs-inode保持一致,这样在用ext_inode构建vfs_inode时,就不需要一个个赋值,只需要一次拷贝。

故非ext格式的文件系统,mount的过程会慢一些


根目录有一个dentry结构,而根目录里的文件盒目录都链接到这个跟dentry;同样的道理,二级目录里的文件和目录链接到二级目录,这样一层层,就形成了一颗dentry树。从树顶可以遍历整个文件系统。

为了加快对dentry的查找,内核使用hash表来缓存dentry,称为dentry cache,dentry一般现在dentry cache中查找。

 

dentry结构里有d_subdirs成员和d_child成员。d_subdirs是子项的链表头,所有的子项都要链接在这个链表上,d_child是自身链表头,需要连接到父dentry的d_subdirs成员。

d_parent是指针,指向父dentry结构。

d_hash是连接到dentry cache的hash链表。

d_name保存目录或文件的名字。打开一个文件的时候,根据这个成员和用户输入的名字来搜寻目标。

d_mounted用来指示dentry是否是一个挂载点。如果是,则成员不为零。


dentry的hash定位,通过d_hash()函数将父目录dentry的地址和所要查找的文件名的hash值结合起来,重新计算一个hash值,并根据其定位到dentry_hashtable哈希表中(即定位某个表头,缩小查找范围),该表是dentry缓存一部分,接下来扫描该链表,从中找到目标dentry,若没有找到,则通过real_lookup()函数从磁盘中查找。


目录项对象存放在dentry_cache的slab高速缓存中。故目录项的创建和删除是通过kmem_cache_alloc()和kmem_cache_free()实现的。目录项高速缓存由两种类型数据结构组成:

1.处于正在使用、未使用或负状态的目录项对象的集合。

2.一个散列表。用于hash快速查找给定文件名和目录名对应的目录项对象。散列表是由dentry_hashtable数组实现。数组中每个元素是一个指向链表的指针。

 

参考:

http://book.2cto.com/201312/38229.html

http://blog.csdn.net/vanbreaker/article/details/8208173
http://blog.chinaunix.net/uid-20184656-id-3151111.html

http://blog.csdn.net/fudan_abc/article/details/1775313

Category: 文件系统 | Tags:
5
21
2014
1

C/C++中堆、栈、自由存储区、全局/静态存储区、常量存储区

本文的内容来自

http://www.cnblogs.com/hanyonglu/archive/2011/04/12/2014212.html

 

在C/C++中,内存分为5个区,分别是堆、栈、自由存储区、全局/静态存区、常量存储区。

栈:由编译器在需要的时候分配,不需要时自动清除的存储区。里面的变量为局部变量、函数参数等。

堆:由new分配的内存块,释放是程序员代码手动的。delete来释放new的东西

自由存储区:malloc分配的内存块,和堆类似,不同处在于用free结束生命

全局/静态存储区:全局变量和静态变量。内存在程序编译的时候就已经分配好,这块内存在整个程序运行的期间都在

常量存储区:里面存放常量

以下看一个例子:

void f(){ int *p = new int[5];}

上面这个语句就调用了栈和堆,new 对应的为堆中分配的空间、指针p为栈中的存储区间。


下面重点讨论一下栈和堆的区别。

管理方式--栈:编译器自动管理,无需手动控制;堆:释放工作手动

空间大小--栈:默认大小较小,大小约为1M ;堆:32为系统,内存可达到4G。

碎片问题--栈,先进后出,不存在空间碎片;堆:频繁的new/delete会造成内存空间不连续

生长方向--栈,向内存地址小的方向增长;堆:向内存地址大的方向增长

分配方式--栈:静态和动态分配,静态分配编译器完成:如局部变量的分配。动态分配,如alloc函数,但其由编译器自动释放;堆:只能动态分配,new 需要手动释放。

分配效率--栈:机器系统提供的数据结构,计算机在底层对栈提供支持,效率高;堆:库函数提供,故机制较为复杂,效率偏低。

 

Category: 编程理解 | Tags:
5
14
2014
0

《剑指offer》笔记

1.《剑指offer》 44页 替换空格。题目:给一个字符串"we are young",把其中空格替换为"%20".即变为"we%20are%20young"

   key:先遍历字符串,统计空格数目,然后从后往前替换。在原空间上把空间加大。

2.《剑指offer》 51页 从尾到头打印链表。

 思路一:顺序遍历一遍,并把结点压入栈中,然后从栈中pop出结点

 思路二:递归,每访问一个结点,先递归输出其后面的结点,再输出自身的结点。

3.《剑指offer》55页,由先序遍历和中序遍历构建二叉树。

 key 先序遍历第一个为根。找到根后可以再中序遍历中找到根的左子树和右子树。左右子树再利用相同的思想,于是关键就是递归了。

4.《剑指offer》59页。利用两个栈实现一个队列。

  key 插入则放入stack1中,删除,则从stack2中删除。其中stack2中的元素是从stack1中pop后在push到stack2中的。

5,《剑指offer》65页。实现O(n)时间复杂度的排序算法。

  key 问清楚排序数字的范围,数据的多少。然后具体问题具体分析。题目对几万员工的年龄排序。故可以建立timesOfAge[oldestAge+1]的数据,里面存放每一个岁数的人员个数

6.《剑指offer》66页。旋转数组中最小的数字

 key 用二分查找法可以使时间复杂度降低到log(n)

 

7.《剑指offer》75页斐波那契数列。定义f(n)=f(n-1)+f(n-2)。

解决问题:一只青蛙一次可以跳一级台阶同时也可以跳两级台阶。请问跳n 阶台阶共有多少种跳法。分析,在跳到n阶台阶前有两种情况,1:处在n-1阶台阶上,跳1级到达n阶台阶。2:处在n-2阶台阶上,跳2级到达n接台阶。故f(n)=f(n-1)+f(n-2)

8.《剑指offer》78页二进制数中1的个数

解法1 负数右移最高位补1,防止该现象,用flag=1左移的结果与n做按位与操作。当flag为负数时,按位与操作结束。

解法2 key 把一个整数减1,与原来的数做与运算,则能把左右边的1变为0,则一个整数的二进制表示中有多少个1,就能进行多少次这个操作。

9. 《剑指offer》82页判断一个数是不是2的整数次方。

  key 2的整数次方的二进制表示只有一个1,故可以使用8中的解法2

10.两个整数m和n,计算m需要改变多少个二进制位的个数才能得到n,如10的二进制表示1010,13的二进制表示1101,则要改变3个

 key 做抑或操作后,看二进制中1的个数

11《剑指offer》96 未懂

12《剑指offer》99页 已知一个单向链表的头指针和一个节点的指针,要求在O(1)的时间复杂度内删除这一个节点

  key 常规方法从头遍历找到该节点前驱为O(n)。故通过给出该节点的指针找到该节点的后继节点,然后把值赋值到该节点,删除该节点后一个节点的存储空间。

13《剑指offer》102页 调整整数组顺序使奇数位于偶数的前面

  key p1,p2两个指针(即数字),p1从前往后移,p2从后往前移。前者遇到偶数停下,后者遇到奇数停下。然后交换顺序。直到p1>p2。前者遇到偶数停下,后者遇到奇数停下是根据题目"使奇数位于偶数的前面"设定的。题目不同则停下条件不同。故这儿的条件判断可以写成函数形式,通过函数返回值判断

14《剑指offer》119页 未懂

15《剑指offer》127 顺时针打印矩阵

  key 一圈一圈的打印,要点1:判断该圈是否要打即,(cloumns>starts*2&&rows>starts*2),其中starts初始值为0,每打印一圈,start值自增一次;要点二:每圈有四条路径,即左到右,上到下,右到左,下到上。若该圈需要打,则一定会有第一条路径,接着判断其余三条路径是否需要打印。

16《剑指offer》132 自定义栈数据结构。在该栈中能得到该栈中最小的元素min函数。在该栈中,调用min,push,pop的时间复杂度都为1

key:使用一个辅助栈,每向栈中push一次,辅助栈push入栈中当前最小的元素。栈每pop一次,辅助栈pop出栈顶的元素。这样min值就为辅助栈中的栈顶的值

17《剑指offer》134 给出一个入栈序列,判断某序列是否可能为该栈的弹出顺序。

key:元素逐一入栈,每压入一个元素,判断此时栈顶是否为即将弹出的元素,若是,则弹出该元素,继续入栈;若不是,继续入栈,若元素都入栈完毕,还不是要弹出的非弹出序列,则判断该弹出序列不可能成立

18《剑指offer》 137页。按层打印树。

key。利用队列,每打印一个结点后,再把该结点的左右儿子压入队列,然后再打印队列中的下一个元素

19《剑指offer》140页 判断一个数组,该数组是否可能是某个二叉搜索树的后序遍历序列。

key。二叉树的左子树小于根,右子树大于根,数组的最后一个元素是根。通过sequence[i]<root的条件找到左子树和右子树的分界后,在右子树的数据部分若再发现小于根的数据,则可以return false,再在分隔的左右子树数组中递归调用该函数,return left&&right;

20.《剑指offer》143页  输入一个二叉树和一个整数,打印二叉树中和为该整数的所有路径。该路径只统计从树的根节点往下一直到叶子节点的路径。

key 可以用递归思想,若当前为NULL,且当前和为0,则为有效路径。

21.《剑指offer》147页 复杂链表的复制。该链表除了有一个常规的m_pNext指针指向下一个结点外,还有一个m_pSibling指向链表中的任意结点或者NULL。请实现该复杂链表的复制。

key:由于m_pSlibing任意指向,所以若先复制m_pNext链表后再复制m_pSibling,则需要从表头定位m_pSlibing,故时间复杂度O(N^)。故正解思路如下:将复制的链表逐个插入到原结点后边,则新结点的m_pSlibing应为源节点的m_pSlibing->next。赋值好新结点的m_pSlibing后就可以重新定位p_mNext,得到新的赋值链表

22.《剑指offer》151页 输入一个二叉搜索树,将其转化为一个排序的双向链表。要求不能创建人和新的结点,只能调整数中结点指针的指向。即m_pLeft和m_pRight指向。

key:递归思想,未懂

23.《剑指offer》154页 输入一个字符串,打印该字符串的所有排列

key:把一个问题拆分为和它类似的问题后,就可以用递归的思想了。这个问题可以分为两步,首先求所有可能出现在第一个位置的字符,即把第一个字符和所有的字符交换。然后固定第一个字符,求后面所有字符的排列。显然这就是一个递归的问题。

拓展问题1:输入一个含有8个数字的数组,判断有没有可能把8个数字分别放到正方体的8个顶点上,使得正方体上三组相对的面上的4个顶点的和相等。

key。得到a1,a2,a3,a4,a5,a6,a7,a8这8个数字的所有排列,然后判断有没有一个排列符合a1+a2+a3+a4=a5+a6+a7+a8且a1+a3+a5+a7=a2+a4+a6+a8且a1+a2+a5+a6=a3+a4+a7+a8.(画一个正方体,把8个顶点用a1至a8标上,然后得到上面三组等式)

拓展问题2:在8*8的国际象棋上方8个皇后,使其不能相互攻击,即任意两个皇后不能在同一行、一列、一个对角线上。求符合条件的摆法。

key。ColumnIndex[8]中的第i个数字表示第i行的皇后所在的列好,把这8个元素用0~7初始化,即对ColumnIndex做全排列。所以对数组的两个下标i和j,判断i-j=ColumnIndex[i]-ColumnIndex[j]或者i-j=ColumnIndex[j]-ColumnIndex[i]

24.《剑指offer》163页 数组中出现次数超过一半的数字。

key1:长度过半,那么把数组排序后,若存在该数,那中间的那个数字一定是所要找的数字。step1:排序;step2:再遍历一遍数组,判断该数出现的次数。

key2:不排序,step1:遍历一次数组元素,得到可能的出现次数超过一半的数字,方法如下:当遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,则次数加1;若不同,则次数减1.如果次数为零,则保存下一个数字,并把次数设为1.则若存在概述,则肯定是最后一次把次数设为1的数。step2:再遍历一遍数组,判断该数出现的次数。

25.《剑指offer》167页:输入n个整数,找出其中最小的k个数

key1:若能修改数组中数的排序,则使用partition函数来解决问题。把比K小的数放在K的左边,比K大的数放在K的右边,位于数组左边的k个数就是最小的K个数,注意这K个数不一定是排序了的。该方法会使输入的数组中的数改变顺序

key2:若要求不能修改数组中的数,则顺序遍历一次数组,把数组中读到的最小的k个数放在一个容器中。容器未满k个数时,将读到的数直接加入,满了,则比较容器中最大的数和正在遍历的数。当容器满了需要1.在k个数中找最大的数。2.可能删除该数。3.可能插入新的数字。因此对于二叉树实现这个容器,能在O(logk)实现三个操作,若n个输入数字,总效率为O(n*logk)

26.《剑指offer》170页:连续子数组的最大和。要求时间复杂度为O(n)

保存两个变量,nCurSum和nGreatestSum,若nCurSum小于0了,则其对整体和的增大不可能再有贡献。nCurSum赋值为下一个读入的数,并比较if(nCurSum>nGreatestSum) nGreatestSum = nCurSum;

27.《剑指offer》174页:从1到n出现1的次数。输入一个整数n,求1到n这n个整数的十进制表示中1出现的次数,如输入12,从1到12有1,10,11,12,共出现5次

未懂

28.《剑指offer》177页:把数组排成最小的数。输入一个正整数,把数组中所有的数字拼接起来,并打印所有数字钟最小的一个。如{3,32,321}则打印321323.

key:若求出所有可能的排列,具排列组合,则有n!种排列方法,过于复杂。故考虑另外的方法。给出数字m,n要将mn和nm比较大小。直接的数学方法要考虑拼接了m和n后的溢出问题。故考虑常规的大数问题解决方法:将数字转换成字符串。然后用qsort函数解决,自定义compare函数。

29.《剑指offer》182页:丑数。把只包含银子2,3,5的数称为丑数。从按小到大1500个丑数。如6、8是丑数,但14不是丑数。习惯上把1当成第一个丑数。

key1:从1到x,每个数字都判断是否为丑数,直到判断到第1500个。丑数判断:

while(number%2==0)number/=2;
while(number%3==0)number/=3;
while(number%5==0)number/=5;
return (number==1)?true:false;

key2:基于已经找到的丑数基础上进行乘2、3、5的操作。找到以下丑数。

30.《剑指offer》186页:第一个只出现一次的字符:在字符串中找出第一个只出现一次的字符。如出入“abaccdeff”,则输出'b'.

key1:由于字母只有26,故可以利用哈希表的键值(key)是字符,而值(value)是该字符出现的次数。然后再扫描一次字符串,输出值第一次为1的字母。

31.《剑指offer》189页:数组中的逆序对。在数组中的两个数字,如果前面一个数字大于后面一个数字,则这两个数字组成一个逆序对。输出所有逆序对。

没细看

32.《剑指offer》193页:求两个链表的第一个公共结点。

key1:因为链表的元素只有一个next,故一旦公共结点了,则后面所有的结点都是公共结点。可以遍历两个链表,把两个链表中的元素的地址压入两个不同的栈,然后再从栈中弹出元素。直到找到最后一个地址相同的元素。

key2:先遍历得到两个链表长度;长的链表先走几部;一起走,直到找到相同点。

33.《剑指offer》207页:判断二叉树是否是平衡二叉树。

key1 常规递归遍历方法,二叉树中许多结点多要反复查找

34.《剑指offer》211页:数组中只出现一次的数字。一个整形数组除了两个数字之外,其他的数字都出现了两次。请写程序找到这两个数字

key1.若除了一个数字外,其他数字都出现了两次。则可以异或,最后的结果就是要找的数字

15 《剑指offer》 237页 写一个函数,求两个整数的和,函数体内不得使用+、-、*、/  四则运算符号。

 key 先相加,后进位。相加相当于位运算的异或。进位相当于位运算中的与。只有当与结果等于0才能停止

16 《剑指offer》239页 用c++设计一个不能被继承的类

key:

5
13
2014
0

pcmfs的mkfs分析

在文章最前面说一下mkfs的意义:即在dev设备上建立相应的数据布局。也就是你输入mkfs指令后,要跟上一个设备参数,于是乎,mkfs执行完毕后,就有了常见的数据布局。

在我们这个mkfs函数中,最终数据布局如下

 

 

一:函数流程图

下面是mkfs.pcmfs.c函数流程图

          图1 流程图

解释:

1.根据参数获取blocksize

   在输入mkfs指令时,要输入设备参数。如mkfs.pcmfs /dev/sdb1。该指令就是把/dev/sdb1设备格式化为pcmfs文件系统。Main函数会获取参数的设备名,然后通过get_size函数计算出该设备的字节数。在计算出设备的字节数后,在根据blocksize大小计算出该设备的block总数。    get_size函数获取设备大小主要通过count_block函数实现。基本思想是通过read函数返回值得正负来判断是否越界。该函数先利用二乘的思想来确定该dev的粗略的范围,即n未越界,则下次判断2n是否越界。若2n越界则可判断该设备大小在n与2n之间,粗略判断后在通过在n和2n之间的二分查找确定该设备的具体大小。

2.计算block数目

  在上述操作后获取了该设备的字节数,于是可以通过BLOCKS=get_size(device_name)/blocksize,来得到该设备包含的block数目。

3.初始化superblock以及bitmap所需要的数据结构

    Mkfs的目的是格式化非易失介质,即将非意识介质上文件系统的必要的信息准备好,而superblock以及bitmap的结构是文件系统格式化时写入非易失介质的重要信息,将该信息写入到非意识介质中有两步,第一步是在内存中申请一个对应的空间,将该空间的内容赋值成我们所需要写入非易失介质中的数据;第二步就是通过调用write函数将该数据写入到介质当中。

    mkfs.pcmfs.c文件通过setup_tables函数在内存中准备好要写入非易失介质中的superblock信息以及bitmap区域的信息,其中bitmap有inode的bitmap以及block的bitmap。分别对应着IMAPS以及ZMAPS。

    Superblock的该文件系统整体信息的赋值,如第一个data区域所在的block编号,IMAP、ZMAP所占的block数目的赋值等。在该pcmfs文件系统中inode的bitmap占两个block,block的bitmap占8个block。

    同样在内存中申请IMAPS和ZMAPS所占的空间大小,然后通过memset的函数把该区域的数据置0。

4. 初始化根节点inode的数据结构

    在初始化文件系统时,必须初始化根节点的信息,整个系统才有了开始索引、操作的入口。根节点所指向的数据区域是整个data区的第一个数据块。即inode->i_zone[0] =Super.s_firstdatazone;

    由于根节点是一个目录,所以其数据区其实就是一个个的目录项。每个目录项占16个字节。目录项的定义在头文件Pcmfs_fs.h中。目录项如下

struct pcmfs_dir_entry {

       __u16 inode;

       char name[0];

}

   初始化是需要在目录项中写入两个内容。即当前目录的inode号,以及父目录的inode号。由于为根节点,故父目录的inode号与当前目录inode号实则是一样的。写入的两项内容如下

#define ROOT_INO_STRING "\001\000"

static char root_dentry[BLOCK_SIZE] =

ROOT_INO_STRING ".\0\0\0\0\0\0\0\0\0\0\0\0\0"

ROOT_INO_STRING "..\0\0\0\0\0\0\0\0\0\0\0\0";

其中ROOT_INO_STRING是inode号,".\0\0\0\0\0\0\0\0\0\0\0\0\0"为该inode号对应内容。这里实则填充了两项,表示的是当前目录 . 以及父目录 .. 的inode号。为了方便理解,见下图

图2 dentry结构图

如上图,每个目录的数据区都可理解为上述表,每一个表项有16个字节,前两个表项的文件名是固定的,分别是当前目录对应的inode号以及父目录对应的inode号。上述初始化实则初始前两项。在内存中准备好该数据后,在通过write函数写到非易失介质中。

5.将初始化的数据写到介质中

   该功能更通过write_tables函数实现。该函数主要通过调用write函数将准备好在内存中的超级块的内容以及bitmap的内容写入到介质中。这里指的注意的是write函数要按顺序写。由于pcmfs文件系统的整体结构图如下

图3 pcmfs文件系统结构图

    仔细观察上图。inode bitmap 占2个block;data bitmap占8个block。故该文件系统设计中,理想情况,每个inode索引节点只是的文件占4个block(8/2=4),这样就不会出现data bitmap用完,而inode bitmap和inode table未用完 或者 inode bitmap和inode table用完,而data bitmap未用完的情况。

   故在调用write函数,要按顺序写入,即先写superblock,然后写bitmap区域。因为write函数写的区域是设备上当前指针所指向的区域。在写过程中,指针后移,故要按顺序写入。

   另外注意一点的是图3中若block大小为1k,(1024B),则inode bitmap的起始block为第3个block。若为blokc大小大于1k,如为2k,3k等等,则预留字节和super block的字节都可以写在第一个block中,即inode bitmap的起始block为第2个block

   至此,设备的mkfs工作完毕。

 

Category: 文件系统 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com