HashTable.H 16.6 KB
Newer Older
Henry's avatar
Henry committed
1
2
3
4
/*---------------------------------------------------------------------------*\
  =========                 |
  \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   \\    /   O peration     |
5
    \\  /    A nd           | Copyright (C) 2011-2016 OpenFOAM Foundation
Henry's avatar
Henry committed
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
     \\/     M anipulation  |
-------------------------------------------------------------------------------
License
    This file is part of OpenFOAM.

    OpenFOAM is free software: you can redistribute it and/or modify it
    under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
    for more details.

    You should have received a copy of the GNU General Public License
    along with OpenFOAM.  If not, see <http://www.gnu.org/licenses/>.

Class
    Foam::HashTable

Description
    An STL-conforming hash table.

Note
    Hashing index collisions are handled via chaining using a singly-linked
    list with the colliding entry being added to the head of the linked
    list. Thus copying the hash table (or indeed even resizing it) will
    often result in a different hash order. Use a sorted table-of-contents
    when the hash order is important.

SourceFiles
    HashTableI.H
    HashTable.C
    HashTableIO.C

\*---------------------------------------------------------------------------*/

#ifndef HashTable_H
#define HashTable_H

#include "label.H"
#include "uLabel.H"
#include "word.H"
#include "Xfer.H"
#include "className.H"
52
#include <initializer_list>
Henry's avatar
Henry committed
53
54
55
56
57
58
59
60
61
62
63
64
65

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

namespace Foam
{

// Forward declaration of friend functions and operators

template<class T> class List;
template<class T> class UList;
template<class T, class Key, class Hash> class HashTable;
template<class T, class Key, class Hash> class HashPtrTable;

66
67
68
template<class Type1, class Type2>
class Tuple2;

Henry's avatar
Henry committed
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
template<class T, class Key, class Hash>
Istream& operator>>(Istream&, HashTable<T, Key, Hash>&);

template<class T, class Key, class Hash>
Ostream& operator<<(Ostream&, const HashTable<T, Key, Hash>&);


/*---------------------------------------------------------------------------*\
                         Class HashTableCore Declaration
\*---------------------------------------------------------------------------*/

//- Template-invariant bits for HashTable
struct HashTableCore
{
    //- Return a canonical (power-of-two) size
    static label canonicalSize(const label);

    //- Maximum allowable table size
    static const label maxTableSize;

    //- Construct null
    HashTableCore()
    {}

    //- Define template name and debug
    ClassName("HashTable");

    //- A zero-sized end iterator
    struct iteratorEnd
    {
        //- Construct null
        iteratorEnd()
        {}
    };

    //- iteratorEnd set to beyond the end of any HashTable
    inline static iteratorEnd cend()
    {
        return iteratorEnd();
    }

    //- iteratorEnd set to beyond the end of any HashTable
    inline static iteratorEnd end()
    {
        return iteratorEnd();
    }
};


/*---------------------------------------------------------------------------*\
                           Class HashTable Declaration
\*---------------------------------------------------------------------------*/

template<class T, class Key=word, class Hash=string::hash>
class HashTable
:
    public HashTableCore
{
    // Private data type for table entries

        //- Structure to hold a hashed entry with SLList for collisions
        struct hashedEntry
        {
            //- The lookup key
            Key key_;

            //- Pointer to next hashedEntry in sub-list
            hashedEntry* next_;

            //- The data object
            T obj_;

            //- Construct from key, next pointer and object
            inline hashedEntry(const Key&, hashedEntry* next, const T&);


        private:
            //- Disallow default bitwise copy construct
            hashedEntry(const hashedEntry&);

            //- Disallow default bitwise assignment
            void operator=(const hashedEntry&);
        };


    // Private data: size of table, the table and current number of elements

        //- The current number of elements in table
        label nElmts_;

        //- Number of primary entries allocated in table
        label tableSize_;

        //- The table of primary entries
        hashedEntry** table_;


    // Private Member Functions

        //- Return a canonical (power-of-two) size
        static label canonicalSize(const label);

        //- Return the hash index of the Key within the current table size.
        //  No checks for zero-sized tables.
        inline label hashKeyIndex(const Key&) const;

        //- Assign a new hashedEntry to a possibly already existing key
        bool set(const Key&, const T& newElmt, bool protect);

178

Henry's avatar
Henry committed
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
public:

    // Forward declaration of iterators

        class iteratorBase;
        class iterator;
        class const_iterator;

        //- Declare friendship with the HashPtrTable class
        template<class T2, class Key2, class Hash2>
        friend class HashPtrTable;

        //- Declare friendship with the iteratorBase
        friend class iteratorBase;

        //- Declare friendship with the iterator
        friend class iterator;

        //- Declare friendship with the const_iterator
        friend class const_iterator;


    // Constructors

        //- Construct given initial table size
        HashTable(const label size = 128);

        //- Construct from Istream
        HashTable(Istream&, const label size = 128);

        //- Construct as copy
        HashTable(const HashTable<T, Key, Hash>&);

        //- Construct by transferring the parameter contents
213
        HashTable(const Xfer<HashTable<T, Key, Hash>>&);
Henry's avatar
Henry committed
214

215
        //- Construct from an initializer list
216
        HashTable(std::initializer_list<Tuple2<Key, T>>);
217

Henry's avatar
Henry committed
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300

    //- Destructor
    ~HashTable();


    // Member Functions

        // Access

            //- The size of the underlying table
            inline label capacity() const;

            //- Return number of elements in table
            inline label size() const;

            //- Return true if the hash table is empty
            inline bool empty() const;

            //- Return true if hashedEntry is found in table
            bool found(const Key&) const;

            //- Find and return an iterator set at the hashedEntry
            //  If not found iterator = end()
            iterator find(const Key&);

            //- Find and return an const_iterator set at the hashedEntry
            //  If not found iterator = end()
            const_iterator find(const Key&) const;

            //- Return the table of contents
            List<Key> toc() const;

            //- Return the table of contents as a sorted list
            List<Key> sortedToc() const;

            //- Print information
            Ostream& printInfo(Ostream&) const;


        // Edit

            //- Insert a new hashedEntry
            inline bool insert(const Key&, const T& newElmt);

            //- Assign a new hashedEntry, overwriting existing entries
            inline bool set(const Key&, const T& newElmt);

            //- Erase a hashedEntry specified by given iterator
            //  This invalidates the iterator until the next operator++
            bool erase(const iterator&);

            //- Erase a hashedEntry specified by the given key
            bool erase(const Key&);

            //- Remove entries given by the listed keys from this HashTable
            //  Return the number of elements removed
            label erase(const UList<Key>&);

            //- Remove entries given by the given keys from this HashTable
            //  Return the number of elements removed.
            //  The parameter HashTable needs the same type of key, but the
            //  type of values held and the hashing function are arbitrary.
            template<class AnyType, class AnyHash>
            label erase(const HashTable<AnyType, Key, AnyHash>&);

            //- Resize the hash table for efficiency
            void resize(const label newSize);

            //- Clear all entries from table
            void clear();

            //- Clear the table entries and the table itself.
            //  Equivalent to clear() followed by resize(0)
            void clearStorage();

            //- Shrink the allocated table to approx. twice number of elements
            void shrink();

            //- Transfer the contents of the argument table into this table
            //  and annul the argument table.
            void transfer(HashTable<T, Key, Hash>&);

            //- Transfer contents to the Xfer container
301
            inline Xfer<HashTable<T, Key, Hash>> xfer();
Henry's avatar
Henry committed
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317


    // Member Operators

        //- Find and return a hashedEntry
        inline T& operator[](const Key&);

        //- Find and return a hashedEntry
        inline const T& operator[](const Key&) const;

        //- Find and return a hashedEntry, create it null if not present
        inline T& operator()(const Key&);

        //- Assignment
        void operator=(const HashTable<T, Key, Hash>&);

318
319
320
        //- Assignment to an initializer list
        void operator=(std::initializer_list<Tuple2<Key, T>>);

Henry's avatar
Henry committed
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
        //- Equality. Hash tables are equal if the keys and values are equal.
        //  Independent of table storage size and table order.
        bool operator==(const HashTable<T, Key, Hash>&) const;

        //- The opposite of the equality operation. Takes linear time.
        bool operator!=(const HashTable<T, Key, Hash>&) const;



    // STL type definitions

        //- Type of values the HashTable contains.
        typedef T value_type;

        //- Type that can be used for storing into HashTable::value_type
        //  objects.  This type is usually List::value_type&.
        typedef T& reference;

        //- Type that can be used for storing into constant
        //  HashTable::value_type objects.  This type is usually const
        //  HashTable::value_type&.
        typedef const T& const_reference;

        //- The type that can represent the size of a HashTable.
        typedef label size_type;


    // Iterators and helpers

        //- The iterator base for HashTable
        //  Note: data and functions are protected, to allow reuse by iterator
        //  and prevent most external usage.
        //  iterator and const_iterator have the same size, allowing
        //  us to reinterpret_cast between them (if desired)
        class iteratorBase
        {
            // Private Data

                //- Pointer to the HashTable for which this is an iterator
                //  This also lets us use the default bitwise copy/assignment
                HashTable<T, Key, Hash>* hashTable_;

                //- Current element
                hashedEntry* entryPtr_;

                //- Current hash index
                label hashIndex_;


        protected:

            // Constructors

                //- Construct null - equivalent to an 'end' position
                inline iteratorBase();

                //- Construct from hash table, moving to its 'begin' position
                inline explicit iteratorBase
                (
                    const HashTable<T, Key, Hash>* curHashTable
                );

                //- Construct from hash table, element and hash index
384
                inline iteratorBase
Henry's avatar
Henry committed
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
                (
                    const HashTable<T, Key, Hash>* curHashTable,
                    const hashedEntry* elmt,
                    const label hashIndex
                );


            // Protected Member Functions

                //- Increment to the next position
                inline void increment();

                //- Erase the HashTable element at the current position
                bool erase();

                //- Return non-const access to referenced object
                inline T& object();

                //- Return const access to referenced object
                inline const T& cobject() const;


        public:

            // Member operators

                // Access

                //- Return the Key corresponding to the iterator
                inline const Key& key() const;

                //- Compare hashedEntry element pointers
                inline bool operator==(const iteratorBase&) const;
                inline bool operator!=(const iteratorBase&) const;

                //- Compare hashedEntry to iteratorEnd pointers
                inline bool operator==(const iteratorEnd& unused) const;
                inline bool operator!=(const iteratorEnd& unused) const;
        };


        //- An STL-conforming iterator
        class iterator
        :
            public iteratorBase
        {
            friend class HashTable;

            // Private Member Functions

                //- Construct from hash table, moving to its 'begin' position
                inline explicit iterator
                (
                    HashTable<T, Key, Hash>* curHashTable
                );

                //- Construct from hash table, element and hash index
442
                inline iterator
Henry's avatar
Henry committed
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
                (
                    HashTable<T, Key, Hash>* curHashTable,
                    hashedEntry* elmt,
                    const label hashIndex
                );


        public:

            // Constructors

                //- Construct null (end iterator)
                inline iterator();

                //- Construct end iterator
                inline iterator(const iteratorEnd& unused);


            // Member operators

                //- Return referenced hash value
                inline T& operator*();
                inline T& operator()();

                //- Return referenced hash value
                inline const T& operator*() const;
                inline const T& operator()() const;

                inline iterator& operator++();
                inline iterator operator++(int);
        };

475
        //- Iterator set to the beginning of the HashTable
Henry's avatar
Henry committed
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
        inline iterator begin();


    // STL const_iterator

        //- An STL-conforming const_iterator
        class const_iterator
        :
            public iteratorBase
        {
            friend class HashTable;

            // Private Member Functions

                //- Construct from hash table, moving to its 'begin' position
                inline explicit const_iterator
                (
                    const HashTable<T, Key, Hash>* curHashTable
                );

                //- Construct from hash table, element and hash index
497
                inline const_iterator
Henry's avatar
Henry committed
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
                (
                    const HashTable<T, Key, Hash>* curHashTable,
                    const hashedEntry* elmt,
                    const label hashIndex
                );


        public:

            // Constructors

                //- Construct null (end iterator)
                inline const_iterator();

                //- Construct from iterator
                inline const_iterator(const iterator&);

                //- Construct end iterator
                inline const_iterator(const iteratorEnd& unused);


            // Member operators

                //- Return referenced hash value
                inline const T& operator*() const;
                inline const T& operator()() const;

                inline const_iterator& operator++();
                inline const_iterator operator++(int);

        };


        //- const_iterator set to the beginning of the HashTable
        inline const_iterator cbegin() const;

        //- const_iterator set to the beginning of the HashTable
        inline const_iterator begin() const;


    // IOstream Operator

        friend Istream& operator>> <T, Key, Hash>
        (
            Istream&,
            HashTable<T, Key, Hash>&
        );

        friend Ostream& operator<< <T, Key, Hash>
        (
            Ostream&,
            const HashTable<T, Key, Hash>&
        );
};


// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

} // End namespace Foam

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

560
    #include "HashTableI.H"
Henry's avatar
Henry committed
561
562
563
564
565

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

#ifndef NoHashTableC
#ifdef NoRepository
566
    #include "HashTable.C"
Henry's avatar
Henry committed
567
568
569
570
571
572
573
574
#endif
#endif

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

#endif

// ************************************************************************* //