summaryrefslogtreecommitdiff
path: root/libobjc/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'libobjc/hash.c')
-rw-r--r--libobjc/hash.c295
1 files changed, 295 insertions, 0 deletions
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
+<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-11-01 09:31:47 +0000