迎接ChinaUnix九周年庆技术实践之二----C/C++编程大赛！-结果公布！ - Chinaunix

实现关系表的增删改查功能：
功能需求：关系表，即数据库中数据的表示方式，使用二维行列表示，请实现创建表(create)、删除表(drop)、插入行(insert)、删除行(delete)、修改某些行中的某些字段(update)、查询(select)；
限制：表的最大列数不超过255列，最大行数的数量级为百万级，列类型均为int型，表中索引最大数量为16个，
输入：从标准输入输入，第一行为命令字，包括create/drop/insert/delete/update/select六种，当命令字是create时，第二行表示表中包含的列数，这些列由0 -- n-1标识，第三行是一组由空格隔开的数字，表示以这些数字标识的列上有索引，数字的数量不会超过16个或者表的列数；当命令字是drop时，表示将表删除；当命令字是insert时，第二行是一个数字，表示从下一行起要插入到表中的行数，第三行起，每行是一组由空格隔开的数字，数字的数量为表的列数；命令字是delete时，第二行是一个数字，表示后续需要delete的case的数量，每个case一行，第三行起，每行为一些由删除条件组成的case，格式为：no或者列序号1 > num1 and ( 列序号2 < num2 or 列序号3 >= num3 ) and 列序号4 <= num4 and 列序号5 = num5 and 列序号6 != num6，no表示没有条件，即，匹配所有行，条件的组合包含and和or运算，比较运算符包括> < >= <= = !=，由()括起的部分优先级高于未被括起的部分，()不会嵌套，字元之间均有空格隔开；当命令字为update时，第二行为case数量，每个case包括两行，第一行表示要修改的列以及要修改成的值，第二行为过滤条件(与delete的条件格式相同)，每个case的第一行的格式为：列序号1 = num1 , 列序号2 = 列序号2 + num2 , 列序号3 = 列序号4 + num3，进行运算只有+和-，逗号分割各个要修改的列；命令字为select时，第二行是后续case数量，第三行起，每行的格式与delete命令字的条件格式相同。
输出：输出到标准输出，只有select命令字有输出，每个select的输入case的输出格式为，第一行为该case后续输出的行数，第二行起，每行是一组由空格隔开的数字，数字的数量与表的列数量相同，输出的各行是按照从第一个字段到最后一个字段升序排列的；

输入例子：
create
5
1 3 4
insert
3
1 2 3 4 5
10 11 12 13 14
100 101 102 103 104
update
1
0 = 4 , 2 = 2 + 100 , 3 = 4 + 1000
1 > 10 and 1 < 100 and ( 2 > 5 or 2 < 1 )
select
2
no
no
delete
1
no
drop
上述输入的输出：
3
1 2 3 4 5
4 11 112 1014 14
100 101 102 103 104
3
1 2 3 4 5
4 11 112 1014 14
100 101 102 103 104

提示：进行update操作时请注意Halloween Problem

提示：本题的运行及编译环境：

Linux，2.6.30内核，4核CPU，CPU主频2.0G，8G内存，x86_64，gcc4.1，pthread，请注明编译参数

在输出正确的情况下，考察指标：1、速度快；2、占用内存少；3、valgrind给出的结果显示无错误和内存泄漏

#include<stdio.h>
#include<stdlib.h>
#include<sys/socket.h>
#include<netinet/in.h>
#include<linux/if_ether.h>
#include<signal.h>
#include<sys/types.h>
#include<linux/tcp.h>
#include<linux/udp.h>
#include<linux/ip.h>
#include<unistd.h>
#include<signal.h>
#include<pthread.h>
#include<malloc.h>
#define STREAMSIZE 10000
#define BUFSIZE 2048
#define CACHESIZE 20
/*stream item info struct*/
typedef struct {
unsigned short type;/*tcp or udp type */
unsigned int sport;
unsigned int dport;
unsigned int sip;
unsigned int dip;
unsigned long count;
unsigned long bytes;/*total bytes of a stream*/
}stream;
/*stream temp cache info struct*/
typedef struct {
unsigned int type;
unsigned int weight;
unsigned int sport;
unsigned int dport;
unsigned int sip;
unsigned int dip;
}cache_info;
cache_info cache_item[CACHESIZE]; /*streams last captured to make a queue*/
stream *item[STREAMSIZE]; /*items are for stream info*/
int capture=1;
unsigned int item_max=0; /* current total items*/
unsigned int proto,sip,dip,sport,dport,ip_h_len,n_read=0;
void report()
{
int i=0,j;
char pro_type[3];
printf(" protocol\tsrc\t\tdest\t sport dport packets\ttotal bytes\n");
for(i=1;i<=item_max;i++)
{
printf("\t%d\t%s\t%s %d %d %d\t\t%d\n",item[i]->type,inet_ntoa(item[i]->sip),inet_ntoa(item[i]->dip),ntohs(item[i]->sport),ntohs(item[i]->dport),item[i]->count,item[i]->bytes);
}
}
void sig_handle(int signo)
{
capture=0;
report();
exit(1);
}
/*function for caching items that did not find in cache queue*/
void insert_cache_item()
{
printf("insert cache_item");
int i,id=11;
for(i=0;i<CACHESIZE;i++)
{
id=(id < cache_item[i].weight)? id : (cache_item[i].weight);
if(cache_item[i].weight==0)
{
cache_item[i].type=proto;
printf(" %d\n",i);
cache_item[i].sport=sport;
cache_item[i].dport=dport;
cache_item[i].sip=sip;
cache_item[i].dip=dip;
cache_item[i].weight+=2;
break;
}
}
if(id>0) /*in the cache_item,all weight is great than 0,but we
find the smallest weight is id,so cache_item[id]will be
recoverd by the new stream*/
{
printf(" %d\n",id);
cache_item[id].type=proto;
cache_item[id].sport=sport;
cache_item[id].dport=dport;
cache_item[id].sip=sip;
cache_item[id].dip=dip;
cache_item[id].weight=+1;
}
}
/*search the stream current captured in our cache_item.
the cache_item contains an item "weight" to record
how offen this stream being captured recently.when capture
a stream,first check it in cache_item,if find a match one,good,we
need not to search the big item array which contains all
stream items we captured before.
the algorithm of the weight is sample,weight is bettween 0-10,
when first insert into cache_item or the current captured stream
has been in cache_item,we add 2 to the stream weight.and at the
same time sub 1 to other stream item's weight.when the cache_item
is full,the item which has the smallest weight will be coverd.and
this is done by the insert_cache_item function*/
int search_cache_item()
{
int i,j=-1;
for(i=0;i<CACHESIZE;++i)
{
if(cache_item[i].type=proto&&cache_item[i].sport==sport&&cache_item[i].dport==dport&&cache_item[i].sip==sip&&cache_item[i].dip==dip)
{
if(cache_item[i].weight<=10)
{
cache_item[i].weight+=2;
}
j=i;
}/*we hava find one that match the current stream*/
else
{
if(cache_item[i].weight>=1)
cache_item[i].weight-=1;
}
}
printf("search_cache_item result is %d\n",j);
return j;
}
/*function to search the stream current captured
in the item[] which contains all the streams captured
before.*/
int search_item()
{
printf(" search in the item \n");
int i=0,j;
for(i=0;i<item_max;i++)
{
if(item[i]->sip==sip&&item[i]->sport==sport&&item[i]->dport==dport&&item[i]->type==proto&&item[i]->dip==dip)
{
item[i]->count+=1;
item[i]->bytes+=n_read;
break;
}
}
j=(i<item_max)? 1:-1;
printf("search in the item result is %d\n",j);
return j;
}
/*function to add the current stream captured to
the stream struct list*/
int add_to_item()
{
if(item_max<STREAMSIZE)
{
printf("item_max is %d\n",item_max);
item[item_max]=(stream *)(malloc(sizeof(stream)));
memset(item[item_max],0,sizeof(stream));
item[item_max]->type=proto;
item[item_max]->sip=sip;
item[item_max]->dip=dip;
item[item_max]->sport=sport;
item[item_max]->dport=dport;
item[item_max]->bytes+=n_read;
item[item_max]->count=+1;
item_max=item_max+1;
}
else
{
fprintf(stderr,"stream is to large please change the STREAMSIZE\n");
exit(1);
}
}
void main(int argc,char *argv[])
{
int i,ret,id,sockfd;
char buf[BUFSIZE];
struct tcphdr *tcp_head;
struct udphdr *udp_head;
struct iphdr *ip_head;
char *p;
for(i=0;i<CACHESIZE;i++)
{
cache_item[i].weight=0;
}
signal(SIGINT,sig_handle);
if((sockfd = socket(PF_PACKET,SOCK_RAW,htons(ETH_P_IP)))<0)
{
fprintf(stderr,"socket error\n");
printf("%d","sockfd");
exit(1);
}
while(capture)
{
n_read = recvfrom(sockfd,buf,BUFSIZE,0,NULL,NULL);
ip_head = (struct iphdr *)(buf+14);
/*14=6 source mac address
6 destnation mac address
2 type
*/
proto=ip_head->protocol;
sip=ip_head->saddr;
dip=ip_head->daddr;
ip_h_len=ip_head->ihl<<2;
if(proto==IPPROTO_TCP)
{
tcp_head = (struct tcphdr *)(buf+14+ip_h_len);
sport=tcp_head->source;
dport=tcp_head->dest;
if((id=search_cache_item())>=0)/*current stream is in cache*/
{
item[id]->count+=1;
item[id]->bytes+=n_read;
printf("use cache info\n");
}
else
{
insert_cache_item(); /*cache it */
if((ret=search_item())<0)
{
add_to_item();
}
}
}
else if(proto==IPPROTO_UDP)
{
udp_head=(struct udphdr *)(buf+14+ip_h_len);
sport=udp_head->source;
dport=udp_head->dest;
if(id=search_cache_item()>0)
{
item[id]->count+=1;
item[id]->bytes+=n_read;
}
else
{
insert_cache_item();
if(search_item()<0)
add_to_item();
}
}
}
}

复制代码