1 | /* This may look like C code, but it is really -*- C++ -*- */ |
2 | |
3 | /* Simple lookup table abstraction implemented as an Iteration Number Array. |
4 | |
5 | Copyright (C) 1989-1998, 2002 Free Software Foundation, Inc. |
6 | Written by Douglas C. Schmidt <schmidt@ics.uci.edu> |
7 | and Bruno Haible <bruno@clisp.org>. |
8 | |
9 | This file is part of GNU GPERF. |
10 | |
11 | This program is free software: you can redistribute it and/or modify |
12 | it 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 | This program is distributed in the hope that it will be useful, |
17 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
19 | GNU General Public License for more details. |
20 | |
21 | You should have received a copy of the GNU General Public License |
22 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
23 | |
24 | #ifndef bool_array_h |
25 | #define bool_array_h 1 |
26 | |
27 | /* A Bool_Array instance is a bit array of fixed size, optimized for being |
28 | filled sparsely and cleared frequently. For example, when processing |
29 | tests/chill.gperf, the array will be: |
30 | - of size 15391, |
31 | - clear will be called 3509 times, |
32 | - set_bit will be called 300394 times. |
33 | With a conventional bit array implementation, clear would be too slow. |
34 | With a tree/hash based bit array implementation, set_bit would be slower. */ |
35 | |
36 | class Bool_Array |
37 | { |
38 | public: |
39 | /* Initializes the bit array with room for SIZE bits, numbered from |
40 | 0 to SIZE-1. */ |
41 | Bool_Array (unsigned int size); |
42 | |
43 | /* Frees this object. */ |
44 | ~Bool_Array (); |
45 | |
46 | /* Resets all bits to zero. */ |
47 | void clear (); |
48 | |
49 | /* Sets the specified bit to true. |
50 | Returns its previous value (false or true). */ |
51 | bool set_bit (unsigned int index); |
52 | |
53 | private: |
54 | /* Size of array. */ |
55 | unsigned int const _size; |
56 | |
57 | /* Current iteration number. Always nonzero. Starts out as 1, and is |
58 | incremented each time clear() is called. */ |
59 | unsigned int _iteration_number; |
60 | |
61 | /* For each index, we store in storage_array[index] the iteration_number at |
62 | the time set_bit(index) was last called. */ |
63 | unsigned int * const _storage_array; |
64 | }; |
65 | |
66 | #ifdef __OPTIMIZE__ /* efficiency hack! */ |
67 | |
68 | #include <stdio.h> |
69 | #include <string.h> |
70 | #include "options.h" |
71 | #define INLINE inline |
72 | #include "bool-array.icc" |
73 | #undef INLINE |
74 | |
75 | #endif |
76 | |
77 | #endif |
78 | |