HashTbl.H 13.5 KB
Newer Older
1
2
3
4
5
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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
178
179
180
/*---------------------------------------------------------------------------*\
  =========                 |
  \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   \\    /   O peration     |
    \\  /    A nd           | Copyright (C) 1991-2009 OpenCFD Ltd.
     \\/     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 2 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, write to the Free Software Foundation,
    Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA

Class
    Foam::HashTbl

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
    HashTblI.H
    HashTbl.C
    HashTblIO.C

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

#ifndef HashTbl_H
#define HashTbl_H

#include "label.H"
#include "uLabel.H"
#include "word.H"
#include "Xfer.H"
#include "className.H"

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

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 HashTbl;
template<class T, class Key, class Hash> class HashPtrTable;

template<class T, class Key, class Hash>
Istream& operator>>(Istream&, HashTbl<T, Key, Hash>&);

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


/*---------------------------------------------------------------------------*\
                        Class HashTblName Declaration
\*---------------------------------------------------------------------------*/

TemplateName(HashTbl);


/*---------------------------------------------------------------------------*\
                          Class HashTbl Declaration
\*---------------------------------------------------------------------------*/

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

        struct hashedEntry
        {
            //- The lookup key
            Key key_;

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

            //- The data object
            T obj_;

            //- Constructors

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

                //- Dissallow construction as copy
                hashedEntry(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 (not necessarily used)
        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);

public:

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


    // Forward declaration of STL iterators

        class iterator;
        friend class iterator;

        class const_iterator;
        friend class const_iterator;


    // Constructors

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

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

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

        //- Construct by transferring the parameter contents
        HashTbl(const Xfer<HashTbl<T, Key, Hash> >&);


    // Destructor

        ~HashTbl();


    // Member Functions

        // Access

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

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
213
214
215
216
217
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
            //- 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 an hashedEntry specified by given iterator
            bool erase(const iterator&);

            //- Erase an hashedEntry specified by given key if in table
            bool erase(const Key&);

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

            //- Remove entries given by the given keys from this HashTbl
            //  Return the number of elements removed.
            //  The parameter HashTbl needs the same type of keys, but
            //  but the type of values held is arbitrary.
            template<class AnyType>
            label erase(const HashTbl<AnyType, Key, Hash>&);

            //- 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();

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

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
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
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
384
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
442
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
            //- Transfer the contents of the argument table into this table
            //  and annull the argument table.
            void transfer(HashTbl<T, Key, Hash>&);

            //- Transfer contents to the Xfer container
            inline Xfer<HashTbl<T, Key, Hash> > xfer();


    // Member Operators

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

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

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

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

        //- Equality. Two hash tables are equal if all contents of first are
        //  also in second and vice versa. So does not depend on table size or
        //  order!
        bool operator==(const HashTbl<T, Key, Hash>&) const;

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



    // STL type definitions

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

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

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

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


    // STL iterator

        //- An STL-conforming iterator
        class iterator
        {
            friend class HashTbl;
            friend class const_iterator;

            // Private data

                //- Reference to the HashTbl this is an iterator for
                HashTbl<T, Key, Hash>& hashTable_;

                //- Current element
                hashedEntry* elmtPtr_;

                //- Current hash index
                label hashIndex_;

        public:

            // Constructors

                //- Construct from hash table, element and hash index
                inline iterator
                (
                    HashTbl<T, Key, Hash>& curHashTbl,
                    hashedEntry* elmt,
                    label hashIndex
                );

            // Member operators

                inline void operator=(const iterator&);

                inline bool operator==(const iterator&) const;
                inline bool operator!=(const iterator&) const;

                inline bool operator==(const const_iterator&) const;
                inline bool operator!=(const const_iterator&) const;

                inline T& operator*();
                inline T& operator()();

                inline const T& operator*() const;
                inline const T& operator()() const;

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

                inline const Key& key() const;
        };


        //- iterator set to the begining of the HashTbl
        inline iterator begin();

        //- iterator set to beyond the end of the HashTbl
        inline const iterator& end();


    // STL const_iterator

        //- An STL-conforming const_iterator
        class const_iterator
        {
            friend class iterator;

            // Private data

                //- Reference to the HashTbl this is an iterator for
                const HashTbl<T, Key, Hash>& hashTable_;

                //- Current element
                const hashedEntry* elmtPtr_;

                //- Current hash index
                label hashIndex_;


        public:

            // Constructors

                //- Construct from hash table, element and hash index
                inline const_iterator
                (
                    const HashTbl<T, Key, Hash>& curHashTbl,
                    const hashedEntry* elmt,
                    label hashIndex
                );

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


            // Member operators

                inline void operator=(const const_iterator&);

                inline bool operator==(const const_iterator&) const;
                inline bool operator!=(const const_iterator&) const;

                inline bool operator==(const iterator&) const;
                inline bool operator!=(const iterator&) const;

                inline const T& operator*() const;
                inline const T& operator()() const;

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

                inline const Key& key() const;
        };


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

        //- const_iterator set to beyond the end of the HashTbl
        inline const const_iterator& cend() const;

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

        //- const_iterator set to beyond the end of the HashTbl
        inline const const_iterator& end() const;


    // IOstream Operator

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

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


private:

        //- iterator returned by end()
        iterator endIter_;

        //- const_iterator returned by end()
        const_iterator endConstIter_;
};


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

} // End namespace Foam

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

#   include "HashTblI.H"

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

#ifndef NoHashTblC
#ifdef NoRepository
#   include "HashTbl.C"
#endif
#endif

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

#endif

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