src/kmk/hash.c

/* hash.c -- hash table maintenance
Copyright (C) 1995, 1999, 2002, 2010 Free Software Foundation, Inc.
Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org>

GNU Make 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 of the License, or (at your option) any later
version.

GNU Make 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
this program.  If not, see <http://www.gnu.org/licenses/>.  */

#include "make.h"
#include "hash.h"
#ifdef CONFIG_WITH_STRCACHE2
# include <assert.h>
#endif


/*#define	CALLOC(t, n) ((t *) calloc (sizeof (t), (n)))*/
#define	CALLOC(t, n) ((t *) xcalloc (sizeof (t) * (n)))
#define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n)))
#define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n)))
#define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n)))

static void hash_rehash __P((struct hash_table* ht));
static unsigned long round_up_2 __P((unsigned long rough));

/* Implement double hashing with open addressing.  The table size is
   always a power of two.  The secondary (`increment') hash function
   is forced to return an odd-value, in order to be relatively prime
   to the table size.  This guarantees that the increment can
   potentially hit every slot in the table during collision
   resolution.  */

void *hash_deleted_item = &hash_deleted_item;

/* Force the table size to be a power of two, possibly rounding up the
   given size.  */

void
hash_init (struct hash_table *ht, unsigned long size,
           hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)
{
  ht->ht_size = round_up_2 (size);
  ht->ht_empty_slots = ht->ht_size;
  ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size);
  if (ht->ht_vec == 0)
    {
      fprintf (stderr, _("can't allocate %lu bytes for hash table: memory exhausted"),
	       ht->ht_size * (unsigned long) sizeof (struct token *));
      exit (1);
    }

  ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */
  ht->ht_fill = 0;
  ht->ht_collisions = 0;
  ht->ht_lookups = 0;
  ht->ht_rehashes = 0;
  ht->ht_hash_1 = hash_1;
  ht->ht_hash_2 = hash_2;
  ht->ht_compare = hash_cmp;
#ifdef CONFIG_WITH_STRCACHE2
  ht->ht_strcache = 0;
  ht->ht_off_string = 0;
#endif
}

#ifdef CONFIG_WITH_STRCACHE2
/* Same as hash_init, except that no callbacks are needed since all
   keys - including the ones being searched for - are from a string
   cache.  This means that any give string will only have one pointer
   value and that the hash and length can be retrived very cheaply,
   thus permitting some nice optimizations.

   STRCACHE points to the string cache, while OFF_STRING gives the
   offset of the string pointer in the item structures the hash table
   entries points to.  */
void hash_init_strcached (struct hash_table *ht, unsigned long size,
                          struct strcache2 *strcache, unsigned int off_string)
{
  hash_init (ht, size, 0, 0, 0);
  ht->ht_strcache = strcache;
  ht->ht_off_string = off_string;
}
#endif /* CONFIG_WITH_STRCACHE2 */

/* Load an array of items into `ht'.  */

void
hash_load (struct hash_table *ht, void *item_table,
           unsigned long cardinality, unsigned long size)
{
  char *items = (char *) item_table;
#ifndef CONFIG_WITH_STRCACHE2
  while (cardinality--)
    {
      hash_insert (ht, items);
      items += size;
    }
#else  /* CONFIG_WITH_STRCACHE2 */
  if (ht->ht_strcache)
    while (cardinality--)
      {
        hash_insert_strcached (ht, items);
        items += size;
      }
  else
    while (cardinality--)
      {
        hash_insert (ht, items);
        items += size;
      }
#endif /* CONFIG_WITH_STRCACHE2 */
}

/* Returns the address of the table slot matching `key'.  If `key' is
   not found, return the address of an empty slot suitable for
   inserting `key'.  The caller is responsible for incrementing
   ht_fill on insertion.  */

void **
hash_find_slot (struct hash_table *ht, const void *key)
{
  void **slot;
  void **deleted_slot = 0;
  unsigned int hash_2 = 0;
  unsigned int hash_1 = (*ht->ht_hash_1) (key);

#ifdef CONFIG_WITH_STRCACHE2
  assert (ht->ht_strcache == 0);
#endif

  MAKE_STATS (ht->ht_lookups++);
  MAKE_STATS_3 (make_stats_ht_lookups++);
  for (;;)
    {
      hash_1 &= (ht->ht_size - 1);
      slot = &ht->ht_vec[hash_1];

      if (*slot == 0)
	return (deleted_slot ? deleted_slot : slot);
      if (*slot == hash_deleted_item)
	{
	  if (deleted_slot == 0)
	    deleted_slot = slot;
	}
      else
	{
	  if (key == *slot)
	    return slot;
	  if ((*ht->ht_compare) (key, *slot) == 0)
	    return slot;
	  MAKE_STATS (ht->ht_collisions++);
	  MAKE_STATS_3 (make_stats_ht_collisions++);
	}
      if (!hash_2)
	  hash_2 = (*ht->ht_hash_2) (key) | 1;
      hash_1 += hash_2;
    }
}

#ifdef CONFIG_WITH_STRCACHE2
/* hash_find_slot version for tables created with hash_init_strcached.  */
void **
hash_find_slot_strcached (struct hash_table *ht, const void *key)
{
  void **slot;
  void **deleted_slot = 0;
  const char *str1 = *(const char **)((const char *)key + ht->ht_off_string);
  const char *str2;
  unsigned int hash_1 = strcache2_calc_ptr_hash (ht->ht_strcache, str1);
  unsigned int hash_2;

#ifdef CONFIG_WITH_STRCACHE2
  assert (ht->ht_strcache != 0);
#endif

  MAKE_STATS (ht->ht_lookups++);
  MAKE_STATS_3 (make_stats_ht_lookups++);

  /* first iteration unrolled. */

  hash_1 &= (ht->ht_size - 1);
  slot = &ht->ht_vec[hash_1];
  if (*slot == 0)
    return slot;
  if (*slot != hash_deleted_item)
    {
      str2 = *(const char **)((const char *)(*slot) + ht->ht_off_string);
      if (str1 == str2)
        return slot;

      MAKE_STATS (ht->ht_collisions++);
      MAKE_STATS_3 (make_stats_ht_collisions++);
    }
  else
    deleted_slot = slot;

  /* the rest of the loop. */

  hash_2 = strcache2_get_hash (ht->ht_strcache, str1) | 1;
  hash_1 += hash_2;
  for (;;)
    {
      hash_1 &= (ht->ht_size - 1);
      slot = &ht->ht_vec[hash_1];

      if (*slot == 0)
	return (deleted_slot ? deleted_slot : slot);
      if (*slot == hash_deleted_item)
	{
	  if (deleted_slot == 0)
	    deleted_slot = slot;
	}
      else
	{
          str2 = *(const char **)((const char *)(*slot) + ht->ht_off_string);
          if (str1 == str2)
	    return slot;

	  MAKE_STATS (ht->ht_collisions++);
	  MAKE_STATS_3 (make_stats_ht_collisions++);
	}

      hash_1 += hash_2;
    }
}
#endif /* CONFIG_WITH_STRCACHE2 */

void *
hash_find_item (struct hash_table *ht, const void *key)
{
  void **slot = hash_find_slot (ht, key);
  return ((HASH_VACANT (*slot)) ? 0 : *slot);
}

#ifdef CONFIG_WITH_STRCACHE2
void *
hash_find_item_strcached (struct hash_table *ht, const void *key)
{
  void **slot = hash_find_slot_strcached (ht, key);
  return ((HASH_VACANT (*slot)) ? 0 : *slot);
}
#endif /* CONFIG_WITH_STRCACHE2 */

void *
hash_insert (struct hash_table *ht, const void *item)
{
  void **slot = hash_find_slot (ht, item);
  const void *old_item = *slot;
  hash_insert_at (ht, item, slot);
  return (void *)((HASH_VACANT (old_item)) ? 0 : old_item);
}

#ifdef CONFIG_WITH_STRCACHE2
void *
hash_insert_strcached (struct hash_table *ht, const void *item)
{
  void **slot = hash_find_slot_strcached (ht, item);
  const void *old_item = slot ? *slot : 0;
  hash_insert_at (ht, item, slot);
  return (void *)((HASH_VACANT (old_item)) ? 0 : old_item);
}
#endif /* CONFIG_WITH_STRCACHE2 */

void *
hash_insert_at (struct hash_table *ht, const void *item, const void *slot)
{
  const void *old_item = *(void **) slot;
  if (HASH_VACANT (old_item))
    {
      ht->ht_fill++;
      if (old_item == 0)
	ht->ht_empty_slots--;
      old_item = item;
    }
  *(void const **) slot = item;
  if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity)
    {
      hash_rehash (ht);
#ifdef CONFIG_WITH_STRCACHE2
      if (ht->ht_strcache)
        return (void *)hash_find_slot_strcached (ht, item);
#endif /* CONFIG_WITH_STRCACHE2 */
      return (void *) hash_find_slot (ht, item);
    }
  else
    return (void *) slot;
}

void *
hash_delete (struct hash_table *ht, const void *item)
{
  void **slot = hash_find_slot (ht, item);
  return hash_delete_at (ht, slot);
}

#ifdef CONFIG_WITH_STRCACHE2
void *
hash_delete_strcached (struct hash_table *ht, const void *item)
{
  void **slot = hash_find_slot_strcached (ht, item);
  return hash_delete_at (ht, slot);
}
#endif /* CONFIG_WITH_STRCACHE2 */

void *
hash_delete_at (struct hash_table *ht, const void *slot)
{
  void *item = *(void **) slot;
  if (!HASH_VACANT (item))
    {
      *(void const **) slot = hash_deleted_item;
      ht->ht_fill--;
      return item;
    }
  else
    return 0;
}

void
hash_free_items (struct hash_table *ht)
{
  void **vec = ht->ht_vec;
  void **end = &vec[ht->ht_size];
  for (; vec < end; vec++)
    {
      void *item = *vec;
      if (!HASH_VACANT (item))
	free (item);
      *vec = 0;
    }
  ht->ht_fill = 0;
  ht->ht_empty_slots = ht->ht_size;
}

#ifdef CONFIG_WITH_ALLOC_CACHES
void
hash_free_items_cached (struct hash_table *ht, struct alloccache *cache)
{
  void **vec = ht->ht_vec;
  void **end = &vec[ht->ht_size];
  for (; vec < end; vec++)
    {
      void *item = *vec;
      if (!HASH_VACANT (item))
	alloccache_free (cache, item);
      *vec = 0;
    }
  ht->ht_fill = 0;
  ht->ht_empty_slots = ht->ht_size;
}
#endif /* CONFIG_WITH_ALLOC_CACHES */

void
hash_delete_items (struct hash_table *ht)
{
  void **vec = ht->ht_vec;
  void **end = &vec[ht->ht_size];
  for (; vec < end; vec++)
    *vec = 0;
  ht->ht_fill = 0;
  ht->ht_collisions = 0;
  ht->ht_lookups = 0;
  ht->ht_rehashes = 0;
  ht->ht_empty_slots = ht->ht_size;
}

void
hash_free (struct hash_table *ht, int free_items)
{
  if (free_items)
    hash_free_items (ht);
  else
    {
      ht->ht_fill = 0;
      ht->ht_empty_slots = ht->ht_size;
    }
  free (ht->ht_vec);
  ht->ht_vec = 0;
  ht->ht_capacity = 0;
}

#ifdef CONFIG_WITH_ALLOC_CACHES
void
hash_free_cached (struct hash_table *ht, int free_items, struct alloccache *cache)
{
  if (free_items)
    hash_free_items_cached (ht, cache);
  else
    {
      ht->ht_fill = 0;
      ht->ht_empty_slots = ht->ht_size;
    }
  free (ht->ht_vec);
  ht->ht_vec = 0;
  ht->ht_capacity = 0;
}
#endif /* CONFIG_WITH_ALLOC_CACHES */

void
hash_map (struct hash_table *ht, hash_map_func_t map)
{
  void **slot;
  void **end = &ht->ht_vec[ht->ht_size];

  for (slot = ht->ht_vec; slot < end; slot++)
    {
      if (!HASH_VACANT (*slot))
	(*map) (*slot);
    }
}

void
hash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg)
{
  void **slot;
  void **end = &ht->ht_vec[ht->ht_size];

  for (slot = ht->ht_vec; slot < end; slot++)
    {
      if (!HASH_VACANT (*slot))
	(*map) (*slot, arg);
    }
}

/* Double the size of the hash table in the event of overflow... */

static void
hash_rehash (struct hash_table *ht)
{
  unsigned long old_ht_size = ht->ht_size;
  void **old_vec = ht->ht_vec;
  void **ovp;

  if (ht->ht_fill >= ht->ht_capacity)
    {
      ht->ht_size *= 2;
      ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
    }
  ht->ht_rehashes++;
  ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size);

#ifndef CONFIG_WITH_STRCACHE2
  for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
    {
      if (! HASH_VACANT (*ovp))
	{
	  void **slot = hash_find_slot (ht, *ovp);
	  *slot = *ovp;
	}
    }
#else  /* CONFIG_WITH_STRCACHE2 */
  if (ht->ht_strcache)
    for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
      {
        if (! HASH_VACANT (*ovp))
          {
            void **slot = hash_find_slot_strcached (ht, *ovp);
            *slot = *ovp;
          }
      }
  else
    for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
      {
        if (! HASH_VACANT (*ovp))
          {
            void **slot = hash_find_slot (ht, *ovp);
            *slot = *ovp;
          }
      }
#endif /* CONFIG_WITH_STRCACHE2 */
  ht->ht_empty_slots = ht->ht_size - ht->ht_fill;
  free (old_vec);
}

void
hash_print_stats (struct hash_table *ht, FILE *out_FILE)
{
  /* GKM FIXME: honor NO_FLOAT */
  fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,
	   100.0 * (double) ht->ht_fill / (double) ht->ht_size);
  fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);
  MAKE_STATS(
  fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,
	   (ht->ht_lookups
	    ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
	    : 0));
  );
}

/* Dump all items into a NULL-terminated vector.  Use the
   user-supplied vector, or malloc one.  */

void **
hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)
{
  void **vector;
  void **slot;
  void **end = &ht->ht_vec[ht->ht_size];

  if (vector_0 == 0)
    vector_0 = MALLOC (void *, ht->ht_fill + 1);
  vector = vector_0;

  for (slot = ht->ht_vec; slot < end; slot++)
    if (!HASH_VACANT (*slot))
      *vector++ = *slot;
  *vector = 0;

  if (compare)
    qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
  return vector_0;
}

/* Round a given number up to the nearest power of 2. */

static unsigned long
round_up_2 (unsigned long n)
{
  n |= (n >> 1);
  n |= (n >> 2);
  n |= (n >> 4);
  n |= (n >> 8);
  n |= (n >> 16);

#if !defined(HAVE_LIMITS_H) || ULONG_MAX > 4294967295
  /* We only need this on systems where unsigned long is >32 bits.  */
  n |= (n >> 32);
#endif

  return n + 1;
}