From 7d534bbf798a4036dd3cee1c36df05b2c34defe8 Mon Sep 17 00:00:00 2001 From: bustico Date: Mon, 24 Jan 2011 13:39:15 +0000 Subject: make ivy-c c++ compiler compliant use last version (1.9.3) of uthash header --- src/intervalRegexp.c | 4 +- src/ivy.c | 44 +- src/ivy.h | 4 +- src/ivybind.c | 2 +- src/ivybuffer.c | 4 +- src/ivychannel.h | 12 +- src/ivyfifo.c | 6 +- src/ivyglibloop.c | 4 +- src/ivyglutloop.c | 2 +- src/ivyloop.c | 6 +- src/ivyloop.h | 4 +- src/ivysocket.c | 40 +- src/ivysocket.h | 14 +- src/ivytcl.c | 8 +- src/ivyxtloop.c | 4 +- src/uthash.h | 1363 ++++++++++++++++++++++++++++++----------------- tools/ivyperf.c | 2 +- tools/ivyprobe.c | 6 +- tools/ivythroughput.cpp | 32 +- 19 files changed, 979 insertions(+), 582 deletions(-) diff --git a/src/intervalRegexp.c b/src/intervalRegexp.c index a513178..1425df5 100644 --- a/src/intervalRegexp.c +++ b/src/intervalRegexp.c @@ -34,7 +34,9 @@ typedef struct { } NextMax ; +#ifndef __cplusplus typedef char bool; +#endif const bool success = 1; const bool fail = 0; @@ -389,7 +391,7 @@ static char* reverse (char *string) int i; size_t len = strlen (string); - locBuf = malloc (len+1); + locBuf = (char *) malloc (len+1); for (i=len-1; i >= 0; i--) { locBuf[len-i-1]= string[i]; /*printf ("DBG> reverse locBuf[%d]= %c\n",len- i-1, string[i]); */ diff --git a/src/ivy.c b/src/ivy.c index 672d688..80f9bf6 100644 --- a/src/ivy.c +++ b/src/ivy.c @@ -62,7 +62,7 @@ * effectuée si on stringifie directement dans la macro GenerateIvyBus */ #define str(bus) #bus #define GenerateIvyBus(domain,bus) str(domain)":"str(bus) -static char* DefaultIvyBus = GenerateIvyBus(DEFAULT_DOMAIN,IVY_DEFAULT_BUS); +static const char* DefaultIvyBus = GenerateIvyBus(DEFAULT_DOMAIN,IVY_DEFAULT_BUS); typedef enum { Bye, /* l'application emettrice se termine */ @@ -252,7 +252,7 @@ static SendState MsgSendTo(IvyClientPtr ivyClient, IvyApplicationCongestion); #ifdef DEBUG { - char *remotehost; + const char *remotehost; unsigned short remoteport; /* probably bogus call, but this is for debug only anyway */ SocketGetRemoteHost( ivyClient->client, &remotehost, &remoteport ); @@ -266,7 +266,7 @@ static SendState MsgSendTo(IvyClientPtr ivyClient, IvyApplicationFifoFull); #ifdef DEBUG { - char *remotehost; + const char *remotehost; unsigned short remoteport; /* probably bogus call, but this is for debug only anyway */ SocketGetRemoteHost( ivyClient->client, &remotehost, &remoteport ); @@ -321,7 +321,7 @@ ClientCall (IvyClientPtr clnt, const char *message) MsgSndDictPtr msgSendDict; for (msgSendDict=messSndByRegexp; msgSendDict != NULL; - msgSendDict=msgSendDict->hh.next) { + msgSendDict= (MsgSndDictPtr) msgSendDict->hh.next) { match_count += RegexpCallUnique (msgSendDict, message, clnt->client); } @@ -392,7 +392,7 @@ RegexpCall (const MsgSndDictPtr msg, const char * const message) IvyApplicationCongestion); #ifdef DEBUG { - char *remotehost; + const char *remotehost; unsigned short remoteport; /* probably bogus call, but this is for debug only anyway */ SocketGetRemoteHost( clnt->client, &remotehost, &remoteport ); @@ -406,7 +406,7 @@ RegexpCall (const MsgSndDictPtr msg, const char * const message) IvyApplicationFifoFull); #ifdef DEBUG { - char *remotehost; + const char *remotehost; unsigned short remoteport; /* probably bogus call, but this is for debug only anyway */ SocketGetRemoteHost( clnt->client, &remotehost, &remoteport ); @@ -749,7 +749,7 @@ static void ClientDelete( Client client, const void *data ) IvyClientPtr clnt; #ifdef DEBUG - char *remotehost; + const char *remotehost; unsigned short remoteport; #endif clnt = (IvyClientPtr)data; @@ -770,7 +770,7 @@ static void ClientDecongestion ( Client client, const void *data ) IvyClientPtr clnt; #ifdef DEBUG - char *remotehost; + const char *remotehost; unsigned short remoteport; #endif clnt = (IvyClientPtr)data; @@ -791,7 +791,7 @@ static void *ClientCreate( Client client ) { char appName[64]; - char *remotehost; + const char *remotehost; unsigned short remoteport; SocketGetRemoteHost( client, &remotehost, &remoteport ); @@ -823,7 +823,7 @@ static void BroadcastReceive( Client client, const void *data, char *line ) char appid[128]; char appname[2048]; unsigned short remoteport; - char *remotehost = 0; + const char *remotehost = 0; memset( appid, 0, sizeof( appid ) ); memset( appname, 0, sizeof( appname ) ); @@ -909,9 +909,9 @@ void IvyInit (const char *appname, const char *ready, void IvyTerminate() { if ( ApplicationName ) - free( ApplicationName ); + free((void *) ApplicationName ); if ( ready_message ) - free( ready_message ); + free((void *) ready_message ); } void IvySetBindCallback( IvyBindCallback bind_callback, void *bind_data ) @@ -1249,7 +1249,7 @@ int IvySendMsg(const char *fmt, ...) /* version dictionnaire */ #else // PAS OPENMP - for (msgSendDict=messSndByRegexp; msgSendDict ; msgSendDict=msgSendDict->hh.next) { + for (msgSendDict=messSndByRegexp; msgSendDict ; msgSendDict=(MsgSndDictPtr) msgSendDict->hh.next) { match_count += RegexpCall (msgSendDict, buffer.data); } #endif @@ -1309,14 +1309,14 @@ void IvySendDieMsg(IvyClientPtr app ) MsgSendTo(app, Die, 0, "" ); } -char *IvyGetApplicationName(IvyClientPtr app ) +const char *IvyGetApplicationName(IvyClientPtr app ) { if ( app && app->app_name ) return app->app_name; else return "Unknown"; } -char *IvyGetApplicationHost(IvyClientPtr app ) +const char *IvyGetApplicationHost(IvyClientPtr app ) { if ( app && app->client ) return SocketGetPeerHost (app->client ); @@ -1420,7 +1420,7 @@ static void substituteInterval (IvyBuffer *src) char *itvPos; IvyBuffer dst = {NULL, 0, 0}; dst.size = 8192; - dst.data = malloc (dst.size); + dst.data = (char *) malloc (dst.size); curPos = src->data; while ((itvPos = strstr (curPos, "(?I")) != NULL) { @@ -1578,7 +1578,8 @@ static void delAllRegexpsFromDictionary () RWIvyClientPtr client; /* pour toutes les entrees du dictionnaire des regexps */ - for (msgSendDict=messSndByRegexp; msgSendDict ; msgSendDict=msgSendDict->hh.next) { + for (msgSendDict=messSndByRegexp; msgSendDict ; + msgSendDict= (MsgSndDictPtr) msgSendDict->hh.next) { /* on efface le binding */ IvyBindingFree (msgSendDict->binding); /* pour chaque client abonne a cette regexp */ @@ -1623,7 +1624,7 @@ static void addRegexpToDictionary (const char* regexp, IvyClientPtr client) const char *errbuf; int erroffset; - msgSendDict = malloc (sizeof (struct _msg_snd_dict)); + msgSendDict = (MsgSndDictPtr) malloc (sizeof (struct _msg_snd_dict)); msgSendDict->regexp_src = strdup (regexp); msgSendDict->binding = IvyBindingCompile(regexp, & erroffset, & errbuf ); @@ -1641,11 +1642,11 @@ static void addRegexpToDictionary (const char* regexp, IvyClientPtr client) {// DEBUG int debugSize=0, nDebugSize=0; MsgSndDictPtr msd; - for (msd=messSndByRegexp; msd ; msd=msd->hh.next) { + for (msd=messSndByRegexp; msd ; msd= (MsgSndDictPtr) msd->hh.next) { debugSize++; } HASH_ADD_KEYPTR(hh, messSndByRegexp, msgSendDict->regexp_src, strlen (msgSendDict->regexp_src), msgSendDict); - for (msd=messSndByRegexp; msd ; msd=msd->hh.next) { + for (msd=messSndByRegexp; msd ; msd= (MsgSndDictPtr) msd->hh.next) { nDebugSize++; } if ((nDebugSize-debugSize) != 1) { @@ -1737,7 +1738,8 @@ static void delOneClient (const Client client) // on libère la mémoire de l'element courrant dans le corp de la boucle // ce qui oblige a recuperer le champ next avant de faire ce free for ( msgSendDict = messSndByRegexp ; - (mnext = msgSendDict ? msgSendDict->hh.next: msgSendDict ),msgSendDict ; + (mnext = msgSendDict ? (MsgSndDictPtr) msgSendDict->hh.next + : msgSendDict ),msgSendDict ; msgSendDict = mnext ) { delOneClientFromDictionaryEntry (msgSendDict, client); } diff --git a/src/ivy.h b/src/ivy.h index 97841bd..286ea7a 100644 --- a/src/ivy.h +++ b/src/ivy.h @@ -80,8 +80,8 @@ void IvyStart (const char*); void IvyStop (void); /* query sur les applications connectees */ -char *IvyGetApplicationName( IvyClientPtr app ); -char *IvyGetApplicationHost( IvyClientPtr app ); +const char *IvyGetApplicationName( IvyClientPtr app ); +const char *IvyGetApplicationHost( IvyClientPtr app ); IvyClientPtr IvyGetApplication( char *name ); char *IvyGetApplicationList(const char *sep); char **IvyGetApplicationMessages( IvyClientPtr app); /* demande de reception d'un message */ diff --git a/src/ivybind.c b/src/ivybind.c index d433d1a..bbf422e 100644 --- a/src/ivybind.c +++ b/src/ivybind.c @@ -99,7 +99,7 @@ IvyBinding IvyBindingCompile( const char * expression, int *erroffset, const ch free( bind->ovector ); // + 1 pour la capture totale bind->ovectorsize = (capture_count+1) * 3; - bind->ovector = malloc( sizeof( int )* bind->ovectorsize); + bind->ovector = (int *) malloc( sizeof( int )* bind->ovectorsize); } else { diff --git a/src/ivybuffer.c b/src/ivybuffer.c index bbb1313..d21114f 100644 --- a/src/ivybuffer.c +++ b/src/ivybuffer.c @@ -40,7 +40,7 @@ int make_message(IvyBuffer* buffer, const char *fmt, va_list ap) { buffer->size = IVY_BUFFER_SIZE; buffer->offset = 0; - buffer->data = malloc (IVY_BUFFER_SIZE); + buffer->data = (char *) malloc (IVY_BUFFER_SIZE); if ( buffer->data == NULL ) { perror(" Ivy make message MALLOC error: " ); @@ -69,7 +69,7 @@ int make_message(IvyBuffer* buffer, const char *fmt, va_list ap) buffer->size = buffer->offset + n+1; /* precisely what is needed */ else /* glibc 2.0 */ buffer->size *= 2; /* twice the old size */ - if ((buffer->data = realloc (buffer->data, buffer->size)) == NULL) + if ((buffer->data = (char *) realloc (buffer->data, buffer->size)) == NULL) { perror(" Ivy make message REALLOC error: " ); return -1; diff --git a/src/ivychannel.h b/src/ivychannel.h index cc579b8..801fa25 100644 --- a/src/ivychannel.h +++ b/src/ivychannel.h @@ -25,17 +25,17 @@ extern "C" { #ifdef WIN32 #include -#define HANDLE SOCKET +#define IVY_HANDLE SOCKET #else -#define HANDLE int +#define IVY_HANDLE int #endif typedef struct _channel *Channel; /* callback declenche par la gestion de boucle sur evenement exception sur le canal */ typedef void (*ChannelHandleDelete)( void *data ); /* callback declenche par la gestion de boucle sur donnees pretes sur le canal */ -typedef void (*ChannelHandleRead)( Channel channel, HANDLE fd, void *data); -typedef void (*ChannelHandleWrite)( Channel channel, HANDLE fd, void *data); +typedef void (*ChannelHandleRead)( Channel channel, IVY_HANDLE fd, void *data); +typedef void (*ChannelHandleWrite)( Channel channel, IVY_HANDLE fd, void *data); /* fonction appele par le bus pour initialisation */ extern void IvyChannelInit(void); @@ -44,11 +44,11 @@ extern void IvyChannelStop (void); /* fonction appele par le bus pour mise en place des callback sur le canal */ extern Channel IvyChannelAdd( - HANDLE fd, + IVY_HANDLE fd, void *data, ChannelHandleDelete handle_delete, ChannelHandleRead handle_read, - ChannelHandleRead handle_write + ChannelHandleWrite handle_write ); /* fonction appele par le bus pour suppression des callback sur le canal */ diff --git a/src/ivyfifo.c b/src/ivyfifo.c index a13b276..b427dc3 100644 --- a/src/ivyfifo.c +++ b/src/ivyfifo.c @@ -29,7 +29,7 @@ static void IvyFifoDrain(IvyFifoBuffer *f, int size); int IvyFifoInit(IvyFifoBuffer *f) { f->wptr = f->rptr = - f->buffer = malloc(IVY_FIFO_ALLOC_SIZE); + f->buffer = (char *) malloc(IVY_FIFO_ALLOC_SIZE); f->end = f->buffer + IVY_FIFO_ALLOC_SIZE; f->full = 0; @@ -47,7 +47,7 @@ void IvyFifoFree (IvyFifoBuffer *f) IvyFifoBuffer* IvyFifoNew (void) { - IvyFifoBuffer* ifb = malloc (sizeof (IvyFifoBuffer)); + IvyFifoBuffer* ifb = (IvyFifoBuffer*) malloc (sizeof (IvyFifoBuffer)); IvyFifoInit (ifb); return (ifb); } @@ -93,7 +93,7 @@ void IvyFifoRealloc (IvyFifoBuffer *f, unsigned int new_size) IvyFifoBuffer f2; f2.wptr = f2.rptr = - f2.buffer = malloc(alignedNewSize); + f2.buffer = (char *) malloc(alignedNewSize); f2.end = f2.buffer + alignedNewSize; f2.full = 0; diff --git a/src/ivyglibloop.c b/src/ivyglibloop.c index 8bd2ad8..760d878 100644 --- a/src/ivyglibloop.c +++ b/src/ivyglibloop.c @@ -67,7 +67,7 @@ void IvyChannelInit(void) { -Channel IvyChannelAdd(HANDLE fd, void *data, +Channel IvyChannelAdd(IVY_HANDLE fd, void *data, ChannelHandleDelete handle_delete, ChannelHandleRead handle_read, ChannelHandleWrite handle_write @@ -85,7 +85,7 @@ Channel IvyChannelAdd(HANDLE fd, void *data, channel->io_channel = io_channel; channel->id_read = g_io_add_watch( io_channel, G_IO_IN, IvyGlibHandleChannelRead, channel); - channel->id_delete = g_io_add_watch( io_channel, G_IO_ERR | G_IO_HUP, + channel->id_delete = g_io_add_watch( io_channel, (GIOCondition) (G_IO_ERR | G_IO_HUP), IvyGlibHandleChannelDelete, channel); } return channel; diff --git a/src/ivyglutloop.c b/src/ivyglutloop.c index b383d8f..c472d1a 100644 --- a/src/ivyglutloop.c +++ b/src/ivyglutloop.c @@ -90,7 +90,7 @@ static void IvyGlutHandleChannelDelete( int source, GLUTInputId id, void *data ) (*channel->handle_delete)(channel->data); } -Channel IvyChannelAdd(HANDLE fd, void *data, +Channel IvyChannelAdd(IVY_HANDLE fd, void *data, ChannelHandleDelete handle_delete, ChannelHandleRead handle_read ) diff --git a/src/ivyloop.c b/src/ivyloop.c index bda5cc7..f4bc6fc 100644 --- a/src/ivyloop.c +++ b/src/ivyloop.c @@ -42,7 +42,7 @@ struct _channel { Channel next; - HANDLE fd; + IVY_HANDLE fd; void *data; int tobedeleted; ChannelHandleDelete handle_delete; @@ -56,7 +56,7 @@ static int channel_initialized = 0; static fd_set open_fds; static fd_set wrdy_fds; -static HANDLE highestFd=0; +static IVY_HANDLE highestFd=0; static int MainLoop = 1; @@ -99,7 +99,7 @@ ChannelDefferedDelete () } } -Channel IvyChannelAdd (HANDLE fd, void *data, +Channel IvyChannelAdd (IVY_HANDLE fd, void *data, ChannelHandleDelete handle_delete, ChannelHandleRead handle_read, ChannelHandleWrite handle_write diff --git a/src/ivyloop.h b/src/ivyloop.h index 63e30f3..5639495 100644 --- a/src/ivyloop.h +++ b/src/ivyloop.h @@ -31,9 +31,9 @@ extern "C" { #ifdef WIN32 #include -#define HANDLE SOCKET +#define IVY_HANDLE SOCKET #else -#define HANDLE int +#define IVY_HANDLE int #endif /* diff --git a/src/ivysocket.c b/src/ivysocket.c index a1f24e5..2dacb19 100644 --- a/src/ivysocket.c +++ b/src/ivysocket.c @@ -61,7 +61,7 @@ typedef long ssize_t; struct _server { Server next; - HANDLE fd; + IVY_HANDLE fd; Channel channel; unsigned short port; int ipv6; @@ -73,7 +73,7 @@ struct _server { struct _client { Client next; - HANDLE fd; + IVY_HANDLE fd; Channel channel; unsigned short port; char app_uuid[128]; @@ -148,7 +148,7 @@ static void DeleteServerSocket(void *data) } -static void HandleSocket (Channel channel, HANDLE fd, void *data) +static void HandleSocket (Channel channel, IVY_HANDLE fd, void *data) { Client client = (Client)data; char *ptr; @@ -163,7 +163,7 @@ static void HandleSocket (Channel channel, HANDLE fd, void *data) nb_to_read = client->buffer_size - nb_occuped; if (nb_to_read == 0 ) { client->buffer_size *= 2; /* twice old size */ - client->buffer = realloc( client->buffer, client->buffer_size ); + client->buffer = (char *) realloc( client->buffer, client->buffer_size ); if (!client->buffer ) { fprintf(stderr,"HandleSocket Buffer Memory Alloc Error\n"); @@ -186,7 +186,7 @@ static void HandleSocket (Channel channel, HANDLE fd, void *data) } client->ptr += nb; ptr = client->buffer; - while ((ptr_nl = memchr (ptr, client->terminator, client->ptr - ptr ))) + while ((ptr_nl = (char *) memchr (ptr, client->terminator, client->ptr - ptr ))) { *ptr_nl ='\0'; if (client->interpretation ) @@ -208,7 +208,7 @@ static void HandleSocket (Channel channel, HANDLE fd, void *data) -static void HandleCongestionWrite (Channel channel, HANDLE fd, void *data) +static void HandleCongestionWrite (Channel channel, IVY_HANDLE fd, void *data) { Client client = (Client)data; @@ -225,11 +225,11 @@ static void HandleCongestionWrite (Channel channel, HANDLE fd, void *data) } -static void HandleServer(Channel channel, HANDLE fd, void *data) +static void HandleServer(Channel channel, IVY_HANDLE fd, void *data) { Server server = (Server ) data; Client client; - HANDLE ns; + IVY_HANDLE ns; socklen_t addrlen; struct sockaddr_storage remote; #ifdef WIN32 @@ -250,7 +250,7 @@ static void HandleServer(Channel channel, HANDLE fd, void *data) IVY_LIST_ADD_START (clients_list, client ); client->buffer_size = IVY_BUFFER_SIZE; - client->buffer = malloc( client->buffer_size ); + client->buffer = (char *) malloc( client->buffer_size ); if (!client->buffer ) { fprintf(stderr,"HandleSocket Buffer Memory Alloc Error\n"); @@ -312,7 +312,7 @@ Server SocketServer(int ipv6, unsigned short port, void(*interpretation) (Client client, const void *data, char *ligne)) { Server server; - HANDLE fd; + IVY_HANDLE fd; int one=1; struct sockaddr_storage local; socklen_t addrlen; @@ -404,7 +404,7 @@ void SocketServerClose (Server server ) IvyChannelRemove (server->channel ); } -char *SocketGetPeerHost (Client client ) +const char *SocketGetPeerHost (Client client ) { int err; struct sockaddr_storage name; @@ -481,7 +481,7 @@ struct sockaddr_storage * SocketGetRemoteAddr (Client client ) return client ? &client->from : 0; } -void SocketGetRemoteHost (Client client, char **hostptr, unsigned short *port ) +void SocketGetRemoteHost (Client client, const char **hostptr, unsigned short *port ) { int err; static char host[NI_MAXHOST]; @@ -681,7 +681,7 @@ void SocketSetData (Client client, const void *data ) } } -SendState SocketSend (Client client, char *fmt, ... ) +SendState SocketSend (Client client, const char *fmt, ... ) { SendState state; static IvyBuffer buffer = {NULL, 0, 0 }; /* Use static mem to eliminate multiple call to malloc /free */ @@ -751,7 +751,7 @@ Client SocketConnectAddr (int ipv6, struct sockaddr_storage * addr, unsigned sho void(*handle_decongestion)(Client client, const void *data) ) { - HANDLE handle; + IVY_HANDLE handle; Client client; struct sockaddr_storage remote; socklen_t addrlen; @@ -816,7 +816,7 @@ Client SocketConnectAddr (int ipv6, struct sockaddr_storage * addr, unsigned sho IVY_LIST_ADD_START(clients_list, client ); client->buffer_size = IVY_BUFFER_SIZE; - client->buffer = malloc( client->buffer_size ); + client->buffer = (char *) malloc( client->buffer_size ); if (!client->buffer ) { fprintf(stderr,"HandleSocket Buffer Memory Alloc Error\n"); @@ -855,7 +855,7 @@ int SocketWaitForReply (Client client, char *buffer, int size, int delai) char *ptr_nl; long nb_to_read = 0; long nb; - HANDLE fd; + IVY_HANDLE fd; fd = client->fd; ptr = buffer; @@ -905,7 +905,7 @@ Client SocketBroadcastCreate (int ipv6, unsigned short port, SocketInterpretation interpretation ) { - HANDLE handle; + IVY_HANDLE handle; Client client; int on = 1; struct sockaddr_storage local; @@ -964,7 +964,7 @@ Client SocketBroadcastCreate (int ipv6, unsigned short port, IVY_LIST_ADD_START(clients_list, client ); client->buffer_size = IVY_BUFFER_SIZE; - client->buffer = malloc( client->buffer_size ); + client->buffer = (char *) malloc( client->buffer_size ); if (!client->buffer ) { perror("HandleSocket Buffer Memory Alloc Error: "); @@ -989,7 +989,7 @@ Client SocketBroadcastCreate (int ipv6, unsigned short port, return client; } /* TODO unifier les deux fonctions */ -void SocketSendBroadcast (Client client, unsigned long host, unsigned short port, char *fmt, ... ) +void SocketSendBroadcast (Client client, unsigned long host, unsigned short port, const char *fmt, ... ) { struct sockaddr_in remote; static IvyBuffer buffer = { NULL, 0, 0 }; /* Use satic mem to eliminate multiple call to malloc /free */ @@ -1020,7 +1020,7 @@ void SocketSendBroadcast (Client client, unsigned long host, unsigned short port } -void SocketSendBroadcast6 (Client client, struct in6_addr* host, unsigned short port, char *fmt, ... ) +void SocketSendBroadcast6 (Client client, struct in6_addr* host, unsigned short port, const char *fmt, ... ) { struct sockaddr_in6 remote; static IvyBuffer buffer = { NULL, 0, 0 }; /* Use satic mem to eliminate multiple call to malloc /free */ diff --git a/src/ivysocket.h b/src/ivysocket.h index 809d696..530c987 100644 --- a/src/ivysocket.h +++ b/src/ivysocket.h @@ -32,13 +32,13 @@ extern "C" { #ifdef __MINGW32__ #include #endif -#define HANDLE SOCKET +#define IVY_HANDLE SOCKET #define socklen_t int #ifndef IN_MULTICAST #define IN_MULTICAST(i) (((long)(i) & 0xf0000000) == 0xe0000000) #endif #else -#define HANDLE int +#define IVY_HANDLE int #include #endif #ifdef __INTERIX @@ -69,10 +69,10 @@ extern void SocketServerClose( Server server ); /* Client Part */ extern void SocketClose( Client client ); -extern SendState SocketSend( Client client, char *fmt, ... ); +extern SendState SocketSend( Client client, const char *fmt, ... ); extern SendState SocketSendRaw( const Client client, const char *buffer, const int len ); extern SendState SocketSendRawWithId( const Client client, const char *id, const char *buffer, const int len ); -extern char *SocketGetPeerHost( Client client ); +extern const char *SocketGetPeerHost( Client client ); extern void SocketSetData( Client client, const void *data ); extern const void *SocketGetData( Client client ); extern void SocketBroadcast( char *fmt, ... ); @@ -110,13 +110,13 @@ extern struct sockaddr_storage* SocketGetRemoteAddr( Client client ); extern void SocketSetUuid (Client client, const char *uuid); extern const char* SocketGetUuid (const Client client); extern int SocketCmpUuid (const Client c1, const Client c2); -extern void SocketGetRemoteHost (Client client, char **host, unsigned short *port ); +extern void SocketGetRemoteHost (Client client, const char **host, unsigned short *port ); extern unsigned short int SocketGetLocalPort ( Client client ); extern unsigned short int SocketGetRemotePort ( Client client ); /* emmission d'un broadcast UDP */ -extern void SocketSendBroadcast( Client client, unsigned long host, unsigned short port, char *fmt, ... ); -extern void SocketSendBroadcast6( Client client, struct in6_addr* host, unsigned short port, char *fmt, ... ); +extern void SocketSendBroadcast( Client client, unsigned long host, unsigned short port, const char *fmt, ... ); +extern void SocketSendBroadcast6( Client client, struct in6_addr* host, unsigned short port, const char *fmt, ... ); #ifdef __cplusplus } diff --git a/src/ivytcl.c b/src/ivytcl.c index 5fb7880..ed23713 100644 --- a/src/ivytcl.c +++ b/src/ivytcl.c @@ -40,7 +40,7 @@ /* Il n'y a pas de Tcl_MakeTCPserver */ struct _channel { - HANDLE fd; + IVY_HANDLE fd; void *data; Tcl_Channel tcl_channel; ChannelHandleDelete handle_delete; @@ -102,7 +102,7 @@ void IvyChannelRemove( Channel channel ) } -Channel IvyChannelAdd(HANDLE fd, void *data, +Channel IvyChannelAdd(IVY_HANDLE fd, void *data, ChannelHandleDelete handle_delete, ChannelHandleRead handle_read, ChannelHandleWrite handle_write @@ -194,7 +194,7 @@ IvyAppCB(IvyClientPtr app, void *user_data, /* script a appeler */ IvyApplicationEvent event) { - static char *app_event_str[] = { + static const char *app_event_str[] = { "Connected", "Disconnected" }; filter_struct *filter = (filter_struct *) user_data; int result, size, dummy; @@ -541,7 +541,7 @@ IvyApplicationHostCmd(ClientData clientData, return TCL_ERROR; } - Tcl_SetResult(interp, IvyGetApplicationHost((IvyClientPtr) Tcl_GetHashValue(entry)), + Tcl_SetResult(interp, (char *) IvyGetApplicationHost((IvyClientPtr) Tcl_GetHashValue(entry)), TCL_STATIC); return TCL_OK; diff --git a/src/ivyxtloop.c b/src/ivyxtloop.c index fc5b0ae..e5ceb19 100644 --- a/src/ivyxtloop.c +++ b/src/ivyxtloop.c @@ -48,7 +48,7 @@ struct _channel { XtInputId id_write; XtInputId id_delete; - HANDLE fd; + IVY_HANDLE fd; void *data; ChannelHandleDelete handle_delete; ChannelHandleRead handle_read; @@ -117,7 +117,7 @@ void IvyXtChannelAppContext( XtAppContext cntx ) app = cntx; } -Channel IvyChannelAdd(HANDLE fd, void *data, +Channel IvyChannelAdd(IVY_HANDLE fd, void *data, ChannelHandleDelete handle_delete, ChannelHandleRead handle_read, ChannelHandleWrite handle_write diff --git a/src/uthash.h b/src/uthash.h index 3ebbae5..a4bdc18 100644 --- a/src/uthash.h +++ b/src/uthash.h @@ -1,5 +1,5 @@ /* -Copyright (c) 2003-2006, Troy Hanson http://uthash.sourceforge.net +Copyright (c) 2003-2010, Troy D. Hanson http://uthash.sourceforge.net All rights reserved. Redistribution and use in source and binary forms, with or without @@ -7,13 +7,6 @@ modification, are permitted provided that the following conditions are met: * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. - * Redistributions in binary form must reproduce the above copyright - notice, this list of conditions and the following disclaimer in - the documentation and/or other materials provided with the - distribution. - * Neither the name of the copyright holder nor the names of its - contributors may be used to endorse or promote products derived - from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED @@ -28,210 +21,301 @@ NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -#include /* memcmp,strlen */ - #ifndef UTHASH_H #define UTHASH_H +#include /* memcmp,strlen */ +#include /* ptrdiff_t */ + +/* These macros use decltype or the earlier __typeof GNU extension. + As decltype is only available in newer compilers (VS2010 or gcc 4.3+ + when compiling c++ source) this code uses whatever method is needed + or, for VS2008 where neither is available, uses casting workarounds. */ +#ifdef _MSC_VER /* MS compiler */ +#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ +#define DECLTYPE(x) (decltype(x)) +#else /* VS2008 or older (or VS2010 in C mode) */ +#define NO_DECLTYPE +#define DECLTYPE(x) +#endif +#else /* GNU, Sun and other compilers */ +#define DECLTYPE(x) (__typeof(x)) +#endif + +#ifdef NO_DECLTYPE +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + char **_da_dst = (char**)(&(dst)); \ + *_da_dst = (char*)(src); \ +} while(0) +#else +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + (dst) = DECLTYPE(dst)(src); \ +} while(0) +#endif + +/* a number of the hash function use uint32_t which isn't defined on win32 */ +#ifdef _MSC_VER +typedef unsigned int uint32_t; +#else +#include /* uint32_t */ +#endif + +#define UTHASH_VERSION 1.9.3 + #define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */ -#define uthash_bkt_malloc(sz) malloc(sz) /* malloc fcn for UT_hash_bucket's */ -#define uthash_bkt_free(ptr) free(ptr) /* free fcn for UT_hash_bucket's */ -#define uthash_tbl_malloc(sz) malloc(sz) /* malloc fcn for UT_hash_table */ -#define uthash_tbl_free(ptr) free(ptr) /* free fcn for UT_hash_table */ +#define uthash_malloc(sz) malloc(sz) /* malloc fcn */ +#define uthash_free(ptr,sz) free(ptr) /* free fcn */ #define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ #define uthash_expand_fyi(tbl) /* can be defined to log expands */ /* initial number of buckets */ -#define HASH_INITIAL_NUM_BUCKETS 32 /* initial number of buckets */ -#define HASH_BKT_CAPACITY_THRESH 10 /* expand when bucket count reaches */ - -#define HASH_FIND(hh,head,keyptr,keylen_in,out) \ -do { \ - out=head; \ - if (head) { \ - (head)->hh.tbl->key = (char*)(keyptr); \ - (head)->hh.tbl->keylen = keylen_in; \ - HASH_FCN((head)->hh.tbl->key,(head)->hh.tbl->keylen, \ - (head)->hh.tbl->num_buckets,(head)->hh.tbl->bkt, \ - (head)->hh.tbl->i, (head)->hh.tbl->j,(head)->hh.tbl->k); \ - HASH_FIND_IN_BKT(hh, (head)->hh.tbl->buckets[ (head)->hh.tbl->bkt], \ - keyptr,keylen_in,out); \ - } \ +#define HASH_INITIAL_NUM_BUCKETS 32 /* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS_LOG2 5 /* lg2 of initial number of buckets */ +#define HASH_BKT_CAPACITY_THRESH 10 /* expand when bucket count reaches */ + +/* calculate the element whose hash handle address is hhe */ +#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) + +#define HASH_FIND(hh,head,keyptr,keylen,out) \ +do { \ + unsigned _hf_bkt,_hf_hashv; \ + out=NULL; \ + if (head) { \ + HASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt); \ + if (HASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv)) { \ + HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], \ + keyptr,keylen,out); \ + } \ + } \ } while (0) -#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ +#ifdef HASH_BLOOM +#define HASH_BLOOM_BITLEN (1ULL << HASH_BLOOM) +#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8) + ((HASH_BLOOM_BITLEN%8) ? 1:0) +#define HASH_BLOOM_MAKE(tbl) \ +do { \ + (tbl)->bloom_nbits = HASH_BLOOM; \ + (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \ + if (!((tbl)->bloom_bv)) { uthash_fatal( "out of memory"); } \ + memset((tbl)->bloom_bv, 0, HASH_BLOOM_BYTELEN); \ + (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \ +} while (0); + +#define HASH_BLOOM_FREE(tbl) \ +do { \ + uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ +} while (0); + +#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8] |= (1U << ((idx)%8))) +#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8] & (1U << ((idx)%8))) + +#define HASH_BLOOM_ADD(tbl,hashv) \ + HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) + +#define HASH_BLOOM_TEST(tbl,hashv) \ + HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) + +#else +#define HASH_BLOOM_MAKE(tbl) +#define HASH_BLOOM_FREE(tbl) +#define HASH_BLOOM_ADD(tbl,hashv) +#define HASH_BLOOM_TEST(tbl,hashv) (1) +#endif + +#define HASH_MAKE_TABLE(hh,head) \ +do { \ + (head)->hh.tbl = (UT_hash_table*)uthash_malloc( \ + sizeof(UT_hash_table)); \ + if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \ + memset((head)->hh.tbl, 0, sizeof(UT_hash_table)); \ + (head)->hh.tbl->tail = &((head)->hh); \ + (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ + (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ + (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ + (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ + HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ + if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \ + memset((head)->hh.tbl->buckets, 0, \ + HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ + HASH_BLOOM_MAKE((head)->hh.tbl); \ + (head)->hh.tbl->signature = HASH_SIGNATURE; \ +} while(0) + +#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ HASH_ADD_KEYPTR(hh,head,&add->fieldname,keylen_in,add) -#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ -do { \ - add->hh.next = NULL; \ - add->hh.key = (char*)keyptr; \ - add->hh.keylen = keylen_in; \ - add->hh.elmt = add; \ - if (!(head)) { \ - head = add; \ - (head)->hh.prev = NULL; \ - (head)->hh.tbl = (UT_hash_table*)uthash_tbl_malloc( \ - sizeof(UT_hash_table)); \ - if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \ - (head)->hh.tbl->name = #head; \ - (head)->hh.tbl->tail = &(add->hh); \ - (head)->hh.tbl->noexpand = 0; \ - (head)->hh.tbl->hash_q = 1; \ - (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ - (head)->hh.tbl->num_items = 0; \ - (head)->hh.tbl->hho = ((long)(&add->hh) - (long)(add)); \ - (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_bkt_malloc( \ - HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ - if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \ - memset((head)->hh.tbl->buckets, 0, \ - HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ - } else { \ - (head)->hh.tbl->tail->next = add; \ - add->hh.prev = (head)->hh.tbl->tail->elmt; \ - (head)->hh.tbl->tail = &(add->hh); \ - } \ - (head)->hh.tbl->num_items++; \ - add->hh.tbl = (head)->hh.tbl; \ - (head)->hh.tbl->key = (char*)keyptr; \ - (head)->hh.tbl->keylen = keylen_in; \ - HASH_FCN((head)->hh.tbl->key,(head)->hh.tbl->keylen, \ - (head)->hh.tbl->num_buckets, \ - (head)->hh.tbl->bkt, \ - (head)->hh.tbl->i, (head)->hh.tbl->j, (head)->hh.tbl->k ); \ - HASH_ADD_TO_BKT(hh,(head)->hh.tbl->buckets[(head)->hh.tbl->bkt],add); \ - HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \ - HASH_FSCK(head); \ +#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ +do { \ + unsigned _ha_bkt; \ + (add)->hh.next = NULL; \ + (add)->hh.key = (char*)keyptr; \ + (add)->hh.keylen = keylen_in; \ + if (!(head)) { \ + head = (add); \ + (head)->hh.prev = NULL; \ + HASH_MAKE_TABLE(hh,head); \ + } else { \ + (head)->hh.tbl->tail->next = (add); \ + (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ + (head)->hh.tbl->tail = &((add)->hh); \ + } \ + (head)->hh.tbl->num_items++; \ + (add)->hh.tbl = (head)->hh.tbl; \ + HASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets, \ + (add)->hh.hashv, _ha_bkt); \ + HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh); \ + HASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv); \ + HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \ + HASH_FSCK(hh,head); \ +} while(0) + +#define HASH_TO_BKT( hashv, num_bkts, bkt ) \ +do { \ + bkt = ((hashv) & ((num_bkts) - 1)); \ } while(0) -#define HASH_DELETE(hh,head,delptr) \ -do { \ - if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \ - uthash_bkt_free((head)->hh.tbl->buckets ); \ - uthash_tbl_free((head)->hh.tbl); \ - head = NULL; \ - } else { \ - if ((delptr) == (head)->hh.tbl->tail->elmt) { \ - (head)->hh.tbl->tail = (void*)(((long)((delptr)->hh.prev)) + \ - (head)->hh.tbl->hho); \ - } \ - if ((delptr)->hh.prev) { \ - ((UT_hash_handle*)(((long)((delptr)->hh.prev)) + \ - (head)->hh.tbl->hho))->next = (delptr)->hh.next; \ - } else { \ - head = (delptr)->hh.next; \ - } \ - if ((delptr)->hh.next) { \ - ((UT_hash_handle*)(((long)((delptr)->hh.next)) + \ - (head)->hh.tbl->hho))->prev = (delptr)->hh.prev; \ - } \ - (head)->hh.tbl->key = (char*)((delptr)->hh.key); \ - (head)->hh.tbl->keylen = (delptr)->hh.keylen; \ - HASH_FCN((head)->hh.tbl->key,(head)->hh.tbl->keylen, \ - (head)->hh.tbl->num_buckets,(head)->hh.tbl->bkt, \ - (head)->hh.tbl->i,(head)->hh.tbl->j,(head)->hh.tbl->k ); \ - HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[(head)->hh.tbl->bkt], \ - delptr); \ - (head)->hh.tbl->num_items--; \ - } \ - HASH_FSCK(head); \ +/* delete "delptr" from the hash table. + * "the usual" patch-up process for the app-order doubly-linked-list. + * The use of _hd_hh_del below deserves special explanation. + * These used to be expressed using (delptr) but that led to a bug + * if someone used the same symbol for the head and deletee, like + * HASH_DELETE(hh,users,users); + * We want that to work, but by changing the head (users) below + * we were forfeiting our ability to further refer to the deletee (users) + * in the patch-up process. Solution: use scratch space to + * copy the deletee pointer, then the latter references are via that + * scratch pointer rather than through the repointed (users) symbol. + */ +#define HASH_DELETE(hh,head,delptr) \ +do { \ + unsigned _hd_bkt; \ + struct UT_hash_handle *_hd_hh_del; \ + if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ + HASH_BLOOM_FREE((head)->hh.tbl); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + head = NULL; \ + } else { \ + _hd_hh_del = &((delptr)->hh); \ + if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \ + (head)->hh.tbl->tail = \ + (UT_hash_handle*)((char*)((delptr)->hh.prev) + \ + (head)->hh.tbl->hho); \ + } \ + if ((delptr)->hh.prev) { \ + ((UT_hash_handle*)((char*)((delptr)->hh.prev) + \ + (head)->hh.tbl->hho))->next = (delptr)->hh.next; \ + } else { \ + DECLTYPE_ASSIGN(head,(delptr)->hh.next); \ + } \ + if (_hd_hh_del->next) { \ + ((UT_hash_handle*)((char*)_hd_hh_del->next + \ + (head)->hh.tbl->hho))->prev = \ + _hd_hh_del->prev; \ + } \ + HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ + HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ + (head)->hh.tbl->num_items--; \ + } \ + HASH_FSCK(hh,head); \ } while (0) /* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ -#define HASH_FIND_STR(head,findstr,out) \ +#define HASH_FIND_STR(head,findstr,out) \ HASH_FIND(hh,head,findstr,strlen(findstr),out) -#define HASH_ADD_STR(head,strfield,add) \ +#define HASH_ADD_STR(head,strfield,add) \ HASH_ADD(hh,head,strfield,strlen(add->strfield),add) -#define HASH_FIND_INT(head,findint,out) \ +#define HASH_FIND_INT(head,findint,out) \ HASH_FIND(hh,head,findint,sizeof(int),out) -#define HASH_ADD_INT(head,intfield,add) \ +#define HASH_ADD_INT(head,intfield,add) \ HASH_ADD(hh,head,intfield,sizeof(int),add) -#define HASH_DEL(head,delptr) \ +#define HASH_FIND_PTR(head,findptr,out) \ + HASH_FIND(hh,head,findptr,sizeof(void *),out) +#define HASH_ADD_PTR(head,ptrfield,add) \ + HASH_ADD(hh,head,ptrfield,sizeof(void *),add) +#define HASH_DEL(head,delptr) \ HASH_DELETE(hh,head,delptr) /* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. - * This function misuses fields in UT_hash_table for its bookkeeping variables. */ #ifdef HASH_DEBUG #define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0) -#define HASH_FSCK(head) \ -do { \ - if (head) { \ - (head)->hh.tbl->keylen = 0; /* item counter */ \ - for( (head)->hh.tbl->bkt_i = 0; \ - (head)->hh.tbl->bkt_i < (head)->hh.tbl->num_buckets; \ - (head)->hh.tbl->bkt_i++) \ - { \ - (head)->hh.tbl->bkt_ideal = 0; /* bkt item counter */ \ - (head)->hh.tbl->hh = \ - (head)->hh.tbl->buckets[(head)->hh.tbl->bkt_i].hh_head; \ - (head)->hh.tbl->key = NULL; /* hh_prev */ \ - while ((head)->hh.tbl->hh) { \ - if ((head)->hh.tbl->key != \ - (char*)((head)->hh.tbl->hh->hh_prev)) { \ - HASH_OOPS("invalid hh_prev %x, actual %x\n", \ - (head)->hh.tbl->hh->hh_prev, \ - (head)->hh.tbl->key ); \ - } \ - (head)->hh.tbl->bkt_ideal++; \ - (head)->hh.tbl->key = (char*)((head)->hh.tbl->hh); \ - (head)->hh.tbl->hh = (head)->hh.tbl->hh->hh_next; \ - } \ - (head)->hh.tbl->keylen += (head)->hh.tbl->bkt_ideal; \ - if ((head)->hh.tbl->buckets[(head)->hh.tbl->bkt_i].count \ - != (head)->hh.tbl->bkt_ideal) { \ - HASH_OOPS("invalid bucket count %d, actual %d\n", \ - (head)->hh.tbl->buckets[(head)->hh.tbl->bkt_i].count, \ - (head)->hh.tbl->bkt_ideal); \ - } \ - } \ - if ((head)->hh.tbl->keylen != (head)->hh.tbl->num_items) { \ - HASH_OOPS("invalid hh item count %d, actual %d\n", \ - (head)->hh.tbl->num_items, (head)->hh.tbl->keylen ); \ - } \ - /* traverse hh in app order; check next/prev integrity, count */ \ - (head)->hh.tbl->keylen = 0; /* item counter */ \ - (head)->hh.tbl->key = NULL; /* app prev */ \ - (head)->hh.tbl->hh = &(head)->hh; \ - while ((head)->hh.tbl->hh) { \ - (head)->hh.tbl->keylen++; \ - if ((head)->hh.tbl->key !=(char*)((head)->hh.tbl->hh->prev)) {\ - HASH_OOPS("invalid prev %x, actual %x\n", \ - (head)->hh.tbl->hh->prev, \ - (head)->hh.tbl->key ); \ - } \ - (head)->hh.tbl->key = (head)->hh.tbl->hh->elmt; \ - (head)->hh.tbl->hh = ( (head)->hh.tbl->hh->next ? \ - (UT_hash_handle*)((long)((head)->hh.tbl->hh->next) + \ - (head)->hh.tbl->hho) \ - : NULL ); \ - } \ - if ((head)->hh.tbl->keylen != (head)->hh.tbl->num_items) { \ - HASH_OOPS("invalid app item count %d, actual %d\n", \ - (head)->hh.tbl->num_items, (head)->hh.tbl->keylen ); \ - } \ - } \ +#define HASH_FSCK(hh,head) \ +do { \ + unsigned _bkt_i; \ + unsigned _count, _bkt_count; \ + char *_prev; \ + struct UT_hash_handle *_thh; \ + if (head) { \ + _count = 0; \ + for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \ + _bkt_count = 0; \ + _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ + _prev = NULL; \ + while (_thh) { \ + if (_prev != (char*)(_thh->hh_prev)) { \ + HASH_OOPS("invalid hh_prev %p, actual %p\n", \ + _thh->hh_prev, _prev ); \ + } \ + _bkt_count++; \ + _prev = (char*)(_thh); \ + _thh = _thh->hh_next; \ + } \ + _count += _bkt_count; \ + if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ + HASH_OOPS("invalid bucket count %d, actual %d\n", \ + (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ + } \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("invalid hh item count %d, actual %d\n", \ + (head)->hh.tbl->num_items, _count ); \ + } \ + /* traverse hh in app order; check next/prev integrity, count */ \ + _count = 0; \ + _prev = NULL; \ + _thh = &(head)->hh; \ + while (_thh) { \ + _count++; \ + if (_prev !=(char*)(_thh->prev)) { \ + HASH_OOPS("invalid prev %p, actual %p\n", \ + _thh->prev, _prev ); \ + } \ + _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \ + _thh = ( _thh->next ? (UT_hash_handle*)((char*)(_thh->next) + \ + (head)->hh.tbl->hho) : NULL ); \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("invalid app item count %d, actual %d\n", \ + (head)->hh.tbl->num_items, _count ); \ + } \ + } \ } while (0) #else -#define HASH_FSCK(head) +#define HASH_FSCK(hh,head) #endif /* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to * the descriptor to which this macro is defined for tuning the hash function. * The app can #include to get the prototype for write(2). */ #ifdef HASH_EMIT_KEYS -#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ - (head)->hh.tbl->keylen = fieldlen; \ - write(HASH_EMIT_KEYS, &((head)->hh.tbl->keylen), sizeof(int)); \ - write(HASH_EMIT_KEYS, keyptr, fieldlen); +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ +do { \ + unsigned _klen = fieldlen; \ + write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ + write(HASH_EMIT_KEYS, keyptr, fieldlen); \ +} while (0) #else #define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) #endif -/* default to Jenkins unless specified e.g. DHASH_FUNCTION=HASH_SAX */ +/* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */ #ifdef HASH_FUNCTION #define HASH_FCN HASH_FUNCTION #else @@ -239,367 +323,650 @@ do { \ #endif /* The Bernstein hash function, used in Perl prior to v5.6 */ -#define HASH_BER(key,keylen,num_bkts,bkt,i,j,k) \ - bkt = 0; \ - while (keylen--) bkt = (bkt * 33) + *key++; \ - bkt &= (num_bkts-1); - - -/* SAX/FNV/OAT/JEN/JSW hash functions are macro variants of those listed at - * http://eternallyconfuzzled.com/tuts/hashing.html (thanks Julienne Walker) */ -#define HASH_SAX(key,keylen,num_bkts,bkt,i,j,k) \ - bkt = 0; \ - for(i=0; i < keylen; i++) \ - bkt ^= (bkt << 5) + (bkt >> 2) + key[i]; \ - bkt &= (num_bkts-1); - -#define HASH_FNV(key,keylen,num_bkts,bkt,i,j,k) \ - bkt = 2166136261UL; \ - for(i=0; i < keylen; i++) \ - bkt = (bkt * 16777619) ^ key[i]; \ - bkt &= (num_bkts-1); +#define HASH_BER(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _hb_keylen=keylen; \ + char *_hb_key=(char*)(key); \ + (hashv) = 0; \ + while (_hb_keylen--) { (hashv) = ((hashv) * 33) + *_hb_key++; } \ + bkt = (hashv) & (num_bkts-1); \ +} while (0) + + +/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at + * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ +#define HASH_SAX(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _sx_i; \ + char *_hs_key=(char*)(key); \ + hashv = 0; \ + for(_sx_i=0; _sx_i < keylen; _sx_i++) \ + hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \ + bkt = hashv & (num_bkts-1); \ +} while (0) + +#define HASH_FNV(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _fn_i; \ + char *_hf_key=(char*)(key); \ + hashv = 2166136261UL; \ + for(_fn_i=0; _fn_i < keylen; _fn_i++) \ + hashv = (hashv * 16777619) ^ _hf_key[_fn_i]; \ + bkt = hashv & (num_bkts-1); \ +} while(0); -#define HASH_OAT(key,keylen,num_bkts,bkt,i,j,k) \ - bkt = 0; \ - for(i=0; i < keylen; i++) { \ - bkt += key[i]; \ - bkt += (bkt << 10); \ - bkt ^= (bkt >> 6); \ - } \ - bkt += (bkt << 3); \ - bkt ^= (bkt >> 11); \ - bkt += (bkt << 15); \ - bkt &= (num_bkts-1); - -#define HASH_JEN_MIX(a,b,c) \ -{ \ - a -= b; a -= c; a ^= ( c >> 13 ); \ - b -= c; b -= a; b ^= ( a << 8 ); \ - c -= a; c -= b; c ^= ( b >> 13 ); \ - a -= b; a -= c; a ^= ( c >> 12 ); \ - b -= c; b -= a; b ^= ( a << 16 ); \ - c -= a; c -= b; c ^= ( b >> 5 ); \ - a -= b; a -= c; a ^= ( c >> 3 ); \ - b -= c; b -= a; b ^= ( a << 10 ); \ - c -= a; c -= b; c ^= ( b >> 15 ); \ -} - -#define HASH_JEN(key,keylen,num_bkts,bkt,i,j,k) \ - bkt = 0xfeedbeef; \ - i = j = 0x9e3779b9; \ - k = keylen; \ - while (k >= 12) { \ - i += (key[0] + ( (unsigned)key[1] << 8 ) \ - + ( (unsigned)key[2] << 16 ) \ - + ( (unsigned)key[3] << 24 ) ); \ - j += (key[4] + ( (unsigned)key[5] << 8 ) \ - + ( (unsigned)key[6] << 16 ) \ - + ( (unsigned)key[7] << 24 ) ); \ - bkt += (key[8] + ( (unsigned)key[9] << 8 ) \ - + ( (unsigned)key[10] << 16 ) \ - + ( (unsigned)key[11] << 24 ) ); \ - \ - HASH_JEN_MIX(i, j, bkt); \ - \ - key += 12; \ - k -= 12; \ - } \ - bkt += keylen; \ - switch ( k ) { \ - case 11: bkt += ( (unsigned)key[10] << 24 ); \ - case 10: bkt += ( (unsigned)key[9] << 16 ); \ - case 9: bkt += ( (unsigned)key[8] << 8 ); \ - case 8: j += ( (unsigned)key[7] << 24 ); \ - case 7: j += ( (unsigned)key[6] << 16 ); \ - case 6: j += ( (unsigned)key[5] << 8 ); \ - case 5: j += key[4]; \ - case 4: i += ( (unsigned)key[3] << 24 ); \ - case 3: i += ( (unsigned)key[2] << 16 ); \ - case 2: i += ( (unsigned)key[1] << 8 ); \ - case 1: i += key[0]; \ - } \ - HASH_JEN_MIX(i, j, bkt); \ - bkt &= (num_bkts-1); - -#define HASH_JSW(key,keylen,num_bkts,bkt,i,j,k) \ - bkt = 16777551; \ - for(i=0; i < keylen; i++) { \ - bkt = (bkt << 1 | bkt >> 31) ^ \ - *(int*)((long)( \ - "\xe9\x81\x51\xe4\x84\x9d\x32\xd9\x2d\xda\xca\x94\xa7\x85\x1e" \ - "\x28\xfe\xa3\x18\x60\x28\x45\xa6\x48\x67\xdb\xd5\xa2\x91\x4d" \ - "\x1a\x2f\x97\x37\x82\xd8\xe9\x1c\xb7\x7b\x3c\xa5\x4c\x23\x2" \ - "\x42\x85\x20\x78\x6c\x6\x67\x6f\xa5\xcb\x53\x8c\xe1\x1f\x12" \ - "\x66\xcb\xa0\xbe\x47\x59\x8\x20\xd5\x31\xd9\xdc\xcc\x27\xc3" \ - "\x4d\x8\x9f\xb3\x50\x8\x90\x4f\x1f\x20\x60\xb8\xe2\x7b\x63" \ - "\x49\xc0\x64\xc7\xaf\xc9\x81\x9c\x5f\x7d\x45\xc5\xe4\xe4\x86" \ - "\xaf\x1a\x15\x6c\x9b\xc3\x7c\xc5\x88\x2b\xf3\xd9\x72\x76\x47" \ - "\x56\xe6\x8c\xd1\x6c\x94\x41\x59\x4d\xe2\xd7\x44\x9a\x55\x5e" \ - "\xee\x9d\x7c\x8f\x21\x57\x10\x77\xf7\x4b\xd8\x7e\xc0\x4d\xba" \ - "\x1f\x96\x2a\x60\x13\xae\xab\x58\x70\xe5\x23\x62\x2b\x63\xb6" \ - "\x42\x8e\x8f\x57\xf2\xfa\x47\x37\x91\xac\x11\x3d\x9a\x85\x73" \ - "\x9e\x39\x65\xc8\xd4\x5b\xaa\x35\x72\x5f\x40\x31\x9a\xb0\xdd" \ - "\xa9\x2c\x16\xa3\x32\xef\xcb\x8c\x80\x33\x60\xd\x85\xce\x22" \ - "\x8c\x28\x6\x7f\xff\xf6\x8a\x5f\x21\x8e\xf2\xd0\xd9\x63\x66" \ - "\x22\xe8\xe6\x3\x39\xfd\x10\x69\xce\x6c\xc4\xde\xf3\x87\x56" \ - "\xc8\x4a\x31\x51\x58\xc5\x62\x30\x8e\xd\xd5\x2f\x7c\x24\xca" \ - "\xd1\x12\x1b\x3a\x3e\x95\x99\xa\x7\xc1\x83\xd0\x4f\x97\x8c" \ - "\xf1\xb0\x9c\xd8\xb9\x72\xd7\x3e\x6b\x66\x83\x8e\xe9\x86\xad" \ - "\xfa\xc2\xe\x4\xb5\x7b\x5d\x0\xbc\x47\xbe\x4\x69\xfa\xd1" \ - "\x29\x5c\x77\x38\xfc\x88\xeb\xd5\xe1\x17\x54\xf6\xe5\xb3\xae" \ - "\xc7\x14\xb6\x4b\xa6\x42\x4b\xa3\xdf\xa5\xcf\xdb\xad\xcd\x2c" \ - "\xa3\x3\x13\xc0\x42\x5d\x6e\x3c\xfe\xd8\xeb\xa7\x96\x47\x2b" \ - "\x61\xb3\x70\xc9\x6d\xff\x1a\x82\x65\xdc\x92\x4b\x1a\x52\x75" \ - "\xa5\x61\x55\x2b\xe\x7\xde\x1e\x71\xc5\x12\x34\x59\x4f\x19" \ - "\x2\x9\xb6\x5\xe6\x7b\xad\xb6\x92\xfb\x84\x32\xf1\x45\x6c" \ - "\xec\x1a\xcb\x39\x32\x2\x47\x51\xd6\xc8\x9d\xd0\xb1\xdb\xa8" \ - "\x90\x4c\x65\x5a\x77\x1f\xca\x74\x8e\x3b\xce\x76\x55\x8b\x78" \ - "\x3c\xf3\x19\x8f\xe1\xc3\xa9\x8a\xc8\xf3\x14\x30\x4e\x77\xe9" \ - "\xd5\x6a\xcb\x96\x2f\x31\x35\xff\x6b\x10\x92\xf7\xc4\x33\xb8" \ - "\x76\x35\x6\xf\x82\x1c\xfa\x1f\x92\x47\xa1\xf9\x7e\xe5\x51" \ - "\xee\x63\xaa\x9a\x38\xa3\xa1\x86\xbf\xf0\xe8\x29\xe1\x19\x83" \ - "\xff\x36\x3c\x26\x15\x89\x36\x22\x93\x41\x3e\x63\x36\x34\x4c" \ - "\xda\x18\xd4\x18\xd8\xc8\x8a\x10\x1f\x14\x4c\x7f\x79\xfc\x46" \ - "\xbb\xc8\x24\x51\xc7\xe4\xfb\xc0\x78\xb1\xe9\xac\xf1\x3d\x55" \ - "\x51\x9c\x8\xf0\xa6\x3\xcb\x91\xc6\xf4\xe2\xd4\xe5\x18\x61" \ - "\xfc\x8f\x8a\xce\x89\x33\xcd\xf\x7d\x50\xa0\x7d\x3f\xac\x49" \ - "\xe1\x71\x92\xc7\x8d\xc0\xd0\x6e\xe4\xf7\xcd\xc1\x47\x9f\x99" \ - "\xd5\x7\x20\xad\x64\xdb\xab\x44\xd4\x8\xc6\x9a\xa4\xa7\x7c" \ - "\x9b\x13\xe4\x9c\x88\xec\xc4\xcb\xe1\x3f\x5\x5\xf\xd\x3a" \ - "\x75\xed\xfa\xc0\x23\x34\x74\xfd\xca\x1c\x74\x77\x29\xc8\xb6" \ - "\xe2\xbb\xa1\xa\x2e\xae\x65\x3e\xcb\xf5\x5e\xe0\x29\x4c\xfa" \ - "\xab\x35\xea\x7\x9f\xb3\x3b\x9c\x4e\x86\xe8\x5b\x76\x11\xf1" \ - "\xbf\x7f\x73\x34\x71\x9\x2d\x2a\x60\x8f\x14\x12\xba\x26\x84" \ - "\xb9\x94\xa9\x59\x38\x25\xfd\x77\xc3\xe5\x86\xc4\x3\xda\x32" \ - "\x30\xd8\x84\x81\x83\x14\x8c\x24\xee\x51\xa9\x92\x61\xb2\xeb" \ - "\xce\xac\x34\xc1\xad\x24\x74\xce\xf9\xce\x5c\xfd\x45\x69\x1d" \ - "\xc6\xc2\xaf\x7c\x8d\x5\x52\xb5\x88\x2f\x9f\xee\x6b\x5f\xbd" \ - "\xfe\x22\x6\x47\xa2\xc8\x25\x37\x67\x44\x4c\xe\xfe\x7e\x5a" \ - "\x36\x7f\x18\x83\x8f\x82\x87\x3b\xbf\xb8\xd2\x37\xff\x52\x60" \ - "\xb5\xf3\xd\x20\x80\xcc\xb2\x7a\xdd\xc2\x94\xbc\xe3\xb1\x87" \ - "\x3e\x49\x57\xcc\xe9\x5a\xea\xb4\xe\xdf\xa6\x8f\x70\x60\x32" \ - "\xb\x7d\x74\xf5\x46\xb6\x93\xc2\x5\x92\x72\xfc\xd9\xd2\xe5" \ - "\x90\x36\x2a\xd4\xf9\x50\x33\x52\xa5\xcc\xcf\x14\x9e\xdc\x4f" \ - "\xb7\x7d\xcf\x25\xdb\xc0\x46\xdb\xea\xe\x27\xc8\x18\x40\x39" \ - "\xbd\xec\x48\xa3\xfa\x87\xa3\x18\x68\xfc\x7a\x44\xa8\xc5\x8c" \ - "\x45\x81\x70\x72\x14\x70\xf9\x40\xc8\xe7\x41\xcb\xde\xd\x4e" \ - "\x35\x4d\xcd\xe2\x40\xa3\x2e\xbb\xb7\x50\x6c\x26\xb8\xbe\x2a" \ - "\x36\x8e\x23\xb\xa\xfe\xed\xa\xe7\xa0\x16\x73\xad\x24\x51" \ - "\x7f\xda\x9d\xd7\x9f\x18\xe6\xa8\xe4\x98\xbc\x62\x77\x55\x60" \ - "\x88\x16\x25\xbf\x95\xad\xea\xe1\x87\x18\x35\x9e\x7c\x51\xee" \ - "\xc0\x80\x8b\xb8\x37\xfd\x95\xfe\x87\x15\xf4\x97\xd5\x61\x4f" \ - "\x97\xfa\xaf\x48\xd\x5b\x84\x2d\xdb\x15\xf2\xb4\x17\x4f\x41" \ - "\x31\x58\x32\x93\xc1\x52\x34\xa6\x17\xd\x56\x5\xee\xfb\xfb" \ - "\x2d\x69\x14\xbe\x24\x94\x8\xb0\xfc\x9f\x2\x95\x88\x7d\xd6" \ - "\xe7\xa4\x5b\xbb\xf2\x7d\xd8\xa5\xd2\x7c\x9\x62\x22\x5\x53" \ - "\xd0\x67\xeb\x68\xfc\x82\x80\xf\xc9\x73\x76\x36\xb8\x13\x9f" \ - "\xb1\xf1\xee\x61\x12\xe7\x5d\x75\x65\xb8\x84\x17\xb\x7b\x28" \ - "\x4c\xb7\xda\xbb" ) \ - + ( (unsigned char)key[i] * sizeof(int) )); \ - } \ - bkt &= (num_bkts-1); +#define HASH_OAT(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _ho_i; \ + char *_ho_key=(char*)(key); \ + hashv = 0; \ + for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ + hashv += _ho_key[_ho_i]; \ + hashv += (hashv << 10); \ + hashv ^= (hashv >> 6); \ + } \ + hashv += (hashv << 3); \ + hashv ^= (hashv >> 11); \ + hashv += (hashv << 15); \ + bkt = hashv & (num_bkts-1); \ +} while(0) + +#define HASH_JEN_MIX(a,b,c) \ +do { \ + a -= b; a -= c; a ^= ( c >> 13 ); \ + b -= c; b -= a; b ^= ( a << 8 ); \ + c -= a; c -= b; c ^= ( b >> 13 ); \ + a -= b; a -= c; a ^= ( c >> 12 ); \ + b -= c; b -= a; b ^= ( a << 16 ); \ + c -= a; c -= b; c ^= ( b >> 5 ); \ + a -= b; a -= c; a ^= ( c >> 3 ); \ + b -= c; b -= a; b ^= ( a << 10 ); \ + c -= a; c -= b; c ^= ( b >> 15 ); \ +} while (0) + +#define HASH_JEN(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _hj_i,_hj_j,_hj_k; \ + char *_hj_key=(char*)(key); \ + hashv = 0xfeedbeef; \ + _hj_i = _hj_j = 0x9e3779b9; \ + _hj_k = keylen; \ + while (_hj_k >= 12) { \ + _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ + + ( (unsigned)_hj_key[2] << 16 ) \ + + ( (unsigned)_hj_key[3] << 24 ) ); \ + _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ + + ( (unsigned)_hj_key[6] << 16 ) \ + + ( (unsigned)_hj_key[7] << 24 ) ); \ + hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ + + ( (unsigned)_hj_key[10] << 16 ) \ + + ( (unsigned)_hj_key[11] << 24 ) ); \ + \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ + \ + _hj_key += 12; \ + _hj_k -= 12; \ + } \ + hashv += keylen; \ + switch ( _hj_k ) { \ + case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); \ + case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); \ + case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); \ + case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); \ + case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); \ + case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); \ + case 5: _hj_j += _hj_key[4]; \ + case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); \ + case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); \ + case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); \ + case 1: _hj_i += _hj_key[0]; \ + } \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ + bkt = hashv & (num_bkts-1); \ +} while(0) + +/* The Paul Hsieh hash function */ +#undef get16bits +#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ + || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) +#define get16bits(d) (*((const uint16_t *) (d))) +#endif + +#if !defined (get16bits) +#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ + +(uint32_t)(((const uint8_t *)(d))[0]) ) +#endif +#define HASH_SFH(key,keylen,num_bkts,hashv,bkt) \ +do { \ + char *_sfh_key=(char*)(key); \ + uint32_t _sfh_tmp, _sfh_len = keylen; \ + \ + int _sfh_rem = _sfh_len & 3; \ + _sfh_len >>= 2; \ + hashv = 0xcafebabe; \ + \ + /* Main loop */ \ + for (;_sfh_len > 0; _sfh_len--) { \ + hashv += get16bits (_sfh_key); \ + _sfh_tmp = (get16bits (_sfh_key+2) << 11) ^ hashv; \ + hashv = (hashv << 16) ^ _sfh_tmp; \ + _sfh_key += 2*sizeof (uint16_t); \ + hashv += hashv >> 11; \ + } \ + \ + /* Handle end cases */ \ + switch (_sfh_rem) { \ + case 3: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 16; \ + hashv ^= _sfh_key[sizeof (uint16_t)] << 18; \ + hashv += hashv >> 11; \ + break; \ + case 2: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 11; \ + hashv += hashv >> 17; \ + break; \ + case 1: hashv += *_sfh_key; \ + hashv ^= hashv << 10; \ + hashv += hashv >> 1; \ + } \ + \ + /* Force "avalanching" of final 127 bits */ \ + hashv ^= hashv << 3; \ + hashv += hashv >> 5; \ + hashv ^= hashv << 4; \ + hashv += hashv >> 17; \ + hashv ^= hashv << 25; \ + hashv += hashv >> 6; \ + bkt = hashv & (num_bkts-1); \ +} while(0); + +#ifdef HASH_USING_NO_STRICT_ALIASING +/* The MurmurHash exploits some CPU's (e.g. x86) tolerance for unaligned reads. + * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error. + * So MurmurHash comes in two versions, the faster unaligned one and the slower + * aligned one. We only use the faster one on CPU's where we know it's safe. + * + * Note the preprocessor built-in defines can be emitted using: + * + * gcc -m64 -dM -E - < /dev/null (on gcc) + * cc -## a.c (where a.c is a simple test file) (Sun Studio) + */ +#if (defined(__i386__) || defined(__x86_64__)) +#define HASH_MUR HASH_MUR_UNALIGNED +#else +#define HASH_MUR HASH_MUR_ALIGNED +#endif + +/* Appleby's MurmurHash fast version for unaligned-tolerant archs like i386 */ +#define HASH_MUR_UNALIGNED(key,keylen,num_bkts,hashv,bkt) \ +do { \ + const unsigned int _mur_m = 0x5bd1e995; \ + const int _mur_r = 24; \ + hashv = 0xcafebabe ^ keylen; \ + char *_mur_key = (char *)(key); \ + uint32_t _mur_tmp, _mur_len = keylen; \ + \ + for (;_mur_len >= 4; _mur_len-=4) { \ + _mur_tmp = *(uint32_t *)_mur_key; \ + _mur_tmp *= _mur_m; \ + _mur_tmp ^= _mur_tmp >> _mur_r; \ + _mur_tmp *= _mur_m; \ + hashv *= _mur_m; \ + hashv ^= _mur_tmp; \ + _mur_key += 4; \ + } \ + \ + switch(_mur_len) \ + { \ + case 3: hashv ^= _mur_key[2] << 16; \ + case 2: hashv ^= _mur_key[1] << 8; \ + case 1: hashv ^= _mur_key[0]; \ + hashv *= _mur_m; \ + }; \ + \ + hashv ^= hashv >> 13; \ + hashv *= _mur_m; \ + hashv ^= hashv >> 15; \ + \ + bkt = hashv & (num_bkts-1); \ +} while(0) + +/* Appleby's MurmurHash version for alignment-sensitive archs like Sparc */ +#define HASH_MUR_ALIGNED(key,keylen,num_bkts,hashv,bkt) \ +do { \ + const unsigned int _mur_m = 0x5bd1e995; \ + const int _mur_r = 24; \ + hashv = 0xcafebabe ^ (keylen); \ + char *_mur_key = (char *)(key); \ + uint32_t _mur_len = keylen; \ + int _mur_align = (int)_mur_key & 3; \ + \ + if (_mur_align && (_mur_len >= 4)) { \ + unsigned _mur_t = 0, _mur_d = 0; \ + switch(_mur_align) { \ + case 1: _mur_t |= _mur_key[2] << 16; \ + case 2: _mur_t |= _mur_key[1] << 8; \ + case 3: _mur_t |= _mur_key[0]; \ + } \ + _mur_t <<= (8 * _mur_align); \ + _mur_key += 4-_mur_align; \ + _mur_len -= 4-_mur_align; \ + int _mur_sl = 8 * (4-_mur_align); \ + int _mur_sr = 8 * _mur_align; \ + \ + for (;_mur_len >= 4; _mur_len-=4) { \ + _mur_d = *(unsigned *)_mur_key; \ + _mur_t = (_mur_t >> _mur_sr) | (_mur_d << _mur_sl); \ + unsigned _mur_k = _mur_t; \ + _mur_k *= _mur_m; \ + _mur_k ^= _mur_k >> _mur_r; \ + _mur_k *= _mur_m; \ + hashv *= _mur_m; \ + hashv ^= _mur_k; \ + _mur_t = _mur_d; \ + _mur_key += 4; \ + } \ + _mur_d = 0; \ + if(_mur_len >= _mur_align) { \ + switch(_mur_align) { \ + case 3: _mur_d |= _mur_key[2] << 16; \ + case 2: _mur_d |= _mur_key[1] << 8; \ + case 1: _mur_d |= _mur_key[0]; \ + } \ + unsigned _mur_k = (_mur_t >> _mur_sr) | (_mur_d << _mur_sl); \ + _mur_k *= _mur_m; \ + _mur_k ^= _mur_k >> _mur_r; \ + _mur_k *= _mur_m; \ + hashv *= _mur_m; \ + hashv ^= _mur_k; \ + _mur_k += _mur_align; \ + _mur_len -= _mur_align; \ + \ + switch(_mur_len) \ + { \ + case 3: hashv ^= _mur_key[2] << 16; \ + case 2: hashv ^= _mur_key[1] << 8; \ + case 1: hashv ^= _mur_key[0]; \ + hashv *= _mur_m; \ + } \ + } else { \ + switch(_mur_len) \ + { \ + case 3: _mur_d ^= _mur_key[2] << 16; \ + case 2: _mur_d ^= _mur_key[1] << 8; \ + case 1: _mur_d ^= _mur_key[0]; \ + case 0: hashv ^= (_mur_t >> _mur_sr) | (_mur_d << _mur_sl); \ + hashv *= _mur_m; \ + } \ + } \ + \ + hashv ^= hashv >> 13; \ + hashv *= _mur_m; \ + hashv ^= hashv >> 15; \ + } else { \ + for (;_mur_len >= 4; _mur_len-=4) { \ + unsigned _mur_k = *(unsigned*)_mur_key; \ + _mur_k *= _mur_m; \ + _mur_k ^= _mur_k >> _mur_r; \ + _mur_k *= _mur_m; \ + hashv *= _mur_m; \ + hashv ^= _mur_k; \ + _mur_key += 4; \ + } \ + switch(_mur_len) \ + { \ + case 3: hashv ^= _mur_key[2] << 16; \ + case 2: hashv ^= _mur_key[1] << 8; \ + case 1: hashv ^= _mur_key[0]; \ + hashv *= _mur_m; \ + } \ + \ + hashv ^= hashv >> 13; \ + hashv *= _mur_m; \ + hashv ^= hashv >> 15; \ + } \ + bkt = hashv & (num_bkts-1); \ +} while(0) +#endif /* HASH_USING_NO_STRICT_ALIASING */ /* key comparison function; return 0 if keys equal */ #define HASH_KEYCMP(a,b,len) memcmp(a,b,len) /* iterate over items in a known bucket to find desired item */ -#define HASH_FIND_IN_BKT(hh,head,keyptr,keylen_in,out) \ -out = (head.hh_head) ? (head.hh_head->elmt) : NULL; \ -while (out) { \ - if (out->hh.keylen == keylen_in) { \ - if ((HASH_KEYCMP(out->hh.key,keyptr,keylen_in)) == 0) break; \ - } \ - out= (out->hh.hh_next) ? (out->hh.hh_next->elmt) : NULL; \ -} +#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \ +do { \ + if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); \ + else out=NULL; \ + while (out) { \ + if (out->hh.keylen == keylen_in) { \ + if ((HASH_KEYCMP(out->hh.key,keyptr,keylen_in)) == 0) break; \ + } \ + if (out->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,out->hh.hh_next)); \ + else out = NULL; \ + } \ +} while(0) /* add an item to a bucket */ -#define HASH_ADD_TO_BKT(hh,head,add) \ - head.count++; \ - add->hh.hh_next = head.hh_head; \ - add->hh.hh_prev = NULL; \ - if (head.hh_head) head.hh_head->hh_prev = &add->hh; \ - head.hh_head=&add->hh; \ - if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \ - && add->hh.tbl->noexpand != 1) { \ - HASH_EXPAND_BUCKETS(add->hh.tbl) \ - } +#define HASH_ADD_TO_BKT(head,addhh) \ +do { \ + head.count++; \ + (addhh)->hh_next = head.hh_head; \ + (addhh)->hh_prev = NULL; \ + if (head.hh_head) { (head).hh_head->hh_prev = (addhh); } \ + (head).hh_head=addhh; \ + if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \ + && (addhh)->tbl->noexpand != 1) { \ + HASH_EXPAND_BUCKETS((addhh)->tbl); \ + } \ +} while(0) /* remove an item from a given bucket */ -#define HASH_DEL_IN_BKT(hh,head,delptr) \ - (head).count--; \ - if ((head).hh_head->elmt == delptr) { \ - (head).hh_head = delptr->hh.hh_next; \ - } \ - if (delptr->hh.hh_prev) { \ - delptr->hh.hh_prev->hh_next = delptr->hh.hh_next; \ - } \ - if (delptr->hh.hh_next) { \ - delptr->hh.hh_next->hh_prev = delptr->hh.hh_prev; \ +#define HASH_DEL_IN_BKT(hh,head,hh_del) \ + (head).count--; \ + if ((head).hh_head == hh_del) { \ + (head).hh_head = hh_del->hh_next; \ + } \ + if (hh_del->hh_prev) { \ + hh_del->hh_prev->hh_next = hh_del->hh_next; \ + } \ + if (hh_del->hh_next) { \ + hh_del->hh_next->hh_prev = hh_del->hh_prev; \ } -#define HASH_EXPAND_BUCKETS(tbl) \ - tbl->new_buckets = (UT_hash_bucket*)uthash_bkt_malloc( \ - 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ - if (!tbl->new_buckets) { uthash_fatal( "out of memory"); } \ - memset(tbl->new_buckets, 0, \ - 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ - tbl->bkt_ideal= (tbl->num_items / tbl->num_buckets*2) + \ - ((tbl->num_items % (tbl->num_buckets*2)) ? 1 : 0);\ - tbl->sum_of_deltas = 0; \ - for(tbl->bkt_i = 0; tbl->bkt_i < tbl->num_buckets; tbl->bkt_i++) \ - { \ - tbl->hh = tbl->buckets[ tbl->bkt_i ].hh_head; \ - while (tbl->hh) { \ - tbl->hh_nxt = tbl->hh->hh_next; \ - tbl->key = tbl->hh->key; \ - tbl->keylen = tbl->hh->keylen; \ - HASH_FCN(tbl->key,tbl->keylen,tbl->num_buckets*2,tbl->bkt,\ - tbl->i,tbl->j,tbl->k); \ - tbl->newbkt = &(tbl->new_buckets[ tbl->bkt ]); \ - if (++(tbl->newbkt->count) > tbl->bkt_ideal) { \ - tbl->sum_of_deltas++; \ - tbl->newbkt->expand_mult = tbl->newbkt->count / \ - tbl->bkt_ideal; \ - } \ - tbl->hh->hh_prev = NULL; \ - tbl->hh->hh_next = tbl->newbkt->hh_head; \ - if (tbl->newbkt->hh_head) tbl->newbkt->hh_head->hh_prev = \ - tbl->hh; \ - tbl->newbkt->hh_head = tbl->hh; \ - tbl->hh = tbl->hh_nxt; \ - } \ - } \ - tbl->num_buckets *= 2; \ - uthash_bkt_free( tbl->buckets ); \ - tbl->buckets = tbl->new_buckets; \ - tbl->new_hash_q = 1-(tbl->sum_of_deltas * 1.0 / tbl->num_items); \ - if (tbl->hash_q < 0.5 && tbl->new_hash_q < 0.5) { \ - tbl->noexpand=1; \ - uthash_noexpand_fyi(tbl); \ - } \ - tbl->hash_q = tbl->new_hash_q; \ - uthash_expand_fyi(tbl); +/* Bucket expansion has the effect of doubling the number of buckets + * and redistributing the items into the new buckets. Ideally the + * items will distribute more or less evenly into the new buckets + * (the extent to which this is true is a measure of the quality of + * the hash function as it applies to the key domain). + * + * With the items distributed into more buckets, the chain length + * (item count) in each bucket is reduced. Thus by expanding buckets + * the hash keeps a bound on the chain length. This bounded chain + * length is the essence of how a hash provides constant time lookup. + * + * The calculation of tbl->ideal_chain_maxlen below deserves some + * explanation. First, keep in mind that we're calculating the ideal + * maximum chain length based on the *new* (doubled) bucket count. + * In fractions this is just n/b (n=number of items,b=new num buckets). + * Since the ideal chain length is an integer, we want to calculate + * ceil(n/b). We don't depend on floating point arithmetic in this + * hash, so to calculate ceil(n/b) with integers we could write + * + * ceil(n/b) = (n/b) + ((n%b)?1:0) + * + * and in fact a previous version of this hash did just that. + * But now we have improved things a bit by recognizing that b is + * always a power of two. We keep its base 2 log handy (call it lb), + * so now we can write this with a bit shift and logical AND: + * + * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) + * + */ +#define HASH_EXPAND_BUCKETS(tbl) \ +do { \ + unsigned _he_bkt; \ + unsigned _he_bkt_i; \ + struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ + UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ + _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ + 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \ + memset(_he_new_buckets, 0, \ + 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + tbl->ideal_chain_maxlen = \ + (tbl->num_items >> (tbl->log2_num_buckets+1)) + \ + ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0); \ + tbl->nonideal_items = 0; \ + for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \ + { \ + _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \ + while (_he_thh) { \ + _he_hh_nxt = _he_thh->hh_next; \ + HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt); \ + _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \ + if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \ + tbl->nonideal_items++; \ + _he_newbkt->expand_mult = _he_newbkt->count / \ + tbl->ideal_chain_maxlen; \ + } \ + _he_thh->hh_prev = NULL; \ + _he_thh->hh_next = _he_newbkt->hh_head; \ + if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev = \ + _he_thh; \ + _he_newbkt->hh_head = _he_thh; \ + _he_thh = _he_hh_nxt; \ + } \ + } \ + uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ + tbl->num_buckets *= 2; \ + tbl->log2_num_buckets++; \ + tbl->buckets = _he_new_buckets; \ + tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \ + (tbl->ineff_expands+1) : 0; \ + if (tbl->ineff_expands > 1) { \ + tbl->noexpand=1; \ + uthash_noexpand_fyi(tbl); \ + } \ + uthash_expand_fyi(tbl); \ +} while(0) /* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ -#define HASH_SORT(head,cmpfcn) \ - if (head) { \ - (head)->hh.tbl->insize = 1; \ - (head)->hh.tbl->looping = 1; \ - (head)->hh.tbl->list = &((head)->hh); \ - while ((head)->hh.tbl->looping) { \ - (head)->hh.tbl->p = (head)->hh.tbl->list; \ - (head)->hh.tbl->list = NULL; \ - (head)->hh.tbl->tale = NULL; \ - (head)->hh.tbl->nmerges = 0; \ - while ((head)->hh.tbl->p) { \ - (head)->hh.tbl->nmerges++; \ - (head)->hh.tbl->q = (head)->hh.tbl->p; \ - (head)->hh.tbl->psize = 0; \ - for ( (head)->hh.tbl->i = 0; \ - (head)->hh.tbl->i < (head)->hh.tbl->insize; \ - (head)->hh.tbl->i++ ) { \ - (head)->hh.tbl->psize++; \ - (head)->hh.tbl->q = (((head)->hh.tbl->q->next) ? \ - ((void*)(((long)((head)->hh.tbl->q->next)) + \ - (head)->hh.tbl->hho)) : NULL); \ - if (! ((head)->hh.tbl->q) ) break; \ - } \ - (head)->hh.tbl->qsize = (head)->hh.tbl->insize; \ - while (((head)->hh.tbl->psize > 0) || \ - (((head)->hh.tbl->qsize > 0) && (head)->hh.tbl->q )) { \ - if ((head)->hh.tbl->psize == 0) { \ - (head)->hh.tbl->e = (head)->hh.tbl->q; \ - (head)->hh.tbl->q = (((head)->hh.tbl->q->next) ? \ - ((void*)(((long)((head)->hh.tbl->q->next)) + \ - (head)->hh.tbl->hho)) : NULL); \ - (head)->hh.tbl->qsize--; \ - } else if ( ((head)->hh.tbl->qsize == 0) || \ - !((head)->hh.tbl->q) ) { \ - (head)->hh.tbl->e = (head)->hh.tbl->p; \ - (head)->hh.tbl->p = (((head)->hh.tbl->p->next) ? \ - ((void*)(((long)((head)->hh.tbl->p->next)) + \ - (head)->hh.tbl->hho)) : NULL); \ - (head)->hh.tbl->psize--; \ - } else if (( \ - cmpfcn((head)->hh.tbl->p->elmt,(head)->hh.tbl->q->elmt)) \ - <= 0) { \ - (head)->hh.tbl->e = (head)->hh.tbl->p; \ - (head)->hh.tbl->p = (((head)->hh.tbl->p->next) ? \ - ((void*)(((long)((head)->hh.tbl->p->next)) + \ - (head)->hh.tbl->hho)) : NULL); \ - (head)->hh.tbl->psize--; \ - } else { \ - (head)->hh.tbl->e = (head)->hh.tbl->q; \ - (head)->hh.tbl->q = (((head)->hh.tbl->q->next) ? \ - ((void*)(((long)((head)->hh.tbl->q->next)) + \ - (head)->hh.tbl->hho)) : NULL); \ - (head)->hh.tbl->qsize--; \ - } \ - if ( (head)->hh.tbl->tale ) { \ - (head)->hh.tbl->tale->next = (((head)->hh.tbl->e) ? \ - ((head)->hh.tbl->e->elmt) : NULL); \ - } else { \ - (head)->hh.tbl->list = (head)->hh.tbl->e; \ - } \ - (head)->hh.tbl->e->prev = (((head)->hh.tbl->tale) ? \ - ((head)->hh.tbl->tale->elmt) : NULL); \ - (head)->hh.tbl->tale = (head)->hh.tbl->e; \ - } \ - (head)->hh.tbl->p = (head)->hh.tbl->q; \ - } \ - (head)->hh.tbl->tale->next = NULL; \ - if ( (head)->hh.tbl->nmerges <= 1 ) { \ - (head)->hh.tbl->looping=0; \ - (head)->hh.tbl->tail = (head)->hh.tbl->tale; \ - (head) = (head)->hh.tbl->list->elmt; \ - } \ - (head)->hh.tbl->insize *= 2; \ - } \ - HASH_FSCK(head); \ - } +/* Note that HASH_SORT assumes the hash handle name to be hh. + * HASH_SRT was added to allow the hash handle name to be passed in. */ +#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) +#define HASH_SRT(hh,head,cmpfcn) \ +do { \ + unsigned _hs_i; \ + unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ + struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ + if (head) { \ + _hs_insize = 1; \ + _hs_looping = 1; \ + _hs_list = &((head)->hh); \ + while (_hs_looping) { \ + _hs_p = _hs_list; \ + _hs_list = NULL; \ + _hs_tail = NULL; \ + _hs_nmerges = 0; \ + while (_hs_p) { \ + _hs_nmerges++; \ + _hs_q = _hs_p; \ + _hs_psize = 0; \ + for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \ + _hs_psize++; \ + _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + if (! (_hs_q) ) break; \ + } \ + _hs_qsize = _hs_insize; \ + while ((_hs_psize > 0) || ((_hs_qsize > 0) && _hs_q )) { \ + if (_hs_psize == 0) { \ + _hs_e = _hs_q; \ + _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_qsize--; \ + } else if ( (_hs_qsize == 0) || !(_hs_q) ) { \ + _hs_e = _hs_p; \ + _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ + ((void*)((char*)(_hs_p->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_psize--; \ + } else if (( \ + cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \ + DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \ + ) <= 0) { \ + _hs_e = _hs_p; \ + _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ + ((void*)((char*)(_hs_p->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_psize--; \ + } else { \ + _hs_e = _hs_q; \ + _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_qsize--; \ + } \ + if ( _hs_tail ) { \ + _hs_tail->next = ((_hs_e) ? \ + ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \ + } else { \ + _hs_list = _hs_e; \ + } \ + _hs_e->prev = ((_hs_tail) ? \ + ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \ + _hs_tail = _hs_e; \ + } \ + _hs_p = _hs_q; \ + } \ + _hs_tail->next = NULL; \ + if ( _hs_nmerges <= 1 ) { \ + _hs_looping=0; \ + (head)->hh.tbl->tail = _hs_tail; \ + DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ + } \ + _hs_insize *= 2; \ + } \ + HASH_FSCK(hh,head); \ + } \ +} while (0) + +/* This function selects items from one hash into another hash. + * The end result is that the selected items have dual presence + * in both hashes. There is no copy of the items made; rather + * they are added into the new hash through a secondary hash + * hash handle that must be present in the structure. */ +#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ +do { \ + unsigned _src_bkt, _dst_bkt; \ + void *_last_elt=NULL, *_elt; \ + UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ + ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ + if (src) { \ + for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ + for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ + _src_hh; \ + _src_hh = _src_hh->hh_next) { \ + _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ + if (cond(_elt)) { \ + _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \ + _dst_hh->key = _src_hh->key; \ + _dst_hh->keylen = _src_hh->keylen; \ + _dst_hh->hashv = _src_hh->hashv; \ + _dst_hh->prev = _last_elt; \ + _dst_hh->next = NULL; \ + if (_last_elt_hh) { _last_elt_hh->next = _elt; } \ + if (!dst) { \ + DECLTYPE_ASSIGN(dst,_elt); \ + HASH_MAKE_TABLE(hh_dst,dst); \ + } else { \ + _dst_hh->tbl = (dst)->hh_dst.tbl; \ + } \ + HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ + HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \ + (dst)->hh_dst.tbl->num_items++; \ + _last_elt = _elt; \ + _last_elt_hh = _dst_hh; \ + } \ + } \ + } \ + } \ + HASH_FSCK(hh_dst,dst); \ +} while (0) + +#define HASH_CLEAR(hh,head) \ +do { \ + if (head) { \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + (head)=NULL; \ + } \ +} while(0) + +#ifdef NO_DECLTYPE +#define HASH_ITER(hh,head,el,tmp) \ +for((el)=(head), (*(char**)(&(tmp)))=(char*)((head)?(head)->hh.next:NULL); \ + el; (el)=(tmp),(*(char**)(&(tmp)))=(char*)((tmp)?(tmp)->hh.next:NULL)) +#else +#define HASH_ITER(hh,head,el,tmp) \ +for((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL); \ + el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL)) +#endif + +/* obtain a count of items in the hash */ +#define HASH_COUNT(head) HASH_CNT(hh,head) +#define HASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0) typedef struct UT_hash_bucket { struct UT_hash_handle *hh_head; - unsigned count; - unsigned expand_mult; + unsigned count; + + /* expand_mult is normally set to 0. In this situation, the max chain length + * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If + * the bucket's chain exceeds this length, bucket expansion is triggered). + * However, setting expand_mult to a non-zero value delays bucket expansion + * (that would be triggered by additions to this particular bucket) + * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. + * (The multiplier is simply expand_mult+1). The whole idea of this + * multiplier is to reduce bucket expansions, since they are expensive, in + * situations where we know that a particular bucket tends to be overused. + * It is better to let its chain length grow to a longer yet-still-bounded + * value, than to do an O(n) bucket expansion too often. + */ + unsigned expand_mult; + } UT_hash_bucket; +/* random signature used only to find hash tables in external analysis */ +#define HASH_SIGNATURE 0xa0111fe1 +#define HASH_BLOOM_SIGNATURE 0xb12220f2 + typedef struct UT_hash_table { UT_hash_bucket *buckets; - unsigned num_buckets; + unsigned num_buckets, log2_num_buckets; unsigned num_items; - int noexpand; /* when set, inhibits expansion of buckets for this hash */ - double hash_q; /* measures the evenness of the items among buckets (0-1) */ struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ - char *name; /* macro-stringified name of list head, used by libut */ - int hho; - /* scratch */ - unsigned bkt; - char *key; - int keylen; - unsigned i,j,k; - /* scratch for bucket expansion */ - UT_hash_bucket *new_buckets, *newbkt; - struct UT_hash_handle *hh, *hh_nxt; - unsigned bkt_i, bkt_ideal, sum_of_deltas; - double new_hash_q; - /* scratch for sort */ - int looping,nmerges,insize,psize,qsize; - struct UT_hash_handle *p, *q, *e, *list, *tale; - -} UT_hash_table; + ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ + + /* in an ideal situation (all buckets used equally), no bucket would have + * more than ceil(#items/#buckets) items. that's the ideal chain length. */ + unsigned ideal_chain_maxlen; + + /* nonideal_items is the number of items in the hash whose chain position + * exceeds the ideal chain maxlen. these items pay the penalty for an uneven + * hash distribution; reaching them in a chain traversal takes >ideal steps */ + unsigned nonideal_items; + + /* ineffective expands occur when a bucket doubling was performed, but + * afterward, more than half the items in the hash had nonideal chain + * positions. If this happens on two consecutive expansions we inhibit any + * further expansion, as it's not helping; this happens when the hash + * function isn't a good fit for the key domain. When expansion is inhibited + * the hash will still work, albeit no longer in constant time. */ + unsigned ineff_expands, noexpand; + + uint32_t signature; /* used only to find hash tables in external analysis */ +#ifdef HASH_BLOOM + uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ + uint8_t *bloom_bv; + char bloom_nbits; +#endif +} UT_hash_table; typedef struct UT_hash_handle { struct UT_hash_table *tbl; - void *elmt; /* ptr to enclosing element */ void *prev; /* prev element in app order */ void *next; /* next element in app order */ struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ struct UT_hash_handle *hh_next; /* next hh in bucket order */ void *key; /* ptr to enclosing struct's key */ - int keylen; /* enclosing struct's key len */ + unsigned keylen; /* enclosing struct's key len */ + unsigned hashv; /* result of hash-fcn(key) */ } UT_hash_handle; #endif /* UTHASH_H */ diff --git a/tools/ivyperf.c b/tools/ivyperf.c index 6fefda5..50f42da 100644 --- a/tools/ivyperf.c +++ b/tools/ivyperf.c @@ -111,7 +111,7 @@ void TimerCall(TimerId id, void *user_data, unsigned long delta) void binCB( IvyClientPtr app, void *user_data, int id, const char* regexp, IvyBindEvent event ) { - char *app_name = IvyGetApplicationName( app ); + const char *app_name = IvyGetApplicationName( app ); switch ( event ) { case IvyAddBind: diff --git a/tools/ivyprobe.c b/tools/ivyprobe.c index 2bbff95..2b21da0 100644 --- a/tools/ivyprobe.c +++ b/tools/ivyprobe.c @@ -104,7 +104,7 @@ char * Chop(char *arg) return arg; } -void HandleStdin (Channel channel, HANDLE fd, void *data) +void HandleStdin (Channel channel, IVY_HANDLE fd, void *data) { static const char *separator = "#"; char buf[4096]; @@ -220,8 +220,8 @@ void HandleStdin (Channel channel, HANDLE fd, void *data) void ApplicationCallback (IvyClientPtr app, void *user_data, IvyApplicationEvent event) { - char *appname; - char *host; + const char *appname; + const char *host; /* char **msgList;*/ appname = IvyGetApplicationName (app); host = IvyGetApplicationHost (app); diff --git a/tools/ivythroughput.cpp b/tools/ivythroughput.cpp index 692c639..d99588e 100644 --- a/tools/ivythroughput.cpp +++ b/tools/ivythroughput.cpp @@ -12,7 +12,8 @@ ° traitement des options : -v (affi version) -b bus, -r regexp file, -m message file, -n : nombre de recepteurs - -t [type de test => ml (memory leak), tp (throughput) + -t [type de test => ml (memory leak), tp (throughput), dx (gestion des deconnexions + intenpestives) test memory leak ° fork d'un emetteur et d'un (ou plusieurs) recepteur : le recepteur s'abonne à toutes les regexps, @@ -24,6 +25,10 @@ ° l'emetteur envoie en boucle tous les messages du fichier de message ° l'emetteur note le temps d'envoi des messages ° l'emetteur envoie un die all et quitte + + UTILISATION TYPIQUES: + pour la deconnexion intenpestive : + ivythroughput -R 500 -t dx -d 40 -n 2 */ #include @@ -61,7 +66,7 @@ typedef std::map MapBindByClnt; #define MILLISEC 1000.0 -typedef enum {memoryLeak1, memoryLeak2, throughput} KindOfTest ; +typedef enum {memoryLeak1, memoryLeak2, throughput, disconnect} KindOfTest ; typedef struct { @@ -97,6 +102,7 @@ void endOfSeqCB (IvyClientPtr app, void *user_data, int argc, char *argv[]); void desabonneEtReabonneCB (TimerId id, void *user_data, unsigned long delta); void changeRegexpCB (TimerId id, void *user_data, unsigned long delta); void exitCB (TimerId id, void *user_data, unsigned long delta); +void doNothingAndSuicideCB (TimerId id, void *user_data, unsigned long delta); unsigned int nbMess=0, nbReg=0, numClients =1, globalInst, numRegexps=1e6, numMessages=1e6; MapUintToBool recReady; @@ -155,6 +161,8 @@ int main(int argc, char *argv[]) kindOfTest = memoryLeak2; } else if (strcasecmp (optarg, "tp") == 0) { kindOfTest = throughput; + } else if (strcasecmp (optarg, "dx") == 0) { + kindOfTest = disconnect; } else { printf("usage: %s %s",argv[0],helpmsg); exit(1); @@ -209,6 +217,9 @@ int main(int argc, char *argv[]) case memoryLeak2 : recepteur_tp (bus, kindOfTest, i, regexps, testDuration-5); break; + case disconnect : + recepteur_tp (bus, kindOfTest, i, regexps, testDuration); + break; } exit (0); } else { @@ -297,8 +308,10 @@ void recepteur_tp (const char* bus, KindOfTest kod, unsigned int inst, if (kod == memoryLeak2) { TimerRepeatAfter (1, exitAfter*1000, exitCB, NULL); + } else if (kod == disconnect) { + TimerRepeatAfter (1, exitAfter*1000/3, doNothingAndSuicideCB, (void *) exitAfter); } - + //usleep (inst * 50 * 1000); IvyStart (bus); IvyMainLoop (); @@ -646,3 +659,16 @@ void exitCB (TimerId id, void *user_data, unsigned long delta) printf ("DBG> client exit\n"); exit (0); } + +void doNothingAndSuicideCB (TimerId id, void *user_data, unsigned long delta) +{ + printf ("."); + long time = (long) user_data; + time = ((time-2)/2) * 1000; + printf ("DBG> client hanging for %d milliseconds\n", time); + usleep (time * 1000); + printf ("DBG> client suicide\n"); + _exit(42); + printf ("DBG> CECI NE DEVRAIT JAMAIS ETRE AFFICHE\n"); +} + -- cgit v1.1