/* Hash tables for Objective C method dispatch.
   Copyright (C) 1993, 1995, 1996 Free Software Foundation, Inc.

This file is part of GNU CC.

GNU CC 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 2, or (at your option)
any later version.

GNU CC 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.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

/* As a special exception, if you link this library with files
   compiled with GCC to produce an executable, this does not cause
   the resulting executable to be covered by the GNU General Public License.
   This exception does not however invalidate any other reasons why
   the executable file might be covered by the GNU General Public License.  */


#ifndef __hash_INCLUDE_GNU
#define __hash_INCLUDE_GNU

#include <stddef.h>
#include <stdlib.h>
#include <objc/objc.h>
#include <objc/objc-api.h>

/*
 * This data structure is used to hold items
 *  stored in a hash table.  Each node holds 
 *  a key/value pair.
 *
 * Items in the cache are really of type void *.
 */
typedef struct cache_node
{
  struct cache_node *next;	/* Pointer to next entry on the list.
				   NULL indicates end of list. */
  const void *key;		/* Key used to locate the value.  Used
				   to locate value when more than one
				   key computes the same hash
				   value. */
  void *value;			/* Value stored for the key. */
} *node_ptr;

/*
 * This data structure is the cache.
 *
 * It must be passed to all of the hashing routines
 *   (except for new).
 */
typedef struct cache
{
  /* Variables used to implement the hash itself.  */
  node_ptr *node_table; /* Pointer to an array of hash nodes.  */
  /* Variables used to track the size of the hash table so to determine
    when to resize it.  */
  unsigned int size; /* Number of buckets allocated for the hash table
			(number of array entries allocated for
			"node_table").  Must be a power of two.  */
  unsigned int used; /* Current number of entries in the hash table.  */
  unsigned int mask; /* Precomputed mask.  */

  /* Variables used to implement indexing through the hash table.  */

  unsigned int last_bucket; /* Tracks which entry in the array where
			       the last value was returned.  */

  char hashType; // 1 = string-hash, 0 = ptr-hash
} *cache_ptr;

static __inline__ unsigned int objc_call_hash(cache_ptr cache, const void *key)
{
  if (cache->hashType == 1) { // string hash
    register unsigned int ret = 0;
    register unsigned int ctr = 0;
        
    while (*(char*)key) {
      ret ^= *(char*)key++ << ctr;
      ctr = (ctr + 1) % sizeof (void *);
    }

    return (ret & cache->mask);
  }
  else if (cache->hashType == 0) // ptr hash
    return ((size_t)key / sizeof (void *)) & cache->mask;
  else
    abort();
}
static __inline__ int objc_call_compare(cache_ptr cache,
                                        const void *k1, const void *k2)
{
  if (cache->hashType == 1) { // string compare
    if (k1 == k2)
      return 1;
    else if (k1 == 0 || k2 == 0)
      return 0;
    else {
      while ((*(char*)k1 == *(char*)k2) && (*(char*)k1 != '\0'))
        k1++, k2++;

      return (*(char*)k1 == *(char*)k2) ? 1 : 0;
    }
  }
  else if (cache->hashType == 0) // ptr compare
    return !(k1 - k2);
  else
    abort();
}

/* Two important hash tables.  */
objc_EXPORT cache_ptr module_hash_table, class_hash_table;

#include <objc/objc-mem.h>

static __inline__ void hash_delete(cache_ptr cache);
static __inline__ void hash_remove(cache_ptr cache, const void *key);
static __inline__ unsigned int hash_ptr(cache_ptr cache, const void *key);
static __inline__ int compare_ptrs(register const void *k1, register const void *k2);
static __inline__ unsigned int hash_string(cache_ptr cache,register const void *key);

static __inline__ int
compare_strings(register const char *k1,register const char *k2);

/* Allocate and initialize a hash table.  */ 

static __inline__ cache_ptr ptrhash_new(unsigned int size) {
  cache_ptr hash_new (unsigned int size,
                      char hashType);
  return hash_new(size, 0);
}
static __inline__ cache_ptr strhash_new(unsigned int size) {
  cache_ptr hash_new (unsigned int size,
                      char hashType);
  return hash_new(size, 1);
}

/* Deallocate all of the hash nodes and the cache itself.  */

static __inline__ void 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 hash_next. this makes 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)) {
	hash_remove (cache,node->key);
	node = next_node;
      }

      hash_remove (cache,node->key);
    }
  }

  /* Release the array of nodes and the cache itself.  */
#if OBJC_WITH_GC
  GC_FREE(cache->node_table); cache->node_table = NULL;
  GC_FREE(cache); cache = NULL;
#else
  objc_free(cache->node_table);
  objc_free(cache);
#endif
}

/* Add the key/value pair to the hash table.  If the
   hash table reaches a level of fullness then it will be resized. 
                                                   
   assert if the key is already in the hash.  */

void hash_add (cache_ptr *cachep, const void *key, void *value);
     
/* Remove the key/value pair from the hash table.  
   assert if the key isn't in the table.  */

static __inline__ void hash_remove (cache_ptr cache, const void *key) {
  size_t indx = objc_call_hash(cache, 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.  */
  if (node == NULL) abort();

  /* Special case.  First element is the key/value pair to be removed.  */
  //if ((*cache->compare_func)(node->key, key)) {
  if (objc_call_compare(cache, node->key, key)) {
    cache->node_table[indx] = node->next;
#if OBJC_WITH_GC
    GC_FREE(node); node = NULL;
#else
    objc_free(node);
#endif
  }
  else {
    /* Otherwise, find the hash entry.  */
    node_ptr prev = node;
    BOOL removed = NO;

    do {
      //if ((*cache->compare_func)(node->key, key)) {
      if (objc_call_compare(cache, node->key, key)) {
        prev->next = node->next, removed = YES;
#if OBJC_WITH_GC
        GC_FREE(node); node = NULL;
#else
        objc_free(node);
#endif
      } else {
        prev = node, node = node->next;
      }
    } while (!removed && node);
    if(removed==0) abort();
  }

  /* Decrement the number of entries in the hash table.  */
  --cache->used;
}

/* Used to index through the hash table.  Start with NULL
   to get the first entry.
                                                  
   Successive calls pass the value returned previously.
   ** Don't modify the hash during this operation *** 
                                                  
   Cache nodes are returned such that key or value can
   be extracted.  */

static __inline__ node_ptr 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;
}

/* Used to return a value from a hash table using a given key.  */

static __inline__ void *hash_value_for_key (cache_ptr cache, const void *key) {
  /* Given KEY, return corresponding value for it in CACHE.
     Return NULL if the KEY is not recorded.  */

  node_ptr node    = cache->node_table[objc_call_hash(cache, 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)) {
      if (objc_call_compare(cache, node->key, key)) {
        retval = node->value;
              break;
      } else
        node = node->next;
    } while (!retval && node);

  return retval;
}

/* Used to determine if the given key exists in the hash table */

static __inline__ BOOL hash_is_key_in_hash (cache_ptr cache, const void *key) {
  /* Given KEY, return YES if it exists in the CACHE.
     Return NO if it does not */
  
  //node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
  register node_ptr node = cache->node_table[objc_call_hash(cache, key)];

  if (node) {
    do {
      //if ((*cache->compare_func)(node->key, key))
      if (objc_call_compare(cache, node->key, key))
	  return YES;

      node = node->next;
    } while (node);
  }
  return NO;
}

/************************************************

        Useful hashing functions.  
        
        Declared inline for your pleasure.
        
************************************************/

/* Calculate a hash code by performing some 
   manipulation of the key pointer.  (Use the lowest bits
   except for those likely to be 0 due to alignment.)  */

static __inline__ unsigned int hash_ptr (cache_ptr cache, const void *key)
{
  return ((size_t)key / sizeof (void *)) & cache->mask;
}


/* Calculate a hash code by iterating over a NULL 
   terminate string.  */
static __inline__ unsigned int
hash_string (cache_ptr cache,register const void *key)
{
  register unsigned int ret = 0;
  register unsigned int ctr = 0;
        
  while (*(char*)key) {
    ret ^= *(char*)key++ << ctr;
    ctr = (ctr + 1) % sizeof (void *);
  }

  return (ret & cache->mask);
}


/* Compare two pointers for equality.  */
static __inline__ int
compare_ptrs (register const void *k1, register const void *k2)
{
  return !(k1 - k2);
}


/* Compare two strings.  */
static __inline__ int
compare_strings(register const char *k1,register const char *k2)
{
  if (k1 == k2)
    return 1;
  else if (k1 == 0 || k2 == 0)
    return 0;
  else {
    while ((*k1 == *k2) && (*k1 != '\0')) {
      k1++;
      k2++;
    }
    return (*k1 == *k2) ? 1 : 0;

    //return !strcmp (k1, k2);
  }
}

#endif /* not __hash_INCLUDE_GNU */