src/OpenFOAM/containers/HashTables/StaticHashTable/StaticHashTable.H

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright (C) 2004-2010 OpenCFD Ltd.
   6      \\/     M anipulation  |
   7 -------------------------------------------------------------------------------
   8 License
   9     This file is part of OpenFOAM.
  10
  11     OpenFOAM is free software: you can redistribute it and/or modify it
  12     under the terms of the GNU General Public License as published by
  13     the Free Software Foundation, either version 3 of the License, or
  14     (at your option) any later version.
  15
  16     OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
  17     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19     for more details.
  20
  21     You should have received a copy of the GNU General Public License
  22     along with OpenFOAM.  If not, see <http://www.gnu.org/licenses/>.
  23
  24 Class
  25     Foam::StaticHashTable
  26
  27 Description
  28     STL conforming hash table.
  29
  30 Note
  31     Uses straight lists as underlying type.
  32     Is slower to insert than the standard HashTable, but should be more
  33     memory efficient and faster to access.
  34
  35 SourceFiles
  36     StaticHashTableI.H
  37     StaticHashTable.C
  38     StaticHashTableIO.C
  39
  40 \*---------------------------------------------------------------------------*/
  41
  42 #ifndef StaticHashTable_H
  43 #define StaticHashTable_H
  44
  45 #include "label.H"
  46 #include "uLabel.H"
  47 #include "word.H"
  48 #include "Xfer.H"
  49 #include "className.H"
  50
  51 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
  52
  53 namespace Foam
  54 {
  55
  56 // Forward declaration of friend functions and operators
  57
  58 template<class T> class List;
  59 template<class T, class Key, class Hash> class StaticHashTable;
  60
  61 template<class T, class Key, class Hash> Istream& operator>>
  62 (
  63     Istream&,
  64     StaticHashTable<T, Key, Hash>&
  65 );
  66
  67 template<class T, class Key, class Hash> Ostream& operator<<
  68 (
  69     Ostream&,
  70     const StaticHashTable<T, Key, Hash>&
  71 );
  72
  73
  74 /*---------------------------------------------------------------------------*\
  75                      Class StaticHashTableCore Declaration
  76 \*---------------------------------------------------------------------------*/
  77
  78 //- Template-invariant bits for StaticHashTable
  79 struct StaticHashTableCore
  80 {
  81     //- Return a canonical (power-of-two) size
  82     static label canonicalSize(const label);
  83
  84     //- Construct null
  85     StaticHashTableCore()
  86     {}
  87
  88     //- Define template name and debug
  89     ClassName("StaticHashTable");
  90
  91     //- A zero-sized end iterator
  92     struct iteratorEnd
  93     {
  94         //- Construct null
  95         iteratorEnd()
  96         {}
  97     };
  98 };
  99
 100
 101
 102 /*---------------------------------------------------------------------------*\
 103                        Class StaticHashTable Declaration
 104 \*---------------------------------------------------------------------------*/
 105
 106 template<class T, class Key=word, class Hash=string::hash>
 107 class StaticHashTable
 108 :
 109     public StaticHashTableCore
 110 {
 111     // Private data type for table entries
 112
 113         //- The lookup keys, ordered per hash value
 114         List<List<Key> > keys_;
 115
 116         //- For each key the corresponding object.
 117         List<List<T> > objects_;
 118
 119         //- The current number of elements in table
 120         label nElmts_;
 121
 122         //- Return a canonical (power-of-two) size
 123         static label canonicalSize(const label);
 124
 125         //- Return the hash index of the Key within the current table size.
 126         //  No checks for zero-sized tables.
 127         inline label hashKeyIndex(const Key&) const;
 128
 129         //- Assign a new hashed entry to a possibly already existing key
 130         bool set(const Key&, const T& newElmt, bool protect);
 131
 132
 133 public:
 134
 135
 136     // Forward declaration of STL iterators
 137
 138         template<class TRef, class TableRef>
 139         class Iterator;
 140
 141         typedef Iterator
 142         <
 143             T&,
 144             StaticHashTable<T, Key, Hash>&
 145         > iterator;
 146
 147         typedef Iterator
 148         <
 149             const T&,
 150             const StaticHashTable<T, Key, Hash>&
 151         > const_iterator;
 152
 153
 154     // Declare friendship with the iterators
 155
 156         friend class Iterator
 157         <
 158             T&,
 159             StaticHashTable<T, Key, Hash>&
 160         >;
 161
 162         friend class Iterator
 163         <
 164             const T&,
 165             const StaticHashTable<T, Key, Hash>&
 166         >;
 167
 168
 169     // Constructors
 170
 171         //- Construct given initial table size
 172         StaticHashTable(const label size = 128);
 173
 174         //- Construct from Istream
 175         StaticHashTable(Istream&, const label size = 128);
 176
 177         //- Construct as copy
 178         StaticHashTable(const StaticHashTable<T, Key, Hash>&);
 179
 180         //- Construct by transferring the parameter contents
 181         StaticHashTable(const Xfer<StaticHashTable<T, Key, Hash> >&);
 182
 183
 184     //- Destructor
 185     ~StaticHashTable();
 186
 187
 188     // Member Functions
 189
 190         // Access
 191
 192             //- Return number of elements in table.
 193             inline label size() const;
 194
 195             //- Return true if the hash table is empty
 196             inline bool empty() const;
 197
 198             //- Return true if hashed entry is found in table
 199             bool found(const Key& key) const;
 200
 201             //- Find and return an iterator set at the hashed entry
 202             //  If not found iterator = end()
 203             iterator find(const Key& key);
 204
 205             //- Find and return an const_iterator set at the hashed entry
 206             //  If not found iterator = end()
 207             const_iterator find(const Key& key) const;
 208
 209             //- Return the table of contents
 210             List<Key> toc() const;
 211
 212             //- Print information
 213             Ostream& printInfo(Ostream&) const;
 214
 215
 216         // Edit
 217
 218             //- Insert a new hashed entry
 219             bool insert(const Key& key, const T& newElmt);
 220
 221             //- Assign a new hashed entry, overwriting existing entries
 222             inline bool set(const Key&, const T& newElmt);
 223
 224             //- Erase an hashed entry specified by given iterator
 225             bool erase(const iterator& it);
 226
 227             //- Erase an hashed entry specified by given key if in table
 228             bool erase(const Key& key);
 229
 230             //- Resize the hash table for efficiency
 231             void resize(const label newSize);
 232
 233             //- Remove entries in the given hash table from this hash table
 234             //  Return the number of elements removed
 235             label erase(const StaticHashTable<T, Key, Hash>&);
 236
 237             //- Clear all entries from table
 238             void clear();
 239
 240             //- Clear the table entries and the table itself.
 241             //  Equivalent to clear() followed by resize(1)
 242             void clearStorage();
 243
 244             //- Transfer the contents of the argument table into this table
 245             //  and annul the argument table.
 246             void transfer(StaticHashTable<T, Key, Hash>&);
 247
 248             //- Transfer contents to the Xfer container
 249             inline Xfer<StaticHashTable<T, Key, Hash> > xfer();
 250
 251
 252     // Member Operators
 253
 254         //- Find and return an hashed entry
 255         inline T& operator[](const Key&);
 256
 257         //- Find and return an hashed entry
 258         inline const T& operator[](const Key&) const;
 259
 260         //- Find and return an hashed entry, create it null if not present.
 261         inline T& operator()(const Key&);
 262
 263         //- Assignment
 264         void operator=(const StaticHashTable<T, Key, Hash>&);
 265
 266         //- Equality. Two hash tables are equal if all contents of first are
 267         //  also in second and vice versa.
 268         bool operator==(const StaticHashTable<T, Key, Hash>&) const;
 269
 270         //- The opposite of the equality operation.
 271         bool operator!=(const StaticHashTable<T, Key, Hash>&) const;
 272
 273
 274     // STL type definitions
 275
 276         //- Type of values the StaticHashTable contains.
 277         typedef T value_type;
 278
 279         //- Type that can be used for storing into StaticHashTable::value_type
 280         //  objects.  This type is usually List::value_type&.
 281         typedef T& reference;
 282
 283         //- Type that can be used for storing into constant
 284         //  StaticHashTable::value_type objects.  This type is usually const
 285         //  StaticHashTable::value_type&.
 286         typedef const T& const_reference;
 287
 288         //- The type that can represent the size of a StaticHashTable.
 289         typedef label size_type;
 290
 291
 292     // STL iterator
 293
 294         //- An STL iterator
 295         template<class TRef, class TableRef>
 296         class Iterator
 297         {
 298             friend class StaticHashTable;
 299
 300 #           ifndef __INTEL_COMPILER
 301             template<class TRef2, class TableRef2>
 302             friend class Iterator;
 303 #           endif
 304
 305             // Private data
 306
 307                 //- Reference to the StaticHashTable this is an iterator for
 308                 TableRef hashTable_;
 309
 310                 //- Current hash index
 311                 label hashIndex_;
 312
 313                 //- Index of current element at hashIndex
 314                 label elemIndex_;
 315
 316
 317         public:
 318
 319             // Constructors
 320
 321                 //- Construct from hash table, hash index and element index
 322                 inline Iterator
 323                 (
 324                     TableRef,
 325                     label hashIndex_,
 326                     label elemIndex_
 327                 );
 328
 329                 //- Construct from the non-const iterator
 330                 inline Iterator(const iterator&);
 331
 332
 333             // Member operators
 334
 335                 inline void operator=(const iterator&);
 336
 337                 inline bool operator==(const iterator&) const;
 338                 inline bool operator==(const const_iterator&) const;
 339
 340                 inline bool operator!=(const iterator&) const;
 341                 inline bool operator!=(const const_iterator&) const;
 342
 343                 inline TRef operator*();
 344                 inline TRef operator()();
 345
 346                 inline Iterator& operator++();
 347                 inline Iterator operator++(int);
 348
 349                 inline const Key& key() const;
 350         };
 351
 352
 353         //- iterator set to the beginning of the StaticHashTable
 354         inline iterator begin();
 355
 356         //- iterator set to beyond the end of the StaticHashTable
 357         inline const iterator& end();
 358
 359         //- const_iterator set to the beginning of the StaticHashTable
 360         inline const_iterator cbegin() const;
 361
 362         //- const_iterator set to beyond the end of the StaticHashTable
 363         inline const const_iterator& cend() const;
 364
 365         //- const_iterator set to the beginning of the StaticHashTable
 366         inline const_iterator begin() const;
 367
 368         //- const_iterator set to beyond the end of the StaticHashTable
 369         inline const const_iterator& end() const;
 370
 371     // IOstream Operator
 372
 373         friend Istream& operator>> <T, Key, Hash>
 374         (
 375             Istream&,
 376             StaticHashTable<T, Key, Hash>&
 377         );
 378
 379         friend Ostream& operator<< <T, Key, Hash>
 380         (
 381             Ostream&,
 382             const StaticHashTable<T, Key, Hash>&
 383         );
 384
 385
 386 private:
 387
 388         //- iterator returned by end()
 389         iterator endIter_;
 390
 391         //- const_iterator returned by end()
 392         const_iterator endConstIter_;
 393 };
 394
 395
 396 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 397
 398 } // End namespace Foam
 399
 400 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 401
 402 #   include "StaticHashTableI.H"
 403
 404 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 405
 406 #ifndef NoStaticHashTableC
 407 #ifdef NoRepository
 408 #   include "StaticHashTable.C"
 409 #endif
 410 #endif
 411
 412 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 413
 414 #endif
 415
 416 // ************************************************************************* //