hash.c

wget讓你可以在console介面下

static void
grow_hash_table (struct hash_table *ht)
{
  hashfun_t hasher = ht->hash_function;
  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_MAX_FULLNESS;

  mappings = xnew_array (struct mapping, newsize);
  memset (mappings, INVALID_PTR_BYTE, newsize * sizeof (struct mapping));
  ht->mappings = mappings;

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

      MARK_AS_EMPTY (mp);
      --ht->count;

      /* Rehash all the entries following MP.  The alternative
	 approach is to mark the entry as deleted, i.e. create a
	 "tombstone".  That speeds up removal, 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;

	  /* Find the new location for the key. */
	  mp_new = mappings + HASH_POSITION (key2, hasher, size);
	  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;
	  MARK_AS_EMPTY (mp);

	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, INVALID_PTR_BYTE, 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.  */

/* Guidelines for creating custom hash and test functions:

   - The test function returns non-zero for keys that are considered
     "equal", zero otherwise.

   - The hash function returns a number that represents the
     "distinctness" of the object.  In more precise terms, it means
     that for any two objects that test "equal" under the test
     function, the hash function MUST produce the same result.

     This does not mean that all different objects must produce
     different values (that would be "perfect" hashing), only that
     non-distinct objects must produce the same values!  For instance,
     a hash function that returns 0 for any given object is a
     perfectly valid (albeit extremely bad) hash function.  A hash
     function that hashes a string by adding up all its characters is
     another example of a valid (but quite bad) hash function.

     It is not hard to make hash and test functions agree about
     equality.  For example, if the test function compares strings
     case-insensitively, the hash function can lower-case the
     characters when calculating the hash value.  That ensures that
     two strings differing only in case will hash the same.

   - If you care about performance, choose a hash function with as
     good "spreading" as possible.  A good hash function will use all
     the bits of the input when calculating the hash, and will react
     to even small changes in input with a completely different
     output.  Finally, don't make the hash function itself overly
     slow, because you'll be incurring a non-negligible overhead to
     all hash table operations.  */

/*
 * 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.  */

static unsigned long
hash_string (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. */

static int
cmp_string (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, hash_string, cmp_string);
}

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

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

static unsigned long
hash_string_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, hash_string_nocase, string_cmp_nocase);
}

/* Hashing of numeric values, such as pointers and integers.

   This implementation is the Robert Jenkins' 32 bit Mix Function,
   with a simple adaptation for 64-bit values.  It offers excellent
   spreading of values and doesn't need to know the hash table size to
   work (unlike the very popular Knuth's multiplication hash).  */

unsigned long
hash_pointer (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;
}

static int
cmp_pointer (const void *ptr1, const void *ptr2)
{
  return ptr1 == ptr2;
}

#ifdef TEST

#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 /* TEST */