diff options
Diffstat (limited to 'src/bool-array.h')
| -rw-r--r-- | src/bool-array.h | 83 |
1 files changed, 48 insertions, 35 deletions
diff --git a/src/bool-array.h b/src/bool-array.h index 8330fcd220190..ddfbd869b5015 100644 --- a/src/bool-array.h +++ b/src/bool-array.h @@ -2,54 +2,67 @@ /* Simple lookup table abstraction implemented as an Iteration Number Array. - Copyright (C) 1989-1998 Free Software Foundation, Inc. - written by Douglas C. Schmidt (schmidt@ics.uci.edu) + Copyright (C) 1989-1998, 2002 Free Software Foundation, Inc. + Written by Douglas C. Schmidt <schmidt@ics.uci.edu> + and Bruno Haible <bruno@clisp.org>. -This file is part of GNU GPERF. + This file is part of GNU GPERF. -GNU GPERF 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 1, or (at your option) -any later version. + GNU GPERF 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, or (at your option) + any later version. -GNU GPERF 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. + GNU GPERF 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 GNU GPERF; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ - -/* Define and implement a simple boolean array abstraction, - uses an Iteration Numbering implementation to save on initialization time. */ + You should have received a copy of the GNU General Public License + along with this program; see the file COPYING. + If not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef bool_array_h #define bool_array_h 1 -#include "trace.h" - -#ifdef LO_CAL -/* If we are on a memory diet then we'll only make these use a limited - amount of storage space. */ -typedef unsigned short STORAGE_TYPE; -#else -typedef unsigned int STORAGE_TYPE; -#endif +/* A Bool_Array instance is a bit array of fixed size, optimized for being + filled sparsely and cleared frequently. For example, when processing + tests/chill.gperf, the array will be: + - of size 15391, + - clear will be called 3509 times, + - set_bit will be called 300394 times. + With a conventional bit array implementation, clear would be too slow. + With a tree/hash based bit array implementation, set_bit would be slower. */ class Bool_Array { +public: + /* Initializes the bit array with room for SIZE bits, numbered from + 0 to SIZE-1. */ + Bool_Array (unsigned int size); + + /* Frees this object. */ + ~Bool_Array (); + + /* Resets all bits to zero. */ + void clear (); + + /* Sets the specified bit to true. + Returns its previous value (false or true). */ + bool set_bit (unsigned int index); + private: - static STORAGE_TYPE *storage_array; /* Initialization of the index space. */ - static STORAGE_TYPE iteration_number; /* Keep track of the current iteration. */ - static unsigned int size; /* Keep track of array size. */ + /* Size of array. */ + unsigned int const _size; -public: - Bool_Array (void); - ~Bool_Array (void); - static void init (STORAGE_TYPE *buffer, unsigned int s); - static int find (int hash_value); - static void reset (void); + /* Current iteration number. Always nonzero. Starts out as 1, and is + incremented each time clear() is called. */ + unsigned int _iteration_number; + + /* For each index, we store in storage_array[index] the iteration_number at + the time set_bit(index) was last called. */ + unsigned int * const _storage_array; }; #ifdef __OPTIMIZE__ /* efficiency hack! */ |