cde/programs/dtmail/libDtMail/Common/HashTable.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*
  24  *+SNOTICE
  25  *
  26  *
  27  *      $XConsortium: HashTable.C /main/3 1995/11/06 16:37:14 rswiston $
  28  *
  29  *      RESTRICTED CONFIDENTIAL INFORMATION:
  30  *
  31  *      The information in this document is subject to special
  32  *      restrictions in a confidential disclosure agreement bertween
  33  *      HP, IBM, Sun, USL, SCO and Univel.  Do not distribute this
  34  *      document outside HP, IBM, Sun, USL, SCO, or Univel wihtout
  35  *      Sun's specific written approval.  This documment and all copies
  36  *      and derivative works thereof must be returned or destroyed at
  37  *      Sun's request.
  38  *
  39  *      Copyright 1993 Sun Microsystems, Inc.  All rights reserved.
  40  *
  41  *+ENOTICE
  42  */
  43
  44 #ifndef I_HAVE_NO_IDENT
  45 #endif
  46
  47 #include <string.h>
  48 #include <DtMail/HashTable.hh>
  49
  50 HashTableImpl::HashTableImpl(int table_size)
  51 {
  52     _table_size = table_size;
  53     _hash_table = new HashEntry[table_size];
  54     memset(_hash_table, 0, table_size * sizeof(HashEntry));
  55 }
  56
  57 HashTableImpl::~HashTableImpl(void)
  58 {
  59   // Scan the entire hash table, deleting all keys and chains, and
  60   // eventually delete the hash table itself
  61   //
  62   for (int slot = 0; slot < _table_size; slot++) {
  63     if (_hash_table[slot].key != NULL) {
  64       HashEntry * chain;
  65       HashEntry * chainHead;
  66       for (chainHead = chain = &_hash_table[slot]; chain; chain = chain->next) {
  67         if (chain->key)
  68           delete chain->key;
  69         if (chain != chainHead)
  70           delete chain;
  71       }
  72     }
  73   }
  74   delete _hash_table;
  75 }
  76
  77 void *
  78 HashTableImpl::lookup(ObjectKey & key)
  79 {
  80     short hash_key = key.hashValue();
  81
  82     int slot = hash_key % _table_size;
  83
  84     // Search the slot looking for the value. Return NULL if there
  85     // are no objects matching this key.
  86     //
  87     for (HashEntry * chain = &_hash_table[slot]; chain; chain = chain->next) {
  88         if (chain->key && key == *(chain->key)) {
  89             break;
  90         }
  91     }
  92
  93     if (chain) {
  94         return(chain->value);
  95     }
  96
  97     return(NULL);
  98 }
  99
 100 void
 101 HashTableImpl::set(ObjectKey & key, void * value)
 102 {
 103     short hash_key = key.hashValue();
 104     int slot = hash_key % _table_size;
 105
 106     // See if we have already filled the slot.
 107     //
 108     if (_hash_table[slot].key == NULL) {
 109         // Simple, put it in the slot.
 110         //
 111         _hash_table[slot].key = &key;
 112         _hash_table[slot].value = value;
 113         return;
 114     }
 115
 116     // We either have a collision or a duplicate. In the case of duplicates
 117     // we simply replace the value.
 118     //
 119     for (HashEntry * chain = &_hash_table[slot]; chain->next; chain = chain->next) {
 120         // If this item is already stored then update the value.
 121         //
 122         if (key == *(chain->key)) {
 123             chain->value = value;
 124             return;
 125         }
 126     }
 127
 128     HashEntry * new_ent = new HashEntry;
 129     new_ent->key = &key;
 130     new_ent->value = value;
 131     new_ent->next = NULL;
 132
 133     chain->next = new_ent;
 134 }
 135
 136 void *
 137 HashTableImpl::remove(ObjectKey & key)
 138 {
 139     short hash_val = key.hashValue();
 140     int slot = hash_val % _table_size;
 141     void * removed_val = NULL;
 142
 143     // See if we even have this object.
 144     //
 145     if (!_hash_table[slot].key) {
 146         // Obviously not.
 147         //
 148         return(removed_val);
 149     }
 150
 151     // Try to find it in the chain.
 152     //
 153     HashEntry * last = NULL;
 154     for (HashEntry * chain = &_hash_table[slot]; chain; chain = chain->next) {
 155         if (key == *(chain->key)) {
 156             break;
 157         }
 158         last = chain;
 159     }
 160
 161     if (!chain) { // Not found
 162         return(removed_val);
 163     }
 164
 165     if (last) {
 166         last->next = chain->next;
 167         delete chain->key;
 168         removed_val = chain->value;
 169         delete chain;
 170     }
 171     else {
 172         // This is the first entry. In this case we copy the next entry
 173         // into this memory and through away the next item. If we have
 174         // no next, then simply zero the slot.
 175         //
 176         removed_val = chain->value;
 177         delete chain->key;
 178         if (chain->next) {
 179             *chain = *(chain->next);
 180             delete chain->next;
 181         }
 182         else {
 183             memset(chain, 0, sizeof(HashEntry));
 184         }
 185     }
 186     return(removed_val);
 187 }
 188
 189 #if !defined(HPUX) && !defined(__uxp__)
 190 void
 191 HashTableImpl::forEach(HashImplIterator iterator, void * client_data)
 192 {
 193     // Scan the entire hash table, passing valid entries to the
 194     // iterator.
 195     //
 196     for (int slot = 0; slot < _table_size; slot++) {
 197         if (_hash_table[slot].key == NULL) {
 198             continue;
 199         }
 200
 201         for (HashEntry * chain = &_hash_table[slot]; chain; chain = chain->next) {
 202             int cont = 0;
 203             cont = iterator(*chain->key, chain->value, client_data);
 204             if (!cont) {
 205                 return;
 206             }
 207         }
 208     }
 209 }
 210 #endif