From a57cfff0d32b6f4e751030fb58770d908b6a0516 Mon Sep 17 00:00:00 2001 From: bustico Date: Wed, 6 Feb 2008 16:34:02 +0000 Subject: --- src/ivythroughput.cpp | 511 ++++++++++++++++++++++++++++++++++++++++++ src/uthash.h | 605 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 1116 insertions(+) create mode 100644 src/ivythroughput.cpp create mode 100644 src/uthash.h (limited to 'src') diff --git a/src/ivythroughput.cpp b/src/ivythroughput.cpp new file mode 100644 index 0000000..3d56a60 --- /dev/null +++ b/src/ivythroughput.cpp @@ -0,0 +1,511 @@ +/* + * IvyThroughput + * + * Copyright (C) 2008 + * Centre d'Études de la Navigation Aérienne + */ + +/* + + TODO : ° utiliser la commande script pour logger le nb de + ° bug pourquoi ça marche plus si plus d'un client ? + + */ + + +// g++ ivythroughput.cpp -o ivythroughput -L/usr/local/lib64/ -Wl,-rpath,/usr/local/lib64/ -livy -lpcrecpp + +/* SCENARIO + + ° 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) + + test memory leak + ° fork d'un emetteur et d'un recepteur : le recepteur s'abonne à toutes les regexps, + se desabonne, se reabonne etc etc en boucle : on teste que l'empreinte mémoire + de l'emetteur ne grossisse pas + + test throughput : + ° fork d'un emetteur et d'un ou plusieurs recepteurs : les recepteurs s'abonnent à toutes les regexps + ° 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 +*/ + +#include +#include +#include +#include "version.h" +#include +#include +#include +#include +#include +#include +#include + +#include "ivysocket.h" +#include "ivy.h" +#include "timer.h" +#include "ivyloop.h" +#include + +#include +#include +#include + +typedef std::list ListOfString; +typedef std::list ListOfPid; +typedef std::map MapUintToBool; +typedef struct { + unsigned int currentBind; + unsigned int totalBind; +} InfoBind; +typedef std::map MapBindByClnt; + +#define MILLISEC 1000.0 + +typedef enum {memoryLeak, throughput} KindOfTest ; + + +extern char *optarg; +extern int optind, opterr, optopt; + +void recepteur (const char* bus, KindOfTest kod, unsigned int inst, + const ListOfString& regexps); +void emetteur (const char* bus, KindOfTest kod, int testDuration, + const ListOfString& messages, int regexpSize); + +bool getMessages (const char*fileName, ListOfString &messages); +bool getRegexps (const char*fileName, ListOfString ®exps); + +double currentTime(); +void binCB( IvyClientPtr app, void *user_data, int id, char* regexp, IvyBindEvent event ) ; +void binCBR( IvyClientPtr app, void *user_data, int id, char* regexp, IvyBindEvent event ) ; +void stopCB (TimerId id, void *user_data, unsigned long delta); +void sendAllMessageCB (TimerId id, void *user_data, unsigned long delta); +void recepteurReadyCB (IvyClientPtr app, void *user_data, int argc, char *argv[]); +void otherRecepteurReadyCB (IvyClientPtr app, void *user_data, int argc, char *argv[]); +void recepteurCB (IvyClientPtr app, void *user_data, int argc, char *argv[]); +void startOfSeqCB (IvyClientPtr app, void *user_data, int argc, char *argv[]); +void endOfSeqCB (IvyClientPtr app, void *user_data, int argc, char *argv[]); +void aliveCB (TimerId id, void *user_data, unsigned long delta); + +unsigned int nbMess=0, nbReg=0, numClients =1, globalInst; +MapUintToBool recReady; +KindOfTest kindOfTest = throughput; +bool regexpAreUniq = false; + +int main(int argc, char *argv[]) +{ + int c; + int testDuration = 10; + char *bus ; + char regexpFile[1024] = "testivy/regexp.txt"; + char messageFile[1024] = "testivy/plantageradargl.ivy"; + ListOfString messages, regexps; + pid_t pid; + ListOfPid recPid; + + const char* helpmsg = + "[options] \n" + "\t -b bus\tdefines the Ivy bus to which to connect to, defaults to 127:2010\n" + "\t -v \t prints the ivy relase number\n\n" + "\t -t \t type of test : ml (memory leak) or tp (throughput)\n" + "\t -r \t regexfile\tread list of regexp's from file\n" + "\t -p \t each client will prepend regexp with uniq string to " + "simulate N clients with differents regexps\n" + "\t -m \t messageFile\tread list of messages from file\n" + "\t -n \t number of clients\n" + "\t -d \t duration of the test in seconds\n" ; + + + if (getenv("IVYBUS") != NULL) { + bus = strdup (getenv("IVYBUS")); + } else { + bus = strdup ("127.0.0.1:2000") ; + } + + + while ((c = getopt(argc, argv, "vpb:r:m:n:t:d:")) != EOF) + switch (c) { + case 'b': + strcpy (bus, optarg); + break; + case 'v': + printf("ivy c library version %d.%d\n",IVYMAJOR_VERSION, IVYMINOR_VERSION); + break; + case 'p': + regexpAreUniq = true; + break; + case 't': + kindOfTest = (strncasecmp (optarg, "ml", 2) == 0) ? memoryLeak : throughput; + break; + case 'r': + strcpy (regexpFile, optarg); + break; + case 'm': + strcpy (messageFile, optarg); + break; + case 'n': + numClients = atoi (optarg); + break; + case 'd': + testDuration = atoi (optarg); + break; + default: + printf("usage: %s %s",argv[0],helpmsg); + exit(1); + } + + if (!getRegexps (regexpFile, regexps)) + {return (1);}; + + if (kindOfTest != memoryLeak) { + if (!getMessages (messageFile, messages)) + {return (1);}; + } + +#ifdef DEBUG + ListOfString::iterator iter; + for (iter=regexps.begin(); iter != regexps.end(); iter++) { + std::cout << "DBG> |" << *iter << "|\n"; + } + + for (iter=messages.begin(); iter != messages.end(); iter++) { + std::cout << "DBG> |" << *iter << "|\n"; + } +#endif // DEBUG + + + + for (unsigned int i=0; i< numClients; i++) { + if ((pid = fork ()) == 0) { + // fils + recepteur (bus, kindOfTest, i, regexps); + exit (0); + } else { + recPid.push_back (pid); + recReady[i]=false; + } + } + + emetteur (bus, kindOfTest, testDuration, messages, regexps.size()); + + ListOfPid::iterator iter; + for (iter=recPid.begin(); iter != recPid.end(); iter++) { + kill (*iter, SIGTERM); + } + + for (iter=recPid.begin(); iter != recPid.end(); iter++) { + waitpid (*iter, NULL, 0); + } + + + + return (0); +} + + + + +/* +# _ _ +# | | | | +# ___ _ __ ___ ___ | |_ | |_ ___ _ _ _ __ +# / _ \ | '_ ` _ \ / _ \ | __| | __| / _ \ | | | | | '__| +# | __/ | | | | | | | __/ \ |_ \ |_ | __/ | |_| | | | +# \___| |_| |_| |_| \___| \__| \__| \___| \__,_| |_| +*/ +void emetteur (const char* bus, KindOfTest kod, int testDuration, + const ListOfString& messages, int regexpSize) +{ + printf ("DBG> emetteur start, pid=%d\n", getpid()); + IvyInit ("IvyThroughputEmit", "IvyThroughputEmit Ready", NULL,NULL,NULL,NULL); + // double origin = currentTime(); + + + IvySetBindCallback (binCB, (void *) regexpSize); + IvyBindMsg (recepteurReadyCB, (void *) &messages, + "^IvyThroughputReceive_(\\d+)\\s+(Bindone|Ready)"); + + TimerRepeatAfter (1, testDuration *1000, stopCB, NULL); + + IvyStart (bus); + IvyMainLoop (); +} + + + +/* +# _ __ _ +# | '_ \ | | +# _ __ ___ ___ ___ | |_) | | |_ ___ _ _ _ __ +# | '__| / _ \ / __| / _ \ | .__/ | __| / _ \ | | | | | '__| +# | | | __/ | (__ | __/ | | \ |_ | __/ | |_| | | | +# |_| \___| \___| \___| |_| \__| \___| \__,_| |_| +*/ +void recepteur (const char* bus, KindOfTest kod, unsigned int inst, + const ListOfString& regexps) +{ + std::string agentName = "IvyThroughputReceive_"; + std::stringstream stream ; + stream << inst; + agentName += stream.str(); + std::string agentNameReady (agentName + " Ready"); + //double origin = currentTime(); + globalInst = inst; + static int nbOtherReady = numClients -1; + + usleep (100 * 1000); + + printf ("DBG> recepteur_%d start, pid=%d\n", inst, getpid()); + IvyInit (agentName.c_str(), agentNameReady.c_str(), NULL,NULL,NULL,NULL); + + unsigned int debugInt = 0; + ListOfString::const_iterator iter; + for (iter=regexps.begin(); iter != regexps.end(); iter++) { + debugInt++; + string reg = *iter; + if (regexpAreUniq) { (reg += " ") += stream.str();} + IvyBindMsg (recepteurCB, (void *) inst, reg.c_str()); + } + IvyBindMsg (startOfSeqCB, NULL, "^start(OfSequence)"); + IvyBindMsg (endOfSeqCB, NULL, "^end(OfSequence)"); + IvyBindMsg (otherRecepteurReadyCB, (void *) &nbOtherReady, + "^IvyThroughputReceive_(\\d+)\\s+Ready"); + + + TimerRepeatAfter (TIMER_LOOP, 1000, aliveCB, NULL); + + IvyStart (bus); + IvyMainLoop (); +} + +// =========================================================================== + + + +/* +# __ _ _ __ __ __ _ +# / _` | | | | \/ | / _` | +# | (_| | ___ | |_ | \ / | ___ ___ ___ __ _ | (_| | ___ +# \__, | / _ \ | __| | |\/| | / _ \ / __| / __| / _` | \__, | / _ \ +# __/ | | __/ \ |_ | | | | | __/ \__ \ \__ \ | (_| | __/ | | __/ +# |___/ \___| \__| |_| |_| \___| |___/ |___/ \__,_| |___/ \___| +*/ + +bool getMessages (const char*fileName, ListOfString &messages) +{ + FILE *infile; + char buffer [1024*64]; + pcrecpp::RE pcreg ("\"(.*)\"$"); + string aMsg; + + infile = fopen(fileName, "r"); + if (!infile) { + fprintf (stderr, "impossible d'ouvrir %s en lecture\n", fileName); + return false; + } + + while (fgets (buffer, sizeof (buffer), infile) != NULL) { + if (pcreg.PartialMatch (buffer, &aMsg)) { + messages.push_back (aMsg); + nbMess++; + } + } + fclose (infile); + return (true); +} + + +/* +# __ _ _ _____ __ _ _ __ +# / _` | | | | __ \ / _` | | '_ \ +# | (_| | ___ | |_ | |__) | ___ | (_| | ___ __ __ | |_) | ___ +# \__, | / _ \ | __| | _ / / _ \ \__, | / _ \ \ \/ / | .__/ / __| +# __/ | | __/ \ |_ | | \ \ | __/ __/ | | __/ > < | | \__ \ +# |___/ \___| \__| |_| \_\ \___| |___/ \___| /_/\_\ |_| |___/ +*/ +bool getRegexps (const char*fileName, ListOfString ®exps) +{ + FILE *infile; + char buffer [1024*64]; + pcrecpp::RE pcreg ("add regexp \\d+ : (.*)$"); + string aMsg; + + infile = fopen(fileName, "r"); + if (!infile) { + fprintf (stderr, "impossible d'ouvrir %s en lecture\n", fileName); + return false; + } + + while (fgets (buffer, sizeof (buffer), infile) != NULL) { + if (pcreg.PartialMatch (buffer, &aMsg)) { + regexps.push_back (aMsg); + nbReg++; + } + } + fclose (infile); + + return (true); +} + + + +/* +# _______ _ +# |__ __| (_) +# ___ _ _ _ __ _ __ | | _ _ __ ___ ___ +# / __| | | | | | '__| | '__| | | | | | '_ ` _ \ / _ \ +# | (__ | |_| | | | | | | | | | | | | | | | | __/ +# \___| \__,_| |_| |_| |_| |_| |_| |_| |_| \___| +*/ +double currentTime() +{ + double current; + + struct timeval stamp; + gettimeofday( &stamp, NULL ); + current = (double)stamp.tv_sec * MILLISEC + (double)(stamp.tv_usec/MILLISEC); + return current; +} + + +/* +# _ _ _____ ____ +# | | (_) / ____| | _ \ +# | |__ _ _ __ | | | |_) | +# | '_ \ | | | '_ \ | | | _ < +# | |_) | | | | | | | | |____ | |_) | +# |_.__/ |_| |_| |_| \_____| |____/ +*/ +void binCB( IvyClientPtr app, void *user_data, int id, char* regexp, IvyBindEvent event ) +{ + string appName = IvyGetApplicationName( app ); + static MapBindByClnt bindByClnt; + + if (bindByClnt.find (appName) == bindByClnt.end()) { + (bindByClnt[appName]).currentBind = 0; + (bindByClnt[appName]).totalBind = (unsigned long) user_data; + } + + switch ( event ) + { + case IvyAddBind: + (bindByClnt[appName]).currentBind ++; + if ((bindByClnt[appName]).currentBind == (bindByClnt[appName]).totalBind) { + printf("Application:%s ALL REGEXPS BINDED\n", appName.c_str()); + } else { + // printf("Application:%s bind [%d/%d]\n", appName.c_str(), + // (bindByClnt[appName]).currentBind, (bindByClnt[appName]).totalBind); + } + break; + case IvyRemoveBind: + printf("Application:%s bind '%s' REMOVED\n", appName.c_str(), regexp ); + break; + case IvyFilterBind: + printf("Application:%s bind '%s' FILTRED\n", appName.c_str(), regexp ); + break; + case IvyChangeBind: + printf("Application:%s bind '%s' CHANGED\n", appName.c_str(), regexp ); + break; + } +} + + +void stopCB (TimerId id, void *user_data, unsigned long delta) +{ + IvyStop (); +} + + +void sendAllMessageCB (TimerId id, void *user_data, unsigned long delta) +{ + ListOfString *messages = (ListOfString *) user_data; + double startTime = currentTime(); + unsigned int envoyes=0; + + IvySendMsg ("startOfSequence"); + ListOfString::iterator iter; + for (iter=messages->begin(); iter != messages->end(); iter++) { + envoyes += IvySendMsg ((*iter).c_str()); + } + IvySendMsg ("endOfSequence"); + + printf ("[ivy %d.%d] envoyer [%d/%d] messages filtrés par %d regexps a %d clients " + "prends %.1f secondes\n", + IVYMAJOR_VERSION, IVYMINOR_VERSION, + envoyes, nbMess, nbReg, numClients, + (currentTime()-startTime) / 1000.0) ; + TimerRepeatAfter (1, 1000, sendAllMessageCB ,user_data); +} + +void recepteurCB (IvyClientPtr app, void *user_data, int argc, char *argv[]) +{ + // unsigned long recN = (long) user_data; + // printf ("."); + // if (!((argc == 1) && (strcmp (argv[0], "OfSequence")) == 0)) + nbMess++; +} + + +void recepteurReadyCB (IvyClientPtr app, void *user_data, int argc, char *argv[]) +{ + ListOfString *messages = (ListOfString *) user_data; + unsigned int instance = atoi( *argv++ ); + if ((strcmp (*argv, "Ready") == 0) && (numClients != 1)) { + return; + } + + + recReady[instance] = true; + bool readyToStart = true; + + for (unsigned int i=0; i< numClients; i++) { + if (recReady[i]==false) { + // printf ("Emetteur : manque recepteur [%d/%d]\n", i, numClients-1); + readyToStart = false; + } + } + + if (readyToStart == true) { + if (kindOfTest == throughput) { + TimerRepeatAfter (1, 2000, sendAllMessageCB , messages); + // printf ("Emetteur : tous recepteurs prets : on envoie la puree !!\n"); + } + } +} + +void otherRecepteurReadyCB (IvyClientPtr app, void *user_data, int argc, char *argv[]) +{ + int *nbOtherReady = (int *) user_data; + + // printf ("DBG>> otherRecepteurReadyCB\n"); + + if ((--(*nbOtherReady)) == 0) { + IvySendMsg ("IvyThroughputReceive_%d Bindone", globalInst); + } else { + // printf ("IvyThroughputReceive_%d nbOtherReady=%d\n", globalInst, *nbOtherReady); + } +} + + +void startOfSeqCB (IvyClientPtr app, void *user_data, int argc, char *argv[]) +{ + nbMess = 0; +} + + +void endOfSeqCB (IvyClientPtr app, void *user_data, int argc, char *argv[]) +{ + nbMess--; + printf ("recepteur %d a recu %d messages\n", globalInst, nbMess); +} + + +void aliveCB (TimerId id, void *user_data, unsigned long delta) +{ + // printf ("********* recepteur alive CALLED ***********\n"); +} diff --git a/src/uthash.h b/src/uthash.h new file mode 100644 index 0000000..3ebbae5 --- /dev/null +++ b/src/uthash.h @@ -0,0 +1,605 @@ +/* +Copyright (c) 2003-2006, Troy Hanson http://uthash.sourceforge.net +All rights reserved. + +Redistribution and use in source and binary forms, with or without +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 +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +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 + +#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_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); \ + } \ +} 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); \ +} 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); \ +} while (0) + + +/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ +#define HASH_FIND_STR(head,findstr,out) \ + HASH_FIND(hh,head,findstr,strlen(findstr),out) +#define HASH_ADD_STR(head,strfield,add) \ + HASH_ADD(hh,head,strfield,strlen(add->strfield),add) +#define HASH_FIND_INT(head,findint,out) \ + HASH_FIND(hh,head,findint,sizeof(int),out) +#define HASH_ADD_INT(head,intfield,add) \ + HASH_ADD(hh,head,intfield,sizeof(int),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 ); \ + } \ + } \ +} while (0) +#else +#define HASH_FSCK(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); +#else +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) +#endif + +/* default to Jenkins unless specified e.g. DHASH_FUNCTION=HASH_SAX */ +#ifdef HASH_FUNCTION +#define HASH_FCN HASH_FUNCTION +#else +#define HASH_FCN HASH_JEN +#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_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); + +/* 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; \ +} + +/* 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) \ + } + +/* 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_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); + + +/* 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); \ + } + +typedef struct UT_hash_bucket { + struct UT_hash_handle *hh_head; + unsigned count; + unsigned expand_mult; +} UT_hash_bucket; + +typedef struct UT_hash_table { + UT_hash_bucket *buckets; + unsigned 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; + + +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 */ +} UT_hash_handle; + +#endif /* UTHASH_H */ -- cgit v1.1