Index: /trunk/psLib/src/sys/psLogMsg.c =================================================================== --- /trunk/psLib/src/sys/psLogMsg.c (revision 963) +++ /trunk/psLib/src/sys/psLogMsg.c (revision 964) @@ -39,5 +39,5 @@ static int log_msg = 1; // Flag to include message info /***************************************************************************** -psSetLogLevel(): Set the current log level and return old level. +psLogSetLevel(): Set the current log level and return old level. Input: level (int): the new log level. @@ -47,5 +47,5 @@ The old log level. *****************************************************************************/ -int psSetLogLevel(int level) +int psLogSetLevel(int level) { int oldLevel = logLevel; @@ -63,5 +63,5 @@ /***************************************************************************** -psSetLogDestination(): sets the destination where log messages will be +psLogSetDestination(): sets the destination where log messages will be sent to. @@ -73,5 +73,5 @@ An integer specifying the old log destination. *****************************************************************************/ -int psSetLogDestination(int dest) +int psLogSetDestination(int dest) { int old = logDest; @@ -95,5 +95,5 @@ /***************************************************************************** -psSetLogFormat(): Set the format of psLogMsg output. More precisely, +psLogSetFormat(): Set the format of psLogMsg output. More precisely, provide a string consisting of the letters {H (host), L (level), M (message), N (name), T (time)}. The default is "HLMNT". This string @@ -109,5 +109,5 @@ NULL. *****************************************************************************/ -void psSetLogFormat(const char *fmt) +void psLogSetFormat(const char *fmt) { int nlog_time = 0; Index: /trunk/psLib/src/sys/psLogMsg.h =================================================================== --- /trunk/psLib/src/sys/psLogMsg.h (revision 963) +++ /trunk/psLib/src/sys/psLogMsg.h (revision 964) @@ -15,14 +15,30 @@ */ -/// Sets the log destination -int psSetLogDestination(int dest); +/// This procedure sets the destination for future log messages. Currently +/// the destination is specified by an integer which can have the following +/// pre-defined values: PS_LOG_NONE, PS_LOG_TO_STDOUT, and PS_LOG_TO_STDERR. +/// IN future versions, this procedure will take a character string as an +/// argument which can specify more general log destinations. +int psLogSetDestination(int dest); -/// Sets the log level -int psSetLogLevel(int level); +/// This procedure sets the global level for future log messages. Future +/// log messages, each with a log level of mylevel, will only be logged if +/// their mylevel is less than the current log level set by this procedure. +/// Ie. higher values set by this procedure will cause more log messages to +/// be displayed. +int psLogSetLevel(int level); -/// sets the log format -void psSetLogFormat(const char *fmt); +/// This procedure sets the log format for future log messages. The argument +/// must be a character string consistsing of the letters H (host), L +/// (level), M (message), N (name), and T (time). The default is "THLNM". +/// Deleting a letter from the string will cause the associated information +/// to not be logged. +void psLogSetFormat(const char *fmt); -/// Logs a message + +/// This procedure logs a message to the destination set by a prior +/// call to psLogSetDestination(), if myLevel is less than the level +/// specified by a prior call to psLogSetLevel(). The message is specified +/// with a printf-stype string an arguments. void psLogMsg(const char *name, ///< name of the log source int myLevel, ///< severity level of this log message @@ -30,5 +46,8 @@ ; -/// Logs a message from varargs + + +/// This procedure is functionally equivalent to psLogMsg(), except that +/// it takes a va_list as the message paramater, not a printf-style string. void psVLogMsg(const char *name, ///< name of the log source int myLevel, ///< severity level of this log message Index: /trunk/psLib/src/sysUtils/psHash.c =================================================================== --- /trunk/psLib/src/sysUtils/psHash.c (revision 963) +++ /trunk/psLib/src/sysUtils/psHash.c (revision 964) @@ -4,5 +4,5 @@ * * This file will hold the functions for defining a hash table with arbitrary - * data types, allocating/deallocating that has table, adding and removing + * data types, allocating/deallocating that hash table, adding and removing * data from that hash table, and listing all keys defined in the hash table. * @@ -10,6 +10,6 @@ * @author George Gusciora, MHPCC * - * @version $Revision: 1.7 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-06-08 19:08:40 $ + * @version $Revision: 1.8 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-06-10 00:09:55 $ * * Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -18,5 +18,4 @@ #include #include -//#include "psLib.h" #include "psHash.h" #include "psMemory.h" @@ -25,8 +24,18 @@ #include "psAbort.h" + +/****************************************************************************** +psHashKeyList(table): this function creates a linked list with an entry in +that list for every key in the hash table. +Inputs: + table: a hash table +Return; + The linked list + *****************************************************************************/ psList *psHashKeyList(psHash *table) { - int i = 0; - psList *myLinkList = NULL; + int i = 0; // Loop index variable + psList *myLinkList = NULL; // The output data structure + psHashBucket *ptr = NULL; // Used to step thru linked list. if (table == NULL) { @@ -34,17 +43,37 @@ } + // Create the linked list myLinkList = psListAlloc(NULL); + // Loop through every bucket in the hash table. If that bucket is not + // NULL, then add the bucket's key to the linked list. for (i=0;inbucket;i++) { if (table->buckets[i] != NULL) { - psListAdd(myLinkList, (table->buckets[i])->key, PS_LIST_HEAD); + // Since a bucket contains a linked list of keys/data, we must + // step trough each key in that linked list: + + ptr = table->buckets[i]; + while (ptr != NULL) { + psListAdd(myLinkList, ptr->key, PS_LIST_HEAD); + ptr = ptr->next; + } } } + // Return the linked list return(myLinkList); } -/****************************************************************************** - Construct buckets + + +/****************************************************************************** +hashBucketAlloc(key, data, next): This procedure creates a new hash bucket +with the specified key, data, and next. +Inputs: + key: the new bucket's key pointer + data: the new bucket's data pointer + next: the new bucket's key pointer +Return: + the new hash bucket. *****************************************************************************/ static psHashBucket *hashBucketAlloc(const char *key, @@ -52,8 +81,21 @@ psHashBucket *next) { + if (key == NULL) { + psAbort(__func__, "psHashBucket() called with NULL key."); + } + + // Allocate memory for the new hash bucket. psHashBucket *bucket = psAlloc(sizeof(psHashBucket)); + // Initialize the bucket. bucket->key = psStringCopy(key); - bucket->data = psMemIncrRefCounter(data); + + if (data == NULL) { + // NOTE: Should we flag a warning message? + bucket->data = NULL; + } else { + bucket->data = psMemIncrRefCounter(data); + } + bucket->next = next; @@ -61,6 +103,16 @@ } -/****************************************************************************** - Destruct buckets + +/****************************************************************************** +hashBucketFree(bucket, itemFree): This procedure deallocates the specified +hash bucket. If "itemFree" is NULL, then we simply free the data with the +standard psFree() function. If "itemFree" is not NULL, then it must be a +function pointer which takes the hash bucket as a parameter, and frees the +data in that hash bucket. +Inputs: + bucket: the hash bucket to be freed. + itemFree: a function pointer, possibly NULL. +Return: + NONE *****************************************************************************/ static void hashBucketFree(psHashBucket *bucket, // bucket to free @@ -72,4 +124,6 @@ } + // A bucket is actually a linked list of buckets. We recursively step + // through that linked list, free each bucket. if (bucket->next != NULL) { @@ -83,4 +137,7 @@ { itemFree(bucket->data); + } else + { + psFree(bucket->data); } @@ -88,10 +145,20 @@ } -/****************************************************************************** - Con/Destruct psHash tables + +/****************************************************************************** +psHashAlloc(nbucket): this procedure creates a new hash table with the +specified number of buckets. +Inputs: + nbucket: initial number of buckets +Return: + The new hash table. *****************************************************************************/ psHash *psHashAlloc(int nbucket) // initial number of buckets { + int i = 0; // loop index variable + // Create the new hash table. psHash *table = psAlloc(sizeof(psHash)); + + // Allocate memory for the buckets. table->buckets = psAlloc(nbucket*sizeof(psHashBucket *)); table->nbucket = nbucket; @@ -99,32 +166,52 @@ psTrace("utils.hash", 1, "Creating %d-element hash table\n", nbucket); - for (int i = 0; i < nbucket; i++) + // Initialize all buckets to NULL. + for (i = 0; i < nbucket; i++) { table->buckets[i] = NULL; } + // Return the new hash table. return table; } -/****************************************************************************** + + +/****************************************************************************** +psHashFree(table, itemFree): This procedure deallocates the specified hash +table. It loops through each bucket, and calls hashBucketFree() on that +bucket. +Inputs: + table: a hash table + itemFree: a function pointer, possibly NULL. +Return: + NONE *****************************************************************************/ void psHashFree(psHash *table, // hash table to be freed void (*itemFree)(void *item)) // how to free hashed data; or NULL { + psHashBucket *tmp = NULL; // Used to step through linked list. + psHashBucket *ptr = NULL; // Used to step through linked list. + int i = 0; // Loop index variable. + if (table == NULL) { return; } - /* - * Release data interned on the list, and delete the buckets - */ - - for (int i = 0; i < table->nbucket; i++) - { + + // Loop through each bucket in the hash table. If that bucket is not + // NULL, then free the bucket via a function call to hashBucketFree(); + + for (i = 0; i < table->nbucket; i++) + { + // A bucket is composed of a linked list of buckets. We use the + // "tmp" and "ptr" pointers to step through that list and free each + // non-NULL bucket. + if (table->buckets[i] != NULL) { - psHashBucket *ptr = table->buckets[i]; + ptr = table->buckets[i]; while (ptr != NULL) { - psHashBucket *tmp = ptr->next; + tmp = ptr->next; hashBucketFree(ptr, itemFree); ptr = tmp; @@ -133,4 +220,5 @@ } + // Free the bucket structure, then the hash table. psFree(table->buckets); psFree(table); @@ -138,7 +226,23 @@ /****************************************************************************** - Here's the routine to do the work of insertion/retrieval/removal +doHashWork(table, key, data, remove, itemFree): This is an internal +procedure which does the bulk of the work in using the hash table. Depending +upon the input parameters, it will either insert a new key/data into the hash +table, retrieve the data for a specified key, or remove a key/data item. If +we try to insert a key that already exists in the hash table, then we call +the user-supplied function itemfree (or psFree if that is NULL), to free the +existing data/key item. +Inputs: + table: a hash table + key: the key to insert, retrieve, or remove. Must not be NULL. + data: the data to insert, if not NULL + remove: set to non-zero if the key/data should be removed from the table. + itemFree: function pointer +Return: + NONE - We need itemFree if the key is already in use and we're inserting +NOTE: consider removing this private function and simply putting the code +into the psHashInsert(), psHashLookup(), and psHashRemove(). Why? Because +there is little common code between those functions. *****************************************************************************/ static void *doHashWork(psHash *table, // table to insert in @@ -149,13 +253,20 @@ void (*itemFree)(void *item)) // how to free hashed data { - long int hash = 1; // This will contained an integer value + long int hash = 1; // This will contain an integer value // "hashed" from the key. - psHashBucket *ptr = NULL; // Used to retrieve the requested hash - // bucket. - psHashBucket *optr = NULL; - char *tmpchar = NULL; - - // NOTE: this is NOT a good hash function! See Knuth. - // + char *tmpchar = NULL; // Used in computing the hash function. + psHashBucket *ptr = NULL; // Used to retrieve the hash bucket. + psHashBucket *optr = NULL; // "original pointer": used to step + // thru the linked list for a bucket. + + // The following condition should never be true, since this is a private + // function, but I'm checking it anyway since future coders might change + // the way this procedure is called. + if ((table == NULL) || (key == NULL)) { + + psAbort(__func__, "psHashRemove() called with NULL key or table."); + } + + // NOTE: This is the originally supplied hash function. // for (int i = 0, len = strlen(key); i < len; i++) { // hash = (hash << 1) ^ key[i]; @@ -172,15 +283,15 @@ // NOTE: This should not be necessary, but for now, I'm checking bounds // anyway. - if ((hash < 0) || - (hash >= table->nbucket)) { - psAbort(__func__,"Internal hash function out of range (%d)", - hash); - } - + if ((hash < 0) || (hash >= table->nbucket)) { + psAbort(__func__,"Internal hash function out of range (%d)", hash); + } + + // ptr will have the correct hash bucket. ptr = table->buckets[hash]; - // We've found the correct hash bucket, now we need to know what to do. + // We know the correct hash bucket, now we need to know what to do. // If the data parameter is NULL, then, by definition, this is a retrieve // or a remove operation on the hash table. + if (data == NULL) { if (remove @@ -191,38 +302,39 @@ optr = ptr; while (ptr != NULL) { + // Dtermine if this entry holds the correct key. if (strcmp(key, ptr->key) == 0) { + // The following lines of code are fairly standard ways + // of removing an item from a single-linked list. + void *data = ptr->data; optr->next = ptr->next; - if (ptr == table->buckets[hash]) { table->buckets[hash] = ptr->next; } - // if (itemFree != NULL) { - // printf("Calling itemFree()\n"); - // itemFree(psMemDecrRefCounter(ptr->data)); - // printf("Called itemFree()\n"); - // } - psFree(ptr->key); psFree(ptr); - return psMemDecrRefCounter(data); // return data + // By definition, the data associated with that key + // must be returned, not freed. + return psMemDecrRefCounter(data); } - optr = ptr; ptr = ptr->next; } + return NULL; // not in hash } else { + // If we get here, then a retrieve operation is requested. So, + // we step trough the linked list at this bucket, and return the + // data once we find it, or return NULL if we don't. while (ptr != NULL) { - if (strcmp(key, ptr->key) == 0) { // found it! + if (strcmp(key, ptr->key) == 0) { return ptr->data; } ptr = ptr->next; } + return NULL; // not in hash } - - return NULL; // not in hash } else { // We get here if this procedure was called with non-NULL data. @@ -231,30 +343,31 @@ // the hash table and look for a duplicate entry for this key. - while (ptr != NULL) { if (strcmp(key, ptr->key) == 0) { // We have found this key in the hash table. - if (itemFree == NULL) { - // The user has not supplied a routine, so we cannot - // insert the data. - return NULL; - } psTrace("utils.hash.insert", 3, "Replacing data for %s\n", key); - itemFree(psMemDecrRefCounter(ptr->data)); + // NOTE: I have changed this behavior from the originally + // supplied code. Formerly, if itemFree was NULL, then + // the new data was not inserted into the hash table. + + if (itemFree == NULL) { + psFree(psMemDecrRefCounter(ptr->data)); + } else { + itemFree(psMemDecrRefCounter(ptr->data)); + } + ptr->data = psMemIncrRefCounter(data); - return data; } } - // We did not found key in the linked list for this bucket of the hash // table. So, we insert this data at the head of that linked list. + table->buckets[hash] = hashBucketAlloc(key, data, table->buckets[hash]); - return data; } @@ -262,5 +375,13 @@ /****************************************************************************** - Insert a value into a hash table +psHashInsert(table, key, data, itemFree): this procedure, which is part of +the public API, inserts a new key/data pair into the hash table. +Inputs: + table: a hash table + key: the key to use + data: the data to insert. + itemFree: a function pointer +Return: + NONE *****************************************************************************/ void *psHashInsert(psHash *table, // table to insert in @@ -269,21 +390,51 @@ void (*itemFree)(void *item)) // how to free hashed data; { - void *tmp; - - tmp = doHashWork(table, key, data, 0, itemFree); - return(tmp); -} - -/****************************************************************************** - Lookup a value in a hash table + if (table == NULL) { + psAbort(__func__, "psHashInsert() called with NULL hash table."); + } + if (key == NULL) { + psAbort(__func__, "psHashInsert() called with NULL key."); + } + if (data == NULL) { + psAbort(__func__, "psHashLookup() called with NULL data."); + } + + return doHashWork(table, key, data, 0, itemFree); +} + +/****************************************************************************** +psHashLookup(table, key): this procedure, which is part of the public API, +looks up the specified key in the hash table and returns the data associated +with that key. + +Inputs: + table: a hash table + key: the key to use +Return: + The data associated with that key. *****************************************************************************/ void *psHashLookup(psHash *table, // table to lookup key in const char *key) // key to lookup { + if (table == NULL) { + psAbort(__func__, "psHashLookup() called with NULL hash table."); + } + if (key == NULL) { + psAbort(__func__, "psHashLookup() called with NULL key."); + } + + return doHashWork(table, key, NULL, 0, NULL); } /****************************************************************************** - Remove and return a value from a hash table +psHashRemove(table, key, itemFree): this procedure, which is part of the +public API, removes the specified key from the hash table. +Inputs: + table: a hash table + key: the key to remove + itemFree: a function pointer +Return: + The data that was associated with that key. *****************************************************************************/ void *psHashRemove(psHash *table, // table to lookup key in @@ -291,4 +442,11 @@ void (*itemFree)(void *item)) // how to free hashed data; { + if (table == NULL) { + psAbort(__func__, "psHashRemove() called with NULL hash table."); + } + if (key == NULL) { + psAbort(__func__, "psHashRemove() called with NULL key."); + } + return doHashWork(table, key, NULL, 1, itemFree); } Index: /trunk/psLib/src/sysUtils/psHash.h =================================================================== --- /trunk/psLib/src/sysUtils/psHash.h (revision 963) +++ /trunk/psLib/src/sysUtils/psHash.h (revision 964) @@ -1,3 +1,3 @@ -/** @file psHash.c +/** @file psHash.h * * @brief Contains support for basic hashing functions. @@ -10,6 +10,6 @@ * @author George Gusciora, MHPCC * - * @version $Revision: 1.8 $ $Name: not supported by cvs2svn $ - * @date $Date: 2004-06-08 19:08:40 $ + * @version $Revision: 1.9 $ $Name: not supported by cvs2svn $ + * @date $Date: 2004-06-10 00:09:55 $ * * Copyright 2004 Maui High Performance Computing Center, University of Hawaii @@ -26,21 +26,18 @@ -/** DO WE NEED TO DEFINE HashTable? */ -//typedef struct HashTable psHash; ///< Opaque type for a hash table -// An entire hash table - // A bucket that holds an item of data typedef struct psHashBucket { - char *key; // key for this item of data - void *data; // the data itself - struct psHashBucket *next; // list of other possible keys + char *key; ///< key for this item of data + void *data; ///< the data itself + struct psHashBucket *next; ///< list of other possible keys } psHashBucket; +//typedef struct HashTable psHash; ///< Opaque type for a hash table typedef struct psHash { - int nbucket; - psHashBucket **buckets; + int nbucket; //< Number of buckets in hash table. + psHashBucket **buckets; //< The bucket data. } psHash; @@ -78,5 +75,6 @@ /// List all keys in table. -psList *psHashKeyList(psHash *table); +psList *psHashKeyList(psHash *table ///< table to list keys from. + ); /* \} */ // End of DataGroup Functions Index: /trunk/psLib/src/sysUtils/psLogMsg.c =================================================================== --- /trunk/psLib/src/sysUtils/psLogMsg.c (revision 963) +++ /trunk/psLib/src/sysUtils/psLogMsg.c (revision 964) @@ -39,5 +39,5 @@ static int log_msg = 1; // Flag to include message info /***************************************************************************** -psSetLogLevel(): Set the current log level and return old level. +psLogSetLevel(): Set the current log level and return old level. Input: level (int): the new log level. @@ -47,5 +47,5 @@ The old log level. *****************************************************************************/ -int psSetLogLevel(int level) +int psLogSetLevel(int level) { int oldLevel = logLevel; @@ -63,5 +63,5 @@ /***************************************************************************** -psSetLogDestination(): sets the destination where log messages will be +psLogSetDestination(): sets the destination where log messages will be sent to. @@ -73,5 +73,5 @@ An integer specifying the old log destination. *****************************************************************************/ -int psSetLogDestination(int dest) +int psLogSetDestination(int dest) { int old = logDest; @@ -95,5 +95,5 @@ /***************************************************************************** -psSetLogFormat(): Set the format of psLogMsg output. More precisely, +psLogSetFormat(): Set the format of psLogMsg output. More precisely, provide a string consisting of the letters {H (host), L (level), M (message), N (name), T (time)}. The default is "HLMNT". This string @@ -109,5 +109,5 @@ NULL. *****************************************************************************/ -void psSetLogFormat(const char *fmt) +void psLogSetFormat(const char *fmt) { int nlog_time = 0; Index: /trunk/psLib/src/sysUtils/psLogMsg.h =================================================================== --- /trunk/psLib/src/sysUtils/psLogMsg.h (revision 963) +++ /trunk/psLib/src/sysUtils/psLogMsg.h (revision 964) @@ -15,14 +15,30 @@ */ -/// Sets the log destination -int psSetLogDestination(int dest); +/// This procedure sets the destination for future log messages. Currently +/// the destination is specified by an integer which can have the following +/// pre-defined values: PS_LOG_NONE, PS_LOG_TO_STDOUT, and PS_LOG_TO_STDERR. +/// IN future versions, this procedure will take a character string as an +/// argument which can specify more general log destinations. +int psLogSetDestination(int dest); -/// Sets the log level -int psSetLogLevel(int level); +/// This procedure sets the global level for future log messages. Future +/// log messages, each with a log level of mylevel, will only be logged if +/// their mylevel is less than the current log level set by this procedure. +/// Ie. higher values set by this procedure will cause more log messages to +/// be displayed. +int psLogSetLevel(int level); -/// sets the log format -void psSetLogFormat(const char *fmt); +/// This procedure sets the log format for future log messages. The argument +/// must be a character string consistsing of the letters H (host), L +/// (level), M (message), N (name), and T (time). The default is "THLNM". +/// Deleting a letter from the string will cause the associated information +/// to not be logged. +void psLogSetFormat(const char *fmt); -/// Logs a message + +/// This procedure logs a message to the destination set by a prior +/// call to psLogSetDestination(), if myLevel is less than the level +/// specified by a prior call to psLogSetLevel(). The message is specified +/// with a printf-stype string an arguments. void psLogMsg(const char *name, ///< name of the log source int myLevel, ///< severity level of this log message @@ -30,5 +46,8 @@ ; -/// Logs a message from varargs + + +/// This procedure is functionally equivalent to psLogMsg(), except that +/// it takes a va_list as the message paramater, not a printf-style string. void psVLogMsg(const char *name, ///< name of the log source int myLevel, ///< severity level of this log message