OpenFOAM logo
Open Source CFD Toolkit

HashTable.H

Go to the documentation of this file.
00001 /*---------------------------------------------------------------------------*\
00002   =========                 |
00003   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
00004    \\    /   O peration     |
00005     \\  /    A nd           | Copyright (C) 1991-2005 OpenCFD Ltd.
00006      \\/     M anipulation  |
00007 -------------------------------------------------------------------------------
00008 License
00009     This file is part of OpenFOAM.
00010 
00011     OpenFOAM is free software; you can redistribute it and/or modify it
00012     under the terms of the GNU General Public License as published by the
00013     Free Software Foundation; either version 2 of the License, or (at your
00014     option) any later version.
00015 
00016     OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
00017     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00018     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
00019     for more details.
00020 
00021     You should have received a copy of the GNU General Public License
00022     along with OpenFOAM; if not, write to the Free Software Foundation,
00023     Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
00024 
00025 Class
00026     HashTable
00027 
00028 Description
00029     STL conforming hash table.
00030 
00031 SourceFiles
00032     HashTableI.H
00033     HashTable.C
00034     HashTableIO.C
00035 
00036 \*---------------------------------------------------------------------------*/
00037 
00038 #ifndef HashTable_H
00039 #define HashTable_H
00040 
00041 #include "label.H"
00042 #include "word.H"
00043 #include "className.H"
00044 
00045 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00046 
00047 namespace Foam
00048 {
00049 
00050 // * * * * * * Forward declaration of template friend fuctions * * * * * * * //
00051 
00052 template<class T>
00053 class List;
00054 
00055 template<class T, class Key, class Hash> class HashTable;
00056 
00057 template<class T, class Key, class Hash> Istream& operator>>
00058 (
00059     Istream&,
00060     HashTable<T, Key, Hash>&
00061 );
00062 
00063 template<class T, class Key, class Hash> Ostream& operator<<
00064 (
00065     Ostream&,
00066     const HashTable<T, Key, Hash>&
00067 );
00068 
00069 
00070 /*---------------------------------------------------------------------------*\
00071                         Class HashTableName Declaration
00072 \*---------------------------------------------------------------------------*/
00073 
00074 TemplateName(HashTable);
00075 
00076 
00077 /*---------------------------------------------------------------------------*\
00078                           Class HashTable Declaration
00079 \*---------------------------------------------------------------------------*/
00080 
00081 template<class T, class Key=word, class Hash=string::hash>
00082 class HashTable
00083 :
00084     public HashTableName
00085 {
00086     // Private data type for table entries
00087 
00088         struct hashedEntry
00089         {
00090             //- The lookup key
00091             Key key_;
00092 
00093             //- Pointer to next hashedEntry in sub-list
00094             hashedEntry* next_;
00095 
00096             //- The data object
00097             T obj_;
00098 
00099             //- Constructors
00100 
00101                 //- Construct given key, next pointer and object
00102                 inline hashedEntry
00103                 (
00104                     const Key& key,
00105                     hashedEntry* next,
00106                     const T& newEntry
00107                 );
00108 
00109                 //- Dissallow construction as copy
00110                 hashedEntry(const hashedEntry&);
00111         };
00112 
00113 
00114     // Private data: size of table, the table and current number of elements
00115 
00116         //- Number of primary entries allocated in table (not necessarily used)
00117         label tableSize_;
00118 
00119         //- The table of primary entries
00120         hashedEntry** table_;
00121 
00122         //- The current number of elements in table
00123         label nElmts_;
00124 
00125 
00126 public:
00127 
00128         //- Declare friendship with the HashPtrTable class
00129         template<class T2, class Key2, class Hash2>
00130         friend class HashPtrTable;
00131 
00132 
00133     // Forward declaration of STL iterators
00134 
00135         template<class TRef, class TableRef, class HashedEntryPtr>
00136         class Iterator;
00137 
00138         typedef Iterator
00139         <
00140             T&,
00141             HashTable<T, Key, Hash>&,
00142             hashedEntry*
00143         > iterator;
00144 
00145         typedef Iterator
00146         <
00147             const T&,
00148             const HashTable<T, Key, Hash>&,
00149             const hashedEntry*
00150         > const_iterator;
00151 
00152 
00153     // Declare friendship with the iterators
00154 
00155         friend class Iterator
00156         <
00157             T&,
00158             HashTable<T, Key, Hash>&,
00159             hashedEntry*
00160         >;
00161 
00162         friend class Iterator
00163         <
00164             const T&,
00165             const HashTable<T, Key, Hash>&,
00166             const hashedEntry*
00167         >;
00168 
00169 
00170     // Constructors
00171 
00172         //- Construct given initial table size
00173         HashTable(const label size = 100);
00174 
00175         //- Construct from Istream
00176         HashTable(Istream&, const label size = 100);
00177 
00178         //- Construct as copy
00179         HashTable(const HashTable<T, Key, Hash>&);
00180 
00181 
00182     // Destructor
00183 
00184         ~HashTable();
00185 
00186 
00187     // Member Functions
00188 
00189         // Access
00190 
00191             //- Return number of elements in table.
00192             inline label size() const;
00193 
00194             //- Return true if hashedEntry is found in table
00195             bool found(const Key& key) const;
00196 
00197             //- Find and return an iterator set at the hashedEntry
00198             //  If not found iterator = end()
00199             iterator find(const Key& key);
00200 
00201             //- Find and return an const_iterator set at the hashedEntry
00202             //  If not found iterator = end()
00203             const_iterator find(const Key& key) const;
00204 
00205             //- Return the table of contents
00206             List<Key> toc() const;
00207 
00208 
00209         // Edit
00210 
00211             //- Insert a new hashedEntry
00212             bool insert(const Key& key, const T& newElmt);
00213 
00214             //- Erase an hashedEntry specified by given iterator
00215             bool erase(const iterator& it);
00216 
00217             //- Erase an hashedEntry specified by given key if in table
00218             bool erase(const Key& key);
00219 
00220             //- Resize the hash table for efficiency
00221             void resize(const label newSize);
00222 
00223             //- Clear all entries from table
00224             void clear();
00225 
00226             //- Transfer the contents of the argument table into this table
00227             //  and annull the argument table.
00228             void transfer(HashTable<T, Key, Hash>&);
00229 
00230 
00231     // Member Operators
00232 
00233         //- Find and return an hashedEntry
00234         inline T& operator[](const Key& key);
00235 
00236         //- Find and return an hashedEntry
00237         inline const T& operator[](const Key& key) const;
00238 
00239         //- Assignment
00240         void operator=(const HashTable<T, Key, Hash>&);
00241 
00242 
00243     // STL type definitions
00244 
00245         //- Type of values the HashTable contains.
00246         typedef T value_type;
00247 
00248         //- Type that can be used for storing into HashTable::value_type
00249         //  objects.  This type is usually List::value_type&.
00250         typedef T& reference;
00251 
00252         //- Type that can be used for storing into constant
00253         //  HashTable::value_type objects.  This type is usually const
00254         //  HashTable::value_type&.
00255         typedef const T& const_reference;
00256 
00257         //- The type that can represent the size of a HashTable.
00258         typedef label size_type;
00259 
00260 
00261     // STL iterator
00262 
00263         template<class TRef, class TableRef, class HashedEntryPtr>
00264         class Iterator
00265         {
00266             friend class HashTable;
00267 
00268 #           ifndef __INTEL_COMPILER
00269             template<class TRef2, class TableRef2, class HashedEntryPtr2>
00270             friend class Iterator;
00271 #           endif
00272 
00273             // Private data
00274 
00275                 //- Reference to the HashTable this is an iterator for
00276                 TableRef curHashTable_;
00277 
00278                 //- Current element
00279                 HashedEntryPtr elmtPtr_;
00280 
00281                 //- Previous element
00282                 HashedEntryPtr prevElmtPtr_;
00283 
00284                 //- Current hash index
00285                 label hashIndex_;
00286 
00287 
00288         public:
00289 
00290             // Constructors
00291 
00292                 //- Construct from hash table, element and hash index
00293                 inline Iterator
00294                 (
00295                     TableRef curHashTable,
00296                     HashedEntryPtr elmt,
00297                     HashedEntryPtr prev,
00298                     label hashIndex
00299                 );
00300 
00301                 //- Construct from the non-const iterator
00302                 inline Iterator(const iterator&);
00303 
00304 
00305             // Member operators
00306 
00307                 inline void operator=(const iterator& iter);
00308 
00309                 inline bool operator==(const iterator& iter) const;
00310                 inline bool operator==(const const_iterator& iter) const;
00311 
00312                 inline bool operator!=(const iterator& iter) const;
00313                 inline bool operator!=(const const_iterator& iter) const;
00314 
00315                 inline TRef operator*();
00316                 inline TRef operator()();
00317 
00318                 inline Iterator& operator++();
00319                 inline Iterator operator++(int);
00320 
00321                 inline const Key& key();
00322         };
00323 
00324 
00325         //- iterator set to the begining of the HashTable
00326         inline iterator begin();
00327 
00328         //- iterator set to beyond the end of the HashTable
00329         inline const iterator& end();
00330 
00331         //- const_iterator set to the begining of the HashTable
00332         inline const_iterator begin() const;
00333 
00334         //- const_iterator set to beyond the end of the HashTable
00335         inline const const_iterator& end() const;
00336 
00337 
00338     // IOstream Operator
00339 
00340         friend Istream& operator>> <T, Key, Hash>
00341         (
00342             Istream&,
00343             HashTable<T, Key, Hash>&
00344         );
00345 
00346         friend Ostream& operator<< <T, Key, Hash>
00347         (
00348             Ostream&,
00349             const HashTable<T, Key, Hash>&
00350         );
00351 
00352 
00353 private:
00354 
00355         //- iterator returned by end()
00356         iterator endIter_;
00357 
00358         //- const_iterator returned by end()
00359         const_iterator endConstIter_;
00360 };
00361 
00362 
00363 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00364 
00365 } // End namespace Foam
00366 
00367 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00368 
00369 #   include "HashTableI.H"
00370 
00371 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00372 
00373 #ifndef NoHashTableC
00374 #ifdef NoRepository
00375 #   include "HashTable.C"
00376 #endif
00377 #endif
00378 
00379 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00380 
00381 #endif
00382 
00383 // ************************************************************************* //
For further information go to www.openfoam.org