dict.h

检查C/C++源程序中的可能错误和容易遭受弱点攻击的地方

/* dict.H
 * John Viega
 *
 * September 1995
 * Converted to C++ somewhere along the line.
 */

#ifndef __DICT_H__
#define __DICT_H__

#include "fatal.H"
#include <stdlib.h>
#include <stdio.h>
#ifdef ITS_DEBUG
#include <assert.h>
#else
#define assert(x)
#endif

void InitDummyBucket();
extern unsigned long primes[];

/* 
** This constant is used to signify where a key was there but has been
** deleted. 
*/
#define INVALID       (char *)~0

template<class T> struct dictBucket
{
  char *key;
  T *value;
};

template<class T> class Dictionary
{
public:
  /*
  ** Dictionary<T>::SetItem(char *key, T* value)
  **
  ** Inserts the key : value pair into dicttable h.  If such an
  ** insertation would make the hash table full enough to resize,
  ** as defined by rehashSize then the hash table is expanded.
  */
  void SetItem(char *key, T* value) 
  {
    unsigned int dictkey = 0;
    unsigned int dict2   = 0;
    unsigned int i       = 0;
    assert(key != NULL);
    assert(key != INVALID);

    /* 
    ** First check to see if the key is already there, 
    ** and if it is, just replace the value.
    */
    dictkey = Hash(key, numBuckets);
    dict2   = Hash(key, secondHash);
    if(!dict2)
      {
	dict2 = 1;
      }
    assert(dictkey < numBuckets);
    /* 
    ** We don't want to do this forever, if the table is full, stop
    ** when we've checked all of the buckets.
    */
    for(i=0;i<numBuckets;i++)
      {
	/*
	** When we find an unused bucket, we can stop, we've never hashed 
	** this key before, or we would have found it by now.
	*/
	if(buckets[dictkey].key == NULL)
	  {
	    break;
	  }

	/*
	** We've found the key in the hashtable.  Just replace the value
	** and return.
	*/
	if(!strcmp(buckets[dictkey].key, key))
	  {
	    buckets[dictkey].value = value;
	    return;
	  }
	dictkey += dict2;
	dictkey %= numBuckets;
      }
    if(((100.*(++numKeys))/numBuckets) >= rehashSize)
      {
	Expand();
	/* Recompute the dict keys because we resized. */
	dictkey = Hash(key, numBuckets);
	dict2   = Hash(key, secondHash);
	if(!dict2)
	  {
	    dict2 = 1;
	  }
      }

  
    assert(dictkey < numBuckets);
    while((buckets[dictkey].key != NULL) && 
	  (buckets[dictkey].key != INVALID))
      {
	dictkey += dict2;
	dictkey %= numBuckets;
      }
    buckets[dictkey].key = key;
    buckets[dictkey].value = value;
  }
  /*
  ** T* Dictionary<T>::GetItem(char *key, short& error)
  **
  ** Returns the T* you passed in as a value, given the key.  It sets
  ** error to 1 and returns null if the key isn't in the hash table.  
  ** 
  */
  T* GetItem(char *key, short& error)
  {
    unsigned int   dictkey, dict2, i;

    assert(key != NULL);
    assert(key != INVALID);
    error = 0;
    dictkey = Hash(key, numBuckets);
    dict2   = Hash(key, secondHash);
    if(!dict2)
      {
	dict2 = 1;
      }
    assert(dictkey < numBuckets);
    assert(dict2 < numBuckets);

    for(i=0;i<numBuckets;i++)
      {
	if(buckets[dictkey].key == NULL)
	  {
	    error = 1;
	    return NULL;
	  }
	if(!strcmp(buckets[dictkey].key, key))
	  {
	    return buckets[dictkey].value;
	  }
	dictkey += dict2;
	dictkey %= numBuckets;
      }
    /* Only get here if the table was full. */
    error = 1;
    return NULL;
  }

  /*
  ** T* Dictionary<T>::DeleteItem(char *key, short& error)
  **
  ** Deletes the key from the dict table h.  Returns the value if the key
  ** was in the map, or else returns NULL and sets error.
  */

  T* DeleteItem(char *key, short& error)
  {
    unsigned int    dictkey, dict2, i;

    error = 0;
    assert(key != NULL);
    assert(key != INVALID);

    dictkey = Hash(key, numBuckets);
    dict2   = Hash(key, secondHash);

    if(!dict2)
      {
	dict2 = 1;
      }
    assert(dictkey < numBuckets);
    for(i=0;i<numBuckets;i++)
      {
	if(buckets[dictkey].key == NULL)
	  {
	    error = 1;
	    return NULL;
	  }
	if(!strcmp(buckets[dictkey].key,key))
	  {
	    buckets[dictkey].key = INVALID;
	    numKeys--;
	    return buckets[dictkey].value;
	  }
	dictkey += dict2;
	dictkey %= numBuckets;
      }
    error = 1;
    return NULL;
  }

  /*
  ** Dictionary<T>::Dictionary(int sizeIndex)
  ** 
  ** Allocate a new Dictionary.  The sizeIndex determines how many items
  ** the dict table will hold.  Note that unless you make REHASH_SIZE 1,
  ** not all of these slots will be used before rehashing occurs.
  ** Here are the valid values:
  **
  ** sizeIndex           Size of Dict Table            Rehashes At n Keys
  ** 1                   7                             6
  ** 2                   13                            10
  ** 3                   31                            24
  ** 4                   61                            46
  ** 5                   127                           96
  ** 6                   251                           189
  ** 7                   509                           382
  ** 8                   1021                          766
  ** 9                   2017                          1513
  ** 10                  4093                          3070
  ** 11                  5987                          4491    
  ** 12                  9551                          7164      
  ** 13                  15683                         11762
  ** 14                  19609                         14707
  ** 15                  31397                         23578
  ** 16                  65521                         49141
  ** 17                  131071                        98304
  ** 18                  262139                        196605
  ** 19                  524287                        393216
  ** 20                  1048573                       786430
  ** 21                  2097143                       1572858
  ** 22                  4194301                       3145726
  ** 23                  8388593                       6291445
  ** 24                  16777213                      12582910
  ** 25                  33554393                      25165795
  ** 26                  67108859                      50331645
  ** 27                  134217689                     100663267
  ** 28                  268435399                     201326550
  ** 29                  536870909                     402653182
  ** 30                  1073741789                    none (805306342)
  */
  Dictionary(int sizeIndex)
  {
    unsigned int i;
    InitDummyBucket();
    assert(sizeIndex > 0);
    assert(sizeIndex < 30);
    rehashSize    = 75.;
    numBuckets    = primes[sizeIndex];
    numKeys       = 0;
    secondHash    = primes[sizeIndex-1];

    buckets = new dictBucket<T>[numBuckets];
    if(!buckets)
      OutOfMemory();
    for(i=0; i<numBuckets;i++)
      {
	buckets[i].key = NULL;
      }
  }
  Dictionary(int sizeIndex, double r)
  {
    assert(r>0 && r<=100);
    assert(sizeIndex > 0);
    assert(sizeIndex < 30);
    rehashSize    = r;
    numBuckets    = primes[sizeIndex];
    numKeys       = 0;
    secondHash    = primes[sizeIndex-1];

    buckets = new dictBucket<T>[numBuckets];
    if(!buckets)
      OutOfMemory();
    for(unsigned int i=0; i<numBuckets;i++)
      {
	buckets[i].key = NULL;
      }
  }

  unsigned int GetNumKeys()
  {
    return numKeys;
  }
  // Note: no bounds check.  Use with caution!
  void GetKeys(char **outbuf)
  {
    int j = 0;
    for(unsigned int i=0;i<numBuckets;i++)
      {
	if(buckets[i].key != NULL && buckets[i].key != INVALID)
	  {
	    outbuf[j++] = buckets[i].key;
	  }
      }
  }

private:
  unsigned int Hash(char *str, int pri)
  {
    unsigned int hashval = 0;
    while(*str != '\0')
      {
	hashval = *str + 31 * hashval;
	str++;
      }
    return hashval % pri;
  }
  /* 
  ** This is what actually expands the hash table, when you insert something
  ** and the table is too full, and needs to expand.
  ** Note that this needs to be atomic.
  */
  void Expand()
  {
    dictBucket<T>      *oldBuckets;
    unsigned int       i;

    i = FindNextSize();
    secondHash = numBuckets;
    numBuckets = primes[i];
    oldBuckets = buckets;
    buckets = new dictBucket<T>[numBuckets];
    if(!buckets)
      OutOfMemory();
    for(i=0;i<numBuckets;i++)
      {
	buckets[i].key = NULL;
      }
    numKeys = 0; // We're about to add them back in. 
    for(i = 0; i < secondHash; i++)
      {
	if(oldBuckets[i].key != NULL && oldBuckets[i].key != INVALID)
	  {
	    SetItem(oldBuckets[i].key, oldBuckets[i].value);
	  }
      }
    delete[] oldBuckets;
  }


  /*
  ** Given the current size of the dict table, this scans the list
  ** of primes until it finds where in that list you are.  Then 
  ** it gives you the new index you should use for expanding your
  ** dict table.
  */ 
  int FindNextSize()
  {
    int i = 0;
    while(1)
      {
	assert(primes[i]);
	if(primes[i] == numBuckets)
	  { 
	    /* If this fails, you asked for too big of a dict table. */
	    assert(primes[i+1]);
	    return i+1;
	  }
	i++;
      }
  }

  dictBucket<T>   *buckets;
  unsigned int    numBuckets;
  unsigned int    numKeys;
  unsigned int    secondHash;
  double          rehashSize;
};

// If you need it.
struct DummyBucket{};
extern DummyBucket *dummy_bucket;

#endif /* __DICT_H__ */