hash.c

wget (command line browser) source code

/* Grow hash table HT as necessary, and rehash all the key-value
   mappings.  */

static void
grow_hash_table (struct hash_table *ht)
{
  struct mapping *old_mappings = ht->mappings;
  struct mapping *old_end      = ht->mappings + ht->size;
  struct mapping *mp, *mappings;
  int newsize;

  newsize = prime_size (ht->size * HASH_RESIZE_FACTOR, &ht->prime_offset);
#if 0
  printf ("growing from %d to %d; fullness %.2f%% to %.2f%%\n",
	  ht->size, newsize,
	  100.0 * ht->count / ht->size,
	  100.0 * ht->count / newsize);
#endif

  ht->size = newsize;
  ht->resize_threshold = newsize * HASH_FULLNESS_THRESHOLD;

  mappings = xmalloc (ht->size * sizeof (struct mapping));
  memset (mappings, '\0', ht->size * sizeof (struct mapping));
  ht->mappings = mappings;

  for (mp = old_mappings; mp < old_end; mp++)
    if (NON_EMPTY (mp))
      {
	struct mapping *new_mp = mappings + HASH_POSITION (ht, mp->key);
	/* We don't need to test for uniqueness of keys because all
	   the keys come from the hash table and are therefore known
	   to be unique.  */
	LOOP_NON_EMPTY (new_mp, mappings, newsize)
	  ;
	*new_mp = *mp;
      }

  xfree (old_mappings);
}

/* Put VALUE in the hash table HT under the key KEY.  This regrows the
   table if necessary.  */

void
hash_table_put (struct hash_table *ht, const void *key, void *value)
{
  struct mapping *mp = find_mapping (ht, key);
  if (NON_EMPTY (mp))
    {
      /* update existing item */
      mp->key   = (void *)key; /* const? */
      mp->value = value;
      return;
    }

  /* If adding the item would make the table exceed max. fullness,
     grow the table first.  */
  if (ht->count >= ht->resize_threshold)
    {
      grow_hash_table (ht);
      mp = find_mapping (ht, key);
    }

  /* add new item */
  ++ht->count;
  mp->key   = (void *)key;	/* const? */
  mp->value = value;
}

/* Remove a mapping that matches KEY from HT.  Return 0 if there was
   no such entry; return 1 if an entry was removed.  */

int
hash_table_remove (struct hash_table *ht, const void *key)
{
  struct mapping *mp = find_mapping (ht, key);
  if (!NON_EMPTY (mp))
    return 0;
  else
    {
      int size = ht->size;
      struct mapping *mappings = ht->mappings;

      mp->key = NULL;
      --ht->count;

      /* Rehash all the entries following MP.  The alternative
	 approach is to mark the entry as deleted, i.e. create a
	 "tombstone".  That makes remove faster, but leaves a lot of
	 garbage and slows down hash_table_get and hash_table_put.  */

      mp = NEXT_MAPPING (mp, mappings, size);
      LOOP_NON_EMPTY (mp, mappings, size)
	{
	  const void *key2 = mp->key;
	  struct mapping *mp_new = mappings + HASH_POSITION (ht, key2);

	  /* Find the new location for the key. */

	  LOOP_NON_EMPTY (mp_new, mappings, size)
	    if (key2 == mp_new->key)
	      /* The mapping MP (key2) is already where we want it (in
		 MP_NEW's "chain" of keys.)  */
	      goto next_rehash;

	  *mp_new = *mp;
	  mp->key = NULL;

	next_rehash:
	  ;
	}
      return 1;
    }
}

/* Clear HT of all entries.  After calling this function, the count
   and the fullness of the hash table will be zero.  The size will
   remain unchanged.  */

void
hash_table_clear (struct hash_table *ht)
{
  memset (ht->mappings, '\0', ht->size * sizeof (struct mapping));
  ht->count = 0;
}

/* Map MAPFUN over all the mappings in hash table HT.  MAPFUN is
   called with three arguments: the key, the value, and MAPARG.

   It is undefined what happens if you add or remove entries in the
   hash table while hash_table_map is running.  The exception is the
   entry you're currently mapping over; you may remove or change that
   entry.  */

void
hash_table_map (struct hash_table *ht,
		int (*mapfun) (void *, void *, void *),
		void *maparg)
{
  struct mapping *mp  = ht->mappings;
  struct mapping *end = ht->mappings + ht->size;

  for (; mp < end; mp++)
    if (NON_EMPTY (mp))
      {
	void *key;
      repeat:
	key = mp->key;
	if (mapfun (key, mp->value, maparg))
	  return;
	/* hash_table_remove might have moved the adjacent
	   mappings. */
	if (mp->key != key && NON_EMPTY (mp))
	  goto repeat;
      }
}

/* Return the number of elements in the hash table.  This is not the
   same as the physical size of the hash table, which is always
   greater than the number of elements.  */

int
hash_table_count (const struct hash_table *ht)
{
  return ht->count;
}

/* Functions from this point onward are meant for convenience and
   don't strictly belong to this file.  However, this is as good a
   place for them as any.  */

/*
 * Support for hash tables whose keys are strings.
 *
 */
   
/* 31 bit hash function.  Taken from Gnome's glib, modified to use
   standard C types.

   We used to use the popular hash function from the Dragon Book, but
   this one seems to perform much better.  */

unsigned long
string_hash (const void *key)
{
  const char *p = key;
  unsigned int h = *p;
  
  if (h)
    for (p += 1; *p != '\0'; p++)
      h = (h << 5) - h + *p;
  
  return h;
}

/* Frontend for strcmp usable for hash tables. */

int
string_cmp (const void *s1, const void *s2)
{
  return !strcmp ((const char *)s1, (const char *)s2);
}

/* Return a hash table of preallocated to store at least ITEMS items
   suitable to use strings as keys.  */

struct hash_table *
make_string_hash_table (int items)
{
  return hash_table_new (items, string_hash, string_cmp);
}

/*
 * Support for hash tables whose keys are strings, but which are
 * compared case-insensitively.
 *
 */

/* Like string_hash, but produce the same hash regardless of the case. */

static unsigned long
string_hash_nocase (const void *key)
{
  const char *p = key;
  unsigned int h = TOLOWER (*p);
  
  if (h)
    for (p += 1; *p != '\0'; p++)
      h = (h << 5) - h + TOLOWER (*p);
  
  return h;
}

/* Like string_cmp, but doing case-insensitive compareison. */

static int
string_cmp_nocase (const void *s1, const void *s2)
{
  return !strcasecmp ((const char *)s1, (const char *)s2);
}

/* Like make_string_hash_table, but uses string_hash_nocase and
   string_cmp_nocase.  */

struct hash_table *
make_nocase_string_hash_table (int items)
{
  return hash_table_new (items, string_hash_nocase, string_cmp_nocase);
}

/* Hashing of pointers.  Used for hash tables that are keyed by
   pointer identity.  (Common Lisp calls them EQ hash tables, and Java
   calls them IdentityHashMaps.)  */

unsigned long
ptrhash (const void *ptr)
{
  unsigned long key = (unsigned long)ptr;
  key += (key << 12);
  key ^= (key >> 22);
  key += (key << 4);
  key ^= (key >> 9);
  key += (key << 10);
  key ^= (key >> 2);
  key += (key << 7);
  key ^= (key >> 12);
#if SIZEOF_LONG > 4
  key += (key << 44);
  key ^= (key >> 54);
  key += (key << 36);
  key ^= (key >> 41);
  key += (key << 42);
  key ^= (key >> 34);
  key += (key << 39);
  key ^= (key >> 44);
#endif
  return key;
}

int
ptrcmp (const void *ptr1, const void *ptr2)
{
  return ptr1 == ptr2;
}

#if 0
/* Currently unused: hashing of integers. */

unsigned long
inthash (unsigned int key)
{
  key += (key << 12);
  key ^= (key >> 22);
  key += (key << 4);
  key ^= (key >> 9);
  key += (key << 10);
  key ^= (key >> 2);
  key += (key << 7);
  key ^= (key >> 12);
  return key;
}
#endif

#ifdef STANDALONE

#include <stdio.h>
#include <string.h>

int
print_hash_table_mapper (void *key, void *value, void *count)
{
  ++*(int *)count;
  printf ("%s: %s\n", (const char *)key, (char *)value);
  return 0;
}

void
print_hash (struct hash_table *sht)
{
  int debug_count = 0;
  hash_table_map (sht, print_hash_table_mapper, &debug_count);
  assert (debug_count == sht->count);
}

int
main (void)
{
  struct hash_table *ht = make_string_hash_table (0);
  char line[80];
  while ((fgets (line, sizeof (line), stdin)))
    {
      int len = strlen (line);
      if (len <= 1)
	continue;
      line[--len] = '\0';
      if (!hash_table_contains (ht, line))
	hash_table_put (ht, strdup (line), "here I am!");
#if 1
      if (len % 5 == 0)
	{
	  char *line_copy;
	  if (hash_table_get_pair (ht, line, &line_copy, NULL))
	    {
	      hash_table_remove (ht, line);
	      xfree (line_copy);
	    }
	}
#endif
    }
#if 0
  print_hash (ht);
#endif
#if 1
  printf ("%d %d\n", ht->count, ht->size);
#endif
  return 0;
}
#endif