hash_table.c

PSlib是一个用来生成PostScript文件的类库。提供了一个生成PostScript文件的简单方法。

/* Get the size of the hash table */
unsigned int ght_table_size(ght_hash_table_t *p_ht)
{
  return p_ht->i_size;
}

/* Insert an entry into the hash table */
int ght_insert(ght_hash_table_t *p_ht,
	       void *p_entry_data,
	       unsigned int i_key_size, void *p_key_data)
{
  ght_hash_entry_t *p_entry;
  ght_uint32_t l_key;
  ght_hash_key_t key;

  assert(p_ht);

  hk_fill(&key, i_key_size, p_key_data);
  l_key = p_ht->fn_hash(&key)&p_ht->i_size_mask;
  if (search_in_bucket(p_ht, l_key, &key, 0))
    {
      /* Don't insert if the key is already present. */
      return -1;
    }
  if (!(p_entry = he_create(p_ht, p_entry_data,
			    i_key_size, p_key_data)))
    {
      return -2;
    }

  /* Rehash if the number of items inserted is too high. */
  if (p_ht->i_automatic_rehash && p_ht->i_items > 2*p_ht->i_size)
    {
      ght_rehash(p_ht, 2*p_ht->i_size);
    }

  /* Place the entry first in the list. */
  p_entry->p_next = p_ht->pp_entries[l_key];
  p_entry->p_prev = NULL;
  if (p_ht->pp_entries[l_key])
    {
      p_ht->pp_entries[l_key]->p_prev = p_entry;
    }
  p_ht->pp_entries[l_key] = p_entry;
  p_ht->p_nr[l_key]++;

  assert( p_ht->pp_entries[l_key]?p_ht->pp_entries[l_key]->p_prev == NULL:1 );

  p_ht->i_items++;

  return 0;
}

/* Get an entry from the hash table. The entry is returned, or NULL if it wasn't found */
void *ght_get(ght_hash_table_t *p_ht,
	      unsigned int i_key_size, void *p_key_data)
{
  ght_hash_entry_t *p_e;
  ght_hash_key_t key;
  ght_uint32_t l_key;

  assert(p_ht);

  hk_fill(&key, i_key_size, p_key_data);

  l_key = p_ht->fn_hash(&key)&p_ht->i_size_mask;

  /* Check that the first element in the list really is the first. */
  assert( p_ht->pp_entries[l_key]?p_ht->pp_entries[l_key]->p_prev == NULL:1 );

  p_e = search_in_bucket(p_ht, l_key, &key, p_ht->i_heuristics);
  return (p_e?p_e->p_data:NULL);
}

/* Replace an entry from the hash table. The entry is returned, or NULL if it wasn't found */
void *ght_replace(ght_hash_table_t *p_ht,
		  void *p_entry_data,
		  unsigned int i_key_size, void *p_key_data)
{
  ght_hash_entry_t *p_e;
  ght_hash_key_t key;
  ght_uint32_t l_key;
  void *p_old;

  assert(p_ht);

  hk_fill(&key, i_key_size, p_key_data);

  l_key = p_ht->fn_hash(&key)&p_ht->i_size_mask;

  /* Check that the first element in the list really is the first. */
  assert( p_ht->pp_entries[l_key]?p_ht->pp_entries[l_key]->p_prev == NULL:1 );

  p_e = search_in_bucket(p_ht, l_key, &key, p_ht->i_heuristics);

  if ( !p_e )
    return NULL;

  p_old = p_e->p_data;
  p_e->p_data = p_entry_data;

  return p_old;
}

/* Remove an entry from the hash table. The removed entry, or NULL, is
   returned (and NOT free'd). */
void *ght_remove(ght_hash_table_t *p_ht,
		 unsigned int i_key_size, void *p_key_data)
{
  ght_hash_entry_t *p_out;
  ght_hash_key_t key;
  ght_uint32_t l_key;
  void *p_ret=NULL;

  assert(p_ht);

  hk_fill(&key, i_key_size, p_key_data);
  l_key = p_ht->fn_hash(&key)&p_ht->i_size_mask;

  /* Check that the first element really is the first */
  assert( (p_ht->pp_entries[l_key]?p_ht->pp_entries[l_key]->p_prev == NULL:1) );

  p_out = search_in_bucket(p_ht, l_key, &key, 0);

  /* Link p_out out of the list. */
  if (p_out)
    {
      if (p_out->p_prev)
	{
	  p_out->p_prev->p_next = p_out->p_next;
	}
      else /* first in list */
	{
	  p_ht->pp_entries[l_key] = p_out->p_next;
	}
      if (p_out->p_next)
	{
	  p_out->p_next->p_prev = p_out->p_prev;
	}

      /* This should ONLY be done for normal items (for now all items) */
      p_ht->i_items--;

      p_ht->p_nr[l_key]--;
#if !defined(NDEBUG)
      p_out->p_next = NULL;
      p_out->p_prev = NULL;
#endif /* NDEBUG */

      p_ret = p_out->p_data;
      he_finalize(p_ht, p_out);
    }

  return p_ret;
}

/* Get the first entry in an iteration */
void *ght_first(ght_hash_table_t *p_ht, ght_iterator_t *p_iterator, void **pp_key)
{
  assert(p_ht && p_iterator);

  /* Fill the iterator */
  p_iterator->p_entry = p_ht->pp_entries[0];
  p_iterator->i_curr_bucket = 0;

  /* Step until non-empty bucket */
  for (; (p_iterator->i_curr_bucket < p_ht->i_size) && !p_ht->pp_entries[p_iterator->i_curr_bucket];
       p_iterator->i_curr_bucket++);
  if (p_iterator->i_curr_bucket < p_ht->i_size)
    {
      p_iterator->p_entry = p_ht->pp_entries[p_iterator->i_curr_bucket];
    }

  if (p_iterator->p_entry)
    {
      p_iterator->p_next = p_iterator->p_entry->p_next;
      *pp_key = p_iterator->p_entry->key.p_key;

      return p_iterator->p_entry->p_data;
    }

  p_iterator->p_next = NULL;
  *pp_key = NULL;

  return NULL;
}

/* Get the next entry in an iteration. You have to call ght_first
   once initially before you use this function */
void *ght_next(ght_hash_table_t *p_ht, ght_iterator_t *p_iterator, void **pp_key)
{
  assert(p_ht && p_iterator);

  if (p_iterator->p_next)
    {
      /* More entries in the current bucket */
      p_iterator->p_entry = p_iterator->p_next;
      p_iterator->p_next = p_iterator->p_next->p_next;

      *pp_key = p_iterator->p_entry->key.p_key;
      return p_iterator->p_entry->p_data; /* We know that this is non-NULL */
    }
  else
    {
      p_iterator->p_entry = NULL;
      p_iterator->i_curr_bucket++;
    }

  /* Step until non-empty bucket */
  for (; (p_iterator->i_curr_bucket < p_ht->i_size) && !p_ht->pp_entries[p_iterator->i_curr_bucket];
       p_iterator->i_curr_bucket++);

  /* FIXME: Add someplace here:
   *  if (p_iterator->p_entry->i_flags & FLAGS_INTERNAL)
   *     return ght_next(p_ht, p_iterator);
   */
  if (p_iterator->i_curr_bucket < p_ht->i_size)
    {
      p_iterator->p_entry = p_ht->pp_entries[p_iterator->i_curr_bucket];

      if (p_iterator->p_entry)
	{
	  p_iterator->p_next = p_iterator->p_entry->p_next;
	}

      *pp_key = p_iterator->p_entry->key.p_key;
      return p_iterator->p_entry->p_data;
    }
  else
    {
      /* Last entry */
      p_iterator->i_curr_bucket = 0;
      p_iterator->p_entry = NULL;
      p_iterator->p_next = NULL;

      *pp_key = NULL;
      return NULL;
    }
}

/* Finalize (free) a hash table */
void ght_finalize(ght_hash_table_t *p_ht)
{
  int i;

  assert(p_ht);

  if (p_ht->pp_entries)
    {
      /* For each bucket, free all entries */
      for (i=0; i<p_ht->i_size; i++)
	{
	  free_entry_chain(p_ht, p_ht->pp_entries[i]);
	  p_ht->pp_entries[i] = NULL;
	}
      free (p_ht->pp_entries);
      p_ht->pp_entries = NULL;
    }
  if (p_ht->p_nr)
    {
      free (p_ht->p_nr);
      p_ht->p_nr = NULL;
    }

  free (p_ht);
}

/* Rehash the hash table (i.e. change its size and reinsert all
 * items). This operation is slow and should not be used frequently.
 */
void ght_rehash(ght_hash_table_t *p_ht, unsigned int i_size)
{
  ght_hash_table_t *p_tmp;
  ght_iterator_t iterator;
  void *p_key;
  void *p;
  int i;

  assert(p_ht);

  /* Recreate the hash table with the new size */
  p_tmp = ght_create(i_size);
  assert(p_tmp);

  /* Set the flags for the new hash table */
  ght_set_hash(p_tmp, p_ht->fn_hash);
  ght_set_heuristics(p_tmp, 0);
  ght_set_rehash(p_tmp, FALSE);

  /* Walk through all elements in the table and insert them into the temporary one. */
  for (p = ght_first(p_ht, &iterator, &p_key); p; p = ght_next(p_ht, &iterator, &p_key))
    {
      assert(iterator.p_entry);

      /* Insert the entry into the new table */
      if (ght_insert(p_tmp,
		     iterator.p_entry->p_data,
		     iterator.p_entry->key.i_size, iterator.p_entry->key.p_key) < 0)
	{
	  fprintf(stderr, "hash_table.c ERROR: Out of memory error or entry already in hash table\n"
		  "when rehashing (internal error)\n");
	}
    }

  /* Remove the old table... */
  for (i=0; i<p_ht->i_size; i++)
    {
      if (p_ht->pp_entries[i])
	{
	  /* Delete the entries in the bucket */
	  free_entry_chain (p_ht, p_ht->pp_entries[i]);
	  p_ht->pp_entries[i] = NULL;
	}
    }

  free (p_ht->pp_entries);
  free (p_ht->p_nr);

  /* ... and replace it with the new */
  p_ht->i_size = p_tmp->i_size;
  p_ht->i_size_mask = p_tmp->i_size_mask;
  p_ht->i_items = p_tmp->i_items;
  p_ht->pp_entries = p_tmp->pp_entries;
  p_ht->p_nr = p_tmp->p_nr;

  /* Clean up */
  p_tmp->pp_entries = NULL;
  p_tmp->p_nr = NULL;
  free (p_tmp);
}