Home
Downloads
Documentation
Installation
User Guide
man-pages
API Documentation
README
Release Notes
Changes
License
Support
SourceForge Project
Main Page
Related Pages
Namespaces
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Pages
src
OpenFOAM
containers
HashTables
HashTable
HashTable.H
Go to the documentation of this file.
1
/*---------------------------------------------------------------------------*\
2
========= |
3
\\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4
\\ / O peration |
5
\\ / A nd | Copyright (C) 1991-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::HashTable
26
27
Description
28
An STL-conforming hash table.
29
30
Note
31
Hashing index collisions are handled via chaining using a singly-linked
32
list with the colliding entry being added to the head of the linked
33
list. Thus copying the hash table (or indeed even resizing it) will
34
often result in a different hash order. Use a sorted table-of-contents
35
when the hash order is important.
36
37
SourceFiles
38
HashTableI.H
39
HashTable.C
40
HashTableIO.C
41
42
\*---------------------------------------------------------------------------*/
43
44
#ifndef HashTable_H
45
#define HashTable_H
46
47
#include <
OpenFOAM/label.H
>
48
#include <
OpenFOAM/uLabel.H
>
49
#include <
OpenFOAM/word.H
>
50
#include <
OpenFOAM/Xfer.H
>
51
#include <
OpenFOAM/className.H
>
52
53
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
54
55
namespace
Foam
56
{
57
58
// Forward declaration of friend functions and operators
59
60
template
<
class
T>
class
List;
61
template
<
class
T>
class
UList;
62
template
<
class
T,
class
Key,
class
Hash>
class
HashTable;
63
template
<
class
T,
class
Key,
class
Hash>
class
HashPtrTable;
64
65
template
<
class
T,
class
Key,
class
Hash>
66
Istream&
operator>>
(Istream&, HashTable<T, Key, Hash>&);
67
68
template
<
class
T,
class
Key,
class
Hash>
69
Ostream& operator<<(Ostream&, const HashTable<T, Key, Hash>&);
70
71
72
/*---------------------------------------------------------------------------*\
73
Class HashTableName Declaration
74
\*---------------------------------------------------------------------------*/
75
76
TemplateName
(HashTable);
77
78
79
/*---------------------------------------------------------------------------*\
80
Class HashTable Declaration
81
\*---------------------------------------------------------------------------*/
82
83
template
<
class
T,
class
Key=word,
class
Hash=
string
::hash>
84
class
HashTable
85
:
86
public
HashTableName
87
{
88
// Private data type for table entries
89
90
struct
hashedEntry
91
{
92
//- The lookup key
93
Key key_;
94
95
//- Pointer to next hashedEntry in sub-list
96
hashedEntry* next_;
97
98
//- The data object
99
T
obj_;
100
101
//- Constructors
102
103
//- Construct given key, next pointer and object
104
inline
hashedEntry
105
(
106
const
Key&,
107
hashedEntry* next,
108
const
T
& newEntry
109
);
110
111
//- Dissallow construction as copy
112
hashedEntry(
const
hashedEntry&);
113
};
114
115
116
// Private data: size of table, the table and current number of elements
117
118
//- The current number of elements in table
119
label nElmts_;
120
121
//- Number of primary entries allocated in table (not necessarily used)
122
label tableSize_;
123
124
//- The table of primary entries
125
hashedEntry** table_;
126
127
128
// Private Member Functions
129
130
//- Return a canonical (power-of-two) size
131
static
label canonicalSize(
const
label);
132
133
//- Return the hash index of the Key within the current table size.
134
// No checks for zero-sized tables.
135
inline
label hashKeyIndex(
const
Key&)
const
;
136
137
//- Assign a new hashedEntry to a possibly already existing key
138
bool
set
(
const
Key&,
const
T
& newElmt,
bool
protect);
139
140
141
public
:
142
143
//- Declare friendship with the HashPtrTable class
144
template
<
class
T2,
class
Key2,
class
Hash2>
145
friend
class
HashPtrTable
;
146
147
148
// Forward declaration of STL iterators
149
150
class
iterator
;
151
friend
class
iterator
;
152
153
class
const_iterator
;
154
friend
class
const_iterator
;
155
156
157
// Constructors
158
159
//- Construct given initial table size
160
HashTable
(
const
label
size
= 128);
161
162
//- Construct from Istream
163
HashTable
(
Istream
&,
const
label
size
= 128);
164
165
//- Construct as copy
166
HashTable
(
const
HashTable<T, Key, Hash>
&);
167
168
//- Construct by transferring the parameter contents
169
HashTable
(
const
Xfer
<
HashTable<T, Key, Hash>
>&);
170
171
172
// Destructor
173
174
~HashTable
();
175
176
177
// Member Functions
178
179
// Access
180
181
//- Return number of elements in table.
182
inline
label
size
()
const
;
183
184
//- Return true if the hash table is empty
185
inline
bool
empty
()
const
;
186
187
//- Return true if hashedEntry is found in table
188
bool
found
(
const
Key&)
const
;
189
190
//- Find and return an iterator set at the hashedEntry
191
// If not found iterator = end()
192
iterator
find
(
const
Key&);
193
194
//- Find and return an const_iterator set at the hashedEntry
195
// If not found iterator = end()
196
const_iterator
find
(
const
Key&)
const
;
197
198
//- Return the table of contents
199
List<Key>
toc
()
const
;
200
201
//- Return the table of contents as a sorted list
202
List<Key>
sortedToc
()
const
;
203
204
//- Print information
205
Ostream
&
printInfo
(
Ostream
&)
const
;
206
207
// Edit
208
209
//- Insert a new hashedEntry
210
inline
bool
insert
(
const
Key&,
const
T
& newElmt);
211
212
//- Assign a new hashedEntry, overwriting existing entries
213
inline
bool
set
(
const
Key&,
const
T
& newElmt);
214
215
//- Erase an hashedEntry specified by given iterator
216
bool
erase
(
const
iterator
&);
217
218
//- Erase an hashedEntry specified by given key if in table
219
bool
erase
(
const
Key&);
220
221
//- Remove entries given by the listed keys from this HashTable
222
// Return the number of elements removed
223
label
erase
(
const
UList<Key>
&);
224
225
//- Remove entries given by the given keys from this HashTable
226
// Return the number of elements removed.
227
// The parameter HashTable needs the same type of key, but the
228
// type of values held and the hashing function are arbitrary.
229
template
<
class
AnyType,
class
AnyHash>
230
label
erase
(
const
HashTable<AnyType, Key, AnyHash>
&);
231
232
//- Resize the hash table for efficiency
233
void
resize
(
const
label newSize);
234
235
//- Clear all entries from table
236
void
clear
();
237
238
//- Clear the table entries and the table itself.
239
// Equivalent to clear() followed by resize(0)
240
void
clearStorage
();
241
242
//- Transfer the contents of the argument table into this table
243
// and annull the argument table.
244
void
transfer
(
HashTable<T, Key, Hash>
&);
245
246
//- Transfer contents to the Xfer container
247
inline
Xfer<HashTable<T, Key, Hash>
>
xfer
();
248
249
250
// Member Operators
251
252
//- Find and return an hashedEntry
253
inline
T
&
operator[]
(
const
Key&);
254
255
//- Find and return an hashedEntry
256
inline
const
T
&
operator[]
(
const
Key&)
const
;
257
258
//- Find and return an hashedEntry, create it null if not present.
259
inline
T
&
operator()
(
const
Key&);
260
261
//- Assignment
262
void
operator=
(
const
HashTable<T, Key, Hash>
&);
263
264
//- Equality. Two hash tables are equal if all contents of first are
265
// also in second and vice versa. So does not depend on table size or
266
// order!
267
bool
operator==
(
const
HashTable<T, Key, Hash>
&)
const
;
268
269
//- The opposite of the equality operation. Takes linear time.
270
bool
operator!=
(
const
HashTable<T, Key, Hash>
&)
const
;
271
272
273
// STL type definitions
274
275
//- Type of values the HashTable contains.
276
typedef
T
value_type
;
277
278
//- Type that can be used for storing into HashTable::value_type
279
// objects. This type is usually List::value_type&.
280
typedef
T
&
reference
;
281
282
//- Type that can be used for storing into constant
283
// HashTable::value_type objects. This type is usually const
284
// HashTable::value_type&.
285
typedef
const
T
&
const_reference
;
286
287
//- The type that can represent the size of a HashTable.
288
typedef
label
size_type
;
289
290
291
// STL iterator
292
293
//- An STL-conforming iterator
294
class
iterator
295
{
296
friend
class
HashTable
;
297
friend
class
const_iterator
;
298
299
// Private data
300
301
//- Reference to the HashTable this is an iterator for
302
HashTable<T, Key, Hash>
& hashTable_;
303
304
//- Current element
305
hashedEntry* elmtPtr_;
306
307
//- Current hash index
308
label hashIndex_;
309
310
public
:
311
312
// Constructors
313
314
//- Construct from hash table, element and hash index
315
inline
iterator
316
(
317
HashTable<T, Key, Hash>
& curHashTable,
318
hashedEntry* elmt,
319
label hashIndex
320
);
321
322
// Member operators
323
324
inline
void
operator=
(
const
iterator
&);
325
326
inline
bool
operator==
(
const
iterator
&)
const
;
327
inline
bool
operator!=
(
const
iterator
&)
const
;
328
329
inline
bool
operator==
(
const
const_iterator
&)
const
;
330
inline
bool
operator!=
(
const
const_iterator
&)
const
;
331
332
inline
T
&
operator*
();
333
inline
T
&
operator()
();
334
335
inline
const
T
&
operator*
()
const
;
336
inline
const
T
&
operator()
()
const
;
337
338
inline
iterator
&
operator++
();
339
inline
iterator
operator++
(
int
);
340
341
inline
const
Key&
key
()
const
;
342
};
343
344
345
//- iterator set to the begining of the HashTable
346
inline
iterator
begin
();
347
348
//- iterator set to beyond the end of the HashTable
349
inline
const
iterator
&
end
();
350
351
352
// STL const_iterator
353
354
//- An STL-conforming const_iterator
355
class
const_iterator
356
{
357
friend
class
iterator
;
358
359
// Private data
360
361
//- Reference to the HashTable this is an iterator for
362
const
HashTable<T, Key, Hash>
& hashTable_;
363
364
//- Current element
365
const
hashedEntry* elmtPtr_;
366
367
//- Current hash index
368
label hashIndex_;
369
370
371
public
:
372
373
// Constructors
374
375
//- Construct from hash table, element and hash index
376
inline
const_iterator
377
(
378
const
HashTable<T, Key, Hash>
& curHashTable,
379
const
hashedEntry* elmt,
380
label hashIndex
381
);
382
383
//- Construct from the non-const iterator
384
inline
const_iterator
(
const
iterator
&);
385
386
387
// Member operators
388
389
inline
void
operator=
(
const
const_iterator
&);
390
391
inline
bool
operator==
(
const
const_iterator
&)
const
;
392
inline
bool
operator!=
(
const
const_iterator
&)
const
;
393
394
inline
bool
operator==
(
const
iterator
&)
const
;
395
inline
bool
operator!=
(
const
iterator
&)
const
;
396
397
inline
const
T
&
operator*
()
const
;
398
inline
const
T
&
operator()
()
const
;
399
400
inline
const_iterator
&
operator++
();
401
inline
const_iterator
operator++
(
int
);
402
403
inline
const
Key&
key
()
const
;
404
};
405
406
407
//- const_iterator set to the beginning of the HashTable
408
inline
const_iterator
cbegin
()
const
;
409
410
//- const_iterator set to beyond the end of the HashTable
411
inline
const
const_iterator
&
cend
()
const
;
412
413
//- const_iterator set to the beginning of the HashTable
414
inline
const_iterator
begin
()
const
;
415
416
//- const_iterator set to beyond the end of the HashTable
417
inline
const
const_iterator
&
end
()
const
;
418
419
420
// IOstream Operator
421
422
friend
Istream
&
operator
>> <
T
, Key,
Hash
>
423
(
424
Istream
&,
425
HashTable<T, Key, Hash>
&
426
);
427
428
friend
Ostream
& operator<< <T, Key, Hash>
429
(
430
Ostream
&,
431
const
HashTable<T, Key, Hash>
&
432
);
433
434
435
private
:
436
437
//- iterator returned by end()
438
iterator
endIter_;
439
440
//- const_iterator returned by end()
441
const_iterator
endConstIter_;
442
};
443
444
445
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
446
447
}
// End namespace Foam
448
449
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
450
451
# include <
OpenFOAM/HashTableI.H
>
452
453
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
454
455
#ifndef NoHashTableC
456
#ifdef NoRepository
457
# include <
OpenFOAM/HashTable.C
>
458
#endif
459
#endif
460
461
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
462
463
#endif
464
465
// ************************ vim: set sw=4 sts=4 et: ************************ //