libobjc/hash.c

/* Hash tables for Objective C internal structures
   Copyright (C) 1993, 1996, 1997, 2004, 2009 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 "assert.h"

#include "objc/hash.h"

#include "objc/runtime.h"		/* for DEBUG_PRINTF */

/* 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;
}