URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [tags/] [gnu-dev/] [fsf-gcc-snapshot-1-mar-12/] [or1k-gcc/] [libobjc/] [hash.c] - Rev 818
Go to most recent revision | Compare with Previous | Blame | View Log
/* 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; }
Go to most recent revision | Compare with Previous | Blame | View Log