aboutsummaryrefslogtreecommitdiffstats
path: root/gcc-4.7/libobjc/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'gcc-4.7/libobjc/hash.c')
-rw-r--r--gcc-4.7/libobjc/hash.c295
1 files changed, 0 insertions, 295 deletions
diff --git a/gcc-4.7/libobjc/hash.c b/gcc-4.7/libobjc/hash.c
deleted file mode 100644
index 733fc6501..000000000
--- a/gcc-4.7/libobjc/hash.c
+++ /dev/null
@@ -1,295 +0,0 @@
-/* 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
-<http://www.gnu.org/licenses/>. */
-
-#include "objc-private/common.h"
-#include <assert.h> /* 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;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-28 10:33:02 +0000