path: root/dbus/dbus-hash.c

/* -*- mode: C; c-file-style: "gnu" -*- */
/* dbus-hash.c  Generic hash table utility (internal to D-BUS implementation)
 * 
 * Copyright (C) 2002  Red Hat, Inc.
 * Copyright (c) 1991-1993 The Regents of the University of California.
 * Copyright (c) 1994 Sun Microsystems, Inc.
 * 
 * Hash table implementation based on generic/tclHash.c from the Tcl
 * source code. The original Tcl license applies to portions of the
 * code from tclHash.c; the Tcl license follows this standad D-BUS
 * license information.
 *
 * Licensed under the Academic Free License version 1.2
 * 
 * This program 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 2 of the License, or
 * (at your option) any later version.
 *
 * This program 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, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */
/* 
 * The following copyright applies to code from the Tcl distribution.
 *
 * Copyright (c) 1991-1993 The Regents of the University of California.
 * Copyright (c) 1994 Sun Microsystems, Inc.
 *
 * This software is copyrighted by the Regents of the University of
 * California, Sun Microsystems, Inc., Scriptics Corporation, and
 * other parties.  The following terms apply to all files associated
 * with the software unless explicitly disclaimed in individual files.
 * 
 * The authors hereby grant permission to use, copy, modify,
 * distribute, and license this software and its documentation for any
 * purpose, provided that existing copyright notices are retained in
 * all copies and that this notice is included verbatim in any
 * distributions. No written agreement, license, or royalty fee is
 * required for any of the authorized uses.  Modifications to this
 * software may be copyrighted by their authors and need not follow
 * the licensing terms described here, provided that the new terms are
 * clearly indicated on the first page of each file where they apply.
 * 
 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
 * NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 * 
 * GOVERNMENT USE: If you are acquiring this software on behalf of the
 * U.S. government, the Government shall have only "Restricted Rights"
 * in the software and related documentation as defined in the Federal
 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
 * are acquiring the software on behalf of the Department of Defense,
 * the software shall be classified as "Commercial Computer Software"
 * and the Government shall have only "Restricted Rights" as defined
 * in Clause 252.227-7013 (c) (1) of DFARs.  Notwithstanding the
 * foregoing, the authors grant the U.S. Government and others acting
 * in its behalf permission to use and distribute the software in
 * accordance with the terms specified in this license.
 */

#include "dbus-memory.h"

typedef struct DBusHashEntry DBusHashEntry;


#if 0

/*
 * Forward declaration of Tcl_HashTable.  Needed by some C++ compilers
 * to prevent errors when the forward reference to Tcl_HashTable is
 * encountered in the Tcl_HashEntry structure.
 */

#ifdef __cplusplus
struct Tcl_HashTable;
#endif

/*
 * Structure definition for an entry in a hash table.  No-one outside
 * Tcl should access any of these fields directly;  use the macros
 * defined below.
 */

typedef struct Tcl_HashEntry {
    struct Tcl_HashEntry *nextPtr;	/* Pointer to next entry in this
					 * hash bucket, or NULL for end of
					 * chain. */
    struct Tcl_HashTable *tablePtr;	/* Pointer to table containing entry. */
    struct Tcl_HashEntry **bucketPtr;	/* Pointer to bucket that points to
					 * first entry in this entry's chain:
					 * used for deleting the entry. */
    ClientData clientData;		/* Application stores something here
					 * with Tcl_SetHashValue. */
    union {				/* Key has one of these forms: */
	char *oneWordValue;		/* One-word value for key. */
	int words[1];			/* Multiple integer words for key.
					 * The actual size will be as large
					 * as necessary for this table's
					 * keys. */
	char string[4];			/* String for key.  The actual size
					 * will be as large as needed to hold
					 * the key. */
    } key;				/* MUST BE LAST FIELD IN RECORD!! */
} Tcl_HashEntry;

/*
 * Structure definition for a hash table.  Must be in tcl.h so clients
 * can allocate space for these structures, but clients should never
 * access any fields in this structure.
 */

#define TCL_SMALL_HASH_TABLE 4
typedef struct Tcl_HashTable {
    Tcl_HashEntry **buckets;		/* Pointer to bucket array.  Each
					 * element points to first entry in
					 * bucket's hash chain, or NULL. */
    Tcl_HashEntry *staticBuckets[TCL_SMALL_HASH_TABLE];
					/* Bucket array used for small tables
					 * (to avoid mallocs and frees). */
    int numBuckets;			/* Total number of buckets allocated
					 * at **bucketPtr. */
    int numEntries;			/* Total number of entries present
					 * in table. */
    int rebuildSize;			/* Enlarge table when numEntries gets
					 * to be this large. */
    int downShift;			/* Shift count used in hashing
					 * function.  Designed to use high-
					 * order bits of randomized keys. */
    int mask;				/* Mask value used in hashing
					 * function. */
    int keyType;			/* Type of keys used in this table. 
					 * It's either TCL_STRING_KEYS,
					 * TCL_ONE_WORD_KEYS, or an integer
					 * giving the number of ints that
                                         * is the size of the key.
					 */
    Tcl_HashEntry *(*findProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
	    CONST char *key));
    Tcl_HashEntry *(*createProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
	    CONST char *key, int *newPtr));
} Tcl_HashTable;

/*
 * Structure definition for information used to keep track of searches
 * through hash tables:
 */

typedef struct Tcl_HashSearch {
    Tcl_HashTable *tablePtr;		/* Table being searched. */
    int nextIndex;			/* Index of next bucket to be
					 * enumerated after present one. */
    Tcl_HashEntry *nextEntryPtr;	/* Next entry to be enumerated in the
					 * the current bucket. */
} Tcl_HashSearch;


/*
 * When there are this many entries per bucket, on average, rebuild
 * the hash table to make it larger.
 */

#define REBUILD_MULTIPLIER	3


/*
 * The following macro takes a preliminary integer hash value and
 * produces an index into a hash tables bucket list.  The idea is
 * to make it so that preliminary values that are arbitrarily similar
 * will end up in different buckets.  The hash function was taken
 * from a random-number generator.
 */

#define RANDOM_INDEX(tablePtr, i) \
    (((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask)

/*
 * Procedure prototypes for static procedures in this file:
 */

static Tcl_HashEntry *	ArrayFind (Tcl_HashTable *tablePtr,
                                   CONST char *key);
static Tcl_HashEntry *	ArrayCreate (Tcl_HashTable *tablePtr,
                                     CONST char *key, int *newPtr);
static Tcl_HashEntry *	BogusFind (Tcl_HashTable *tablePtr,
                                   CONST char *key);
static Tcl_HashEntry *	BogusCreate (Tcl_HashTable *tablePtr,
                                     CONST char *key, int *newPtr);
static unsigned int	HashString (CONST char *string);
static void		RebuildTable (Tcl_HashTable *tablePtr);
static Tcl_HashEntry *	StringFind (Tcl_HashTable *tablePtr,
                                    CONST char *key);
static Tcl_HashEntry *	StringCreate (Tcl_HashTable *tablePtr,
                                      CONST char *key, int *newPtr);
static Tcl_HashEntry *	OneWordFind (Tcl_HashTable *tablePtr,
                                     CONST char *key);
static Tcl_HashEntry *	OneWordCreate (Tcl_HashTable *tablePtr,
                                       CONST char *key, int *newPtr);

/*
 *----------------------------------------------------------------------
 *
 * Tcl_InitHashTable --
 *
 *	Given storage for a hash table, set up the fields to prepare
 *	the hash table for use.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	TablePtr is now ready to be passed to Tcl_FindHashEntry and
 *	Tcl_CreateHashEntry.
 *
 *----------------------------------------------------------------------
 */

void
Tcl_InitHashTable(tablePtr, keyType)
     register Tcl_HashTable *tablePtr;	/* Pointer to table record, which
					 * is supplied by the caller. */
     int keyType;			/* Type of keys to use in table:
					 * TCL_STRING_KEYS, TCL_ONE_WORD_KEYS,
					 * or an integer >= 2. */
{
#if (TCL_SMALL_HASH_TABLE != 4) 
  panic("Tcl_InitHashTable: TCL_SMALL_HASH_TABLE is %d, not 4\n",
        TCL_SMALL_HASH_TABLE);
#endif
    
  tablePtr->buckets = tablePtr->staticBuckets;
  tablePtr->staticBuckets[0] = tablePtr->staticBuckets[1] = 0;
  tablePtr->staticBuckets[2] = tablePtr->staticBuckets[3] = 0;
  tablePtr->numBuckets = TCL_SMALL_HASH_TABLE;
  tablePtr->numEntries = 0;
  tablePtr->rebuildSize = TCL_SMALL_HASH_TABLE*REBUILD_MULTIPLIER;
  tablePtr->downShift = 28;
  tablePtr->mask = 3;
  tablePtr->keyType = keyType;
  if (keyType == TCL_STRING_KEYS) {
    tablePtr->findProc = StringFind;
    tablePtr->createProc = StringCreate;
  } else if (keyType == TCL_ONE_WORD_KEYS) {
    tablePtr->findProc = OneWordFind;
    tablePtr->createProc = OneWordCreate;
  } else {
    tablePtr->findProc = ArrayFind;
    tablePtr->createProc = ArrayCreate;
  };
}

/*
 *----------------------------------------------------------------------
 *
 * Tcl_DeleteHashEntry --
 *
 *	Remove a single entry from a hash table.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The entry given by entryPtr is deleted from its table and
 *	should never again be used by the caller.  It is up to the
 *	caller to free the clientData field of the entry, if that
 *	is relevant.
 *
 *----------------------------------------------------------------------
 */

void
Tcl_DeleteHashEntry(entryPtr)
     Tcl_HashEntry *entryPtr;
{
  register Tcl_HashEntry *prevPtr;

  if (*entryPtr->bucketPtr == entryPtr) {
    *entryPtr->bucketPtr = entryPtr->nextPtr;
  } else {
    for (prevPtr = *entryPtr->bucketPtr; ; prevPtr = prevPtr->nextPtr) {
      if (prevPtr == NULL) {
        panic("malformed bucket chain in Tcl_DeleteHashEntry");
      }
      if (prevPtr->nextPtr == entryPtr) {
        prevPtr->nextPtr = entryPtr->nextPtr;
        break;
      }
    }
  }
  entryPtr->tablePtr->numEntries--;
  ckfree((char *) entryPtr);
}

/*
 *----------------------------------------------------------------------
 *
 * Tcl_DeleteHashTable --
 *
 *	Free up everything associated with a hash table except for
 *	the record for the table itself.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The hash table is no longer useable.
 *
 *----------------------------------------------------------------------
 */

void
Tcl_DeleteHashTable(tablePtr)
     register Tcl_HashTable *tablePtr;		/* Table to delete. */
{
  register Tcl_HashEntry *hPtr, *nextPtr;
  int i;

  /*
   * Free up all the entries in the table.
   */

  for (i = 0; i < tablePtr->numBuckets; i++) {
    hPtr = tablePtr->buckets[i];
    while (hPtr != NULL) {
      nextPtr = hPtr->nextPtr;
      ckfree((char *) hPtr);
      hPtr = nextPtr;
    }
  }

  /*
   * Free up the bucket array, if it was dynamically allocated.
   */

  if (tablePtr->buckets != tablePtr->staticBuckets) {
    ckfree((char *) tablePtr->buckets);
  }

  /*
   * Arrange for panics if the table is used again without
   * re-initialization.
   */

  tablePtr->findProc = BogusFind;
  tablePtr->createProc = BogusCreate;
}

/*
 *----------------------------------------------------------------------
 *
 * Tcl_FirstHashEntry --
 *
 *	Locate the first entry in a hash table and set up a record
 *	that can be used to step through all the remaining entries
 *	of the table.
 *
 * Results:
 *	The return value is a pointer to the first entry in tablePtr,
 *	or NULL if tablePtr has no entries in it.  The memory at
 *	*searchPtr is initialized so that subsequent calls to
 *	Tcl_NextHashEntry will return all of the entries in the table,
 *	one at a time.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

Tcl_HashEntry *
Tcl_FirstHashEntry(tablePtr, searchPtr)
     Tcl_HashTable *tablePtr;		/* Table to search. */
     Tcl_HashSearch *searchPtr;		/* Place to store information about
					 * progress through the table. */
{
  searchPtr->tablePtr = tablePtr;
  searchPtr->nextIndex = 0;
  searchPtr->nextEntryPtr = NULL;
  return Tcl_NextHashEntry(searchPtr);
}

/*
 *----------------------------------------------------------------------
 *
 * Tcl_NextHashEntry --
 *
 *	Once a hash table enumeration has been initiated by calling
 *	Tcl_FirstHashEntry, this procedure may be called to return
 *	successive elements of the table.
 *
 * Results:
 *	The return value is the next entry in the hash table being
 *	enumerated, or NULL if the end of the table is reached.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

Tcl_HashEntry *
Tcl_NextHashEntry(searchPtr)
     register Tcl_HashSearch *searchPtr;	/* Place to store information about
                                                 * progress through the table.  Must
                                                 * have been initialized by calling
                                                 * Tcl_FirstHashEntry. */
{
  Tcl_HashEntry *hPtr;

  while (searchPtr->nextEntryPtr == NULL) {
    if (searchPtr->nextIndex >= searchPtr->tablePtr->numBuckets) {
      return NULL;
    }
    searchPtr->nextEntryPtr =
      searchPtr->tablePtr->buckets[searchPtr->nextIndex];
    searchPtr->nextIndex++;
  }
  hPtr = searchPtr->nextEntryPtr;
  searchPtr->nextEntryPtr = hPtr->nextPtr;
  return hPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Tcl_HashStats --
 *
 *	Return statistics describing the layout of the hash table
 *	in its hash buckets.
 *
 * Results:
 *	The return value is a malloc-ed string containing information
 *	about tablePtr.  It is the caller's responsibility to free
 *	this string.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

char *
Tcl_HashStats(tablePtr)
     Tcl_HashTable *tablePtr;		/* Table for which to produce stats. */
{
#define NUM_COUNTERS 10
  int count[NUM_COUNTERS], overflow, i, j;
  double average, tmp;
  register Tcl_HashEntry *hPtr;
  char *result, *p;

  /*
   * Compute a histogram of bucket usage.
   */

  for (i = 0; i < NUM_COUNTERS; i++) {
    count[i] = 0;
  }
  overflow = 0;
  average = 0.0;
  for (i = 0; i < tablePtr->numBuckets; i++) {
    j = 0;
    for (hPtr = tablePtr->buckets[i]; hPtr != NULL; hPtr = hPtr->nextPtr) {
      j++;
    }
    if (j < NUM_COUNTERS) {
      count[j]++;
    } else {
      overflow++;
    }
    tmp = j;
    average += (tmp+1.0)*(tmp/tablePtr->numEntries)/2.0;
  }

  /*
   * Print out the histogram and a few other pieces of information.
   */

  result = (char *) ckalloc((unsigned) ((NUM_COUNTERS*60) + 300));
  sprintf(result, "%d entries in table, %d buckets\n",
          tablePtr->numEntries, tablePtr->numBuckets);
  p = result + strlen(result);
  for (i = 0; i < NUM_COUNTERS; i++) {
    sprintf(p, "number of buckets with %d entries: %d\n",
            i, count[i]);
    p += strlen(p);
  }
  sprintf(p, "number of buckets with %d or more entries: %d\n",
          NUM_COUNTERS, overflow);
  p += strlen(p);
  sprintf(p, "average search distance for entry: %.1f", average);
  return result;
}

/*
 *----------------------------------------------------------------------
 *
 * HashString --
 *
 *	Compute a one-word summary of a text string, which can be
 *	used to generate a hash index.
 *
 * Results:
 *	The return value is a one-word summary of the information in
 *	string.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

static unsigned int
HashString(string)
     register CONST char *string;/* String from which to compute hash value. */
{
  register unsigned int result;
  register int c;

  /*
   * I tried a zillion different hash functions and asked many other
   * people for advice.  Many people had their own favorite functions,
   * all different, but no-one had much idea why they were good ones.
   * I chose the one below (multiply by 9 and add new character)
   * because of the following reasons:
   *
   * 1. Multiplying by 10 is perfect for keys that are decimal strings,
   *    and multiplying by 9 is just about as good.
   * 2. Times-9 is (shift-left-3) plus (old).  This means that each
   *    character's bits hang around in the low-order bits of the
   *    hash value for ever, plus they spread fairly rapidly up to
   *    the high-order bits to fill out the hash value.  This seems
   *    works well both for decimal and non-decimal strings.
   */

  result = 0;
  while (1) {
    c = *string;
    string++;
    if (c == 0) {
      break;
    }
    result += (result<<3) + c;
  }
  return result;
}

/*
 *----------------------------------------------------------------------
 *
 * StringFind --
 *
 *	Given a hash table with string keys, and a string key, find
 *	the entry with a matching key.
 *
 * Results:
 *	The return value is a token for the matching entry in the
 *	hash table, or NULL if there was no matching entry.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

static Tcl_HashEntry *
StringFind(tablePtr, key)
     Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
     CONST char *key;		/* Key to use to find matching entry. */
{
  register Tcl_HashEntry *hPtr;
  register CONST char *p1, *p2;
  int index;

  index = HashString(key) & tablePtr->mask;

  /*
   * Search all of the entries in the appropriate bucket.
   */

  for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
       hPtr = hPtr->nextPtr) {
    for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) {
      if (*p1 != *p2) {
        break;
      }
      if (*p1 == '\0') {
        return hPtr;
      }
    }
  }
  return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * StringCreate --
 *
 *	Given a hash table with string keys, and a string key, find
 *	the entry with a matching key.  If there is no matching entry,
 *	then create a new entry that does match.
 *
 * Results:
 *	The return value is a pointer to the matching entry.  If this
 *	is a newly-created entry, then *newPtr will be set to a non-zero
 *	value;  otherwise *newPtr will be set to 0.  If this is a new
 *	entry the value stored in the entry will initially be 0.
 *
 * Side effects:
 *	A new entry may be added to the hash table.
 *
 *----------------------------------------------------------------------
 */

static Tcl_HashEntry *
StringCreate(tablePtr, key, newPtr)
     Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
     CONST char *key;		/* Key to use to find or create matching
				 * entry. */
     int *newPtr;		/* Store info here telling whether a new
				 * entry was created. */
{
  register Tcl_HashEntry *hPtr;
  register CONST char *p1, *p2;
  int index;

  index = HashString(key) & tablePtr->mask;

  /*
   * Search all of the entries in this bucket.
   */

  for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
       hPtr = hPtr->nextPtr) {
    for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) {
      if (*p1 != *p2) {
        break;
      }
      if (*p1 == '\0') {
        *newPtr = 0;
        return hPtr;
      }
    }
  }

  /*
   * Entry not found.  Add a new one to the bucket.
   */

  *newPtr = 1;
  hPtr = (Tcl_HashEntry *) ckalloc((unsigned)
                                   (sizeof(Tcl_HashEntry) + strlen(key) - (sizeof(hPtr->key) -1)));
  hPtr->tablePtr = tablePtr;
  hPtr->bucketPtr = &(tablePtr->buckets[index]);
  hPtr->nextPtr = *hPtr->bucketPtr;
  hPtr->clientData = 0;
  strcpy(hPtr->key.string, key);
  *hPtr->bucketPtr = hPtr;
  tablePtr->numEntries++;

  /*
   * If the table has exceeded a decent size, rebuild it with many
   * more buckets.
   */

  if (tablePtr->numEntries >= tablePtr->rebuildSize) {
    RebuildTable(tablePtr);
  }
  return hPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * OneWordFind --
 *
 *	Given a hash table with one-word keys, and a one-word key, find
 *	the entry with a matching key.
 *
 * Results:
 *	The return value is a token for the matching entry in the
 *	hash table, or NULL if there was no matching entry.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

static Tcl_HashEntry *
OneWordFind(tablePtr, key)
     Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
     register CONST char *key;	/* Key to use to find matching entry. */
{
  register Tcl_HashEntry *hPtr;
  int index;

  index = RANDOM_INDEX(tablePtr, key);

  /*
   * Search all of the entries in the appropriate bucket.
   */

  for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
       hPtr = hPtr->nextPtr) {
    if (hPtr->key.oneWordValue == key) {
      return hPtr;
    }
  }
  return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * OneWordCreate --
 *
 *	Given a hash table with one-word keys, and a one-word key, find
 *	the entry with a matching key.  If there is no matching entry,
 *	then create a new entry that does match.
 *
 * Results:
 *	The return value is a pointer to the matching entry.  If this
 *	is a newly-created entry, then *newPtr will be set to a non-zero
 *	value;  otherwise *newPtr will be set to 0.  If this is a new
 *	entry the value stored in the entry will initially be 0.
 *
 * Side effects:
 *	A new entry may be added to the hash table.
 *
 *----------------------------------------------------------------------
 */

static Tcl_HashEntry *
OneWordCreate(tablePtr, key, newPtr)
     Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
     register CONST char *key;	/* Key to use to find or create matching
				 * entry. */
     int *newPtr;		/* Store info here telling whether a new
				 * entry was created. */
{
  register Tcl_HashEntry *hPtr;
  int index;

  index = RANDOM_INDEX(tablePtr, key);

  /*
   * Search all of the entries in this bucket.
   */

  for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
       hPtr = hPtr->nextPtr) {
    if (hPtr->key.oneWordValue == key) {
      *newPtr = 0;
      return hPtr;
    }
  }

  /*
   * Entry not found.  Add a new one to the bucket.
   */

  *newPtr = 1;
  hPtr = (Tcl_HashEntry *) ckalloc(sizeof(Tcl_HashEntry));
  hPtr->tablePtr = tablePtr;
  hPtr->bucketPtr = &(tablePtr->buckets[index]);
  hPtr->nextPtr = *hPtr->bucketPtr;
  hPtr->clientData = 0;
  hPtr->key.oneWordValue = (char *) key;	/* CONST XXXX */
  *hPtr->bucketPtr = hPtr;
  tablePtr->numEntries++;

  /*
   * If the table has exceeded a decent size, rebuild it with many
   * more buckets.
   */

  if (tablePtr->numEntries >= tablePtr->rebuildSize) {
    RebuildTable(tablePtr);
  }
  return hPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * ArrayFind --
 *
 *	Given a hash table with array-of-int keys, and a key, find
 *	the entry with a matching key.
 *
 * Results:
 *	The return value is a token for the matching entry in the
 *	hash table, or NULL if there was no matching entry.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

static Tcl_HashEntry *
ArrayFind(tablePtr, key)
     Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
     CONST char *key;		/* Key to use to find matching entry. */
{
  register Tcl_HashEntry *hPtr;
  int *arrayPtr = (int *) key;
  register int *iPtr1, *iPtr2;
  int index, count;

  for (index = 0, count = tablePtr->keyType, iPtr1 = arrayPtr;
       count > 0; count--, iPtr1++) {
    index += *iPtr1;
  }
  index = RANDOM_INDEX(tablePtr, index);

  /*
   * Search all of the entries in the appropriate bucket.
   */

  for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
       hPtr = hPtr->nextPtr) {
    for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words,
           count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
      if (count == 0) {
        return hPtr;
      }
      if (*iPtr1 != *iPtr2) {
        break;
      }
    }
  }
  return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * ArrayCreate --
 *
 *	Given a hash table with one-word keys, and a one-word key, find
 *	the entry with a matching key.  If there is no matching entry,
 *	then create a new entry that does match.
 *
 * Results:
 *	The return value is a pointer to the matching entry.  If this
 *	is a newly-created entry, then *newPtr will be set to a non-zero
 *	value;  otherwise *newPtr will be set to 0.  If this is a new
 *	entry the value stored in the entry will initially be 0.
 *
 * Side effects:
 *	A new entry may be added to the hash table.
 *
 *----------------------------------------------------------------------
 */

static Tcl_HashEntry *
ArrayCreate(tablePtr, key, newPtr)
     Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
     register CONST char *key;	/* Key to use to find or create matching
				 * entry. */
     int *newPtr;		/* Store info here telling whether a new
				 * entry was created. */
{
  register Tcl_HashEntry *hPtr;
  int *arrayPtr = (int *) key;
  register int *iPtr1, *iPtr2;
  int index, count;

  for (index = 0, count = tablePtr->keyType, iPtr1 = arrayPtr;
       count > 0; count--, iPtr1++) {
    index += *iPtr1;
  }
  index = RANDOM_INDEX(tablePtr, index);

  /*
   * Search all of the entries in the appropriate bucket.
   */

  for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
       hPtr = hPtr->nextPtr) {
    for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words,
           count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
      if (count == 0) {
        *newPtr = 0;
        return hPtr;
      }
      if (*iPtr1 != *iPtr2) {
        break;
      }
    }
  }

  /*
   * Entry not found.  Add a new one to the bucket.
   */

  *newPtr = 1;
  hPtr = (Tcl_HashEntry *) ckalloc((unsigned) (sizeof(Tcl_HashEntry)
                                               + (tablePtr->keyType*sizeof(int)) - 4));
  hPtr->tablePtr = tablePtr;
  hPtr->bucketPtr = &(tablePtr->buckets[index]);
  hPtr->nextPtr = *hPtr->bucketPtr;
  hPtr->clientData = 0;
  for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words, count = tablePtr->keyType;
       count > 0; count--, iPtr1++, iPtr2++) {
    *iPtr2 = *iPtr1;
  }
  *hPtr->bucketPtr = hPtr;
  tablePtr->numEntries++;

  /*
   * If the table has exceeded a decent size, rebuild it with many
   * more buckets.
   */

  if (tablePtr->numEntries >= tablePtr->rebuildSize) {
    RebuildTable(tablePtr);
  }
  return hPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * BogusFind --
 *
 *	This procedure is invoked when an Tcl_FindHashEntry is called
 *	on a table that has been deleted.
 *
 * Results:
 *	If panic returns (which it shouldn't) this procedure returns
 *	NULL.
 *
 * Side effects:
 *	Generates a panic.
 *
 *----------------------------------------------------------------------
 */

/* ARGSUSED */
static Tcl_HashEntry *
BogusFind(tablePtr, key)
     Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
     CONST char *key;		/* Key to use to find matching entry. */
{
  panic("called Tcl_FindHashEntry on deleted table");
  return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * BogusCreate --
 *
 *	This procedure is invoked when an Tcl_CreateHashEntry is called
 *	on a table that has been deleted.
 *
 * Results:
 *	If panic returns (which it shouldn't) this procedure returns
 *	NULL.
 *
 * Side effects:
 *	Generates a panic.
 *
 *----------------------------------------------------------------------
 */

/* ARGSUSED */
static Tcl_HashEntry *
BogusCreate(tablePtr, key, newPtr)
     Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
     CONST char *key;		/* Key to use to find or create matching
				 * entry. */
     int *newPtr;		/* Store info here telling whether a new
				 * entry was created. */
{
  panic("called Tcl_CreateHashEntry on deleted table");
  return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * RebuildTable --
 *
 *	This procedure is invoked when the ratio of entries to hash
 *	buckets becomes too large.  It creates a new table with a
 *	larger bucket array and moves all of the entries into the
 *	new table.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Memory gets reallocated and entries get re-hashed to new
 *	buckets.
 *
 *----------------------------------------------------------------------
 */

static void
RebuildTable(tablePtr)
     register Tcl_HashTable *tablePtr;	/* Table to enlarge. */
{
  int oldSize, count, index;
  Tcl_HashEntry **oldBuckets;
  register Tcl_HashEntry **oldChainPtr, **newChainPtr;
  register Tcl_HashEntry *hPtr;

  oldSize = tablePtr->numBuckets;
  oldBuckets = tablePtr->buckets;

  /*
   * Allocate and initialize the new bucket array, and set up
   * hashing constants for new array size.
   */

  tablePtr->numBuckets *= 4;
  tablePtr->buckets = (Tcl_HashEntry **) ckalloc((unsigned)
                                                 (tablePtr->numBuckets * sizeof(Tcl_HashEntry *)));
  for (count = tablePtr->numBuckets, newChainPtr = tablePtr->buckets;
       count > 0; count--, newChainPtr++) {
    *newChainPtr = NULL;
  }
  tablePtr->rebuildSize *= 4;
  tablePtr->downShift -= 2;
  tablePtr->mask = (tablePtr->mask << 2) + 3;

  /*
   * Rehash all of the existing entries into the new bucket array.
   */

  for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) {
    for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) {
      *oldChainPtr = hPtr->nextPtr;
      if (tablePtr->keyType == TCL_STRING_KEYS) {
        index = HashString(hPtr->key.string) & tablePtr->mask;
      } else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) {
        index = RANDOM_INDEX(tablePtr, hPtr->key.oneWordValue);
      } else {
        register int *iPtr;
        int count;

        for (index = 0, count = tablePtr->keyType,
               iPtr = hPtr->key.words; count > 0; count--, iPtr++) {
          index += *iPtr;
        }
        index = RANDOM_INDEX(tablePtr, index);
      }
      hPtr->bucketPtr = &(tablePtr->buckets[index]);
      hPtr->nextPtr = *hPtr->bucketPtr;
      *hPtr->bucketPtr = hPtr;
    }
  }

  /*
   * Free up the old bucket array, if it was dynamically allocated.
   */

  if (oldBuckets != tablePtr->staticBuckets) {
    ckfree((char *) oldBuckets);
  }
}

#endif