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
36class Bool_Array
37{
38public:
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
53private:
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