tclhash.c

CMX990 demonstration board (DE9901)

 *	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(Tcl_HashTable *tablePtr, char *key, int *newPtr)
  //  Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
  //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 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(Tcl_HashTable *tablePtr, char *key)
  //  Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
  //register 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(Tcl_HashTable *tablePtr, char *key, int *newPtr)
  //  Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
  //register 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 = 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;
}

/*
 *----------------------------------------------------------------------
 *
 * 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(Tcl_HashTable *tablePtr, char *key)
  //  Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
  //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(Tcl_HashTable *tablePtr, char *key, int *newPtr)
  //  Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
  //register 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.
 *
 *----------------------------------------------------------------------
 */
static Tcl_HashEntry *BogusFind(Tcl_HashTable *tablePtr, char *key)
  //  Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
  //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.
 *
 *----------------------------------------------------------------------
 */
static Tcl_HashEntry *BogusCreate(Tcl_HashTable *tablePtr, char *key, int *newPtr)
  //  Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */
  //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(Tcl_HashTable *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);
  }
}