libchash.c

google hash table算法

HTItem *HashFind(HashTable *ht, ulong key)
{
   LOAD_AND_RETURN(ht, Find(ht, KEY_TRUNC(ht, key), NULL));
}

HTItem *HashFindLast(HashTable *ht)
{
   LOAD_AND_RETURN(ht, ht->posLastFind);
}

/*************************************************************************\
| HashFindOrInsert()                                                      |
| HashFindOrInsertItem()                                                  |
| HashInsert()                                                            |
| HashInsertItem()                                                        |
| HashDelete()                                                            |
| HashDeleteLast()                                                        |
|     Pretty obvious what these guys do.  Some take buckets (items),      |
|     some take keys and data separately.  All things RETURN the bucket   |
|     (a pointer into the hashtable) if appropriate.                      |
\*************************************************************************/

HTItem *HashFindOrInsert(HashTable *ht, ulong key, ulong dataInsert)
{
      /* This is equivalent to Insert without samekey-overwrite */
   return Insert(ht, KEY_TRUNC(ht, key), dataInsert, 0);
}

HTItem *HashFindOrInsertItem(HashTable *ht, HTItem *pItem)
{
   return HashFindOrInsert(ht, pItem->key, pItem->data);
}

HTItem *HashInsert(HashTable *ht, ulong key, ulong data)
{
   return Insert(ht, KEY_TRUNC(ht, key), data, SAMEKEY_OVERWRITE);
}

HTItem *HashInsertItem(HashTable *ht, HTItem *pItem)
{
   return HashInsert(ht, pItem->key, pItem->data);
}

int HashDelete(HashTable *ht, ulong key)
{
   return Delete(ht, KEY_TRUNC(ht, key), !FAST_DELETE, 0);
}

int HashDeleteLast(HashTable *ht)
{
   if ( !ht->posLastFind  )                /* last find failed */
      return 0;
   return Delete(ht, 0, !FAST_DELETE, 1);  /* no need to specify a key */
}

/*************************************************************************\
| HashFirstBucket()                                                       |
| HashNextBucket()                                                        |
|     Iterates through the items in the hashtable by iterating through    |
|     the table.  Since we know about deleted buckets and loading data    |
|     off disk, and the table doesn't, our job is to take care of these   |
|     things.  RETURNS a bucket, or NULL after the last bucket.           |
\*************************************************************************/

HTItem *HashFirstBucket(HashTable *ht)
{
   HTItem *retval;

   for ( retval = Table(FirstBucket)(ht->iter, ht->table, ht->cBuckets);
	 retval;  retval = Table(NextBucket)(ht->iter) )
      if ( !IS_BCK_DELETED(retval) )
	 LOAD_AND_RETURN(ht, retval);
   return NULL;
}

HTItem *HashNextBucket(HashTable *ht)
{
   HTItem *retval;

   while ( (retval=Table(NextBucket)(ht->iter)) )
      if ( !IS_BCK_DELETED(retval) )
	 LOAD_AND_RETURN(ht, retval);
   return NULL;
}

/*************************************************************************\
| HashSetDeltaGoalSize()                                                  |
|     If we're going to insert 100 items, set the delta goal size to      |
|     100 and we take that into account when inserting.  Likewise, if     |
|     we're going to delete 10 items, set it to -100 and we won't         |
|     rehash until all 100 have been done.  It's ok to be wrong, but      |
|     it's efficient to be right.  Returns the delta value.               |
\*************************************************************************/

int HashSetDeltaGoalSize(HashTable *ht, int delta)
{
   ht->cDeltaGoalSize = delta;
#if FAST_DELETE == 1 || defined INSERT_ONLY
   if ( ht->cDeltaGoalSize < 0 )   /* for fast delete, we never */
      ht->cDeltaGoalSize = 0;      /* ...rehash after deletion  */
#endif
   return ht->cDeltaGoalSize;
}


/*************************************************************************\
| HashSave()                                                              |
| HashLoad()                                                              |
| HashLoadKeys()                                                          |
|     Routines for saving and loading the hashtable from disk.  We can    |
|     then use the hashtable in two ways: loading it back into memory     |
|     (HashLoad()) or loading only the keys into memory, in which case    |
|     the data for a given key is loaded off disk when the key is         |
|     retrieved.  The data is freed when something new is retrieved in    |
|     its place, so this is not a "lazy-load" scheme.                     |
|        The key is saved automatically and restored upon load, but the   |
|     user needs to specify a routine for reading and writing the data.   |
|     fSaveKeys is of course set to 1 when you read in a hashtable.       |
|     HashLoad RETURNS a newly allocated hashtable.                       |
|        DATA_WRITE() takes an fp and a char * (representing the data     |
|     field), and must perform two separate tasks.  If fp is NULL,        |
|     return the number of bytes written.  If not, writes the data to     |
|     disk at the place the fp points to.                                 |
|        DATA_READ() takes an fp and the number of bytes in the data      |
|     field, and returns a char * which points to wherever you've         |
|     written the data.  Thus, you must allocate memory for the data.     |
|        Both dataRead and dataWrite may be NULL if you just wish to      |
|     store the data field directly, as an integer.                       |
\*************************************************************************/

void HashSave(FILE *fp, HashTable *ht, int (*dataWrite)(FILE *, char *))
{
   long cchData, posStart;
   HTItem *bck;

   /* File format: magic number (4 bytes)
                 : cchKey (one word)
                 : cItems (one word)
                 : cDeletedItems (one word)
                 : table info (buckets and a bitmap)
		 : cchAllKeys (one word)
      Then the keys, in a block.  If cchKey is NULL_TERMINATED, the keys
      are null-terminated too, otherwise this takes up cchKey*cItems bytes.
      Note that keys are not written for DELETED buckets.
      Then the data:
                 : EITHER DELETED (one word) to indicate it's a deleted bucket,
                 : OR number of bytes for this (non-empty) bucket's data
                   (one word).  This is not stored if dataWrite == NULL
                   since the size is known to be sizeof(ul).  Plus:
                 : the data for this bucket (variable length)
      All words are in network byte order. */

   fprintf(fp, "%s", MAGIC_KEY);
   WRITE_UL(fp, ht->cchKey);        /* WRITE_UL, READ_UL, etc in fks-hash.h */
   WRITE_UL(fp, ht->cItems);
   WRITE_UL(fp, ht->cDeletedItems);
   Table(Write)(fp, ht->table, ht->cBuckets);        /* writes cBuckets too */

   WRITE_UL(fp, 0);                 /* to be replaced with sizeof(key block) */
   posStart = ftell(fp);
   for ( bck = HashFirstBucket(ht); bck; bck = HashNextBucket(ht) )
      fwrite(KEY_PTR(ht, bck->key), 1,
	     (ht->cchKey == NULL_TERMINATED ?
	      strlen(KEY_PTR(ht, bck->key))+1 : ht->cchKey), fp);
   cchData = ftell(fp) - posStart;
   fseek(fp, posStart - sizeof(unsigned long), SEEK_SET);
   WRITE_UL(fp, cchData);
   fseek(fp, 0, SEEK_END);          /* done with our sojourn at the header */

      /* Unlike HashFirstBucket, TableFirstBucket iters through deleted bcks */
   for ( bck = Table(FirstBucket)(ht->iter, ht->table, ht->cBuckets);
	 bck;  bck = Table(NextBucket)(ht->iter) )
      if ( dataWrite == NULL || IS_BCK_DELETED(bck) )
	 WRITE_UL(fp, bck->data);
      else                          /* write cchData followed by the data */
      {
	 WRITE_UL(fp, (*dataWrite)(NULL, (char *)bck->data));
	 (*dataWrite)(fp, (char *)bck->data);
      }
}

static HashTable *HashDoLoad(FILE *fp, char * (*dataRead)(FILE *, int), 
			     HashTable *ht)
{
   ulong cchKey;
   char szMagicKey[4], *rgchKeys;
   HTItem *bck;

   fread(szMagicKey, 1, 4, fp);
   if ( strncmp(szMagicKey, MAGIC_KEY, 4) )
   {
      fprintf(stderr, "ERROR: not a hash table (magic key is %4.4s, not %s)\n",
	      szMagicKey, MAGIC_KEY);
      exit(3);
   }
   Table(Free)(ht->table, ht->cBuckets);  /* allocated in AllocateHashTable */

   READ_UL(fp, ht->cchKey);
   READ_UL(fp, ht->cItems);
   READ_UL(fp, ht->cDeletedItems);
   ht->cBuckets = Table(Read)(fp, &ht->table);    /* next is the table info */

   READ_UL(fp, cchKey);
   rgchKeys = (char *) HTsmalloc( cchKey );  /* stores all the keys */
   fread(rgchKeys, 1, cchKey, fp);
      /* We use the table iterator so we don't try to LOAD_AND_RETURN */
   for ( bck = Table(FirstBucket)(ht->iter, ht->table, ht->cBuckets);
	 bck;  bck = Table(NextBucket)(ht->iter) )
   {
      READ_UL(fp, bck->data);        /* all we need if dataRead is NULL */
      if ( IS_BCK_DELETED(bck) )     /* always 0 if defined(INSERT_ONLY) */
	 continue;                   /* this is why we read the data first */
      if ( dataRead != NULL )        /* if it's null, we're done */
	 if ( !ht->fpData )          /* load data into memory */
	    bck->data = (ulong)dataRead(fp, bck->data);
	 else                        /* store location of data on disk */
	 {
	    fseek(fp, bck->data, SEEK_CUR);  /* bck->data held size of data */
	    bck->data = ftell(fp) - bck->data - sizeof(unsigned long);
	 }

      if ( ht->cchKey == NULL_TERMINATED )   /* now read the key */
      {
	 bck->key = (ulong) rgchKeys;
	 rgchKeys = strchr(rgchKeys, '\0') + 1;    /* read past the string */
      }
      else
      {
	 if ( STORES_PTR(ht) )               /* small keys stored directly */
	    bck->key = (ulong) rgchKeys;
	 else
	    memcpy(&bck->key, rgchKeys, ht->cchKey);
	 rgchKeys += ht->cchKey;
      }
   }
   if ( !STORES_PTR(ht) )                    /* keys are stored directly */
      HTfree(rgchKeys - cchKey, cchKey);     /* we've advanced rgchK to end */
   return ht;
}

HashTable *HashLoad(FILE *fp, char * (*dataRead)(FILE *, int))
{
   HashTable *ht;
   ht = AllocateHashTable(0, 2);  /* cchKey set later, fSaveKey should be 2! */
   return HashDoLoad(fp, dataRead, ht);
}

HashTable *HashLoadKeys(FILE *fp, char * (*dataRead)(FILE *, int))
{
   HashTable *ht;

   if ( dataRead == NULL )
      return HashLoad(fp, NULL);  /* no reason not to load the data here */
   ht = AllocateHashTable(0, 2);  /* cchKey set later, fSaveKey should be 2! */
   ht->fpData = fp;               /* tells HashDoLoad() to only load keys */
   ht->dataRead = dataRead;
   return HashDoLoad(fp, dataRead, ht);
}

/*************************************************************************\
| PrintHashTable()                                                        |
|     A debugging tool.  Prints the entire contents of the hash table,    |
|     like so: <bin #>: key of the contents.  Returns number of bytes     |
|     allocated.  If time is not -1, we print it as the time required     |
|     for the hash.  If iForm is 0, we just print the stats.  If it's     |
|     1, we print the keys and data too, but the keys are printed as      |
|     ulongs.  If it's 2, we print the keys correctly (as long numbers    |
|     or as strings).                                                     |
\*************************************************************************/

ulong PrintHashTable(HashTable *ht, double time, int iForm)
{
   ulong cbData = 0, cbBin = 0, cItems = 0, cOccupied = 0;
   HTItem *item;

   printf("HASH TABLE.\n");
   if ( time > -1.0 )
   {
      printf("----------\n");
      printf("Time: %27.2f\n", time);
   }

   for ( item = Table(FirstBucket)(ht->iter, ht->table, ht->cBuckets);
	 item;  item = Table(NextBucket)(ht->iter) )
   {
      cOccupied++;                    /* this includes deleted buckets */
      if ( IS_BCK_DELETED(item) )     /* we don't need you for anything else */
	 continue;
      cItems++;                       /* this is for a sanity check */
      if ( STORES_PTR(ht) )
	 cbData += ht->cchKey == NULL_TERMINATED ? 
	    WORD_ROUND(strlen((char *)item->key)+1) : ht->cchKey;
      else
	 cbBin -= sizeof(item->key), cbData += sizeof(item->key);
      cbBin -= sizeof(item->data), cbData += sizeof(item->data);
      if ( iForm != 0 )      /* we want the actual contents */
      {
	 if ( iForm == 2 && ht->cchKey == NULL_TERMINATED ) 
	    printf("%s/%lu\n", (char *)item->key, item->data);
	 else if ( iForm == 2 && STORES_PTR(ht) )
	    printf("%.*s/%lu\n", 
		   (int)ht->cchKey, (char *)item->key, item->data);
	 else     /* either key actually is a ulong, or iForm == 1 */
	    printf("%lu/%lu\n", item->key, i