⟦c1fe315bc⟧

TextFile

/* Copyright 1988 Stephan v. Bechtolsheim */

/* This file is part of the TeXPS Software Package.

The TeXPS Software Package is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY.  No author or distributor
accepts responsibility to anyone for the consequences of using it
or for whether it serves any particular purpose or works at all,
unless he says so in writing.  Refer to the TeXPS Software Package
General Public License for full details.

Everyone is granted permission to copy, modify and redistribute
the TeXPS Software Package, but only under the conditions described in the
TeXPS Software Package General Public License.   A copy of this license is
supposed to have been given to you along with TeXPS Software Package so you
can know your rights and responsibilities.  It should be in a
file named CopyrightLong.  Among other things, the copyright notice
and this notice must be preserved on all copies.  */

/* A collection of hash table functions. */

#include <stdio.h>

/* External declarations. */
extern char * Malloc();
extern char * StrcpyAlloc();

/* Definitions. */
#define TRUE 1
#define FALSE 0

/* Forward declarations. */
void HashTableError();
char * SetUpHashTable();
char * LookUpKeyInHashTable();

/* A hash table consists of a header, from which we hang off an
 * array of hash table elements. In case there is a collision,
 * we follow a linked list of hash table elements from the
 * element, where the collision occured.
 * This structure does not have to be known to
 * the user. After initialisation a hash table is identified by
 * a pointer to its header. A generic (char *) pointer is sufficient.
 *
 * There are two different types of hash tables:
 * (1) hh_size_els == 0: all elements have length zero. This means
 *     that looking up keys simply returns the info whether the key
 *     is in the table or not.
 * (2) hh_size_els != 0: the user has hh_size_els bytes for each element
 *     in his table. Everything goes throug pointers then.
 */
typedef struct hh {
  int hh_num_els_alloc; /* Length of the hash table array. */
  int hh_num_els; /* Number of elements already inserted into the hash
		     table. */
  int hh_size_els; /* Length of the user's element's size. The user in
		      other words can store information with each hash
		      table entry. This length can be zero, in which
		      case the hash table lookup function has a
		      function like "known/unknow". */
  char * hh_name; /* Name of the hash table. Is used for error messages. */
  struct hhe * hh_els; /* Pointer to the beginning of the array of hash
			  table elements. */
  /* The following three fields are for pointers to maintain a linked
     list of the elements insered into the table. The linked list links
     the elements in the order inserted. */
  struct hhe * hh_ll_first; /* We create a linked list of all elements of
			       the hash table. Points to the first element
			       inserted into the hash table. NULL if the
			       hash table is empty. Follow the links through
			       hhe_ll_first to find the other elements. */
  struct hhe * hh_ll_last; /* Pointer to last element inserted. */
  struct hhe * hh_ll_next; /* See GetNextKey() and InitNextKey(). This pointer
			      is only used while these functions are active! */
}
HH;

/* Hash table elements: an hash table consists of a fixed length array of
 * such elements. */
typedef struct hhe {
  char  *hhe_key; /* The hash key */
  struct hhe * hhe_next; /* Next element in case of a collision (same
			    hash index, different key). */
  char  *hhe_user; /* Pointer to user's data. */
  struct hhe * hhe_ll_next; /* Linked list of all elements in the
			       hash table. NULL indicates the end of the
			       linked list. Linked in the order of insertion.
			       See above for details. */
}
HHE;

/*
 * SetUpHashTable
 * **************
 * Call this routine to initiate a hash table.
 *
 * num_els: number of elements, the hash table is going to have.
 * size_els: size of the data stored with the hash table entries.
 *   can be 0, which means, that no data is stored with the key---it's
 *   simply yes/no type of stuff.
 * name: name of the hash table (for error messages).
 */
char *
SetUpHashTable (num_els, size_els, name)
     int num_els;
     int size_els;
     char * name;
{
  HH * hash_table;
  HHE * hash_elem;
  int i;

  hash_table = (HH *) Malloc (sizeof(HH));
  hash_table->hh_num_els_alloc = num_els;
  hash_table->hh_num_els = 0;
  hash_table->hh_size_els = size_els;
  hash_table->hh_name = StrcpyAlloc(name);
  hash_table->hh_ll_first = NULL;
  hash_table->hh_ll_last = NULL;
  hash_table->hh_ll_next = NULL;

#ifdef DEBUG
  fprintf (stderr, "%% HashTable \"%s\" set up\n", hash_table->hh_name);
  fprintf (stderr, "%% Number of elements: %d\n",
	   hash_table->hh_num_els_alloc);
#endif
  /* Allocate space for hash table array and initialize its elements. */
  hash_table->hh_els = (HHE *) Malloc (sizeof (HHE) * num_els);
  for (i=0; i<num_els; i++) {
    hash_elem = &(hash_table->hh_els[i]);
    hash_elem->hhe_key  = NULL;
    hash_elem->hhe_next = NULL;
    hash_elem->hhe_user = NULL;
    hash_elem->hhe_ll_next = NULL;
  }
  return ((char *) hash_table);
}

/*
 * hashfunc
 * *********
 * Given a key and the hash table, return the index to find the key
 * in the hash table. No check on whether the key is already
 * in the table or not. In other words, this here is the hashing function.
 *
 * ht:          hash table.
 * key:         the key.
 * RETURN:      index to be used to find the key in the table.
 */
int
hashfunc (ht, key)
     HH *ht;
     char *key;
{
  int ret;

#ifdef DEBUG
  char * key2;
  key2 = key;
#endif

  if (Strlen(key)==0)
    HashTableError (ht, "null key", NULL);

  /* Compute the hash key. */
  ret = 0;
  while (*key)
    ret += *key++;
  ret = ret % ht->hh_num_els_alloc;
#ifdef DEBUG
  fprintf (stderr, "%% hashfunc(): %s --> %d\n", key2, ret);
#endif

  return (ret);
}

/*
 * LookUpKeyInHashTable
 * ********************
 * Look up a key in a hash table. Does NOT generate a fatal error
 * if key cannot be found (see below for details).
 *
 * ht: hash table
 * key: the key
 * RET:
 *     if not found: NULL
 *     if found:
 *      (a) a pointer to the user's structure for this entry (hh_els != 0)
 *      (b) something !NULL, if there is no such structure (hh_els==0).
 */
char*
LookUpKeyInHashTable(ht, key)
     HH * ht;
     char * key;
{
  HHE * hash_elem;

  /* If the entry is in the hash table, you have to start looking here.
     You may have to follow a linked list (in case of collisions). */
  hash_elem = &(ht->hh_els[hashfunc (ht, key)]);

  /* Check whether key is in hash table */
  while (Strcmp(key, hash_elem->hhe_key) != 0) {
    if (hash_elem->hhe_next == NULL)
      return (NULL); /* No more hope: cannot find the key. */
    else
      /* Continue looking (linked list for collisions) */
      hash_elem = hash_elem->hhe_next;
  }

  /* Come here only, if key was found. */
  if (ht->hh_size_els == 0)
    return ((char *) TRUE);
  else
    return (hash_elem->hhe_user);
}

/*
 * LookUpKeyInHashTableE
 * *********************
 * Look up a key in a hash table. Generate a fatal error if key could not
 * be found. This is different from the preceding procedure which does
 * NOT generate a fatal error. Also note that the call to this procedure
 * is different from the preceding one.
 *
 * ht: hash table
 * key: the key
 * errorm: additional error message to be generated in case entry can
 *         not be found.
 * RETURN: a pointer to the user's information,
 *         and if there is no user info (hh_size_els == 0), then
 *         return TRUE as indication, that the entry is in the table.
 */
char *
LookUpKeyInHashTableE (ht, key, errorm)
     struct hh * ht;
     char * key;
     char * errorm;
{
  HHE * hash_elem;

  if ((hash_elem = (HHE *)LookUpKeyInHashTable (ht, key)) == NULL)
    Fatal4("LookUpKeyInHashTableE(): no key \"%s\" in hash-table \"%s\" [%s]",
	   key, ht->hh_name, errorm);

  /* Come here only if key was found. */
  return ((char *)hash_elem);
}

/*
 * InsertKeyIntoHashTable
 * **********************
 * Insert a key into a hash table. Fatal error, if the key is already
 * in the table; see InsertKeyIntoHashTableDup() for non-fatal treatment.
 *
 * hash_table: hash table
 * key: the key to be used
 * RET: pointer to user data structure to be filled by the user (if hh_size_els != 0).
 *      Some none-NULL value (if hh_size_els == 0).
 */
char*
InsertKeyIntoHashTable(hash_table, key)
     HH * hash_table;
     char * key;
{
  HHE *hash_elem;
  HHE *new_hash_el;

  if ((hash_elem = (HHE *) LookUpKeyInHashTable(hash_table, key)) != NULL)
    HashTableError (hash_table, "InsertKeyIntoHashTable(): Key already in table, key = ",
		    key);

  /* Come here only if the hash key is new. */
  hash_elem = &(hash_table->hh_els[hashfunc(hash_table, key)]);
  hash_table->hh_num_els++; /* +1 element inserted. */
  if (hash_elem->hhe_key == NULL) {
    /* First entry into hash table with this particular hash index. */
    hash_elem->hhe_key = StrcpyAlloc(key);
    hash_elem->hhe_next = NULL;
    hash_elem->hhe_user = NULL;
    hash_elem->hhe_ll_next = NULL;
    /* Maintaining linked list of hash keys now. */
    if (hash_table->hh_num_els == 1) {
      hash_table->hh_ll_first = hash_elem;
      hash_table->hh_ll_last  = hash_elem;
    } else {
      hash_table->hh_ll_last->hhe_ll_next = hash_elem;
      hash_table->hh_ll_last = hash_elem;
    }
    if (hash_table->hh_size_els == 0)
      return ((char *) TRUE);
    else
      return (hash_elem->hhe_user = Malloc(hash_table->hh_size_els));
  } else {
    /* Linked list business: there is already a key with the same index
     * in the table. So we have a collision! */
    new_hash_el = (HHE *) Malloc (sizeof(HHE)); /* Get a new hash table element. */
    new_hash_el->hhe_key = StrcpyAlloc(key);
    new_hash_el->hhe_next= hash_elem->hhe_next;
    new_hash_el->hhe_user = NULL;
    new_hash_el->hhe_ll_next = NULL;
    /* Now add the new hash element just allocated to the linked list of
       collision hash elements. */
    hash_elem->hhe_next = new_hash_el;
    /* Now add the new hash element to the linked list of all hash
       table entries. Note that when we come here we know that the new hash
       key is not the very first hash key of the hash table. */
    hash_table->hh_ll_last->hhe_ll_next = new_hash_el;
    hash_table->hh_ll_last = new_hash_el;
    /* Take care of user's data now. */
    if (hash_table->hh_size_els == 0) {
      new_hash_el->hhe_user = NULL;
      return ((char *) 1);
    } else {
      new_hash_el->hhe_user = Malloc(hash_table->hh_size_els);
      return (new_hash_el->hhe_user);
    }
  }
}

/*
 * InsertKeyIntoHashTableDup
 * *************************
 * Insert key in the hash table, but if it's already there,
 * don't complain and return NULL. If it's not there, return
 * a pointer to the new entry.
 *
 * hash_table: hash table
 * key: the key for which info is inserted.
 * RET: pointer to the hash data structure, NULL if you try to insert
 *      a duplicate.
 */
char *
InsertKeyIntoHashTableDup(hash_table, key)
     HH * hash_table;
     char * key;
{
  if (LookUpKeyInHashTable(hash_table, key) != NULL)
    return (NULL);
  return (InsertKeyIntoHashTable(hash_table, key));
}

/*
 * HashTableError
 * **************
 * This function is called to generate a fatal error occuring in
 * a hash table lookup operation.
 *
 * hash_table: hash table
 * s1, s2: two strings for error messages in the hash table, where
 *         s2 can be NULL.
 */
void
HashTableError(hash_table, s1, s2)
     HH * hash_table;
     char * s1, *s2;
{
  if (Strlen(s2) != 0)
    Fatal4 ("HashTableError(): in \"%s\"\n\t %s %s", hash_table->hh_name, s1, s2);
  else
    Fatal3 ("HashTableError(): in \"%s\"\n\t %s", hash_table->hh_name, s1);
}

/*
 * InitNextKeyHash
 * ***************
 * Call this function to initialize a linear traversal of the hash table.
 * Keys are returned in the order they were inserted, NOT in alphabetical
 * order.
 *
 * hash_table: pointer to the hash table
 */
void
InitNextKeyHash(hash_table)
     HH * hash_table;
{
  hash_table->hh_ll_next = hash_table->hh_ll_first;
}

/*
 * GetNextKeyHash
 * **************
 * For a linear traversal of the hash table call this function
 * to get the next key (after you called InitKeyHash). The function
 * will return a pointer to the key and NOT to the user's structure
 * to store data! Returns NULL after you read the last key.
 *
 * hash_table: hash table
 * RET: next key, NULL if you reached the end.
 */
char *
GetNextKeyHash(hash_table)
     HH * hash_table;
{
  char * ret;
  if (hash_table->hh_ll_next == NULL)
    return (NULL);
  ret = hash_table->hh_ll_next->hhe_key;
  hash_table->hh_ll_next = hash_table->hh_ll_next->hhe_ll_next;
  return (ret);
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦c1fe315bc⟧ TextFile

Derivation

TextFile
