2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
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)
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
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
27 * $XConsortium: HashTable.C /main/3 1995/11/06 16:37:14 rswiston $
29 * RESTRICTED CONFIDENTIAL INFORMATION:
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
39 * Copyright 1993 Sun Microsystems, Inc. All rights reserved.
44 #ifndef I_HAVE_NO_IDENT
48 #include <DtMail/HashTable.hh>
50 HashTableImpl::HashTableImpl(int table_size)
52 _table_size = table_size;
53 _hash_table = new HashEntry[table_size];
54 memset(_hash_table, 0, table_size * sizeof(HashEntry));
57 HashTableImpl::~HashTableImpl(void)
59 // Scan the entire hash table, deleting all keys and chains, and
60 // eventually delete the hash table itself
62 for (int slot = 0; slot < _table_size; slot++) {
63 if (_hash_table[slot].key != NULL) {
65 HashEntry * chainHead;
66 for (chainHead = chain = &_hash_table[slot]; chain; chain = chain->next) {
69 if (chain != chainHead)
78 HashTableImpl::lookup(ObjectKey & key)
80 short hash_key = key.hashValue();
82 int slot = hash_key % _table_size;
84 // Search the slot looking for the value. Return NULL if there
85 // are no objects matching this key.
87 for (HashEntry * chain = &_hash_table[slot]; chain; chain = chain->next) {
88 if (chain->key && key == *(chain->key)) {
101 HashTableImpl::set(ObjectKey & key, void * value)
103 short hash_key = key.hashValue();
104 int slot = hash_key % _table_size;
106 // See if we have already filled the slot.
108 if (_hash_table[slot].key == NULL) {
109 // Simple, put it in the slot.
111 _hash_table[slot].key = &key;
112 _hash_table[slot].value = value;
116 // We either have a collision or a duplicate. In the case of duplicates
117 // we simply replace the value.
119 for (HashEntry * chain = &_hash_table[slot]; chain->next; chain = chain->next) {
120 // If this item is already stored then update the value.
122 if (key == *(chain->key)) {
123 chain->value = value;
128 HashEntry * new_ent = new HashEntry;
130 new_ent->value = value;
131 new_ent->next = NULL;
133 chain->next = new_ent;
137 HashTableImpl::remove(ObjectKey & key)
139 short hash_val = key.hashValue();
140 int slot = hash_val % _table_size;
141 void * removed_val = NULL;
143 // See if we even have this object.
145 if (!_hash_table[slot].key) {
151 // Try to find it in the chain.
153 HashEntry * last = NULL;
154 for (HashEntry * chain = &_hash_table[slot]; chain; chain = chain->next) {
155 if (key == *(chain->key)) {
161 if (!chain) { // Not found
166 last->next = chain->next;
168 removed_val = chain->value;
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.
176 removed_val = chain->value;
179 *chain = *(chain->next);
183 memset(chain, 0, sizeof(HashEntry));
189 #if !defined(HPUX) && !defined(__uxp__)
191 HashTableImpl::forEach(HashImplIterator iterator, void * client_data)
193 // Scan the entire hash table, passing valid entries to the
196 for (int slot = 0; slot < _table_size; slot++) {
197 if (_hash_table[slot].key == NULL) {
201 for (HashEntry * chain = &_hash_table[slot]; chain; chain = chain->next) {
203 cont = iterator(*chain->key, chain->value, client_data);