From b27d8f616c4b97e1a35c2f0f347832e316de1c59 Mon Sep 17 00:00:00 2001 From: FlavioJS Date: Thu, 28 Dec 2006 19:11:40 +0000 Subject: - Part 3 of TheUltraMage's socket cleanup. - Fixed the packet structure in mmo_char_send006b for PACKETVER 8. - Removed search_str from add_str (add_str already searches for the string). - Native script words like do,while,for,... are case insensitive now. - Changed SCRIPT_HASH_SIZE to 1021 (prime hash sizes give better distributions). - Added alternative hash implementations to the script engine (to try out later). removed int_homun.c from header section of the VS8 map project files git-svn-id: https://rathena.svn.sourceforge.net/svnroot/rathena/trunk@9588 54d463be-8e91-2dee-dedb-b68131a5f0ec --- src/char/char.c | 26 +++++------ src/char_sql/char.c | 9 +--- src/common/socket.c | 82 +++++++++++++++------------------- src/map/script.c | 125 +++++++++++++++++++++++++++++++++++++--------------- 4 files changed, 141 insertions(+), 101 deletions(-) (limited to 'src') diff --git a/src/char/char.c b/src/char/char.c index dd229999d..16dfe1192 100644 --- a/src/char/char.c +++ b/src/char/char.c @@ -1694,7 +1694,12 @@ int mmo_char_send006b(int fd, struct char_session_data *sd) { for(i = 0; i < found_num; i++) { p = &char_dat[sd->found_char[i]].status; +#if PACKETVER > 7 + j = offset + (found_num * 2) + (i * 106); // increase speed of code + WFIFOW(fd,offset+(i*2)) = 1; //TODO: Handle this rename bit: 0 to enable renaming +#else j = offset + (i * 106); // increase speed of code +#endif WFIFOL(fd,j) = p->char_id; WFIFOL(fd,j+4) = p->base_exp>LONG_MAX?LONG_MAX:p->base_exp; @@ -1709,7 +1714,7 @@ int mmo_char_send006b(int fd, struct char_session_data *sd) { WFIFOL(fd,j+32) = p->karma; WFIFOL(fd,j+36) = p->manner; - WFIFOW(fd,j+40) = (p->status_point>SHRT_MAX) ? SHRT_MAX : p->status_point; + WFIFOW(fd,j+40) = (p->status_point > SHRT_MAX) ? SHRT_MAX : p->status_point; WFIFOW(fd,j+42) = (p->hp > SHRT_MAX) ? SHRT_MAX : p->hp; WFIFOW(fd,j+44) = (p->max_hp > SHRT_MAX) ? SHRT_MAX : p->max_hp; WFIFOW(fd,j+46) = (p->sp > SHRT_MAX) ? SHRT_MAX : p->sp; @@ -1719,7 +1724,7 @@ int mmo_char_send006b(int fd, struct char_session_data *sd) { WFIFOW(fd,j+54) = p->hair; WFIFOW(fd,j+56) = p->option&0x20?0:p->weapon; //When the weapon is sent and your option is riding, the client crashes on login!? WFIFOW(fd,j+58) = p->base_level; - WFIFOW(fd,j+60) = (p->skill_point>SHRT_MAX)? SHRT_MAX : p->skill_point; + WFIFOW(fd,j+60) = (p->skill_point > SHRT_MAX) ? SHRT_MAX : p->skill_point; WFIFOW(fd,j+62) = p->head_bottom; WFIFOW(fd,j+64) = p->shield; WFIFOW(fd,j+66) = p->head_top; @@ -1729,18 +1734,13 @@ int mmo_char_send006b(int fd, struct char_session_data *sd) { memcpy(WFIFOP(fd,j+74), p->name, NAME_LENGTH); - WFIFOB(fd,j+98) = (p->str > 255) ? 255 : p->str; - WFIFOB(fd,j+99) = (p->agi > 255) ? 255 : p->agi; - WFIFOB(fd,j+100) = (p->vit > 255) ? 255 : p->vit; - WFIFOB(fd,j+101) = (p->int_ > 255) ? 255 : p->int_; - WFIFOB(fd,j+102) = (p->dex > 255) ? 255 : p->dex; - WFIFOB(fd,j+103) = (p->luk > 255) ? 255 : p->luk; -#if PACKETVER > 7 + WFIFOB(fd,j+98) = (p->str > UCHAR_MAX) ? UCHAR_MAX : p->str; + WFIFOB(fd,j+99) = (p->agi > UCHAR_MAX) ? UCHAR_MAX : p->agi; + WFIFOB(fd,j+100) = (p->vit > UCHAR_MAX) ? UCHAR_MAX : p->vit; + WFIFOB(fd,j+101) = (p->int_ > UCHAR_MAX) ? UCHAR_MAX : p->int_; + WFIFOB(fd,j+102) = (p->dex > UCHAR_MAX) ? UCHAR_MAX : p->dex; + WFIFOB(fd,j+103) = (p->luk > UCHAR_MAX) ? UCHAR_MAX : p->luk; WFIFOW(fd,j+104) = p->char_num; - WFIFOB(fd,j+106) = 1; //TODO: Handle this rename bit: 0 to enable renaming -#else - WFIFOB(fd,j+104) = p->char_num; -#endif } WFIFOSET(fd,WFIFOW(fd,2)); diff --git a/src/char_sql/char.c b/src/char_sql/char.c index 95b713307..3c1a98a12 100644 --- a/src/char_sql/char.c +++ b/src/char_sql/char.c @@ -1725,7 +1725,8 @@ int mmo_char_send006b(int fd, struct char_session_data *sd) { p = &char_dat; #if PACKETVER > 7 - j = offset + (i * 108); + j = offset + (found_num * 2) + (i * 108); + WFIFOW(fd,offset+(i*2)) = 1; //TODO: Handle this rename bit: 0 to enable renaming //Updated packet structure with rename-button included. Credits to Sara-chan #else j = offset + (i * 106); // increase speed of code #endif @@ -1769,13 +1770,7 @@ int mmo_char_send006b(int fd, struct char_session_data *sd) { WFIFOB(fd,j+101) = (p->int_ > UCHAR_MAX) ? UCHAR_MAX : p->int_; WFIFOB(fd,j+102) = (p->dex > UCHAR_MAX) ? UCHAR_MAX : p->dex; WFIFOB(fd,j+103) = (p->luk > UCHAR_MAX) ? UCHAR_MAX : p->luk; -#if PACKETVER > 7 - //Updated packet structure with rename-button included. Credits to Sara-chan WFIFOW(fd,j+104) = p->char_num; - WFIFOB(fd,j+106) = 1; //TODO: Handle this rename bit: 0 to enable renaming -#else - WFIFOB(fd,j+104) = p->char_num; -#endif } WFIFOSET(fd,WFIFOW(fd,2)); // printf("mmo_char_send006b end..\n"); diff --git a/src/common/socket.c b/src/common/socket.c index 0bcc979da..81411808e 100644 --- a/src/common/socket.c +++ b/src/common/socket.c @@ -6,7 +6,7 @@ #include #ifdef __WIN32 - #define __USE_W32_SOCKETS + #define WIN32_LEAN_AND_MEAN #include #include #include @@ -23,21 +23,28 @@ #include #ifndef SIOCGIFCONF - #include // SIOCGIFCONF on Solaris, maybe others? [Shinomori] + #include // SIOCGIFCONF on Solaris, maybe others? [Shinomori] #endif #endif // portability layer #ifdef _WIN32 typedef int socklen_t; - #define EBADF WSAENOTSOCK - #define ECONNABORTED WSAECONNABORTED - #define EAGAIN WSAEWOULDBLOCK + + #define s_errno WSAGetLastError() + #define S_ENOTSOCK WSAENOTSOCK + #define S_EWOULDBLOCK WSAEWOULDBLOCK + #define S_ECONNABORTED WSAECONNABORTED #else #define SOCKET_ERROR -1 #define INVALID_SOCKET -1 #define ioctlsocket ioctl #define closesocket close + + #define s_errno errno + #define S_ENOTSOCK EBADF + #define S_EWOULDBLOCK EAGAIN + #define S_ECONNABORTED ECONNABORTED #endif #include @@ -55,11 +62,6 @@ time_t last_tick; time_t stall_time = 60; int ip_rules = 1; -// reuse port -#ifndef SO_REUSEPORT - #define SO_REUSEPORT 15 -#endif - #ifndef TCP_FRAME_LEN #define TCP_FRAME_LEN 1024 #endif @@ -126,7 +128,7 @@ void set_nonblocking(int fd, int yes) // FIONBIO Use with a nonzero argp parameter to enable the nonblocking mode of socket s. // The argp parameter is zero if nonblocking is to be disabled. if (ioctlsocket(fd, FIONBIO, &yes) != 0) - ShowError("Couldn't set the socket to non-blocking mode (code %d)!\n", h_errno); + ShowError("Couldn't set the socket to non-blocking mode (code %d)!\n", s_errno); } static void setsocketopts(int fd) @@ -176,12 +178,12 @@ static int recv_to_fifo(int fd) len = recv(fd, (char *) session[fd]->rdata + session[fd]->rdata_size, RFIFOSPACE(fd), 0); if (len == SOCKET_ERROR) { - if (h_errno == ECONNABORTED) { + if (s_errno == S_ECONNABORTED) { ShowWarning("recv_to_fifo: Software caused connection abort on session #%d\n", fd); FD_CLR(fd, &readfds); //Remove the socket so the select() won't hang on it. } - if (h_errno != EAGAIN) { - ShowDebug("recv_to_fifo: error %d, ending connection #%d\n", h_errno, fd); + if (s_errno != S_EWOULDBLOCK) { + ShowDebug("recv_to_fifo: error %d, ending connection #%d\n", s_errno, fd); set_eof(fd); } return 0; @@ -210,14 +212,14 @@ static int send_from_fifo(int fd) len = send(fd, (const char *) session[fd]->wdata, session[fd]->wdata_size, 0); if (len == SOCKET_ERROR) { - if (h_errno == ECONNABORTED) { + if (s_errno == S_ECONNABORTED) { ShowWarning("send_from_fifo: Software caused connection abort on session #%d\n", fd); session[fd]->wdata_size = 0; //Clear the send queue as we can't send anymore. [Skotlex] set_eof(fd); FD_CLR(fd, &readfds); //Remove the socket so the select() won't hang on it. } - if (h_errno != EAGAIN) { - ShowDebug("send_from_fifo: error %d, ending connection #%d\n", h_errno, fd); + if (s_errno != S_EWOULDBLOCK) { + ShowDebug("send_from_fifo: error %d, ending connection #%d\n", s_errno, fd); session[fd]->wdata_size = 0; //Clear the send queue as we can't send anymore. [Skotlex] set_eof(fd); } @@ -275,7 +277,7 @@ static int connect_client(int listen_fd) fd = accept(listen_fd,(struct sockaddr*)&client_address,&len); if ( fd == INVALID_SOCKET ) { - ShowError("accept failed (code %i)!\n", h_errno); + ShowError("accept failed (code %i)!\n", s_errno); return -1; } @@ -316,7 +318,7 @@ int make_listen_bind(long ip,int port) fd = (int)socket( AF_INET, SOCK_STREAM, 0 ); if (fd == INVALID_SOCKET) { - ShowError("socket() creation failed (code %d)!\n", fd, h_errno); + ShowError("socket() creation failed (code %d)!\n", fd, s_errno); exit(1); } @@ -329,12 +331,12 @@ int make_listen_bind(long ip,int port) result = bind(fd, (struct sockaddr*)&server_address, sizeof(server_address)); if( result == SOCKET_ERROR ) { - ShowError("bind failed (socket %d, code %d)!\n", fd, h_errno); + ShowError("bind failed (socket %d, code %d)!\n", fd, s_errno); exit(1); } result = listen( fd, 5 ); if( result == SOCKET_ERROR ) { - ShowError("listen failed (socket %d, code %d)!\n", fd, h_errno); + ShowError("listen failed (socket %d, code %d)!\n", fd, s_errno); exit(1); } if ( fd < 0 || fd > FD_SETSIZE ) @@ -444,7 +446,7 @@ int make_connection(long ip,int port) fd = (int)socket( AF_INET, SOCK_STREAM, 0 ); if (fd == INVALID_SOCKET) { - ShowError("socket() creation failed (code %d)!\n", fd, h_errno); + ShowError("socket() creation failed (code %d)!\n", fd, s_errno); return -1; } @@ -459,7 +461,7 @@ int make_connection(long ip,int port) result = connect(fd, (struct sockaddr *)(&server_address), sizeof(struct sockaddr_in)); if( result == SOCKET_ERROR ) { - ShowError("connect failed (socket %d, code %d)!\n", fd, h_errno); + ShowError("connect failed (socket %d, code %d)!\n", fd, s_errno); do_close(fd); return -1; } @@ -598,8 +600,7 @@ int do_sendrecv(int next) fd_set rfd,efd; //Added the Error Set so that such sockets can be made eof. They are the same as the rfd for now. [Skotlex] struct sockaddr_in addr_check; struct timeval timeout; - int ret,i; - const int size = sizeof(struct sockaddr); + int ret,i,size; last_tick = time(0); @@ -624,7 +625,7 @@ int do_sendrecv(int next) memcpy(&rfd, &readfds, sizeof(rfd)), memcpy(&efd, &readfds, sizeof(efd))) { - if(h_errno != EBADF) + if(s_errno != S_ENOTSOCK) return 0; //Well then the error is due to a bad socket. Lets find and remove it @@ -632,32 +633,22 @@ int do_sendrecv(int next) for(i = 1; i < fd_max; i++) { if(!session[i]) - { - if (FD_ISSET(i, &readfds)) { - ShowError("Deleting non-cleared session %d\n", i); - FD_CLR(i, &readfds); - } continue; - } //check the validity of the socket. Does what the last thing did //just alot faster [Meruru] + size = sizeof(struct sockaddr); if(getsockname(i,(struct sockaddr*)&addr_check,&size)<0) - if(h_errno == EBADF) //See the #defines at the top + if(s_errno == S_ENOTSOCK) { - ShowError("Deleting invalid session %d\n", i); - //So the code can react accordingly - session[i]->eof = 1; - if(session[i]->func_parse) - session[i]->func_parse(i); free_session_mem(i); //free the bad session continue; } - - if (!FD_ISSET(i, &readfds)) - FD_SET(i,&readfds); + + FD_SET(i,&readfds); ret = i; } + fd_max = ret; } @@ -673,10 +664,8 @@ int do_sendrecv(int next) session[rfd.fd_array[i]]->func_recv) session[rfd.fd_array[i]]->func_recv(rfd.fd_array[i]); } - for(i=0;i<(int)efd.fd_count;i++) { - ShowDebug("do_sendrecv: Connection error on Session %d.\n", efd.fd_array[i]); + for(i=0;i<(int)efd.fd_count;i++) set_eof(efd.fd_array[i]); - } for (i = 1; i < fd_max; i++) { @@ -690,7 +679,7 @@ int do_sendrecv(int next) if(session[i]->wdata_size && session[i]->func_send) session[i]->func_send(i); - if(session[i]->eof) //func_send can't free a session, this is safe. + if(session[i] && session[i]->eof) //The session check is for when the connection ended in func_parse { //Finally, even if there is no data to parse, connections signalled eof should be closed, so we call parse_func [Skotlex] if (session[i]->func_parse) session[i]->func_parse(i); //This should close the session inmediately. @@ -710,6 +699,7 @@ int do_sendrecv(int next) continue; } + if(FD_ISSET(i,&rfd)){ //ShowMessage("read:%d\n",i); if(session[i]->func_recv) @@ -721,7 +711,7 @@ int do_sendrecv(int next) if(session[i]->wdata_size && session[i]->func_send) session[i]->func_send(i); - if(session[i]->eof) + if(session[i] && session[i]->eof) //The session check is for when the connection ended in func_parse { //Finally, even if there is no data to parse, connections signalled eof should be closed, so we call parse_func [Skotlex] if (session[i]->func_parse) session[i]->func_parse(i); //This should close the session inmediately. diff --git a/src/map/script.c b/src/map/script.c index 78ed1935f..8d338c6a4 100644 --- a/src/map/script.c +++ b/src/map/script.c @@ -78,8 +78,13 @@ static struct str_data_struct { int next; } *str_data = NULL; int str_num=LABEL_START,str_data_size; -#define SCRIPT_HASH_SIZE 1024 +// Using a prime number for SCRIPT_HASH_SIZE should give better distributions +#define SCRIPT_HASH_SIZE 1021 int str_hash[SCRIPT_HASH_SIZE]; +//#define SCRIPT_HASH_DJB2 +//#define SCRIPT_HASH_SDBM +//#define SCRIPT_HASH_ELF +//#define SCRIPT_HASH_PJW static struct dbt *mapreg_db=NULL; static struct dbt *mapregstr_db=NULL; @@ -272,18 +277,53 @@ static void check_event(struct script_state *st, const char *event){ } return; } + /*========================================== * 文字列のハッシュを計算 *------------------------------------------ */ -static int calc_hash(const unsigned char *p) -{ - int h=0; - while(*p){ - h=(h<<1)+(h>>3)+(h>>5)+(h>>8); +#define calc_hash(x) calc_hash2(x)%SCRIPT_HASH_SIZE +static unsigned int calc_hash2(const unsigned char *p) +{ +#if defined(SCRIPT_HASH_DJB2) + unsigned int h = 5381; + while( *p ) // hash*33 + c + h = ( h << 5 ) + h + ((unsigned char)tolower(*p++)); + return h; +#elif defined(SCRIPT_HASH_SDBM) + unsigned int h = 0; + while( *p ) + h = ( h << 6 ) + ( h << 16 ) - h + ((unsigned char)tolower(*p++)); + return h; +#elif defined(SCRIPT_HASH_ELF) + unsigned int h = 0; + unsigned int g; + while( *p ){ // UNIX ELF hash + h = ( h << 4 ) + ((unsigned char)tolower(*p++)); + if ( g = h & 0xF0000000 ) + h ^= g >> 24; + h &= ~g; + } + return h; +#elif defined(SCRIPT_HASH_PJW) + unsigned int h = 0; + unsigned int g; + while( *p ){ + h = ( h << 4 ) + ((unsigned char)tolower(*p++)); + if ( (g=h&0xF0000000) ) { + h ^= g>>24; + h ^= g; + } + } + return h; +#else + unsigned int h = 0; + while( *p ){ + h = ( h << 1 ) + ( h >> 3 ) + ( h >> 5 ) + ( h >> 8 ); h+=(unsigned char)tolower(*p++); } - return h&(SCRIPT_HASH_SIZE-1); + return h; +#endif } /*========================================== @@ -314,9 +354,6 @@ int add_str(const char* p) int i; int len; - if((i=search_str(p)) >= 0) - return i; - i=calc_hash(p); if(str_hash[i]==0){ str_hash[i]=str_num; @@ -922,7 +959,7 @@ const char* parse_curly_close(const char* p) { const char* parse_syntax(const char* p) { switch(*p) { case 'b': - if(!strncmp(p,"break",5) && !ISALPHA(p[5])) { + if(!strncasecmp(p,"break",5) && !ISALPHA(p[5])) { // break の処理 char label[256]; int pos = syntax.curly_count - 1; @@ -957,7 +994,7 @@ const char* parse_syntax(const char* p) { } break; case 'c': - if(!strncmp(p,"case",4) && !ISALPHA(p[4])) { + if(!strncasecmp(p,"case",4) && !ISALPHA(p[4])) { // case の処理 if(syntax.curly_count <= 0 || syntax.curly[syntax.curly_count - 1].type != TYPE_SWITCH) { disp_error_message("parse_syntax: unexpected 'case' ",p); @@ -1012,7 +1049,7 @@ const char* parse_syntax(const char* p) { syntax.curly[pos].count++; } return p + 1; - } else if(!strncmp(p,"continue",8) && !ISALPHA(p[8])) { + } else if(!strncasecmp(p,"continue",8) && !ISALPHA(p[8])) { // continue の処理 char label[256]; int pos = syntax.curly_count - 1; @@ -1045,7 +1082,7 @@ const char* parse_syntax(const char* p) { } break; case 'd': - if(!strncmp(p,"default",7) && !ISALPHA(p[7])) { + if(!strncasecmp(p,"default",7) && !ISALPHA(p[7])) { // switch - default の処理 if(syntax.curly_count <= 0 || syntax.curly[syntax.curly_count - 1].type != TYPE_SWITCH) { disp_error_message("parse_syntax: unexpected 'default'",p); @@ -1085,7 +1122,7 @@ const char* parse_syntax(const char* p) { p = skip_word(p); return p + 1; } - } else if(!strncmp(p,"do",2) && !ISALPHA(p[2])) { + } else if(!strncasecmp(p,"do",2) && !ISALPHA(p[2])) { int l; char label[256]; p=skip_word(p); @@ -1104,7 +1141,7 @@ const char* parse_syntax(const char* p) { } break; case 'f': - if(!strncmp(p,"for",3) && !ISALPHA(p[3])) { + if(!strncasecmp(p,"for",3) && !ISALPHA(p[3])) { int l; char label[256]; int pos = syntax.curly_count; @@ -1183,7 +1220,7 @@ const char* parse_syntax(const char* p) { l=add_str(label); set_label(l,script_pos,p); return p; - } else if(!strncmp(p,"function",8) && !ISALPHA(p[8])) { + } else if(!strncasecmp(p,"function",8) && !ISALPHA(p[8])) { const char *func_name; // function p=skip_word(p); @@ -1226,7 +1263,7 @@ const char* parse_syntax(const char* p) { } break; case 'i': - if(!strncmp(p,"if",2) && !ISALPHA(p[2])) { + if(!strncasecmp(p,"if",2) && !ISALPHA(p[2])) { // if() の処理 char label[256]; p=skip_word(p); @@ -1250,7 +1287,7 @@ const char* parse_syntax(const char* p) { } break; case 's': - if(!strncmp(p,"switch",6) && !ISALPHA(p[6])) { + if(!strncasecmp(p,"switch",6) && !ISALPHA(p[6])) { // switch() の処理 char label[256]; p=skip_word(p); @@ -1277,7 +1314,7 @@ const char* parse_syntax(const char* p) { } break; case 'w': - if(!strncmp(p,"while",5) && !ISALPHA(p[5])) { + if(!strncasecmp(p,"while",5) && !ISALPHA(p[5])) { int l; char label[256]; p=skip_word(p); @@ -1347,11 +1384,11 @@ const char* parse_syntax_close_sub(const char* p,int* flag) { syntax.curly[pos].count++; p = skip_space(p); - if(!syntax.curly[pos].flag && !strncmp(p,"else",4) && !ISALPHA(p[4])) { + if(!syntax.curly[pos].flag && !strncasecmp(p,"else",4) && !ISALPHA(p[4])) { // else or else - if p = skip_word(p); p = skip_space(p); - if(!strncmp(p,"if",2) && !ISALPHA(p[2])) { + if(!strncasecmp(p,"if",2) && !ISALPHA(p[2])) { // else - if p=skip_word(p); p=skip_space(p); @@ -1402,7 +1439,7 @@ const char* parse_syntax_close_sub(const char* p,int* flag) { // 条件が偽なら終了地点に飛ばす p = skip_space(p); p2 = skip_word(p); - if(p2 - p != 5 || strncmp("while",p,5)) { + if(p2 - p != 5 || strncasecmp("while",p,5)) { disp_error_message("parse_syntax: need 'while'",p); } @@ -1662,7 +1699,7 @@ struct script_code* parse_script(const char *src,const char *file,int line,int o p=skip_space(p); // labelだけ特殊処理 tmpp=skip_space(skip_word(p)); - if(*tmpp==':' && !(!strncmp(p,"default:",8) && p + 7 == tmpp)){ + if(*tmpp==':' && !(!strncasecmp(p,"default:",8) && p + 7 == tmpp)){ i=add_word(p); set_label(i,script_pos,p); if( parse_options&SCRIPT_USE_LABEL_DB ) @@ -3266,24 +3303,25 @@ int do_final_script() FILE *fp = fopen("hash_dump.txt","wt"); if(fp) { int i,count[SCRIPT_HASH_SIZE]; - int min=0x7fffffff,max=0,zero=0; + int count2[SCRIPT_HASH_SIZE]; // number of buckets with a certain number of items + int n=0; + int min=INT_MAX,max=0,zero=0; + double mean=0.0f; + double median=0.0f; ShowNotice("Dumping script str hash information to hash_dump.txt\n"); memset(count, 0, sizeof(count)); fprintf(fp,"num : calced_val -> hash : data_name\n"); fprintf(fp,"---------------------------------------------------------------\n"); for(i=LABEL_START; i>3)+(h>>5)+(h>>8); - h+=(unsigned char)tolower(*p++); - } - fprintf(fp,"%04d: %10d -> %3d : %s\n",i,h,h&(SCRIPT_HASH_SIZE-1),str_buf+str_data[i].str); - count[h&(SCRIPT_HASH_SIZE-1)]++; + unsigned int h2=calc_hash2(str_buf+str_data[i].str); + unsigned int h =h2%SCRIPT_HASH_SIZE; + fprintf(fp,"%04d: %10u -> %3u : %s\n",i,h2,h,str_buf+str_data[i].str); + ++count[h]; } fprintf(fp,"--------------------\n\n"); - for(i=0; i count[i]) min = count[i]; // minimun count of collision @@ -3291,8 +3329,25 @@ int do_final_script() max = count[i]; // maximun count of collision if(count[i] == 0) zero++; + ++count2[count[i]]; + } + fprintf(fp,"\n--------------------\n items : buckets\n--------------------\n"); + for( i=min; i <= max; ++i ){ + fprintf(fp," %5d : %7d\n",i,count2[i]); + mean += 1.0f*i*count2[i]/SCRIPT_HASH_SIZE; // Note: this will always result in / + } + for( i=min; i <= max; ++i ){ + n += count2[i]; + if( n*2 >= SCRIPT_HASH_SIZE ) + { + if( SCRIPT_HASH_SIZE%2 == 0 && SCRIPT_HASH_SIZE/2 == n ) + median = (i+i+1)/2.0f; + else + median = i; + break; + } } - fprintf(fp,"--------------------\n min = %d, max = %d, zero = %d\n",min,max,zero); + fprintf(fp,"--------------------\n min = %d, max = %d, zero = %d\n mean = %lf, median = %lf\n",min,max,zero,mean,median); fclose(fp); } } -- cgit v1.2.3-70-g09d2