===================================================================
@@ -1,3 +1,7 @@
+2010-12-21 Nicola Pero <nicola.pero@meta-innovation.com>
+
+ * hash.c: Tidied up comments and indentation. No code changes.
+
2010-12-19 Nicola Pero <nicola.pero@meta-innovation.com>
PR libobjc/47012
===================================================================
@@ -23,12 +23,12 @@ see the files COPYING3 and COPYING.RUNTIME respect
<http://www.gnu.org/licenses/>. */
#include "objc-private/common.h"
-#include <assert.h> /* For assert */
+#include <assert.h> /* For assert. */
-#include "objc/runtime.h" /* For objc_calloc */
-#include "objc/thr.h" /* Required by objc-private/runtime.h. */
+#include "objc/runtime.h" /* For objc_calloc. */
+#include "objc/thr.h" /* Required by objc-private/runtime.h. */
#include "objc-private/hash.h"
-#include "objc-private/runtime.h" /* for DEBUG_PRINTF */
+#include "objc-private/runtime.h" /* for DEBUG_PRINTF. */
/* These two macros determine when a hash table is full and
by how much it should be expanded respectively.
@@ -49,27 +49,27 @@ objc_hash_new (unsigned int size, hash_func_type h
assert (size);
assert (! (size & (size - 1)));
- /* Allocate the cache structure. calloc insures
- its initialization for default values. */
+ /* Allocate the cache structure. calloc insures its initialization
+ for default values. */
cache = (cache_ptr) objc_calloc (1, sizeof (struct cache));
assert (cache);
- /* Allocate the array of buckets for the cache.
- calloc initializes all of the pointers to NULL. */
+ /* Allocate the array of buckets for the cache. calloc initializes
+ all of the pointers to NULL. */
cache->node_table
= (node_ptr *) objc_calloc (size, sizeof (node_ptr));
assert (cache->node_table);
cache->size = size;
- /* This should work for all processor architectures? */
+ /* This should work for all processor architectures (?). */
cache->mask = (size - 1);
/* Store the hashing function so that codes can be computed. */
cache->hash_func = hash_func;
- /* Store the function that compares hash keys to
- determine if they are equal. */
+ /* Store the function that compares hash keys to determine if they
+ are equal. */
cache->compare_func = compare_func;
return cache;
@@ -85,19 +85,22 @@ objc_hash_delete (cache_ptr cache)
/* Purge all key/value pairs from the table. */
/* Step through the nodes one by one and remove every node WITHOUT
- using objc_hash_next. this makes objc_hash_delete much more efficient. */
- for (i = 0;i < cache->size;i++) {
- if ((node = cache->node_table[i])) {
- /* an entry in the hash table has been found, now step through the
- nodes next in the list and free them. */
- while ((next_node = node->next)) {
- objc_hash_remove (cache,node->key);
- node = next_node;
- }
-
- objc_hash_remove (cache,node->key);
+ using objc_hash_next. this makes objc_hash_delete much more
+ efficient. */
+ for (i = 0; i < cache->size; i++)
+ {
+ if ((node = cache->node_table[i]))
+ {
+ /* An entry in the hash table has been found. Now step
+ through the nodes next in the list and free them. */
+ while ((next_node = node->next))
+ {
+ objc_hash_remove (cache,node->key);
+ node = next_node;
+ }
+ objc_hash_remove (cache,node->key);
+ }
}
- }
/* Release the array of nodes and the cache itself. */
objc_free(cache->node_table);
@@ -108,10 +111,9 @@ objc_hash_delete (cache_ptr cache)
void
objc_hash_add (cache_ptr *cachep, const void *key, void *value)
{
- size_t indx = (*(*cachep)->hash_func)(*cachep, key);
+ size_t indx = (*(*cachep)->hash_func) (*cachep, key);
node_ptr node = (node_ptr) objc_calloc (1, sizeof (struct cache_node));
-
assert (node);
/* Initialize the new node. */
@@ -119,16 +121,15 @@ objc_hash_add (cache_ptr *cachep, const void *key,
node->value = value;
node->next = (*cachep)->node_table[indx];
- /* Debugging.
- Check the list for another key. */
+ /* Debugging. Check the list for another key. */
#ifdef DEBUG
- { node_ptr node1 = (*cachep)->node_table[indx];
-
- while (node1) {
-
- assert (node1->key != key);
- node1 = node1->next;
- }
+ {
+ node_ptr node1 = (*cachep)->node_table[indx];
+ while (node1)
+ {
+ assert (node1->key != key);
+ node1 = node1->next;
+ }
}
#endif
@@ -137,69 +138,72 @@ objc_hash_add (cache_ptr *cachep, const void *key,
/* Bump the number of entries in the cache. */
++(*cachep)->used;
+
+ /* Check the hash table's fullness. We're going to expand if it is
+ above the fullness level. */
+ if (FULLNESS (*cachep))
+ {
+ /* The hash table has reached its fullness level. Time to
+ expand it.
- /* Check the hash table's fullness. We're going
- to expand if it is above the fullness level. */
- if (FULLNESS (*cachep)) {
-
- /* The hash table has reached its fullness level. Time to
- expand it.
-
- I'm using a slow method here but is built on other
- primitive functions thereby increasing its
- correctness. */
- node_ptr node1 = NULL;
- cache_ptr new = objc_hash_new (EXPANSION (*cachep),
- (*cachep)->hash_func,
- (*cachep)->compare_func);
-
- DEBUG_PRINTF ("Expanding cache %#x from %d to %d\n",
- (int) *cachep, (*cachep)->size, new->size);
-
- /* Copy the nodes from the first hash table to the new one. */
- while ((node1 = objc_hash_next (*cachep, node1)))
- objc_hash_add (&new, node1->key, node1->value);
-
- /* Trash the old cache. */
- objc_hash_delete (*cachep);
-
- /* Return a pointer to the new hash table. */
- *cachep = new;
- }
+ I'm using a slow method here but is built on other primitive
+ functions thereby increasing its correctness. */
+ node_ptr node1 = NULL;
+ cache_ptr new = objc_hash_new (EXPANSION (*cachep),
+ (*cachep)->hash_func,
+ (*cachep)->compare_func);
+
+ DEBUG_PRINTF ("Expanding cache %#x from %d to %d\n",
+ (int) *cachep, (*cachep)->size, new->size);
+
+ /* Copy the nodes from the first hash table to the new one. */
+ while ((node1 = objc_hash_next (*cachep, node1)))
+ objc_hash_add (&new, node1->key, node1->value);
+
+ /* Trash the old cache. */
+ objc_hash_delete (*cachep);
+
+ /* Return a pointer to the new hash table. */
+ *cachep = new;
+ }
}
-
void
objc_hash_remove (cache_ptr cache, const void *key)
{
- size_t indx = (*cache->hash_func)(cache, key);
+ size_t indx = (*cache->hash_func) (cache, key);
node_ptr node = cache->node_table[indx];
-
- /* We assume there is an entry in the table. Error if it is not. */
+ /* We assume there is an entry in the table. Error if it is
+ not. */
assert (node);
- /* Special case. First element is the key/value pair to be removed. */
- if ((*cache->compare_func)(node->key, key)) {
- cache->node_table[indx] = node->next;
- objc_free(node);
- } else {
-
- /* Otherwise, find the hash entry. */
- node_ptr prev = node;
- BOOL removed = NO;
-
- do {
-
- if ((*cache->compare_func)(node->key, key)) {
- prev->next = node->next, removed = YES;
- objc_free(node);
- } else
- prev = node, node = node->next;
- } while (! removed && node);
- assert (removed);
- }
-
+ /* Special case. First element is the key/value pair to be
+ removed. */
+ if ((*cache->compare_func) (node->key, key))
+ {
+ cache->node_table[indx] = node->next;
+ objc_free(node);
+ }
+ else
+ {
+ /* Otherwise, find the hash entry. */
+ node_ptr prev = node;
+ BOOL removed = NO;
+ do
+ {
+ if ((*cache->compare_func) (node->key, key))
+ {
+ prev->next = node->next, removed = YES;
+ objc_free(node);
+ }
+ else
+ prev = node, node = node->next;
+ }
+ while (!removed && node);
+ assert (removed);
+ }
+
/* Decrement the number of entries in the hash table. */
--cache->used;
}
@@ -208,76 +212,85 @@ objc_hash_remove (cache_ptr cache, const void *key
node_ptr
objc_hash_next (cache_ptr cache, node_ptr node)
{
- /* If the scan is being started then reset the last node
- visitied pointer and bucket index. */
- if (! node)
+ /* If the scan is being started then reset the last node visitied
+ pointer and bucket index. */
+ if (!node)
cache->last_bucket = 0;
-
- /* If there is a node visited last then check for another
- entry in the same bucket; Otherwise step to the next bucket. */
- if (node) {
- if (node->next)
- /* There is a node which follows the last node
- returned. Step to that node and retun it. */
- return node->next;
- else
- ++cache->last_bucket;
+
+ /* If there is a node visited last then check for another entry in
+ the same bucket. Otherwise step to the next bucket. */
+ if (node)
+ {
+ if (node->next)
+ {
+ /* There is a node which follows the last node returned.
+ Step to that node and retun it. */
+ return node->next;
+ }
+ else
+ ++cache->last_bucket;
}
- /* If the list isn't exhausted then search the buckets for
- other nodes. */
- if (cache->last_bucket < cache->size) {
- /* Scan the remainder of the buckets looking for an entry
- at the head of the list. Return the first item found. */
- while (cache->last_bucket < cache->size)
- if (cache->node_table[cache->last_bucket])
- return cache->node_table[cache->last_bucket];
- else
- ++cache->last_bucket;
-
- /* No further nodes were found in the hash table. */
+ /* If the list isn't exhausted then search the buckets for other
+ nodes. */
+ if (cache->last_bucket < cache->size)
+ {
+ /* Scan the remainder of the buckets looking for an entry at
+ the head of the list. Return the first item found. */
+ while (cache->last_bucket < cache->size)
+ if (cache->node_table[cache->last_bucket])
+ return cache->node_table[cache->last_bucket];
+ else
+ ++cache->last_bucket;
+
+ /* No further nodes were found in the hash table. */
+ return NULL;
+ }
+ else
return NULL;
- } else
- return NULL;
}
-/* Given KEY, return corresponding value for it in CACHE.
- Return NULL if the KEY is not recorded. */
-
+/* Given KEY, return corresponding value for it in CACHE. Return NULL
+ if the KEY is not recorded. */
void *
objc_hash_value_for_key (cache_ptr cache, const void *key)
{
- node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
+ node_ptr node = cache->node_table[(*cache->hash_func) (cache, key)];
void *retval = NULL;
if (node)
- do {
- if ((*cache->compare_func)(node->key, key)) {
- retval = node->value;
- break;
- } else
- node = node->next;
- } while (! retval && node);
-
+ do
+ {
+ if ((*cache->compare_func) (node->key, key))
+ {
+ retval = node->value;
+ break;
+ }
+ else
+ node = node->next;
+ }
+ while (! retval && node);
+
return retval;
}
-/* Given KEY, return YES if it exists in the CACHE.
- Return NO if it does not */
-
+/* Given KEY, return YES if it exists in the CACHE. Return NO if it
+ does not */
BOOL
objc_hash_is_key_in_hash (cache_ptr cache, const void *key)
{
- node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
-
+ node_ptr node = cache->node_table[(*cache->hash_func) (cache, key)];
+
if (node)
- do {
- if ((*cache->compare_func)(node->key, key))
+ do
+ {
+ if ((*cache->compare_func)(node->key, key))
return YES;
- else
- node = node->next;
- } while (node);
+ else
+ node = node->next;
+ }
+ while (node);
return NO;
}
Reindented file hash.c. No code changes. Committed to trunk. Thanks 2010-12-21 Nicola Pero <nicola.pero@meta-innovation.com> * hash.c: Tidied up comments and indentation. No code changes.