hash_tab.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 486 行 · 第 1/2 页

//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//

#include <cool/Hash_Table.h>

// compare_keys_s -- Key compare
template <class Tkey, class Tval> 
Boolean (*CoolHash_Table<Tkey,Tval>::compare_keys_s)
   (const Tkey&, const Tkey&) = &CoolHash_Table_keys_equal;
//##CoolHash_Table<Tkey,Tval>::Key_Compare CoolHash_Table<Tkey,Tval>::compare_keys_s = &CoolHash_Table_keys_equal;

// compare_values_s -- Value compare
template <class Tkey, class Tval> 
Boolean (*CoolHash_Table<Tkey,Tval>::compare_values_s) (const Tval&, const Tval&) = &CoolHash_Table_values_equal;
//##CoolHash_Table<Tkey,Tval>::Value_Compare CoolHash_Table<Tkey,Tval>::compare_values_s = &CoolHash_Table_values_equal;

// CoolHash_Table -- Simple constructor with no arguments that creates a hash
//               table object with the minimal prime number of buckets and
//               uses the default hash function.
// Input:        None
// Output:       None

template <class Tkey, class Tval> 
CoolHash_Table<Tkey,Tval>::CoolHash_Table() {
  long prime = hash_primes[this->current_bucket]; // Get prime number 
  this->table = new CoolHash_Table_Bucket<Tkey,Tval>[prime]; 
  this->h_function = &CoolHash_Table_default_hash;
}


// CoolHash_Table -- Simple constructor with one argument that creates a hash
//               table object with the minimal prime number of buckets that
//               holds some user-supplied number of items and uses the default
//               hash function.
// Input:        Minimal number of items table must hold
// Output:       None

template <class Tkey, class Tval> 
CoolHash_Table<Tkey,Tval>::CoolHash_Table(unsigned long n)
: CoolBase_Hash_Table(n)
{
  long prime = hash_primes[this->current_bucket]; // Get prime number 
  this->table = new CoolHash_Table_Bucket<Tkey,Tval>[prime]; 
  this->h_function = &CoolHash_Table_default_hash;
}


// CoolHash_Table -- constructor that takes a reference to an existing hash table
//               and duplicates both its size and contents
// Input:        Reference to hash table object
// Output:       None

template <class Tkey, class Tval> 
CoolHash_Table<Tkey,Tval>::CoolHash_Table(const CoolHash_Table<Tkey,Tval>& h)
: CoolBase_Hash_Table(h)
{
  long prime = hash_primes[this->current_bucket]; // Get prime number 
  this->table = new CoolHash_Table_Bucket<Tkey,Tval>[prime]; 
  for (long i = 0; i < prime; i++) { // For each bucket count
    for (int j = 0; j < h.items_in_buckets[i]; j++) { // For items in bucket
      this->table[i].data[j].key = h.table[i].data[j].key; // Copy key 
      this->table[i].data[j].value = h.table[i].data[j].value; // Copy value
    }
  }
  this->h_function = h.h_function;              // Use the same hash function
}


// ~CoolHash_Table -- Destructor for the CoolHash_Table class
// Input:         this*
// Output:        None

template <class Tkey, class Tval> 
CoolHash_Table<Tkey,Tval>::~CoolHash_Table() {
  delete [] this->table;                        // Free key/value storage
}


// find -- Find key/value in hash table
// Input:  Key searching for
// Output: TRUE/FALSE; current_position updated

template <class Tkey, class Tval> 
Boolean CoolHash_Table<Tkey,Tval>::find (const Tkey& key) {
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value 
  for (int i = 0; i < this->items_in_buckets[hash]; i++) { // For each entry
    if ((*this->compare_keys_s)(key,this->table[hash].data[i].key) == TRUE){
      this->curpos = SET_BUCKET_NUMBER(hash); // Set bucket number
      this->curpos |= SET_BUCKET_INDEX(i);      // Set bucket index
      return TRUE;                              // Return success
    }
  }
  return FALSE;
}


// key --  Return key at current position
// Input:  None
// Output: Reference to key at current position

template <class Tkey, class Tval> 
const Tkey& CoolHash_Table<Tkey,Tval>::key () {
  if (this->curpos != INVALID) { // If valid current position
    unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
    long index = BUCKET_INDEX(this->curpos);          // Get index in bucket
    return (this->table[hash].data[index].key);       // Return value
  }
  else                          // Else 
    this->key_error ("Tkey","Tval"); // Raise exception
return (this->table[0].data[0].key);
}


// value -- Return value at current position
// Input:   None
// Output:  Reference to value at current position

template <class Tkey, class Tval> 
const Tval& CoolHash_Table<Tkey,Tval>::value () {
  if (this->curpos != INVALID) { // If valid current position
    unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
    long index = BUCKET_INDEX(this->curpos);          // Get index in bucket
    return (this->table[hash].data[index].value);     // Return value
  }
  else                          // Else 
    this->value_error ("Tkey","Tval"); // Raise exception
return (this->table[0].data[0].value);
}


// put -- Hash key/value pair into table if not already there
// Input: this*, key, value
// Output:TRUE when key is new, else FALSE

template <class T1, class T2> 
Boolean CoolHash_Table<T1,T2>::put (const T1& key, const T2& value) {
 retry:
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  int index = this->items_in_buckets[hash];
  this->curpos = SET_BUCKET_NUMBER(hash); // Save bucket number
  for (int i = 0; i < index; i++)         // For each item
    if ((*this->compare_keys_s)(key,this->table[hash].data[i].key) == TRUE) {
      this->table[hash].data[i].value = value; // Already there, update value
      this->curpos |= SET_BUCKET_INDEX(i);       // Update bucket index position
      return FALSE;                              // And return found
    }
  if (index >= BUCKET_SIZE) {   // If bucket is full
    this->resize (hash_primes[this->current_bucket+1]*BUCKET_SIZE); // Grow
    goto retry;
  }
  this->table[hash].data[index].key = key;
  this->table[hash].data[index].value = value;
  this->entry_count++;  // Increment table entry count
  this->curpos |= SET_BUCKET_INDEX(index); // Update bucket index position
  this->items_in_buckets[hash]++;          // Increment bucket item count
  return TRUE;                     // Indicate new
}


// get -- Get a value based on a key from the table
// Input: this*, reference to a key
// Output:Value for key/value pair from table
//        Returns TRUE when entry is found, else false

template <class Tkey, class Tval> 
Boolean CoolHash_Table<Tkey,Tval>::get (const Tkey& key, Tval& value) {
  Boolean result = FALSE;       // Assume we don't find entry
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  for (int i = 0; i < this->items_in_buckets[hash]; i++) { // For each entry
    if ((*this->compare_keys_s)(key,this->table[hash].data[i].key) == TRUE) {
      this->curpos = SET_BUCKET_NUMBER(hash); // Save bucket number
      this->curpos|= SET_BUCKET_INDEX(i);             // Save index into bucket
      value = this->table[hash].data[i].value;        // Copy value in table
      result = TRUE;                                  // Inidicate success
      break;                                          // Break out of loop
    }
  }
  return result;                // Return success/failure
}


// get_key --Get a key based on a value from the table
// Input:    this*, reference to a value, reference to place to store key
// Output:   TRUE if found with value in reference argument, else FALSE

template <class Tkey, class Tval> 
Boolean CoolHash_Table<Tkey,Tval>::get_key (const Tval& value, Tkey& key) {
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  for (long i = 0; i < prime; i++)                // For each bucket, search
    for (int j = 0; j < this->items_in_buckets[i]; j++) // For item in bucket
      if ((*this->compare_values_s)(value,this->table[i].data[j].value)==TRUE){
        this->curpos = SET_BUCKET_NUMBER(i); // Set bucket number
        this->curpos|= SET_BUCKET_INDEX(j);          // Set index into bucket
        key = this->table[i].data[j].key;                    // Return key for value
        return TRUE;                                         // Indicate success
      }
  return FALSE;         // Indicate failure
}


// remove -- Remove element at current position from the set
// Input:    this*
// Output:   TRUE/FALSE

template <class Tkey, class Tval> 
Boolean CoolHash_Table<Tkey,Tval>::remove () {
  if (this->curpos != INVALID) { // If valid current position
    unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
    long index = BUCKET_INDEX(this->curpos);          // Get index in bucket
    int count = this->items_in_buckets[hash];         // Number of items in bucket
    this->table[hash].data[index].key = this->table[hash].data[count-1].key;
    this->table[hash].data[index].value = this->table[hash].data[count-1].value;
    this->entry_count--;        // Decrement table entry count
    this->items_in_buckets[hash]--; // Decrement bucket item count
    if (this->items_in_buckets[hash]) { // If any more items in bucket
      this->curpos = SET_BUCKET_NUMBER(hash); // Save bucket number
      this->curpos |= SET_BUCKET_INDEX(this->items_in_buckets[hash]-1);
    }
    else
      this->curpos = INVALID;   // Else invalidate marker
    return TRUE;                // Return success
  }
  this->remove_error ("Tkey", "Tval"); // Raise exception
  return FALSE;              // Return failure
}


// remove -- Remove a value based on a key from the table
// Input:    this*, reference to a key
// Output:   TRUE/FALSE