From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- libobjc/hash.c | 295 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 295 insertions(+) create mode 100644 libobjc/hash.c (limited to 'libobjc/hash.c') diff --git a/libobjc/hash.c b/libobjc/hash.c new file mode 100644 index 000000000..733fc6501 --- /dev/null +++ b/libobjc/hash.c @@ -0,0 +1,295 @@ +/* Hash tables for Objective C internal structures + Copyright (C) 1993, 1996, 1997, 2004, 2009, 2010 + Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +Under Section 7 of GPL version 3, you are granted additional +permissions described in the GCC Runtime Library Exception, version +3.1, as published by the Free Software Foundation. + +You should have received a copy of the GNU General Public License and +a copy of the GCC Runtime Library Exception along with this program; +see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +. */ + +#include "objc-private/common.h" +#include /* For assert. */ + +#include "objc/runtime.h" /* For objc_calloc. */ +#include "objc-private/hash.h" + +/* These two macros determine when a hash table is full and + by how much it should be expanded respectively. + + These equations are percentages. */ +#define FULLNESS(cache) \ + ((((cache)->size * 75) / 100) <= (cache)->used) +#define EXPANSION(cache) \ + ((cache)->size * 2) + +cache_ptr +objc_hash_new (unsigned int size, hash_func_type hash_func, + compare_func_type compare_func) +{ + cache_ptr cache; + + /* Pass me a value greater than 0 and a power of 2. */ + assert (size); + assert (! (size & (size - 1))); + + /* 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. */ + 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 (?). */ + 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. */ + cache->compare_func = compare_func; + + return cache; +} + + +void +objc_hash_delete (cache_ptr cache) +{ + node_ptr node; + node_ptr next_node; + unsigned int i; + + /* 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); + } + } + + /* Release the array of nodes and the cache itself. */ + objc_free(cache->node_table); + objc_free(cache); +} + + +void +objc_hash_add (cache_ptr *cachep, const void *key, void *value) +{ + 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. */ + node->key = key; + node->value = value; + node->next = (*cachep)->node_table[indx]; + + /* 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; + } + } +#endif + + /* Install the node as the first element on the list. */ + (*cachep)->node_table[indx] = node; + + /* 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. + + 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); + node_ptr node = cache->node_table[indx]; + + /* 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); + } + + /* Decrement the number of entries in the hash table. */ + --cache->used; +} + + +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) + 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 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; +} + + +/* 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)]; + void *retval = NULL; + + if (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 */ +BOOL +objc_hash_is_key_in_hash (cache_ptr cache, const void *key) +{ + node_ptr node = cache->node_table[(*cache->hash_func) (cache, key)]; + + if (node) + do + { + if ((*cache->compare_func)(node->key, key)) + return YES; + else + node = node->next; + } + while (node); + + return NO; +} -- cgit v1.2.3