存档在 ‘Linux下C编程’ 分类

miniLZO的基本使用

2012年6月19日

miniLZO是一种轻量级的压缩和解压缩库,它是基于LZO压缩和解压缩算法实现的。LZO虽然功能强大,但是编译后的库文件较大,而minilzo编译后的库则小于5kb,因此miniLZO为那些仅需要简单压缩和解压缩功能的程序而设计。

实现miniLZO的源码很简单,包含如下文件:

edsionte@virtualPC ~/minilzo-2.06 $ tree
.
├── COPYING
├── lzoconf.h
├── lzodefs.h
├── Makefile
├── minilzo.c
├── minilzo.h
├── README.LZO
└── testmini.c

在程序中加入miniLZO压缩和解压缩功能的方法很简单,只需将源文件minilzo.c和头文件lzoconf.h,lzodefs.h和minilzo.h拷贝到源文件目录下,在源代码中加入头文件minilzo.h,并且在编译时加入miniloz.c。

如何在源程序中具体使用miniLZO的压缩和解压缩功能?下面将给出一个简单的实例程序来说明使用方法。该程序所演示的功能是:首先利用minilzo提供的压缩API将指定文件的前1024字节进行压缩,并将压缩后的内容保存在cfile文件中;然后将该压缩文件的内容再进行解压缩,并存入另一个文件dcfile中。

正如上面所描述的那样,要使用miniLZO,必须加入头文件minilzo.h。

#include "minilzo.h"

#define MAX_LEN 1024

#define HEAP_ALLOC(var,size) \
    lzo_align_t __LZO_MMODEL var [ ((size) + (sizeof(lzo_align_t) - 1)) / sizeof(lzo_align_t) ]

//the wkmem is used for compressed
static HEAP_ALLOC(wkmem, LZO1X_1_MEM_COMPRESS);

除此之外,定义一个宏HEAP_ALLOC,它为压缩提供一个内存空间。要使用压缩或解压缩功能,必须先通过lzo_init()对miniLZO对应的库进行初始化。

int main()
{
	int fd;
	char *srcbuffer = NULL, *destbuffer = NULL;
	lzo_uint inlen = MAX_LEN;
	lzo_uint outlen = 0;
	lzo_uint newlen = 0;

	//init the lzo lib
	if (lzo_init() != LZO_E_OK) {
		printf("lzo_init error.\n");
		return -1;
	}

打开要压缩的文件,将数据读入内存的缓冲区中。

	if ((fd = open("./minilzo.c", O_RDONLY)) < 0) {
		printerror(__LINE__, errno, "open");
	}

	//alloc the src buffer and dest buffer
	if ((srcbuffer = malloc(MAX_LEN)) < 0) {
		printerror(__LINE__, errno, "malloc");
	}
	if ((destbuffer = malloc(MAX_LEN)) < 0) {
		printerror(__LINE__, errno, "malloc");
	}
	memset(srcbuffer, 0, MAX_LEN);
	memset(destbuffer, 0, MAX_LEN);

	if (read(fd, srcbuffer, MAX_LEN) < 0) {
		printerror(__LINE__, errno, "read");
	}

利用压缩接口lzo1x_1_compress()将srcbuffer中长度为inlen的数据进行压缩,并将压缩后的数据保存在destbuffer中,其压缩数据的长度返回到值结果参数outlen中。其中wkmem为压缩数据时所需要的内存空间。

	int ret;
	if ((ret = lzo1x_1_compress(srcbuffer, inlen, destbuffer, &outlen, wkmem)) != LZO_E_OK) {
		printf("compress error:%d.\n", ret);
		return -1;
	} else {
		printf("compress %lu bytes into %lu bytes.\n", (unsigned long)inlen, (unsigned long)outlen);
	}

	if (outlen >= inlen) {
		printf("This block contains incompressible data.\n");
		return 0;
	}

下面将压缩后的数据保存到新文件cfile中。

	int cfd;
	if ((cfd = open("./cfile", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR)) < 0) {
		printerror(__LINE__, errno, "open");
	}

	if (write(cfd, destbuffer, outlen) < 0) {
		printerror(__LINE__, errno, "write");
	}

接着进行解压缩过程,利用lzo1x_decompress()则可以完成。各个参数的意义与压缩时相同,只不过要调整源数据和目的数据之间的方向。

	memset(srcbuffer, 0, MAX_LEN);
	if ((ret = lzo1x_decompress(destbuffer, outlen, srcbuffer, &newlen, NULL)) != LZO_E_OK) {
		printf("decompress error:%d.\n", ret);
		return -1;
	} else if ( inlen == newlen) {
		printf("decompress %lu bytes into %lu bytes.\n", (unsigned long)outlen, (unsigned long)newlen);
	}

最后将解压缩的数据写入新文件对此dcfile中。

	int dcfd;
	if ((dcfd = open("./dcfile", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR)) < 0) {
		printerror(__LINE__, errno, "open");
	}

	if (write(dcfd, srcbuffer, newlen) < 0) {
		printerror(__LINE__, errno, "write");
	}

	close(fd);
	close(cfd);
	close(dcfd);
	printf("compress success!\n");
	return 0;
}

上述为源代码,如果使用make编译文件,则Makefile为:

edsionte@virtualPC ~/edsionte-code/lzo $ cat Makefile
target:=testlzo
source:=testlzo.c minilzo.c

default:
	gcc -o $(target) $(source)
clean:
	rm $(target)

执行后,可查看两个文件的大小差异:

edsionte@virtualPC ~/edsionte-code/lzo $ ls -l cfile dcfile
-rw------- 1 edsionte edsionte  265  6月 19 10:23 cfile
-rw------- 1 edsionte edsionte 1024  6月 19 10:23 dcfile

可以看出minilzo的压缩率大约为1:4。

Linux内存管理中的slab分配器

2012年5月18日

Linux内核中基于伙伴算法实现的分区页框分配器适合大块内存的请求,它所分配的内存区是以页框为基本单位的。对于内核中小块连续内存的请求,比如说几个字节或者几百个字节,如果依然分配一个页框来来满足该请求,那么这很明显就是一种浪费,即产生内部碎片(internal fragmentation)

为了解决小块内存的分配,Linux内核基于Solaris 2.4中的slab分配算法实现了自己的slab分配器。除此之外,slab分配器另一个主要功能是作为一个高速缓存,它用来存储内核中那些经常分配并释放的对象。

1.slab分配器的基本原理

slab分配器中用到了对象这个概念,所谓对象就是内核中的数据结构以及对该数据结构进行创建和撤销的操作。它的基本思想是将内核中经常使用的对象放到高速缓存中,并且由系统保持为初始的可利用状态。比如进程描述符,内核中会频繁对此数据进行申请和释放。当一个新进程创建时,内核会直接从slab分配器的高速缓存中获取一个已经初始化了的对象;当进程结束时,该结构所占的页框并不被释放,而是重新返回slab分配器中。如果没有基于对象的slab分配器,内核将花费更多的时间去分配、初始化以及释放一个对象。

slab分配器有以下三个基本目标:

1.减少伙伴算法在分配小块连续内存时所产生的内部碎片;

2.将频繁使用的对象缓存起来,减少分配、初始化和释放对象的时间开销。

3.通过着色技术调整对象以更好的使用硬件高速缓存;

2.slab分配器的结构

slab分配器为每种对象分配一个高速缓存,这个缓存可以看做是同类型对象的一种储备。每个高速缓存所占的内存区又被划分多个slab,每个slab是由一个或多个连续的页框组成。每个页框中包含若干个对象,既有已经分配的对象,也包含空闲的对象。slab分配器的大致组成图如下:

每个高速缓存通过kmem_cache结构来描述,这个结构中包含了对当前高速缓存各种属性信息的描述。所有的高速缓存通过双链表组织在一起,形成高速缓存链表cache_chain。每个kmem_cache结构中并不包含对具体slab的描述,而是通过kmem_list3结构组织各个slab。该结构的定义如下:

struct kmem_list3 {
        struct list_head slabs_partial;
        struct list_head slabs_full;
        struct list_head slabs_free;
        unsigned long free_objects;
        unsigned int free_limit;
        unsigned int colour_next;
        spinlock_t list_lock;
        struct array_cache *shared;
        struct array_cache **alien;
        unsigned long next_reap;
        int free_touched;
};

可以看到,该结构将当前缓存中的所有slab分为三个集合:空闲对象的slab链表slabs_free,非空闲对象的slab链表slabs_full以及部分空闲对象的slab链表slabs_partial。每个slab有相应的slab描述符,即slab结构,它的定义如下:

struct slab {
        struct list_head list;
        unsigned long colouroff;
        void *s_mem;
        unsigned int inuse;
        kmem_bufctl_t free;
        unsigned short nodeid;
};

slab描述符中的list字段标明了当前slab处于三个slab链表的其中一个。我们将上述的slab分配器进行细化,可以得到下面的结构图:

3.高速缓存的分类

slab高速缓存分为两大类,普通高速缓存和专用高速缓存。普通高速缓存并不针对内核中特定的对象,它首先会为kmem_cache结构本身提供高速缓存,这类缓存保存在cache_cache变量中,该变量即代表的是cache_chain链表中的第一个元素;另一方面,它为内核提供了一种通用高速缓存。专用高速缓存是根据内核所需,通过指定具体的对象而创建。

3.1 普通高速缓存

slab分配器中kmem_cache是用来描述高速缓存的结构,因此它本身也需要slab分配器对其进行高速缓存。cache_cache变量保存着对高速缓存描述符的高速缓存。

static struct kmem_cache cache_cache = {
        .batchcount = 1,
        .limit = BOOT_CPUCACHE_ENTRIES,
        .shared = 1,
        .buffer_size = sizeof(struct kmem_cache),
        .name = "kmem_cache",
};

slab分配器所提供的小块连续内存的分配是通过通用高速缓存实现的。通用高速缓存所提供的对象具有几何分布的大小,范围为32到131072字节。内核中提供了kmalloc()和kfree()两个接口分别进行内存的申请和释放。

3.2 专用高速缓存

内核为专用高速缓存的申请和释放提供了一套完整的接口,根据所传入的参数为具体的对象分配slab缓存。

高速缓存的申请和释放

kmem_cache_create()用于对一个指定的对象创建高速缓存。它从cache_cache普通高速缓存中为新的专有缓存分配一个高速缓存描述符,并把这个描述符插入到高速缓存描述符形成的cache_chain链表中。kmem_cache_destory()用于撤销一个高速缓存,并将它从cache_chain链表上删除。

slab的申请和释放

kmem_cache_alloc()在其参数所指定的高速缓存中分配一个slab。相反,kmem_cache_free()在其参数所指定的高速缓存中释放一个slab。

内部排序算法小结

2012年3月20日

内部排序算法主要分为插入类排序、交换类排序和选择类排序,它们在性能上的差异主要体现在时间复杂度、空间复杂度和稳定性。各种排序算法都会进行元素间的比较和移动,时间复杂度主要由整个排序过程中的比较次数和移动次数决定。空间复杂度体现在除了待排序记录本身所占的空间,排序过程中占用了多少辅助空间。

1.插入类排序

直接插入排序

如果待排序记录之间是顺序排列,此时整个排序过程中元素比较的次数为n-1次,移动次数为0次。如果待排序记录之间是逆序排列,第i趟排序比较次数为i,移动的次数为i+1,其中i的范围是2到n。因此,整个排序过程中元素的比较次数为(n+2)(n-1)/2,移动次数为(n+4)(n-1)/2。

直接插入排序算法的时间复杂度为O(n^2),空间复杂度为O(1)。从直接插入排序算法的实现可以发现,位置靠后的记录是不可能插入到相同大小的记录之前的,因此直接插入排序算法是稳定的。

折半插入排序

折半插入排序算法与直接插入排序算法相比,每趟的比较次数为log2^i,因此整体的比较次数为O(nlog2^n)。但是折半算法的移动次数较直接插入算法并未改变。

折半算法的时间复杂度仍然是O(n^2),空间复杂度为O(1)。从算法实现可以看出折半插入排序算法是稳定的。

希尔排序

希尔排序利用了当“待排序记录n较小,序列基本有序”时使用直接插入算法性能较好这一特点而改进。希尔排序算法的时间复杂度为O(n^1.5),空间复杂度为O(1),它是不稳定的排序算法。举反例如下:待排序序列为{2,4,1,(2)},设delta[1]=2,则一趟排序后序列为{1,(2),2,4}。

2.交换类排序

冒泡排序

当待排序记录逆序排列时,每趟冒泡算法进行i次比较和3i次交换(两个元素交换),i的范围是1到n-1。因此总的比较次数为n(n-1)/2,总的移动次数为3n(n-1)/2。冒泡排序算法的时间复杂度为O(n^2),空间复杂度O为(1),是一种稳定的排序算法。

快速排序

快速排序最好的情况是每次将待排序的记录都等分为二,此时时间复杂度为O(nlog2^n)。最坏情况下,待排序记录已经排好序,此时总共的比较次数为n(n-1)/2,此时时间复杂度为O(n^2)。

快速排序的平均复杂度为O(nlog2^n),空间复杂度为O(log2^n),它是一种不稳定的排序算法。举反例如下:待排序序列为{3,2,(2)},则一趟排序后记录为{(2),2,3}。

3.选择类排序

简单选择排序

无论待排序记录的初始排列如何,简单选择排序总的比较次数总为n(n-1)/2,因为它每趟比较的次数为n-i,i的范围从1到n-1。最好的情况下,简单选择排序算法的移动次数为0,最坏情况下移动的3(n-1)。

简单选择排序算法的时间复杂度为O(n^2),空间复杂度为O(1),它是不稳定的排序算法。举反例如下:待排序记录为{6,8,(6),2,7},一趟排序后记录为{2,8,(6),6,7},二趟排序后记录为{2,(6),8,6,7}。

堆排序

堆排序的时间复杂度为O(nlog2^n),空间复杂度为O(1),它是不稳定的排序算法。

4.归并排序

归并排序的时间复杂度为O(nlog2^n),空间复杂度为O(n),它是稳定的排序算法。

5.总结

综上所述,内部排序算法的时间复杂度、空间复杂度和稳定性总结如下表:

1.直接插入排序、折半插入排序、冒泡排序和简单选择排序合称为简单排序,它们的时间复杂度均为O(n^2),空间复杂度为O(1)。稳定性方面只有简单选择排序是不稳定的排序算法。简单排序只适合n较小的情况。

2.当待排序记录基本有序时,直接插入排序是最佳的排序算法。它常与快速排序和归并排序等结合使用,因为这些算法会将整个打排序记录划分为若干个子记录,这些子记录数量较小而且基本有序。

3.排序性能较好的有希尔排序、快速排序、堆排序和归并排序,除了希尔排序的时间复杂度为O(n^1.5),其他排序算法均为O(nlogn)。虽然快速排序最坏情况下时间性能下降为O(n^2),但是就平均性能而言快速排序算法是最好的。堆排序和归并排序的性能比较稳定,当n比较大时,归并排序的性能比堆排序要好,但是它需要的辅助空间却为O(n)。

4.所有的排序算法中,不稳定的算法有简单选择排序、希尔排序、快速排序和堆排序。性能较好的排序算法中只有归并排序是稳定的。排序是按记录的主关键字进行的,此时不用考虑排序方法的稳定性。如果排序是按记录的次关键字进行的, 则应充分考虑排序方法的稳定性。

伙伴算法的实现-分配页框

2012年3月7日

内核中alloc_pages系列页框分配函数都是基于伙伴算法实现的,这些函数最终都会调用伙伴算法的入口函数buffered_rmqueue()。

Linux内核管理物理内存有三种方式,其一就是经典的伙伴算法。但是伙伴算法分配物理内存的基本单位是页框,因此内核又引入了slab机制,基于此机制实现的物理内存分配器可以快速有效的分配小于页框的物理内存,并且可以有效避免内部碎片。另外,内核常常会申请单个页框大小的物理内存,因此内核又引入了per-CPU机制,该机制专门用于快速分配单个页框。

1.__rmqueue()

其实buffered_rmqueue()函数仍然没有进行真正的页框分配,该函数首先判断分配阶是否为0,如果是则启用per-CPU机制来分配物理内存,否则调用__rmqueue()。

static struct page *__rmqueue(struct zone *zone, unsigned int order,
                                                int migratetype)
{
        struct page *page;
retry_reserve:
        page = __rmqueue_smallest(zone, order, migratetype);

        if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
                page = __rmqueue_fallback(zone, order, migratetype);

                if (!page) {
                        migratetype = MIGRATE_RESERVE;
                        goto retry_reserve;
                }
        }

        trace_mm_page_alloc_zone_locked(page, order, migratetype);
        return page;
}

传递到此函数中的zone表示伙伴算法将从该内存管理区中分配页框,order即分配阶,migratetype表示迁移类型。该函数首选__rmqueue_smallest()进行内存分配,如果在指定的迁移类型上分配失败后,再选用其他备用的迁移列表进行内存分配,该过程通过__rmqueue_fallback()完成。总之内核总是在竭尽全力保证满足分配内存的请求。

2.__rmqueue_smallest()

该函数的实现比较简单,从当前指定的分配阶到最高分配阶依次进行遍历。在每次遍历的分配阶链表中,根据参数migratetype选择正确的迁移队列。根据以上的限定条件,当选定一个页框块链表后,只要该链表不为空,就说明可以分配该分配阶对应的页框块。

一旦选定在当前遍历的分配阶链表上分配页框,那么就通过list_entry()将该页框块从链表上移除。然后将页框块首页框的PG_buddy标志删除,删除该标志说明当前页框块已经不属于伙伴链表。并且将该首页框描述符中的priveate置0,该字段中本来保存的是其所处页框块的分配阶。以上这个过程通过rmv_page_order()完成。此外,还要更新页框块链表nr_free的值。

static inline
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
                                                int migratetype)
{
        unsigned int current_order;
        struct free_area * area;
        struct page *page;

        for (current_order = order; current_order < MAX_ORDER; ++current_order) {
                area = &(zone->free_area[current_order]);
                if (list_empty(&area->free_list[migratetype]))
                        continue;

                page = list_entry(area->free_list[migratetype].next, struct page, lru);
                list_del(&page->lru);
                rmv_page_order(page);
                area->nr_free--;
                expand(zone, page, order, current_order, area, migratetype);
                return page;
        }

        return NULL;
}

static inline void rmv_page_order(struct page *page)
{
        __ClearPageBuddy(page);
        set_page_private(page, 0);
}

__rmqueue_smallest()内部还有一个重要的函数expand()。进入该函数的条件是当所申请的分配阶order小于当前选中的分配阶current_order,也就是说指定的分配阶链表中没有空闲的页框块,只能选用较大的页框块。因此,expand()必须按照伙伴算法的分裂原理将比较大的页框块分割成较小的块。

3.expand()

分裂函数的实现也是显而易见的,它完全遵照伙伴算法的分裂原理。这里有两个分配阶,一个是申请页框时指定的low,一个是在上级函数中遍历时所选定的high。该函数从high分配阶开始递减向low遍历,也就是从较大的页框块开始依次分裂。

比如high为4,而low为2。那么第一遍历时,将大小为16(分配阶为4)的页框块一份为2。通过list_add()将后面的8个连续页框块加入下级链表(分配阶为3),下级链表通过将area指针自减即可得到,后8个页框块的指针也通过page+size获得,而page仍然指向最初的页框块首页框。此时还要对分配阶为3的链表更新nr_free,以及通过set_page_order()对后8个页框块设置一些标志。

第二次遍历将前面8个页框块继续一分为二,将后4个页框块加入area所指向的下级链表(分配阶为2)。第三次遍历时,循环条件已经不再满足,因此返回前4个页框块首页框的描述符地址page。

static inline void expand(struct zone *zone, struct page *page,
        int low, int high, struct free_area *area,
        int migratetype)
{
        unsigned long size = 1 << high;
         while (high > low) {
                area--;
                high--;
                size >>= 1;
                VM_BUG_ON(bad_range(zone, &page[size]));
                list_add(&page[size].lru, &area->free_list[migratetype]);
                area->nr_free++;
                set_page_order(&page[size], high);
        }
}

static inline void set_page_order(struct page *page, int order)
{
        set_page_private(page, order);
        __SetPageBuddy(page);
}

目录操作API应用之ls命令的实现

2011年10月27日

Linux系统下有一系列对目录操作的API,如果单一的去学习这些API那么学习过程无疑是单调的。本文以实现Linux下ls命令为例,简单说明与目录操作相关的API。

1.获取文件名

获取一个指定目录下的文件名列表是ls命令最基本的功能。对于一个普通文件而言,读文件中数据的步骤是:open()文件,read()文件,close()文件。对于目录文件而言,它包含的内容就是若干个目录项,一个目录项即对应该目录下的一个文件。因此读目录的过程与普通文件类似,不过Linux下的目录是一种特殊的文件,因此有一组针对目录操作的API,具体如下:

       #include < sys/types.h >
       #include < dirent.h >

       DIR *opendir(const char *name);
       struct dirent *readdir(DIR *dirp);
       int closedir(DIR *dirp);

读目录之前必须用opendir()打开目录,它返回一个DIR *类型的目录流,它类似于文件描述符。接着使用readdir()读取该目录流中的目录项,该函数每成功调用一次则返回一个struct dirent类型的目录项。当打开某个目录后,第一次调用该函数则返回当前目录下第一个文件的信息,第二次调用则返回第二个文件的信息,以此类推。当读完该目录下的所有文件后返回NULL。由此可见,要读取指定目录下的所有目录项,则需要一个循环的过程。描述目录项的结构体dirent描述如下:

          struct dirent {
               ino_t          d_ino;       /* inode number */
               off_t          d_off;       /* offset to the next dirent */
               unsigned short d_reclen;    /* length of this record */
               unsigned char  d_type;      /* type of file; not supported
                                              by all file system types */
               char           d_name[256]; /* filename */
           };

目录项与目录是两个完全不同的概念。比如在/home/edsionte/test/下有一个目录文件mydir和一个文本文件mytxt.txt,那么该目录下就包含两个目录项,分别描述mydir和mytxt.txt。但是通过这两个目录项并不能直接就访问到对应文件,因为目录项只用于描述当前目录下的文件名等信息。如果要访问这两个文件,还必须获得/、home/、edsionte/和test/这几个目录项。由此可见,目录项是用来方便搜索文件的结构。

当不再使用某个已打开的目录时,使用closedir()关闭该目录。通过上述三个API就可以实现获取指定目录下文件名的功能。伪代码实现方法如下:

int get_file_name(char *path)
{
	DIR *mydir;
	struct dirent *myentry;

	if ((mydir = opendir(path)) == NULL) {
		do_error();
	}

	while ((myentry = readdir(mydir)) != NULL) {
		printf("%s\t", myentry->d_name);
	}
	printf("\n");
	closedir(mydir);

	return 0;
}

按照这种方式实现的ls命令只能显示path目录下的文件名称,仅此而已。

2.获取文件列表

获取指定目录下文件名对于ls命令来说还远远不够,我们需要获取每个文件名的属性信息,也就是实现类似ls -l的功能。要实现该功能就必须使用stat族函数,该函数会将文件的信息返回到传入的参数buf中,buf是struct stat类型。

       #include < sys/types.h >
       #include < sys/stat.h >
       #include < unistd.h >

       int stat(const char *path, struct stat *buf);
       int fstat(int fd, struct stat *buf);
       int lstat(const char *path, struct stat *buf);

          struct stat {
               dev_t     st_dev;     /* ID of device containing file */
               ino_t     st_ino;     /* inode number */
               mode_t    st_mode;    /* protection */
               nlink_t   st_nlink;   /* number of hard links */
               uid_t     st_uid;     /* user ID of owner */
               gid_t     st_gid;     /* group ID of owner */
               dev_t     st_rdev;    /* device ID (if special file) */
               off_t     st_size;    /* total size, in bytes */
               blksize_t st_blksize; /* blocksize for file system I/O */
               blkcnt_t  st_blocks;  /* number of 512B blocks allocated */
               time_t    st_atime;   /* time of last access */
               time_t    st_mtime;   /* time of last modification */
               time_t    st_ctime;   /* time of last status change */
           };

得到了每个文件的stat结构,就可以按照需求显示文件的属性信息。对于stat族函数,不管使用哪一个都必须获得文件的绝对路径。在本文第一部分中通过读取指定目录下的目录项,只能通过d_name字段获得目录项名字,因此使用stat函数之前必须合成每个文件的绝对路径。获取文件列表的实现方法如下:

int get_file_name(char *path)
{
	DIR *mydir;
	struct dirent *myentry;

	if ((mydir = opendir(dirpath)) == NULL) {
		do_error();
	}

	while ((myentry = readdir(mydir)) != NULL) {
		printf("%s\t", myentry->d_name);
		strcat(tmpbuf, dirpath);
		strcat(tmpbuf, myentry->d_name);
		struct stat myfstat;
		if (stat(tmpbuf, &myfstat) == -1) {
			do_error();
		}
		print_file_stat(myfstat);
		printf("\n");
		memset(tmpbuf, len);
	}
	closedir(mydir);

	return 0;
}

其中,print_file_stat函数可以按照你的具体需求显示当前文件的各种属性,比如关于文件的各种时间,文件大小等。本质上就是将dirent结构中的相关字段打印。

3. 是否可以切换目录

Linux下每个文件都有读写执行(RWX)三个权限。对于普通文件来说,R权限代表可以读文件,W权限代表可以对文件进行修改,X权限代表可以执行该文件(与是否执行成功无关)。对于目录而言,读写执行的含义如下:

R:可以读取该目录下的文件名

W:可以增加、删除、修改或移动该目录下的文件名

X:可以切换到该目录下

这里比较不易理解的是X权限,它并不是指目录具有“执行”权限,而是表示当前进程可以切换到该目录下。

如果某个用户对一个目录只有R权限,那么这个用户只能ls到该目录下的文件名,甚至连ls -l都不能成功执行。通过上述文件列表的实现过程可知,如果要获取每个文件的属性信息则必须能够成功访问到该文件的绝对路径。但是现在没有X权限,进程并不能切换到该目录下,因此也就访问失败了。与此类似,如果要修改一个目录,没有X权限也是不能成功执行的。如果某个用户对一个目录只有执行权限,那么除了可以切换到该目录外,什么也做不了。

根据此原理,我们对ls命令增加一个新的功能:判断当前执行ls命令的用户是否可以切换到该目录下子目录。我们并不依次去判断子目录的权限,通过chdir()就可以完成。

       
       #include < unistd.h >
       int chdir(const char *path);

chdir()用于将当前工作目录切换到path指定的目录,如果切换成功则返回0,否则返回-1。据此,修改后的ls命令实现方法如下:

int get_file_name(char *path)
{
	DIR *mydir;
	struct dirent *myentry;

	if ((mydir = opendir(dirpath)) == NULL) {
		do_error();
	}

	while ((myentry = readdir(mydir)) != NULL) {
		printf("%s\t", myentry->d_name);
		strcat(tmpbuf, dirpath);
		strcat(tmpbuf, myentry->d_name);
		struct stat myfstat;
		if (stat(tmpbuf, &myfstat) == -1) {
			do_error();
		}
		print_file_stat(myfstat);

		if (chdir(tmpbuf) == -1) {
			print_no_chdir();
		} else {
			print_chdir();
		}
		printf("\n");
		memset(tmpbuf, len);
	}
	closedir(mydir);

	return 0;
}

如果切换成功,通过print_no_chdir()打印可切换标志,否则打印不可切换标志。上述的ls实现方式只是基本模型,感兴趣的童鞋可以在此基础上加以改进。

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key