From patchwork Tue Dec 21 11:25:27 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicola Pero X-Patchwork-Id: 76279 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id C97EAB7063 for ; Tue, 21 Dec 2010 22:25:40 +1100 (EST) Received: (qmail 31695 invoked by alias); 21 Dec 2010 11:25:37 -0000 Received: (qmail 31680 invoked by uid 22791); 21 Dec 2010 11:25:35 -0000 X-SWARE-Spam-Status: No, hits=-1.6 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, SARE_SUB_ENC_UTF8, TW_BJ X-Spam-Check-By: sourceware.org Received: from smtp191.iad.emailsrvr.com (HELO smtp191.iad.emailsrvr.com) (207.97.245.191) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 21 Dec 2010 11:25:30 +0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp49.relay.iad1a.emailsrvr.com (SMTP Server) with ESMTP id 379E6190A24 for ; Tue, 21 Dec 2010 06:25:28 -0500 (EST) Received: from dynamic4.wm-web.iad.mlsrvr.com (dynamic4.wm-web.iad1a.rsapps.net [192.168.2.153]) by smtp49.relay.iad1a.emailsrvr.com (SMTP Server) with ESMTP id 20F09190A13 for ; Tue, 21 Dec 2010 06:25:28 -0500 (EST) Received: from meta-innovation.com (localhost [127.0.0.1]) by dynamic4.wm-web.iad.mlsrvr.com (Postfix) with ESMTP id F08791D4A2AE for ; Tue, 21 Dec 2010 06:25:27 -0500 (EST) Received: by www2.webmail.us (Authenticated sender: nicola.pero@meta-innovation.com, from: nicola.pero@meta-innovation.com) with HTTP; Tue, 21 Dec 2010 12:25:27 +0100 (CET) Date: Tue, 21 Dec 2010 12:25:27 +0100 (CET) Subject: =?UTF-8?Q?libobjc:=20reindented=20hash.c=20(no=20code=20changes)?= From: "Nicola Pero" To: "GCC Patches" MIME-Version: 1.0 X-Type: plain Message-ID: <1292930727.983621712@192.168.2.228> X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Reindented file hash.c. No code changes. Committed to trunk. Thanks 2010-12-21 Nicola Pero * hash.c: Tidied up comments and indentation. No code changes. Index: ChangeLog =================================================================== --- ChangeLog (revision 168108) +++ ChangeLog (working copy) @@ -1,3 +1,7 @@ +2010-12-21 Nicola Pero + + * hash.c: Tidied up comments and indentation. No code changes. + 2010-12-19 Nicola Pero PR libobjc/47012 Index: hash.c =================================================================== --- hash.c (revision 168108) +++ hash.c (working copy) @@ -23,12 +23,12 @@ see the files COPYING3 and COPYING.RUNTIME respect . */ #include "objc-private/common.h" -#include /* For assert */ +#include /* 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; }