1140609Sdas/* This may look like C code, but it is really -*- C++ -*- */
2140609Sdas
3140609Sdas/* Simple lookup table abstraction implemented as an Iteration Number Array.
4140609Sdas
5140609Sdas   Copyright (C) 1989-1998, 2002 Free Software Foundation, Inc.
6140609Sdas   Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
7140609Sdas   and Bruno Haible <bruno@clisp.org>.
8140609Sdas
9140609Sdas   This file is part of GNU GPERF.
10140609Sdas
11140609Sdas   GNU GPERF is free software; you can redistribute it and/or modify
12140609Sdas   it under the terms of the GNU General Public License as published by
13140609Sdas   the Free Software Foundation; either version 2, or (at your option)
14140609Sdas   any later version.
15140609Sdas
16140609Sdas   GNU GPERF is distributed in the hope that it will be useful,
17140609Sdas   but WITHOUT ANY WARRANTY; without even the implied warranty of
18140609Sdas   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19140609Sdas   GNU General Public License for more details.
20140609Sdas
21140609Sdas   You should have received a copy of the GNU General Public License
22140609Sdas   along with this program; see the file COPYING.
23140609Sdas   If not, write to the Free Software Foundation, Inc.,
24140609Sdas   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
25140609Sdas
26140609Sdas#ifndef bool_array_h
27140609Sdas#define bool_array_h 1
28140609Sdas
29140609Sdas/* A Bool_Array instance is a bit array of fixed size, optimized for being
30140609Sdas   filled sparsely and cleared frequently.  For example, when processing
31140609Sdas   tests/chill.gperf, the array will be:
32140609Sdas     - of size 15391,
33140609Sdas     - clear will be called 3509 times,
34140609Sdas     - set_bit will be called 300394 times.
35192760Sattilio   With a conventional bit array implementation, clear would be too slow.
36   With a tree/hash based bit array implementation, set_bit would be slower. */
37
38class Bool_Array
39{
40public:
41  /* Initializes the bit array with room for SIZE bits, numbered from
42     0 to SIZE-1. */
43                        Bool_Array (unsigned int size);
44
45  /* Frees this object.  */
46                        ~Bool_Array ();
47
48  /* Resets all bits to zero.  */
49  void                  clear ();
50
51  /* Sets the specified bit to true.
52     Returns its previous value (false or true).  */
53  bool                  set_bit (unsigned int index);
54
55private:
56  /* Size of array.  */
57  unsigned int const    _size;
58
59  /* Current iteration number.  Always nonzero.  Starts out as 1, and is
60     incremented each time clear() is called.  */
61  unsigned int          _iteration_number;
62
63  /* For each index, we store in storage_array[index] the iteration_number at
64     the time set_bit(index) was last called.  */
65  unsigned int * const  _storage_array;
66};
67
68#ifdef __OPTIMIZE__  /* efficiency hack! */
69
70#include <stdio.h>
71#include <string.h>
72#include "options.h"
73#define INLINE inline
74#include "bool-array.icc"
75#undef INLINE
76
77#endif
78
79#endif
80