kk Blog —— 通用基础

SBT -- poj2828

2012-01-16 21:34:00

#include <stdio.h>
#include <algorithm>
#include <iostream>

#define N 4000005
using namespace std;

int tol=0;
struct SBT
{
	int left,right;
	int key;
	int size;
	void init()
	{
	    left=right=0;
	    size=1;
	}
}T[N];

void R_Rotate(int &t)//右旋
{
	int k=T[t].left;
	T[t].left=T[k].right;
	T[k].right=t;
	T[k].size=T[t].size;
	T[t].size=T[T[t].left].size+T[T[t].right].size+1;
	t=k;
	return ;
}
void L_Rotate(int &t)//左旋
{
	int k=T[t].right;
	T[t].right=T[k].left;
	T[k].left=t;
	T[k].size=T[t].size;
	T[t].size=T[T[t].left].size+T[T[t].right].size+1;
	t=k;
}
void Maintain(int &t,bool flag)//维护，SBT精华之所在
{
	if(flag==false)
	{
	    if(T[T[T[t].left].left].size>T[T[t].right].size)
	        R_Rotate(t);
	    else if(T[T[T[t].left].right].size>T[T[t].right].size)
	    {
	        L_Rotate(T[t].left);
	        R_Rotate(t);
	    }
	    else
	        return ;
	}
	else
	{
	    if(T[T[T[t].right].right].size>T[T[t].left].size)
	        L_Rotate(t);
	    else if(T[T[T[t].right].left].size>T[T[t].left].size)
	    {
	        R_Rotate(T[t].right);
	        L_Rotate(t);
	    }
	    else
	        return ;
	}
	Maintain(T[t].left,false);
	Maintain(T[t].right,true);
	Maintain(t,false);
	Maintain(t,true);
}
void Insert(int &t,int v)//插入
{
	if(t==0)
	{
	    t=++tol;
	    T[t].init();
	    T[t].key=v;
	}
	else
	{
	    T[t].size++;
	    if(v<T[t].key)
	        Insert(T[t].left,v);
	    else
	        Insert(T[t].right,v);
	    Maintain(t,v>=T[t].key);
	}
}
int Delete(int &t,int v)//删除
{
	if(!t)
	    return 0;
	T[t].size--;
	if(v==T[t].key||v<T[t].key&&!T[t].left||v>T[t].key&&!T[t].right)
	{
	    if(T[t].left&&T[t].right)
	    {
	        int p=Delete(T[t].left,v+1);
	        T[t].key=T[p].key;
	        return p;
	    }
	    else
	    {
	        int p=t;
	        t=T[t].left+T[t].right;
	        return p;
	    }
	}
	else
	    return Delete(v<T[t].key?T[t].left:T[t].right,v);
}
int Find_k(int t,int k)//找出第k大数
{
   if(k<=T[T[t].left].size)
	    return Find_k(T[t].left,k);
	else if(k>T[T[t].left].size+1)
	    return Find_k(T[t].right,k-T[T[t].left].size-1);
	return T[t].key;
}
int Getmin(int t)//取最小值
{
	while(T[t].left)
	    t=T[t].left;
	return t;
}
int Getmax(int t)//取最大值
{
	while(T[t].right)
	    t=T[t].right;
	return t;
}
int Rank(int t,int key)//排名其实就是它的左子树的size+1
{
	if(t==0)
	    return 0;
	if(key<=T[t].key)
	    return Rank(T[t].left,key);
	else
	    return T[T[t].left].size+1+Rank(T[t].right,key);
}
int eRank(int t,int key)//倒过来排名
{
	if(t==0)
	    return 0;
	if(key>=T[t].key)
	    return eRank(T[t].right,key);
	else
	    return T[T[t].right].size+1+eRank(T[t].left,key);
}

int Exist(int t,int x)//判断这个节点是否存在
{
	if(t==0)
	    return 0;
	if(x<T[t].key)
	    return Exist(T[t].left,x);
	else if(x==T[t].key)
	    return 1;
	else
	    return Exist(T[t].right,x);
}
int Count(int t,int x)//统计出现次数
{
	if(!Exist(t,x))
	    return 0;
	else
	    return Rank(t,x+1)-Rank(t,x);
}
int Pred(int t,int v)//返回比v小的最大的数
{
	if(t==0)
	    return v;
	else if(v>T[t].key)
	{
	    int ret=Pred(T[t].right,v);
	    if(ret==v)
	        return T[t].key;
	    return ret;
	}
	else
	    return Pred(T[t].left,v);
}
int Succ(int t,int v)//返回比v大的最小的数
{
	if(t==0)
	    return v;
	else if(v<T[t].key)
	{
	    int ret=Succ(T[t].left,v);
	    if(ret==v)
	        return T[t].key;
	    return ret;
	}
	else
	    return Succ(T[t].right,v);
}

////////////////////////

int n,m, a[200009], b[200009], c[200009];

void dfs(int root)
{
	if(root == 0) return;
	dfs(T[root].left);
	if(m > 0) printf(" ");
	printf("%d", T[root].key);
	m++;
	dfs(T[root].right);
}

int main()
{
	int i,j,k;
	int root;
	
	while(scanf("%d", &n) != EOF)
	{
	    tol = 0;
	root = 0;
	    for(i=1;i<=n;i++)
	{
	        scanf("%d %d", &a[i], &b[i]);
	    Insert(root, i);
	}
	for(i=n;i>0;i--)
	{
	    k = Find_k(root, a[i]+1);
	    c[k] = b[i];
	    Delete(root, k);
	}
	for(i=1;i<n;i++) printf("%d ", c[i]);
	printf("%d\n", c[i]);
	m = 0;
	dfs(root);
	}
	return 0;
}

strace跟踪系统调用和信号

2011-12-09 00:16:00

strace 用来截取程序发出的系统调用并将其显示出来。被 strace 跟踪的程序，可以是从 strace 命令运行的，也可以是系统上已经运行的进程。strace 是调试汇编语言和高级语言程序时价值无法估量的工具。

为了简单起见(不让 strace 输出太多内容)，这里使用 strace 截取 http://www.groad.net/bbs/read.php?tid-2622.html 中“系统调用返回值“ 里的示例程序：

$ strace ./syscall2
execve("./syscall2", ["./syscall2"], [/* 43 vars */]) = 0
getpid()                                = 2467
getuid()                                = 1000
getgid()                                = 1000
_exit(0)                                = ?

上面，左侧一列显示了系统调用名称，右侧显示系统调用生成的返回值。

高级 strace 参数：

参数       描述
-c        统计每个系统调用的时间、调用和错误
-d        显示 strace 的一些调试输出
-e        指定输出的过滤表达式
-f        在创建子进程的时候跟踪它们
-ff       如果写入到输出文件，则把每个子进程写入到单独的文件中
-i        显示执行系统调用时的指令指针
-o        把输出写入到指定文件
-p        附加到由PID指定的现有进程
-q        抑制关于附加和分离的消息
-r        对每个系统调用显示一个相对的时间戳
-t        把时间添加到每一行
-tt       把时间添加到每一行，包括微秒
-ttt      添加epoch形式的时间(从1970年1月1日开始的秒数)，包括微秒
-T        显示每个系统调用花费的时间
-v        显示系统调用信息的不经省略版本(详细的)
-x        以十六进制格式显示所有非ASCII字符
-xx       以十六进制格式显示所有字符串

其中，-e 参数很方便，因为它可以用于只显示系统调用的子集，而不是全部。-e 参数格式为：
trace=call_list
上面，call_list 是系统调用清单。如上面的程序，如果我们只希望看到系统调用 getuid 和 getgid，那么可以：

$ strace -e trace=getpid,getgid ./syscall2
getpid()                                = 2653
getgid()                                = 1000

注意，上面的 getpid 和 getgid 之间以逗号相隔，不能再有其它符号，包括空格。

使用 -o 参数可以将结果导出到一个文件中，如将跟踪 id 这个命令时，可以：

$ strace -o outfile id
uid=1000(beyes) gid=1000(beyes) 组=4(adm),20(dialout),24(cdrom),46(plugdev),105(lpadmin),119(admin),122(sambashare),1000(beyes)

从输出看出，id 指令也运行了，并在当前目录下生成 outfile 文件，在 outfile 文件里，列出了 id 指令所调用的系统调用。这些系统调用非常多，总共有278次之多。为了帮助组织这些调用信息，我们尝试使用 -c 参数，这时结果会按照时间排列调用：

$ strace -c id
uid=1000(beyes) gid=1000(beyes) 组=4(adm),20(dialout),24(cdrom),46(plugdev),105(lpadmin),119(admin),122(sambashare),1000(beyes)
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
  -nan    0.000000           0        17           read
  -nan    0.000000           0         1           write
  -nan    0.000000           0        44         3 open
  -nan    0.000000           0        47           close
  -nan    0.000000           0         1           execve
  -nan    0.000000           0         9         9 access
  -nan    0.000000           0         3           brk
  -nan    0.000000           0        18           munmap
  -nan    0.000000           0        10           mprotect
  -nan    0.000000           0        20           _llseek
  -nan    0.000000           0        51           mmap2
  -nan    0.000000           0        40           fstat64
  -nan    0.000000           0         1           getuid32
  -nan    0.000000           0         1           getgid32
  -nan    0.000000           0         1           geteuid32
  -nan    0.000000           0         1           getegid32
  -nan    0.000000           0         2           getgroups32
  -nan    0.000000           0         1           fcntl64
  -nan    0.000000           0         1           set_thread_area
  -nan    0.000000           0         1           statfs64
  -nan    0.000000           0         4           socket
  -nan    0.000000           0         4         4 connect
------ ----------- ----------- --------- --------- ----------------
100.00    0.000000                   278        16 total

从上面的输出结果可以看到，调用 open 时发生了 3 次错误，调用 connect 时发生了 4 次错误。为了进一步跟踪这些错误，可以将它们单独挑选出来：

$ strace -e trace=open,connect id
open("/etc/ld.so.cache", O_RDONLY)      = 3
open("/lib/libselinux.so.1", O_RDONLY)  = 3
open("/lib/tls/i686/cmov/libc.so.6", O_RDONLY) = 3
open("/lib/tls/i686/cmov/libdl.so.2", O_RDONLY) = 3
open("/proc/filesystems", O_RDONLY|O_LARGEFILE) = 3
open("/proc/filesystems", O_RDONLY|O_LARGEFILE) = 3
open("/usr/lib/locale/locale-archive", O_RDONLY|O_LARGEFILE) = -1 ENOENT (No such file or directory)
open("/usr/share/locale/locale.alias", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_IDENTIFICATION", O_RDONLY) = 3
open("/usr/lib/gconv/gconv-modules.cache", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_MEASUREMENT", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_TELEPHONE", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_ADDRESS", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_NAME", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_PAPER", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_MESSAGES", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_MESSAGES/SYS_LC_MESSAGES", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_MONETARY", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_COLLATE", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_TIME", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_NUMERIC", O_RDONLY) = 3
open("/usr/lib/locale/zh_CN.utf8/LC_CTYPE", O_RDONLY) = 3
open("/usr/share/locale/zh_CN/LC_MESSAGES/coreutils.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/share/locale/zh/LC_MESSAGES/coreutils.mo", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/share/locale-langpack/zh_CN/LC_MESSAGES/coreutils.mo", O_RDONLY) = 3
connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory)
connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory)
open("/etc/nsswitch.conf", O_RDONLY)    = 3
open("/etc/ld.so.cache", O_RDONLY)      = 3
open("/lib/tls/i686/cmov/libnss_compat.so.2", O_RDONLY) = 3
open("/lib/tls/i686/cmov/libnsl.so.1", O_RDONLY) = 3
open("/etc/ld.so.cache", O_RDONLY)      = 3
open("/lib/tls/i686/cmov/libnss_nis.so.2", O_RDONLY) = 3
open("/lib/tls/i686/cmov/libnss_files.so.2", O_RDONLY) = 3
open("/etc/passwd", O_RDONLY|O_CLOEXEC) = 3
connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory)
connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory)
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/proc/sys/kernel/ngroups_max", O_RDONLY) = 3
open("/proc/sys/kernel/ngroups_max", O_RDONLY) = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
open("/etc/group", O_RDONLY|O_CLOEXEC)  = 3
uid=1000(beyes) gid=1000(beyes) 组=4(adm),20(dialout),24(cdrom),46(plugdev),105(lpadmin),119(admin),122(sambashare),1000(beyes)

从输出结果(红色加亮部分)可以知道错误在哪里了。

附加到正在运行的程序

strace 的另一个非常好的特性是监视已经运行在系统上的程序的能力。-p 参数可以把 strace 附加到一个 PID 并且捕获系统调用。下面程序可以在后台运行，并且这个程序将维持运行一段时间，在此期间我们用 strace 来捕获它。
程序代码：

	.section.data
timespec:
	.int5,0
output:
	.ascii"This is a test/n"
output_end:
	.equlen,output_end-output

.section.bss
	.lcommrem,8

.section.text
.global_start
_start:
	nop
	movl$10,%ecx

loop1:
	pushl%ecx
	movl$4,%eax
	movl$1,%ebx
	movl$output,%ecx
	movl$len,%edx
	int$0x80

	movl$162,%eax
	movl$timespec,%ebx
	movl$rem,%ecx
	int$0x80
	popl%ecx
	looploop1

	movl$1,%eax
	movl$0,%ebx
	int$0x80

程序中使用了 nanosleep() 这个系统调用函数。在一个终端里后台运行这个函数：

./nanostrace &

然后使用 ps 命令得到此进程的 PID 值，接着可以用 strace 来跟踪了：

$ strace -p 3069
Process 3069 attached - interrupt to quit
restart_syscall(<... resuming interrupted call ...>) = 0
write(1, "This is a test/n", 15)        = 15
nanosleep({5, 0}, 0x80490d0)            = 0
write(1, "This is a test/n", 15)        = 15
nanosleep({5, 0}, 0x80490d0)            = 0
write(1, "This is a test/n", 15)        = 15
nanosleep({5, 0}, 0x80490d0)            = 0
write(1, "This is a test/n", 15)        = 15
nanosleep({5, 0}, 0x80490d0)            = 0
_exit(0)                                = ?

由上可见，程序中使用了 write, nanosleep, exit 3个系统调用。

最简单点对点通信样例

2011-12-08 16:22:00

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <unistd.h>
#include <arpa/inet.h>
#define MAXLINE 4096

#include <sys/ioctl.h>
#include <net/if.h>
#include <net/if_arp.h>

#include <pthread.h>

int send_to_port = 6667;
int self_port = 6666;

void *get(void *data)
{
	int listenfd, connfd;
	struct sockaddr_in servaddr;

	if( (listenfd = socket(AF_INET, SOCK_STREAM, 0)) == -1 ) {
		printf("create socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	memset(&servaddr, 0, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
	servaddr.sin_port = htons(self_port);

	if( bind(listenfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1) {
		printf("bind socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	if( listen(listenfd, 10) == -1) {
		printf("listen socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	char buff[4096];
	int n;
	while(1)
	{
		if( (connfd = accept(listenfd, (struct sockaddr*)NULL, NULL)) == -1) {
			printf("accept socket error: %s(errno: %d)",strerror(errno),errno);
			return 0;
		}
		n = recv(connfd, buff, MAXLINE, 0);
		buff[n] = '\0';
		printf("recv msg from server: %s", buff);

		close(connfd);
	}
	return 0;
}

char server_addr[333];

void *sent(void *data)
{
	int sockfd, n;
	struct sockaddr_in servaddr;
	char sendline[4096];

	while(1)
	{
		fgets(sendline, 4096, stdin);
		
		if( (sockfd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
			printf("create socket error: %s(errno: %d)\n", strerror(errno),errno);
			return 0;
		}

		memset(&servaddr, 0, sizeof(servaddr));
		servaddr.sin_family = AF_INET;
		servaddr.sin_port = htons(send_to_port);
		if( inet_pton(AF_INET, server_addr, &servaddr.sin_addr) <= 0) {
			printf("inet_pton error for %s\n", server_addr);
			return 0;
		}

		if( connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) < 0) {
			printf("connect error: %s(errno: %d)\n",strerror(errno),errno);
			return 0;
		}

		if( send(sockfd, sendline, strlen(sendline), 0) < 0) {
			printf("send msg error: %s(errno: %d)\n", strerror(errno), errno);
		}
		close(sockfd);
	}
	return 0;
}

int main(int argc, char** argv)
{
	if( argc != 2) {
		printf("usage: ./client <ip_address>\n");
		return 0;
	}
	strcpy(server_addr, argv[1]);

	pthread_t th1, th2;
	void *retval;
	pthread_create(&th1, NULL, get, 0);
	pthread_create(&th2, NULL, sent, 0);
	pthread_join(th1, &retval);
	pthread_join(th2, &retval);
	return 0;
}

编译：g++ client.cpp -o client -lpthread
运行：./client xx.xx.xx.xx

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <unistd.h>
#include <arpa/inet.h>
#define MAXLINE 4096

#include <sys/ioctl.h>
#include <net/if.h>
#include <net/if_arp.h>

#include <pthread.h>

int send_to_port = 6666;
int self_port = 6667;

void *get(void *data)
{
	int listenfd, connfd;
	struct sockaddr_in servaddr;

	if( (listenfd = socket(AF_INET, SOCK_STREAM, 0)) == -1 ) {
		printf("create socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	memset(&servaddr, 0, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
	servaddr.sin_port = htons(self_port);

	if( bind(listenfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1) {
		printf("bind socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	if( listen(listenfd, 10) == -1) {
		printf("listen socket error: %s(errno: %d)\n",strerror(errno),errno);
		return 0;
	}

	char buff[4096];
	int n;
	while(1)
	{
		if( (connfd = accept(listenfd, (struct sockaddr*)NULL, NULL)) == -1) {
			printf("accept socket error: %s(errno: %d)",strerror(errno),errno);
			return 0;
		}
		n = recv(connfd, buff, MAXLINE, 0);
		buff[n] = '\0';
		printf("recv msg from client: %s", buff);

		close(connfd);
	}
	return 0;
}

char server_addr[333];

void *sent(void *data)
{
	int sockfd, n;
	struct sockaddr_in servaddr;
	char sendline[4096];

	while(1)
	{
		fgets(sendline, 4096, stdin);

		if( (sockfd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
			printf("create socket error: %s(errno: %d)\n", strerror(errno),errno);
			return 0;
		}

		memset(&servaddr, 0, sizeof(servaddr));
		servaddr.sin_family = AF_INET;
		servaddr.sin_port = htons(send_to_port);
		if( inet_pton(AF_INET, server_addr, &servaddr.sin_addr) <= 0) {
			printf("inet_pton error for %s\n", server_addr);
			return 0;
		}

		if( connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) < 0) {
			printf("connect error: %s(errno: %d)\n",strerror(errno),errno);
			return 0;
		}

		if( send(sockfd, sendline, strlen(sendline), 0) < 0) {
			printf("send msg error: %s(errno: %d)\n", strerror(errno), errno);
		}
		close(sockfd);
	}
	return 0;
}

int main(int argc, char** argv)
{
	if( argc != 2) {
		printf("usage: ./server <ip_address>\n");
		return 0;
	}
	strcpy(server_addr, argv[1]);

	pthread_t th1, th2;
	void *retval;
	pthread_create(&th1, NULL, get, 0);
	pthread_create(&th2, NULL, sent, 0);
	pthread_join(th1, &retval);
	pthread_join(th2, &retval);
	return 0;
}

编译：g++ server.cpp -o server -lpthread
运行：./server xx.xx.xx.xx

← Older Blog Archives Newer →