cde/programs/dtinfo/dtinfo/src/Basic/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  * $XConsortium: HashTable.cc /main/3 1996/06/11 16:18:45 cde-hal $
  25  *
  26  * Copyright (c) 1991 HaL Computer Systems, Inc.  All rights reserved.
  27  * UNPUBLISHED -- rights reserved under the Copyright Laws of the United
  28  * States.  Use of a copyright notice is precautionary only and does not
  29  * imply publication or disclosure.
  30  *
  31  * This software contains confidential information and trade secrets of HaL
  32  * Computer Systems, Inc.  Use, disclosure, or reproduction is prohibited
  33  * without the prior express written permission of HaL Computer Systems, Inc.
  34  *
  35  *                         RESTRICTED RIGHTS LEGEND
  36  * Use, duplication, or disclosure by the Government is subject to
  37  * restrictions as set forth in subparagraph (c)(l)(ii) of the Rights in
  38  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  39  *                        HaL Computer Systems, Inc.
  40  *                  1315 Dell Avenue, Campbell, CA  95008
  41  *
  42  */
  43
  44 #define C_StringHash
  45 #define C_HashTable
  46 #define C_List
  47 #define L_Basic
  48 #include <Prelude.h>
  49
  50 #include <string.h>
  51
  52 class HashObject
  53 {
  54   public:
  55     HashObject(const char *key, FolioObject *object);
  56     ~HashObject();
  57
  58     FolioObject *object();
  59
  60     const char *key();
  61
  62 private:
  63     char        *f_key ;
  64     FolioObject *f_object ;
  65 };
  66
  67
  68 inline FolioObject *
  69 HashObject::object()
  70 {
  71     return f_object;
  72 }
  73
  74 HashObject::HashObject(const char *key, FolioObject *object)
  75 : f_object(object)
  76 {
  77     assert(key != NULL);
  78     assert(object != NULL);
  79
  80     int len = strlen(key);
  81     f_key = new char[len + 1] ;
  82     *((char *) memcpy(f_key, key, len) + len) = '\0';
  83 }
  84
  85 HashObject::~HashObject()
  86 {
  87     // NOTE: this is virtual, don't make it inline
  88     assert(f_key != NULL);
  89     delete f_key ;
  90     delete f_object ;           // delete the object
  91 }
  92
  93 inline const char *
  94 HashObject::key()
  95 {
  96     return f_key ;
  97 }
  98
  99 HashTable::~HashTable()
 100 {
 101   ON_DEBUG(cerr << "~HashTable" << endl);
 102   for (int i = 0 ; i < HASH_TABLE_SIZE; i++)
 103     if (f_table[i] != NULL)
 104       {
 105         List_Iterator<HashObject *> cursor(f_table[i]);
 106         while (cursor)
 107           {
 108             delete cursor.item();
 109             f_table[i]->remove(cursor);
 110           }
 111         delete f_table[i] ;
 112       }
 113 }
 114
 115 HashTable::HashTable()
 116 {
 117   for (int i = 0 ; i < HASH_TABLE_SIZE; i++)
 118     f_table[i] = 0 ;
 119 }
 120
 121 void
 122 HashTable::add(const char *key, FolioObject *object)
 123 {
 124     int position = hash(key) ;
 125
 126 //    ON_DEBUG(cerr << "HashTable add " << key << " ==> " << position << endl;);
 127
 128     HashObject *hash_object = new HashObject(key, object);
 129
 130     assert(hash_object != NULL);
 131
 132     if (f_table[position] == NULL)
 133       {
 134         f_table[position] = new xList<HashObject *> ;
 135       }
 136
 137     f_table[position]->insert(hash_object);
 138
 139 }
 140
 141
 142 void *
 143 HashTable::find(const char *key)
 144 {
 145     unsigned int position = hash(key);
 146
 147 //    ON_DEBUG(cerr << "Hash Table find " << key << " ==> " << position << endl);
 148
 149     void *rvalue = NULL ;
 150
 151     if (f_table[position] != NULL)
 152       {
 153         List_Iterator<HashObject *> cursor(f_table[position]);
 154
 155         for (; cursor; cursor++)
 156           if (!strcmp(cursor.item()->key(), key))
 157             {
 158               rvalue =  cursor.item()->object();
 159               break;
 160             }
 161       }
 162     return rvalue ;
 163 }
 164
 165 unsigned int
 166 HashTable::hash (const char *key)
 167 {
 168     return string_hash(key) % HASH_TABLE_SIZE;
 169 }