ACE/apps/gperf/src/Hash_Table.cpp

   1 // -*- C++ -*-
   2
   3 /**
   4  * Copyright (C) 1989 Free Software Foundation, Inc.
   5  * written by Douglas C. Schmidt (d.schmidt@vanderbilt.edu)
   6  *
   7  * This file is part of GNU GPERF.
   8  *
   9  * This program is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU General Public License
  11  * as published by the Free Software Foundation; either version 2
  12  * of the License, or (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  22  */
  23
  24 #include "Hash_Table.h"
  25 #include "ace/ACE.h"
  26 #include "ace/OS_NS_string.h"
  27 #include "ace/OS_Memory.h"
  28
  29 // The size of the hash table is always the smallest power of 2 >= the
  30 // size indicated by the user.  This allows several optimizations,
  31 // including the use of double hashing and elimination of the mod
  32 // instruction.  Note that the size had better be larger than the
  33 // number of items in the hash table, else there's trouble!!!
  34
  35 Hash_Table::Hash_Table (size_t s)
  36   : size_ (ACE_POW (s)),
  37     collisions_ (0)
  38 {
  39   if (this->size_ == 0)
  40     this->size_ = 1;
  41   ACE_NEW (this->table_,
  42            List_Node*[this->size_]);
  43   ACE_OS::memset ((char *) this->table_,
  44                   0,
  45                   this->size_ * sizeof *this->table_);
  46 }
  47
  48 Hash_Table::~Hash_Table ()
  49 {
  50   if (option[DEBUGGING])
  51     {
  52       size_t keysig_width = option.max_keysig_size () > ACE_OS::strlen ("keysig")
  53         ? option.max_keysig_size ()
  54         : ACE_OS::strlen ("keysig");
  55
  56       ACE_DEBUG ((LM_DEBUG,
  57                   "\ndumping the hash table\ntotal available table slots = %d, total bytes = %d, total collisions = %d\n"
  58                   "location, %*s, keyword\n",
  59                   this->size_,
  60                   this->size_ * (int) sizeof *this->table_,
  61                   this->collisions_,
  62                   keysig_width,
  63                   "keysig"));
  64
  65       for (int i = static_cast<int> (this->size_ - 1); i >= 0; i--)
  66         if (this->table_[i])
  67           ACE_DEBUG ((LM_DEBUG,
  68                       "%8d, %*s, %s\n",
  69                       i,
  70                       keysig_width,
  71                       this->table_[i]->keysig,
  72                       this->table_[i]->key));
  73       ACE_DEBUG ((LM_DEBUG,
  74                   "end dumping hash table\n\n"));
  75     }
  76
  77   delete [] this->table_;
  78 }
  79
  80 // If the ITEM is already in the hash table return the item found in
  81 // the table.  Otherwise inserts the ITEM, and returns FALSE.  Uses
  82 // double hashing.
  83
  84 List_Node *
  85 Hash_Table::find (List_Node *item,
  86                   int ignore_length)
  87 {
  88   size_t hash_val = ACE::hash_pjw (item->keysig);
  89   // The following works since the hash table size_ is always a power
  90   // of 2...
  91   size_t size = this->size_ - 1;
  92   size_t probe;
  93   size_t increment = ((hash_val ^ (ignore_length == 0 ? item->length : 0)) | 1) & size;
  94
  95   for (probe = hash_val & size;
  96        this->table_[probe]
  97          && (ACE_OS::strcmp (this->table_[probe]->keysig, item->keysig) != 0
  98              || (ignore_length == 0 && this->table_[probe]->length != item->length));
  99        probe = (probe + increment) & size)
 100     {
 101       ++this->collisions_;
 102     }
 103
 104   if (this->table_[probe])
 105     {
 106       return this->table_[probe];
 107     }
 108   else
 109     {
 110       this->table_[probe] = item;
 111       return 0;
 112     }
 113 }
 114