hashutils.cc

directed diffusion 的ns2 源代码

 * 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(Tcl_HashTable *tablePtr, CONST char *key, int *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 *) malloc((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, register CONST char *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(Tcl_HashTable *tablePtr, register CONST char *key, int *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 *) malloc(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(Tcl_HashTable *tablePtr, CONST char *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(Tcl_HashTable *tablePtr, register CONST char *key, int *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 *) malloc((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(Tcl_HashTable *tablePtr, CONST char *key)
/*
*    Tcl_HashTable *tablePtr;	* Table in which to lookup entry.
*    CONST char *key;		* Key to use to find matching entry.
*/
{
  DiffPrint(DEBUG_ALWAYS, "called Tcl_FindHashEntry on deleted table\n");
  abort();

  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(Tcl_HashTable *tablePtr, CONST char *key, int *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.
*/
{
  DiffPrint(DEBUG_ALWAYS, "called Tcl_CreateHashEntry on deleted table\n");
  abort();

  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(register 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 **) malloc((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) {
    free((char *) oldBuckets);
  }
}