Changeset 875 for trunk/psLib/src/sysUtils/psHash.c

Timestamp:

Jun 4, 2004, 1:46:11 PM (22 years ago)

Author:

gusciora

Message:

...

File:

• trunk/psLib/src/sysUtils/psHash.c (modified) (9 diffs)

trunk/psLib/src/sysUtils/psHash.c

@@ -45 +45 @@
     }
 
+    if (bucket->next != NULL)
+    {
+        hashBucketFree(bucket, itemFree);
+    }
+
     psFree(bucket->key);
     psMemDecrRefCounter(bucket->data);
@@ -88 +93 @@
      * Release data interned on the list, and delete the buckets
      */
+
     for (int i = 0; i < table->nbucket; i++)
     {
@@ -108 +114 @@
  
     We need itemFree if the key is already in use and we're inserting
- 
-    N.b. this is NOT a good hash function! See Knuth for some better ones
- *****************************************************************************/
+  *****************************************************************************/
 static void *doHashWork(psHash     *table,   // table to insert in
                         const char *key,     // key to use
-                        void       *data,    // data to insert,
-                        // or (if NULL) retrieve/remove
+                        void       *data,    // data to insert, or (if NULL) retrieve/remove
                         int remove
                             ,          // remove the item from the list?
-                            void (*itemFree)(void *item))
-    // how to free hashed data
-{
-    long int hash = 1;
-
+                            void (*itemFree)(void *item)) // how to free hashed data
+{
+    long int hash = 1;                  // This will contained an integer value
+    // "hashed" from the key.
+    psHashBucket *ptr = NULL;           // Used to retrieve the requested hash
+    // bucket.
+    psHashBucket *optr = NULL;
+
+    // NOTE: this is NOT a good hash function!  See Knuth.
+    //
     for (int i = 0, len = strlen(key); i < len; i++) {
         hash = (hash << 1) ^ key[i];
     }
-
     hash &= (table->nbucket - 1);
 
-    psHashBucket *ptr = table->buckets[hash];
-
-    // We've found the correct hash bucket, now we need to know what to do
-    if (data == NULL) {   // retrieve/remove
+    ptr = table->buckets[hash];
+
+    // We've found 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
            ) {
-            psHashBucket *optr = ptr;
+            // We search through the linked list for this bucket in
+            // the hash table and look for an entry for this key.
+
+            optr = ptr;
             while (ptr != NULL) {
-                if (strcmp(key, ptr->key) == 0) { // found it!
+                if (strcmp(key, ptr->key) == 0) {
                     void *data = ptr->data;
                     optr->next = ptr->next;
@@ -143 +155 @@
                         table->buckets[hash] = ptr->next;
                     }
+
+                    //                    if (itemFree != NULL) {
+                    //                        printf("Calling itemFree()\n");
+                    //                        itemFree(psMemDecrRefCounter(ptr->data));
+                    //                        printf("Called itemFree()\n");
+                    //                    }
 
                     psFree(ptr->key);
@@ -159 +177 @@
                     return ptr->data;
                 }
-
                 ptr = ptr->next;
             }
@@ -165 +182 @@
 
         return NULL;   // not in hash
-    } else {    // insert
+    } else {
+        // We get here if this procedure was called with non-NULL data.
+        // Therefore, we should insert that data into the hash table.
+        // First, we search through the linked list for this bucket in
+        // the hash table and look for a duplicate entry for this key.
+
+
         while (ptr != NULL) {
-            if (strcmp(key, ptr->key) == 0) { // found it!
+            if (strcmp(key, ptr->key) == 0) {
+                // We have found this key in the hash table.
                 if (itemFree == NULL) {
-                    return NULL; // can't insert
+                    // The user has not supplied a routine, so we cannot
+                    // insert the data.
+                    return NULL;
                 }
 
@@ -182 +208 @@
         }
 
-        // Not found, so insert at the front of the list
-        table->buckets[hash] = hashBucketAlloc(key, data, table->buckets[hash]);
+        // 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;
@@ -197 +226 @@
                    void (*itemFree)(void *item)) // how to free hashed data;
 {
-    return doHashWork(table, key, data, 0, itemFree);
+    void *tmp;
+
+    tmp = doHashWork(table, key, data, 0, itemFree);
+    return(tmp);
 }
 
@@ -213 +245 @@
  *****************************************************************************/
 void *psHashRemove(psHash *table,   // table to lookup key in
-                   const char *key) // key to lookup
-{
-    return doHashWork(table, key, NULL, 1, NULL);
-}
+                   const char *key, // key to lookup
+                   void (*itemFree)(void *item)) // how to free hashed data;
+{
+    return doHashWork(table, key, NULL, 1, itemFree);
+}