分类目录归档:C/C++编程

Linux下C/C++编程相关的技术文章

centos6命令行下安装kvm虚拟机

之前在傲冠的时候,有玩过xen,因为现在这家公司用的是云主机,所以今天抽时间来搞一下kvm的虚拟机。

本文章基于centos 6.2 x64进行
1、首先是加载kvm模块
查看kvm及kvm_intel(或kvm_amd)驱动是否已经加载

lsmod|grep kvm

如果出现下面的字样,表示驱动已经加载上了

kvm_intel              52570  6 
kvm                   314739  1 kvm_intel

注:如果是amd的处理器,这儿就会是kvm_amd
如果没有出现上面的字样,加载驱动

modprobe kvm
modprobe kvm_intel

2、安装虚拟机管理的接口管理程序
不管是xen还是kvm,也不管是盛大云还是阿里云,所有使用云主机的提供商,管理虚拟机的统一接口,一定是使用的libvirt,这是一个上层的虚拟机管理服务,基本上所有的虚拟机hypervisor都会保持对libvirt的兼容(kvm、xen、xenserver、vmware、hyper-v、virtualbox、openvz等等),其能够对虚拟机进行各种控制(包括创建、开机、关机、删除、暂停)。

yum  install  libvirt  -y
chkconfig  --level 35 libvirtd on

/etc/init.d/libvirtd start

3、配置虚拟机运行的网络环境(假设物理网卡设备的名称为【eth0】)
一、桥接模式
安装网卡桥接的管理软件

yum install bridge-utils -y
cd /etc/sysconfig/network-scripts
cp ifcfg-eth0 ifcfg-br0
vim ifcfg-eth0

修改ifcfg-br0中的下面两个参数

DEVICE="br0"
TYPE="Bridge"
IPADDR=192.168.1.17  # 这个要与eth0中设置的ip地址相同
PREFIX=24
GATEWAY=192.168.1.1

修改ifcfg-eth0中的下面两个参数

BRIDGE="br0"
IPADDR=192.168.1.17 # 这个要与br0中设置的ip地址相同
PREFIX=24
GATEWAY=192.168.1.1

重启网络服务

/etc/init.d/network restart
brctl  show

就可以看到下面这样的桥接网络数据了

[root@yanxi vm]# brctl show
bridge name     bridge id               STP enabled     interfaces
br0             8000.d4bed9e46af2       yes             eth0
                                                        vnet0
                                                        vnet1
virbr0          8000.52540078bd93       yes             virbr0-nic

二、NAT模式
暂无
4、命令行下安装虚拟机
假设你已经搭建好了http或ftp服务,可以通过pxe方式匿名安装系统(本地以ftp为例,服务器地址为:ftp://192.168.1.118)

mount -o loop  centos62.iso  /data/software/vm/centos62

挂载的centos镜像的地址为/data/software/vm/centos62,其中/data/software为ftp服务器匿名登陆的家目录
创建虚拟机磁盘镜像(10G),安装虚拟机

dd if=/dev/zero  of=/data/vm/centos62_1.img bs=4k count=2500000
virt-install --name centos62_1 --ram 512 --vcpus 1 --os-type linux --os-variant rhel6 --disk path=/data/vm/centos62_1.img --network bridge=br0 --extra-args "console=tty0 console=ttyS0,115200n8 serial" --location ftp://192.168.1.118/vm/centos62

然后按照正常的步骤就可以安装系统了
注意:
1、–extra-args后面的console相关的参数一定需要带上,否则不能在命令行下安装系统。
2、另外rhel系的系统通过网络安装,不能自定义系统分区,这是一个很SB的设计,不如debian系。
========================全文完=======================

redis的epoll网络模型实例——redis源码分析之网络

linux网络编程之epoll学习
http://www.cxphp.com/?p=224

对redis中使用的网络框架结构,相信很多文章都写了、也分析了,但是很少有抽取其结构出来的实作的。
本文根据上面的例子修改而成,使整个类似redis的epoll的读、写流转起来。
本epoll模型是根据redis中使用的epoll网络事件模型抽取而来。
socket.h

#ifndef _SOCKET_H_
#define _SOCKET_H_

#include 
#include 
#include 
#include 
#include 

#define EV_READ 1
#define EV_WRITE 2
#define EV_SIZE (1024 * 10)

typedef void procEvent(int fd, void *argv);

typedef struct fileEvent
{
	procEvent *readProc;
	procEvent *writeProc;
	void *argv;
}FileEvent;

typedef struct firedEvent
{
	int fd;
	int mask;
}FiredEvent;

typedef struct _event
{
	FileEvent fe[EV_SIZE];
	struct epoll_event events[EV_SIZE];
	FiredEvent fired[EV_SIZE];
	int epfd;
	unsigned char running;
}EventLoop;

int setnonblocking(int fd);
int createSocket(char *host, unsigned short port);
int createEvent(EventLoop *el, int fd);
int enableEventIn(EventLoop *el, int fd, procEvent *proc);
int disableEventIn(EventLoop *el, int fd);
int enableEventOut(EventLoop *el, int fd, procEvent *proc);
int disableEventOut(EventLoop *el, int fd);
int deleteEvent(EventLoop *el, int fd, short mask);
int dispatchEvent(EventLoop *el);
void stopEvent(EventLoop *el);
EventLoop *initEvent();

#endif

socket.c

#include 
#include "socket.h"

int setnonblocking(int fd)
{
	if(fcntl(fd, F_SETFL, fcntl(fd, F_GETFL) | O_NONBLOCK) == -1)
		return -1;

	return 0;
}


int createSocket(char *host, unsigned short port)
{
	struct sockaddr_in addr;
	int fd = socket(AF_INET, SOCK_STREAM, 0);
	if(fd == -1)
		return -1;


	if(setnonblocking(fd) == -1)
	{
		close(fd);
		return -1;
	}


	int reuse_addr = 1;
	setsockopt(fd, SOL_SOCKET, SO_REUSEADDR, &reuse_addr, sizeof(reuse_addr));

	addr.sin_family = AF_INET;
	addr.sin_port	= htons(port);
	addr.sin_addr.s_addr = inet_addr(host);
	if(bind(fd, (struct sockaddr*)&addr, sizeof(struct sockaddr)) == -1)
	{
		close(fd);
		return -1;
	}

	if(listen(fd, 512) == -1)
	{
		close(fd);
		return -1;
	}

	return fd;
}

EventLoop *initEvent()
{
	EventLoop *el = malloc(sizeof(EventLoop));
	int i = 0;
	el->epfd = epoll_create(1024);
	if(el->epfd == -1)
	{
		free(el);
		return NULL;
	}

	for(i = 0; i < EV_SIZE; ++i)
	{
		el->events[i].events = 0;
	}

	return el;
}


int createEvent(EventLoop *el, int fd)
{
	struct epoll_event ee;

	ee.events = 0;
	ee.data.fd = fd;


	if(epoll_ctl(el->epfd, EPOLL_CTL_ADD, fd, &ee) == -1)
		return -1;

	return 0;
}

int enableEventIn(EventLoop *el, int fd, procEvent *proc)
{
	struct epoll_event *pee = el->events + fd;
	pee->events |= EPOLLIN;
	pee->data.fd = fd;
	el->fe[fd].readProc = proc;
	if(epoll_ctl(el->epfd, EPOLL_CTL_MOD, fd, pee) == -1)
			return -1;

	return 0;
}

int disableEventIn(EventLoop *el, int fd)
{
	struct epoll_event *pee = el->events + fd;
	pee->events &= ~EPOLLIN;
	pee->data.fd = fd;
	if(epoll_ctl(el->epfd, EPOLL_CTL_MOD, fd, pee) == -1)
			return -1;

	return 0;
}

int enableEventOut(EventLoop *el, int fd, procEvent *proc)
{
	struct epoll_event *pee = el->events + fd;
	pee->events |= EPOLLOUT;
	pee->data.fd = fd;
	el->fe[fd].writeProc = proc;
	if(epoll_ctl(el->epfd, EPOLL_CTL_MOD, fd, pee) == -1)
			return -1;

	return 0;
}

int disableEventOut(EventLoop *el, int fd)
{
	struct epoll_event *pee = el->events + fd;
	pee->events &= ~EPOLLOUT;
	pee->data.fd = fd;
	if(epoll_ctl(el->epfd, EPOLL_CTL_MOD, fd, pee) == -1)
			return -1;

	return 0;
}


int deleteEvent(EventLoop *el, int fd, short mask)
{
	struct epoll_event ee;
	ee.events = 0;
	ee.data.fd = fd;

	if(mask & EV_READ)
	{
		ee.events &= ~EPOLLIN;
		el->fe[fd].readProc = NULL;
	}

	if(mask & EV_WRITE)
	{
		ee.events &= ~EPOLLOUT;
		el->fe[fd].writeProc = NULL;
	}

	if(epoll_ctl(el->epfd, EPOLL_CTL_MOD, fd, &ee) == -1)
		return -1;

	return 0;
}

int dispatchEvent(EventLoop *el)
{
	int nfds, i;
	el->running = 1;
	while(el->running)
	{
		nfds = epoll_wait(el->epfd, el->events, EV_SIZE, 100);
		for(i = 0; i < nfds; ++i)
		{
			struct epoll_event *ee = el->events + i;
			int mask = 0;
			if(ee->events & EPOLLIN)
				mask |= EV_READ;

			if(ee->events &EPOLLOUT)
				mask |= EV_WRITE;

			el->fired[i].fd = ee->data.fd;
			el->fired[i].mask = mask;
		}

		for(i = 0; i < nfds; ++i)
		{
			int mask = el->fired[i].mask;
			int fd = el->fired[i].fd;

			FileEvent *fe = &el->fe[fd];

			if(mask & EV_READ)
				fe->readProc(fd, fe->argv);

			if(mask & EV_WRITE)
				fe->writeProc(fd, fe->argv);
		}

		if(nfds == 0)
		{
			printf("nfds = %d\n", nfds);
			usleep(1000 * 1000);
		}
	}

	return 0;
}

void stopEvent(EventLoop *el)
{
	el->running = 0;
}

main.c

#include 
#include 
#include 
#include 
#include 
#include "socket.h"

#define MAX_BUFFER_SIZE 4096

EventLoop *base;

void onRead(int fd, void* argv);

void onWrite(int fd, void* argv)
{
	char *pbuf = "I've received...\n";
	send(fd, pbuf, strlen(pbuf), 0);
	disableEventOut(base, fd);
	enableEventIn(base, fd, onRead);
}

void onRead(int fd, void* argv)
{
	char buf[MAX_BUFFER_SIZE] = {0};
	int nread = 0;
	if((nread = read(fd, buf, MAX_BUFFER_SIZE)) == 0)
	{
		deleteEvent(base, fd, EV_READ & EV_WRITE);
		printf("close fd = %d\n", fd);
		close(fd);
		return;
	}

	buf[nread] = '\0';

	printf("read buf = [%s] from fd = %d\n", buf, fd);
	disableEventIn(base, fd);
	enableEventOut(base, fd, onWrite);
}

void onAccept(int fd, void* argv)
{
	struct sockaddr_in addr;
	int len = sizeof(addr);
	int cfd;

	while(1)
	{
		cfd = accept(fd, (struct sockaddr*)&addr, &len);
		if(cfd == -1)
		{
			if(errno == EINTR)
				continue;

			printf("accept failed\n");
			return;
		}

		break;
	}

	setnonblocking(cfd);
	printf("new client accept, cfd = %d\n", cfd);
	createEvent(base, cfd);
	enableEventIn(base, cfd, onRead);
	disableEventOut(base, cfd);
}

void sigHandle(const int sig)
{
	printf("sighandled\n");
	kill(getpid(), sig);
	exit(EXIT_SUCCESS);
}

int main(int argc, char* argv[])
{
	int fd;

	signal(SIGINT, sigHandle);
	signal(SIGKILL, sigHandle);
	signal(SIGQUIT, sigHandle);
	signal(SIGTERM, sigHandle);
	signal(SIGHUP, sigHandle);

	if((fd = createSocket("0.0.0.0", 7000)) == -1){
		perror("create socket failed\n");
		exit(EXIT_FAILURE);
	}

	base = initEvent();
	if(base == NULL){
		perror("initialize event failed\n");
		exit(EXIT_FAILURE);
	}

	createEvent(base, fd, EV_READ, onAccept, NULL);
	dispatchEvent(base);
	close(fd);

	return 0;
}

编译

cc socket.c main.c  -g -O0

netlink注意的几个地方

netlink是个功能强大的socket,可以很方便的应用在用户态程序和内核态的通信,具体可以在内核态使用netlink通信,然后在用户态可以使用普通套接字,也可以使用netlink套接字接收消息。最近在使用netlink时发现几点问题,在这里记录下来:

 

1.netlink消息头是一个nlmsghdr的结构体结构,也被称做netlink控制块,每次发送数据都要把这个消息头放在数据头部:
struct nlmsghdr
{
  __u32 nlmsg_len;   /* Length of message */
  __u16 nlmsg_type;  /* Message type*/
  __u16 nlmsg_flags; /* Additional flags */
  __u32 nlmsg_seq;   /* Sequence number */
  __u32 nlmsg_pid;   /* Sending process PID */
};
其中字段 nlmsg_len 指定消息的总长度,包括紧跟该结构的数据部分长度以及该结构的大小,字段 nlmsg_type 用于应用内部定义消息的类型,它对
netlink内核实现是透明的,因此大部分情况下设置为 0,字段 nlmsg_flags 用于设置消息标志对于一般的使用,用户把它设置为 0 就可以,只是一些高
级应用(如 netfilter 和路由 daemon 需要它进行一些复杂的操作),字段 nlmsg_seq 和 nlmsg_pid 用于应用追踪消息,前者表示顺序号,后者为消息
来源进程 ID
2. netlink发送的数据会包装成为一个sk_buff的结构体, sk_buff的意思是socket buff,在sk_buff中包含了很多信息,其中有指向前一个和后一个要发
送的buffer的指针、数据长度、指向数据的指针等,其中有个tail的元素为记录发送数据结尾的变量,这个元素的类型是sk_buff_data_t,而这个类型的定
义是:
#if BITS_PER_LONG > 32
#define NET_SKBUFF_DATA_USES_OFFSET 1
#endif

#ifdef NET_SKBUFF_DATA_USES_OFFSET
typedef unsigned int sk_buff_data_t;
#else
typedef unsigned char *sk_buff_data_t;
#endif
相信大家已经很清楚了,在32位系统上,是unsigned char*类型,在64位系统上是unsigned int类型,所以要注意这个地方,使用tail这个变量一个好处是
很容易得到发送数据的长度,如下:
old_tail = skb_send->tail;
memcpy(NLMSG_DATA(nlh), data, n);
nlh->nlmsg_len = skb_send->tail - old_tail;
3.在发送和接收时如何往消息中放入真正的数据和取出真正的数据呢?在上面其实已经用到了,没错,就是使用NLMSG_DATA这个宏定义了,发送端上面已经有
例子了,再举个接收端的吧,其中data为客户端接收到的数据:
message = (struct nlmsghdr *)data;
msghdr = (struct ct_msghdr *)NLMSG_DATA(message);

当然这些都是netlink最基本的东西,netlink包含有路由 daemon(NETLINK_ROUTE),1-wire 子系统(NETLINK_W1),用户态 socket 协议(NETLINK_USERSOCK),防火墙(NETLINK_FIREWALL),socket 监视(NETLINK_INET_DIAG),netfilter 日志(NETLINK_NFLOG),ipsec 安全策略(NETLINK_XFRM),SELinux 事件通知(NETLINK_SELINUX),iSCSI 子系统(NETLINK_ISCSI),进程审计(NETLINK_AUDIT),转发信息表查询 (NETLINK_FIB_LOOKUP),netlink connector(NETLINK_CONNECTOR),netfilter 子系统(NETLINK_NETFILTER),IPv6 防火墙NETLINK_IP6_FW),DECnet 路由信息(NETLINK_DNRTMSG),内核事件向用户态通知(NETLINK_KOBJECT_UEVENT),通用 netlink(NETLINK_GENERIC)等多种方式。
可参考网站:http://www.infradead.org/~tgr/libnl/

centos 源码编译安装gcc 4.7.0

gcc官方网站 下载最新版本的gcc-4.7.0.tar.bz2
同时在infrastructure目录下寻找下载【必须】的cloog-0.16.2.tar.gz、mpc-0.8.1.tar.gz、mpfr-2.4.2.tar.bz2、ppl-0.11.tar.gz,去http://gmplib.org/ 下载最新的gmp-5.0.4.tar.bz2
开始前的注意事项:
【我是在CentOS 5.3 x64的虚拟机环境下实践的此文,推荐内存要大于2G,否则在编译一些模块时会出现因为物理内存耗光而死机的情况】

开始安装gcc 4.7.0,以下包的安装步骤不能错乱

tar jxvf gmp-5.0.4.tar.bz2
cd gmp-5.0.4
./configure --prefix=/usr/local/gmp-5.0.4 --build=x86_64-linux
make && make install
cd ../

tar jxvf mpfr-2.4.2.tar.bz2
cd mpfr-2.4.2
./configure --prefix=/usr/local/mpfr-2.4.2 --with-gmp=/usr/local/gmp-5.0.4
make && make install
cd ../

tar zxvf mpc-0.8.1.tar.gz
cd mpc-0.8.1
./configure --prefix=/usr/local/mpc-0.8.1  --with-gmp=/usr/local/gmp-5.0.4 --with-mpfr=/usr/local/mpfr-2.4.2
make && make install
cd ../

由于cloog-0.16.2是【isl-based version】,在gcc的./configure 时,使用–enable-cloog-backend=isl参数来指定cloog的后端为isl即可

tar zxvf ppl-0.11.tar.gz
cd ppl-0.11
./configure --prefix=/usr/local/pp1-0.11 --with-gmp=/usr/local/gmp-5.0.4
make && make install
cd ../

tar zxvf cloog-0.16.2.tar.gz
cd cloog-0.16.2
./configure --prefix=/usr/local/cloog-0.16.2 --with-gmp=/usr/local/gmp-5.0.4
make && make install
cd ../

安装gcc 4.7.0,此处的参数,只针对C、C++语言,如果需要其能编译出其他工具链(如all, ada, fortran, go, java, objc, obj-c++之类的),在enable-language后面添加上,然后添加上相应的参数就是

tar jxvf gcc-4.7.0.tar.bz2
cd gcc-4.7.0
./configure --with-gmp=/usr/local/gmp-5.0.4 --with-mpfr=/usr/local/mpfr-2.4.2 --with-mpc=/usr/local/mpc-0.8.1 --enable-languages=c,c++ --enable-threads=posix --enable-__cxa_atexit --with-cpu=generic --disable-multilib --with-ppl=/usr/local/pp1-0.11 --with-cloog=/usr/local/cloog-0.16.2 --enable-cloog-backend=isl
make && make install

将以上四个库加入系统库路径,使用在/etc/ld.so.conf中添加或LD_LIBRARY_PATH环境变量中添加的方式
如在~/.bashrc中添加上下面语句

export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/gmp-5.0.4/lib:/usr/local/mpfr-2.4.2/lib:/usr/local/mpc-0.8.1/lib:/usr/local/cloog-0.16.2/lib:/usr/local/ppl-0.11/lib

使用gcc -v即可查看到新安装的gcc版本已经变为4.7.0了,如下图

编译安装Pidgin 2.7.11 并安装QQ Fetion插件

编译安装Pidgin 2.7.11 并安装QQ Fetion插件

一、编译安装Pidgin
1、下载 Pidgin 的源代码包 pidgin-2.7.11.tar.bz2

2、解压源代码包

tar jxvf pidgin-2.7.11.tar.bz2
cd pidgin-2.1.1

3、编译

./configure
make
sudo make install

检查依赖出错:

configure: error:
The intltool scripts were not found. Please install intltool.

解决
sudo apt-get install intltool
configure: error:
You must have the GLib 2.0 development headers installed to build.

If you have these installed already you may need to install pkg-config so
I can find them.

解决
sudo apt-get install libglib2.0-dev pkg-config
configure: error:
You must have the GTK 2.0 development headers installed to compile Pidgin.
If you want to build only Finch then specify –disable-gtkui when running configure.

解决
sudo apt-get install libgtk2.0-dev
configure: error:
XScreenSaver extension development headers not found.
Use –disable-screensaver if you do not need XScreenSaver extension support,
this is required for detecting idle time by mouse and keyboard usage.

解决
sudo apt-get install libxss-dev
configure: error:
Startup notification development headers not found.
Use –disable-startup-notification if you do not need it.

解决
sudo apt-get install libstartup-notification0-dev
configure: error:
GtkSpell development headers not found.
Use –disable-gtkspell if you do not need it.

解决
sudo apt-get install libgtkspell-dev
configure: error:
You must have libxml2 >= 2.6.0 development headers installed to build.

解决
sudo apt-get install libxml2-dev
configure: error:
GStreamer development headers not found.
Use –disable-gstreamer if you do not need GStreamer (sound) support.

解决
sudo apt-get install libgstreamer0.10-dev
configure: error:
Dependencies for voice/video were not met.
Install the necessary gstreamer and farsight packages first.
Or use --disable-vv if you do not need voice/video support.

解决
sudo apt-get install libfarsight0.1-dev
sudo apt-get install libgstfarsight0.10-dev
sudo apt-get install libgstreamer-plugins-base0.10-dev
configure: error:
GNU Libidn development headers not found.
Use --disable-idn if you do not need it.
解决
sudo apt-get install libidn11-dev
configure: error:
Meanwhile development headers not found.

Use --disable-meanwhile if you do not need meanwhile (Sametime) support
解 决
sudo apt-get install libmeanwhile-dev
configure: error:
avahi development headers not found.
Use --disable-avahi if you do not need avahi (Bonjour) support.
解决
apt-get install libavahi-client-dev libavahi-glib-dev
configure: error:
D-Bus development headers not found.
Use --disable-dbus if you do not need D-Bus support.
解决
sudo apt-get install libdbus-1-dev libdbus-glib-1-dev
configure: error:
NetworkManager development headers not found.
Use --disable-nm if you do not need NetworkManager support.
解决
sudo apt-get install network-manager-dev
configure: error:
Perl development headers not found.
Use --disable-perl if you do not need Perl scripting support.
解决
sudo apt-get install libperl-dev
configure: error:
Neither GnuTLS or NSS SSL development headers found.
Use --disable-nss --disable-gnutls if you do not need SSL support.
MSN, Yahoo!, Novell Groupwise and Google Talk will not work without GnuTLS or NSS. OpenSSL is NOT usable!
解决
sudo apt-get install libgnutls-dev
configure: error:
Tcl development headers not found.
Use --disable-tcl if you do not need Tcl scripting support.
解决
sudo apt-get install tcl8.4-dev
configure: error:
Tk development headers not found.
Use --disable-tk if you do not need Tk scripting support.
解决
sudo apt-get install tk8.4-dev

安装好上述依赖之后编译成功

二、安装QQ插件

删除自带的QQ插件(自带的是2005和2008协议的)

sodu rm /usr/lib/purple-2/libqq.so

重新安装2010协议的插件

svn checkout http://libqq-pidgin.googlecode.com/svn/trunk/ libqq-pidgin-read-only
cd libqq-pidgin-read-only
chmod +x autogen.sh
./autogen.sh
./configure CFLAGS="-g3 -O0"
make
sudo make install

不想编译的可直接下载so文件拷贝到/usr/lib/purple-2/目录即可

三、安装Fetion插件

sudo apt-get install cmake

hg clone https://ofetion.googlecode.com/hg/ ofetion
cd ofetion/pidgin-ofetion
mkdir build
cd build
cmake ..
sudo make install

如果提示openssl没找到,可安装 libssl-dev

sudo apt-get install libssl-dev 

stat、lstat、fstat文件状态函数

man 2 stat
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 */
           };
#include 
#include 
#include 
#include 

int main(int argc, char* argv[])
{
	int i;
	struct stat buf;
	char *ptr;

	for(i = 1; i < argc; ++i)
	{
		printf("%s: ",argv[i]);
		// 使用stat则不会观察到符号链接
		if(lstat(argv[i],&buf) < 0)
		{
			printf("lstat error\n");
			continue;
		}
		
		if(S_ISREG(buf.st_mode))
			ptr = "regular";
		else if(S_ISDIR(buf.st_mode))
			ptr = "directory";
		else if(S_ISCHR(buf.st_mode))
			ptr = "character special";
		else if(S_ISBLK(buf.st_mode))
			ptr = "block special";
		else if(S_ISFIFO(buf.st_mode))
			ptr = "fifo";
		else if(S_ISLNK(buf.st_mode))
			ptr = "symbolic link";
		else if(S_ISSOCK(buf.st_mode))
			ptr = "socket";
		else
			ptr = "*** unknown mode ***";

		printf("%s\n",ptr);
	}

	return 0;
}

lseek与空洞文件

确定打开文件的当前偏移量

#include 
#include 
#include 

int main(int argc, char* argv[])
{
	off_t offset;
	if((offset = lseek(STDIN_FILENO, 0, SEEK_CUR)) == -1)
		printf("cannot seek\n");
	else
		printf("seek OK,offset = %lu\n",offset);

	return 0;
}

空洞文件:文件中的空洞并不要求在磁盘上占用储存区。当lseek定位超出文件尾端之后写时,对于新写的数据需要分配磁盘块,但是对于原文件尾端和新开始写位置之间的部分则不需要分配磁盘块。其在磁盘中的表现都为0

// 创建空洞文件
#include 
#include 
#include 
#include 
#include 

char buf1[] = "abcdefghij";
char buf2[] = "ABCDEFGHIJ";

int main(void)
{
	int fd;

	if((fd = creat("file.hole", S_IRWXU | S_IRWXG | S_IRWXG)) < 0)
	{
		printf("creat failed\n");
		return -1;
	}

	if(write( fd, buf1, 10) != 10)
	{
		printf("buf1 write error\n");
		return -1;
	}
	// offset now = 10
	
	if(lseek(fd, 16384, SEEK_SET) == -1)
	{
		printf("lseek failed\n");
		return -1;
	}
	// offset now = 16384
	
	if(write(fd, buf2, 10) != 10)
	{
		printf("buf2 write failed\n");
		return -1;
	}
	// offset now = 16394
	
	return 0;
}

将标准输入复制到标准输出

将标准输入复制到标准输出
STDIN_FILENO 0
STDOUT_FILENO 1
STDERR_FILENO 2
三个宏在unistd.h头文件中定义

#include 
#include 

#define BUFFSIZE 4096

int main(int argc,char* argv[])
{
	int n;
	char buf[BUFFSIZE] = {};

	while((n = read(STDIN_FILENO,buf,BUFFSIZE)) > 0)
	{
		if(write(STDOUT_FILENO,buf,n) != n)
		{
			printf("write error\n");
			return -1;
		}
	}

	if(n < 0)
	{
		printf("read error\n");
		return -1;
	}

	return 0;
}

快速排序算法原理与实现

快速排序算法原理与实现
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。一趟快速排序的算法是:

1)、设置两个变量I、J,排序开始的时候I = 1,J = N;
2)、以第一个数组元素作为关键数据,赋值给X,即X = A[1];
3)、从J开始向前搜索,即由后开始向前搜索(J = J – 1),找到第一个小于X的值,两者交换;
4)、从I开始向后搜索,即由前开始向后搜索(I = I + 1),找到第一个大于X的值,两者交换;
5)、重复第3、4步,直到I = J;

   例如:待排序的数组A的值分别是:(初始关键数据X:=49)
                   A[1]     A[2]     A[3]     A[4]     A[5]      A[6]     A[7]
                     49        38       65       97       76       13        27

进行第一次交换后:   27        38       65       97       76       13        49
                  	( 按照算法的第三步从后面开始找第一个小于X的值,此时J = 7)

进行第二次交换后:   27        38       49       97       76       13        65
                  	( 按照算法的第四步从前面开始找第一个大于X的值,65 > 49,两者交换,此时I = 3 )

进行第三次交换后:   27        38       13       97       76       49        65
			( 按照算法的第五步将又一次执行算法的第三步从后开始找,此时J = 6)

进行第四次交换后:   27        38       13       49       76       97        65
			( 按照算法的第四步从前面开始找大于X的值,97 > 49,两者交换,此时I = 4 )

此时再执行第三步的时候就发现I = J,从而结束一趟快速排序,那么经过一趟快速排序之后的结果是:27       38       13       49       76       97        65,即所有大于49的数全部在49的后面,所有小于49的数全部在49的前面。

快速排序就是递归调用此过程——以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:

初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序 {13} 27 {38} 49 {65} 76 {97}

1)、设有N(假设N=10)个数,存放在S数组中;
2)、在S[1。。N]中任取一个元素作为比较基准,例如取T=S[1],起目的就是在定出T应在排序结果中的位置K,这个K的位置在:S[1。。K-1]<=S[K]<=S[K+1..N],即在S[K]以前的数都小于S[K],在S[K]以后的数都大于S[K]; 3)、利用分治思想(即大化小的策略)可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。 如具体数据如下,那么第一趟快速排序的过程是:

数组下标: 
	1      2      3      4      5      6      7      8      9      10

	45     36     18     53     72     30     48     93     15     36

	I                                                              J

(1)      36     36     18     53     72     30     48     93     15      45
(2)      36     36     18     45     72     30     48     93     15      53
(3)      36     36     18     15     72     30     48     93     45      53
(4)      36     36     18     15     45     30     48     93     72      53
(5)      36     36     18     15     30     45     48     93     72      53

通过一趟排序将45放到应该放的位置K,这里K=6,那么再对S[1。。5]和S[6。。10]分别进行快速排序。

一般来说,冒泡法是程序员最先接触的排序方法,它的优点是原理简单,编程实现容易,但它的缺点就是–程序的大忌–速度太慢。下面我介绍一个理解上简单但编程实现上不是太容易的排序方法,我不知道它是不是现有排序方法中最快的,但它是我见过的最快的。排序同样的数组,它所需的时间只有冒泡法的 4% 左右。我暂时称它为“快速排序法”。

“快速排序法”使用的是递归原理,下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53,12,98,63,18,72,80,46, 32,21},先找到第一个数–53,把它作为中间值,也就是说,要把53放在一个位置,使得它左边的值比它小,右边的值比它大。{21,12,32, 46,18,53,80,72,63,98},这样一个数组的排序就变成了两个小数组的排序–53左边的数组和53右边的数组,而这两个数组继续用同样的方式继续下去,一直到顺序完全正确。

我这样讲你们是不是很胡涂,不要紧,我下面给出实现的两个函数:

/*
	n就是需要排序的数组,left和right是你需要排序的左界和右界,
	如果要排序上面那个数组,那么left和right分别是0和9
*/
void quicksort(int n[], int left,int right)
{
	int dp;
	if (left

我们上面提到先定位第一个数,然后整理这个数组,把比这个数小的放到它的左边,大的放右边,然后返回这中间值的位置,下面这函数就是做这个的。

int partition(int n[],int left,int right)
{
	int lo,hi,pivot,t;
	
	pivot = n[left];
	lo = left - 1;
	hi = right + 1;
	
	while(lo + 1 != hi) {
	     if(n[lo + 1] <= pivot)
	       lo++;
	     else if(n[hi - 1] > pivot)
	       hi--;
	     else {
	       t = n[lo + 1];
	       n[++lo]=n[hi - 1];
	       n[--hi]=t;
	     }
	}
	
	n[left] = n[lo];
	n[lo] = pivot;
	return lo;
}

这段程序并不难,应该很好看懂,我把过程大致讲一下,首先你的脑子里先浮现一个数组和三个指针,第一个指针称为p指针,在整个过程结束之前它牢牢的指向第一个数,第二个指针和第三个指针分别为lo指针和hi指针,分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近,在逼近的过程中不停的与p指针的值比较,如果lo指针的值比p指针的值小,lo++,还小还++,再小再++,直到碰到一个大于p指针的值,这时视线转移到hi指针,如果 hi指针的值比p指针的值大,hi--,还大还--,再大再--,直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面,这时把p指针的值和碰面的值做一个调换,然后返回p指针新的位置。

 
// 快速排序的递归实现 
void QuickSort(int arr[], int n)
{
     if(n <= 1)
     return;
     
     int i =0 , j = n - 1;
     int key = arr[0];
     int index = 0;
     
     while(i < j)
     {
             // 从后向前搜索 
             while(j > i && arr[j] > key)
             		j--;
             		
             if(j == i)
             		break;
             else
             {
             		//交换 a[j] a[i]
             		int tmp = arr[i];
             		arr[i] = arr[j];
             		arr[j] = tmp;
                index = j;
             }
             
             // 从前向后搜索
             while(i < j && arr[i] < key)
             		i++;
             		
             if(i == j)
             		break;
             else
             {
             		// 交换 a[i] a[j] 
             		int tmp = arr[i];
             		arr[i] = arr[j];
             		arr[j] = tmp;
                index = i;
             }             
     }    
      
     QuickSort(arr, index);
     QuickSort(arr + index + 1, n - 1 - index);
}